RE: About finding the start symbol of a grammar

Christopher F Clark <christopher.f.clark@compiler-resources.com>
Sat, 22 May 2021 12:14:08 +0300

          From comp.compilers

Related articles
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: Christopher F Clark <christopher.f.clark@compiler-resources.com>
Newsgroups: comp.compilers
Date: Sat, 22 May 2021 12:14:08 +0300
Organization: Compilers Central
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="33574"; mail-complaints-to="abuse@iecc.com"
Keywords: parse
Posted-Date: 22 May 2021 13:24:22 EDT

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.


However, there is one particular curious aspect if you are writing a
translator to a recursive descent parser, one generally makes a
function of each rule, as a result one can consider each symbol a
start symbol for whatever sub-graph is reachable from it. With a
table driven parser, one has to make a table of entries into the
parsing table to achieve the same effect, but that is not difficult to
do, although that may require additional table rows if the symbol
behaves slightly differently when used as a start symbol rather than
in the context of other rules (e.g. follow symbols).


So, in that sense, a start symbol is simply what one wants to parse.


--
******************************************************************************
Chris Clark email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. Web Site: http://world.std.com/~compres
23 Bailey Rd voice: (508) 435-5016
Berlin, MA 01503 USA twitter: @intel_chris
------------------------------------------------------------------------------


Post a followup to this message

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