|About finding the start symbol of a grammar email@example.com (Eduardo Costa) (2021-05-21)|
|Re: About finding the start symbol of a grammar firstname.lastname@example.org (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 email@example.com (2021-05-21)|
|Re: About finding the start symbol of a grammar firstname.lastname@example.org (Ev. Drikos) (2021-05-22)|
|Re: About finding the start symbol of a grammar email@example.com (gah4) (2021-05-22)|
|From:||firstname.lastname@example.org (Anton Ertl)|
|Date:||Fri, 21 May 2021 15:32:22 GMT|
|Organization:||Institut fuer Computersprachen, Technische Universitaet Wien|
|Injection-Info:||gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="33119"; mail-complaints-to="email@example.com"|
|Posted-Date:||22 May 2021 13:23:38 EDT|
Kaz Kylheku <firstname.lastname@example.org> writes:
>Surely, the start symbol of a context-free grammar is one which appears
>only in the left hand side of a rule. If there is such a unique symbol,
>it must be /the/ start symbol.
It could be a now-unused nonterminal, while the start symbol is part
of a strongly connected component of the graph.
If you have one nonterminal that dominates all other nonterminals (the
other nonterminals can be derived from it, but not the other way
round), it probably is the start symbol. Why "probably"? There is
still the possibility that there is a wrapper rule around the real
start symbol that was used for debugging and is left in the grammar.
>On the face of it, this problem does not smell of undecidability, or
>even NP completeness. Where do you suspect is the difficulty?
It's easy to find nodes with particular properties in a graph. But
there is no guarantee that the result really is the start symbol.
There is a reason why you specify the start symbol in some way.
>Whether rules are dangling is also a graph property: is the graph
"Connected" is an undirected-graph property. If a nonterminal is
unreachable from the start symbol, it can still be connected to the
reachable graph through a RHS-nonterminal.
M. Anton Ertl
Return to the
Search the comp.compilers archives again.