Re: About finding the start symbol of a grammar

Kaz Kylheku <563-365-8930@kylheku.com> 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.


"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.


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

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