Path: csiph.com!goblin3!goblin.stu.neva.ru!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.compilers
Subject: Re: About finding the start symbol of a grammar
Date: Fri, 21 May 2021 15:32:22 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 34
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <21-05-018@comp.compilers>
References: <21-05-015@comp.compilers> <21-05-016@comp.compilers>
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="33119"; mail-complaints-to="abuse@iecc.com"
Keywords: parse
Posted-Date: 22 May 2021 13:23:38 EDT
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
Xref: csiph.com comp.compilers:2669

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/