Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #2671 > unrolled thread

RE: About finding the start symbol of a grammar

Back to article view | Back to comp.compilers

Contents

  RE: About finding the start symbol of a grammar Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2021-05-22 12:14 +0300
    Re: About finding the start symbol of a grammar gah4 <gah4@u.washington.edu> - 2021-05-22 13:17 -0700

#2671 — RE: About finding the start symbol of a grammar

As Dodi noted, this is basically a graph analysis problem and the
graph may be disconnected (a forest).  And our moderator has added
several insightful comments.  E.g. you can "declare" a start symbol
and if not present default to some symbol, either the first one in the
grammar, or some symbol from which all other symbols are reachable
(presuming the graph isn't disconnected), and the start symbol can be
recursively defined, etc.

However, there is one particular curious aspect if you are writing a
translator to a recursive descent parser, one generally makes a
function of each rule, as a result one can consider each symbol a
start symbol for whatever sub-graph is reachable from it.   With a
table driven parser, one has to make a table of entries into the
parsing table to achieve the same effect, but that is not difficult to
do, although that may require additional table rows if the symbol
behaves slightly differently when used as a start symbol rather than
in the context of other rules (e.g. follow symbols).

So, in that sense, a start symbol is simply what one wants to parse.

--
******************************************************************************
Chris Clark                  email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc.  Web Site: http://world.std.com/~compres
23 Bailey Rd                 voice: (508) 435-5016
Berlin, MA  01503 USA      twitter: @intel_chris
------------------------------------------------------------------------------

[toc] | [next] | [standalone]

#2672

On Saturday, May 22, 2021 at 10:24:24 AM UTC-7, Christopher F Clark wrote:
> As Dodi noted, this is basically a graph analysis problem and the
> graph may be disconnected (a forest). And our moderator has added
> several insightful comments. E.g. you can "declare" a start symbol
> and if not present default to some symbol, either the first one in the
> grammar, or some symbol from which all other symbols are reachable
> (presuming the graph isn't disconnected), and the start symbol can be
> recursively defined, etc.

Seems to me that this should be related to the problem of finding the
root of a phylogenetic tree.

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7149615/

Unlike CS trees, there is no necessary directionality to the links, and so
finding the root is more difficult.  Yet biologists have some desire to
know where the root is.

But as also noted above, in the case of recursion, it depends on the language.

In most languages, <expression> is recursive, allowing for

  '(' <expression> ')'

however, a language (though I don't know of any) could require all expressions
to be parenthesized, in which case the start would be the parenthesized form.

[I think previous messagees have made it clear that while this is an
interesting exercise, its only practical use is to see if the start
symbol declared in the grammar is different from the computed one, in
which case the grammar is broken. -John]

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web