Fri, 21 May 2021 17:02:34 +0200

Related articles |
---|

About finding the start symbol of a grammar ecosta.tmp@gmail.com (Eduardo Costa) (2021-05-21) |

Re: About finding the start symbol of a grammar 563-365-8930@kylheku.com (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 anton@mips.complang.tuwien.ac.at (2021-05-21) |

Re: About finding the start symbol of a grammar drikosev@gmail.com (Ev. Drikos) (2021-05-22) |

Re: About finding the start symbol of a grammar gah4@u.washington.edu (gah4) (2021-05-22) |

From: | Hans-Peter Diettrich <DrDiettrich1@netscape.net> |

Newsgroups: | comp.compilers |

Date: | Fri, 21 May 2021 17:02:34 +0200 |

Organization: | Compilers Central |

References: | 21-05-015 |

Injection-Info: | gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="88903"; mail-complaints-to="abuse@iecc.com" |

Keywords: | parse |

Posted-Date: | 21 May 2021 11:17:47 EDT |

In-Reply-To: | 21-05-015 |

Content-Language: | de-DE |

On 5/21/21 12:49 PM, Eduardo Costa wrote:

*> I've been lately dealing with a parser generator for LL grammars, and since*

*> it's inception I've always been blindy assuming the first element read from*

*> within the input file is going to be the start symbol or starting rule.*

*>*

*> So I've been wondering all this time, just out of curiosity, if there exists a*

*> method or algorithm to find out the start symbol of a given grammar?*

Graph analysis methods exist to find unreachable nodes which can become

start symbols. In short any node that is a predecessor of *all* nodes

can be a start symbol. If no such node exists then the grammar is faulty

(discontiguous).

*> While there would exist grammars we could recursively check to find out which*

*> it's start symbol is (i.e.: it's the only rule that used the rest of them,*

*> where checking every other resulted in dangling rules that weren't even called*

*> in), there might be other grammars for which more than one rule yields full*

*> coverage (all of these obviously defining different languages) and so leading*

*> to ambiguity.*

IMO this problem can be solved by introduction of an artificial start

symbol that allows to reach all other symbols but can not be reached

itself. Please note that this solution solves a syntactic problem but

may not prevent or even cause semantic problems.

*> I only contemplate a simple coverage test, even though other techniques could*

*> exist, again, all of them leading to a point where we couldn't ascertain if*

*> one or the other is what the user meant.*

*>*

*> So I'm wondering if this is even an issue in production-grade*

*> parser-generators out there?*

A useful parser generator should include checks for grammar sanity.

DoDi

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.