Timeline for CFGs: detecting infinitely many derivations of a single string
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 2, 2015 at 16:35 | comment | added | Bakkot | The method by which I am transforming the standard recognizer into a parser - namely, backpointers, following this, such that backpointers are considered to be a part of the state for purposes of distinguishing states in the chart sets - seems to generate all parses pretty naturally, provided you can short-circuit infinite loops. I'll try to come up with a more natural representation which doesn't involve enumerate at some point, though - do you happen to know of one offhand? | |
| Apr 2, 2015 at 16:01 | comment | added | babou | Even with your goal. Earley's algorithm will not naturally enumerate parses. It is best to first build the graph, and then to use it to enumerate the parses. Earley's graph is a bit messy, too much for students imho. But there are simpler forms that actually show the structure of ambiguity (provided there is not too much ambiguity turning it into a spaghetti dish). | |
| Apr 2, 2015 at 15:40 | comment | added | Bakkot | I am in fact trying to enumerate all parses, when that's possible. The tool is intended for students who are just being introduced to CFGs, and I think it's more useful to see "here are all of the ways the grammar you have given can derive the string you have given" than "here is a graph representing all parses". | |
| Apr 2, 2015 at 15:34 | comment | added | babou | Yes, there is a better way, unless you are actually trying to enumerate all the parses, which is the very thing you should avoid doing. Earley build a linked structure representing all the parses, and all you need is to add a loop (appropriately) in that linked structure which is otherwise a DAG. This structure is always finite, but can be used to enumerate parses, even when there are infinitely many parses. This may be useful when you intend further processing of all the parse-trees. Earley parsers are not the simplest, and use a somewhat complicated structure for parses. | |
| Apr 2, 2015 at 15:20 | comment | added | Bakkot | @babou : I might add that at some point, but I can't think of a better way of doing it than checking to see when a nonterminal may derive itself per below, cutting it off, and making a note that the parse may be extended indefinitely by adding iterations of the loop. Is there a better and/or more standard way of doing it? (For reference, I'm writing an Earley parser.) | |
| Apr 2, 2015 at 8:36 | comment | added | babou | The answer you accepted is good. However, this is not needed to produce a general CF parser. It is perfectly possible to parse any string, even when it has infinitely many parses, and to describe in a finite form the set of parses (even when infinite). You can then easily list parts of that infinite set if you choose to. | |
| Apr 2, 2015 at 6:00 | vote | accept | Bakkot | ||
| Apr 2, 2015 at 4:58 | answer | added | rici | timeline score: 2 | |
| Apr 2, 2015 at 3:55 | review | First posts | |||
| Apr 2, 2015 at 13:54 | |||||
| Apr 2, 2015 at 3:52 | history | asked | Bakkot | CC BY-SA 3.0 |