Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.compilers > #2669
| 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> (permalink) |
| 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 |
Show key headers only | 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
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