Re: About finding the start symbol of a grammar

From	anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups	comp.compilers
Subject	Re: About finding the start symbol of a grammar
Date	2021-05-21 15:32 +0000
Organization	Institut fuer Computersprachen, Technische Universitaet Wien
Message-ID	<21-05-018@comp.compilers> (permalink)
References	<21-05-015@comp.compilers> <21-05-016@comp.compilers>

Show all headers | View raw

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/

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

About finding the start symbol of a grammar Eduardo Costa <ecosta.tmp@gmail.com> - 2021-05-21 03:49 -0700
  Re: About finding the start symbol of a grammar Kaz Kylheku <563-365-8930@kylheku.com> - 2021-05-21 14:14 +0000
    Re: About finding the start symbol of a grammar anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2021-05-21 15:32 +0000
  Re: About finding the start symbol of a grammar Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2021-05-21 17:02 +0200
  Re: About finding the start symbol of a grammar "Ev. Drikos" <drikosev@gmail.com> - 2021-05-22 06:52 +0300

csiph-web