Re: About finding the start symbol of a grammar

gah4 <gah4@u.washington.edu>
Sat, 22 May 2021 13:17:25 -0700 (PDT)

          From comp.compilers

Related articles
About finding the start symbol of a grammar ecosta.tmp@gmail.com (Eduardo Costa) (2021-05-21)
Re: About finding the start symbol of a grammar 563-365-8930@kylheku.com (Kaz Kylheku) (2021-05-21)
Re: About finding the start symbol of a grammar DrDiettrich1@netscape.net (Hans-Peter Diettrich) (2021-05-21)
Re: About finding the start symbol of a grammar anton@mips.complang.tuwien.ac.at (2021-05-21)
Re: About finding the start symbol of a grammar drikosev@gmail.com (Ev. Drikos) (2021-05-22)
RE: About finding the start symbol of a grammar christopher.f.clark@compiler-resources.com (Christopher F Clark) (2021-05-22)
Re: About finding the start symbol of a grammar gah4@u.washington.edu (gah4) (2021-05-22)
| List of all articles for this month |

From: gah4 <gah4@u.washington.edu>
Newsgroups: comp.compilers
Date: Sat, 22 May 2021 13:17:25 -0700 (PDT)
Organization: Compilers Central
References: 21-05-020
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="83623"; mail-complaints-to="abuse@iecc.com"
Keywords: parse, comment
Posted-Date: 27 May 2021 10:40:19 EDT
In-Reply-To: 21-05-020

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]


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.