kach
commented
8 years ago Pearley is really cool! When you think it's "done", I would happily put a link to it in this repository's README file. Imagine being able to write a parser in nearley and get a Python parser for free?!
(PlyPlus seems like a pretty famous parsing module—you must share some of your "module advertising" tips with me sometime. :-) )
Okay, so the algorithm, which I've written about here, works by maintaining a table where every column represents a token of input. Each row of the table represents a partial parse (called an Earley state) and is basically the representation of a production rule's expansion, with a dot representing where you are in that production rule. This is the output of nearley-test, by the way. An example of an Earley state is
statement -> expression • ";" newline
At each iteration, nearley looks at each of these states in the current row of the table, and looks for states that are "expecting" the token you fed it. The state above expects a semicolon, so if you fed the algorithm a semicolon, it would create a fresh state in the next column of the table, that looks like
statement -> expression ";" • newline
Then, it goes ahead and adds new states if the new state expects a nonterminal. Here, for example, it'll add the states
newline -> • "\r\n"
and
newline -> • "\n"
This is what is happening on line 67.
Whenever you create an Earley state where the dot is at the end (i.e. not expecting anything), you go back and find where that state was created, and push it along. So if the next input to the parse was "\n", then you would add the state
newline -> "\n" •
Since this state is complete, you would bump along its creator, getting the state
statement -> expression ";" newline •
and then you'd have to go and find where that state was created, etc.
It turns out that when you have empty rules, then this process goes into an infinite loop because an empty rule is completed as soon as it is created. This sucks, because empty rules are actually useful. For example,
maybe_whitespace -> empty | whitespace
So, give or take, that's why there's that whole epsilon_closure trickery.
Hope that vaguely explains what's going on there. As a corollary, you should be able to figure out why ambiguity needs to be allowed by this algorithm.
Now, for debugging. I would suggest that first, you create special "instrumented" postprocessors for each production rule, such that the processed data knows the production rule that was used to make it. So, take
expr -> expr "+" expr | expr "-" expr
and turn it into
expr -> expr "+" expr {% function(d) {return ["production1", d]; } %} | number {% function(d) {return ["production2", d]; } %}
Then you parse the input that causes ambiguity, and get a data structure for each possible ambiguous parsing:
1+1+1 would yield
["production1", [ ["production2", 1], ["production1", [["production2", 1], ["production2", 1]]] ] ] ["production1", [ ["production1", [["production2", 1], ["production2", 1]]], ["production2", 1] ] ]
Then, do some sort of "tree diff" algorithm to figure out which of the productions is getting parsed in two different ways, and report it to the user. In this case, it would show that a production1 was being parsed in two different ways.
I would recommend writing this as a plugin for nearley before porting it to Python, so that I can help you out if you get stuck.
Hope that helps!
(Sorry if this is unclear, or if there are bugs in my writing. I type this in a hurry because I need to go to a meeting right now!)
erezsh
tjvr
GoMino
Hi, I opened this separate issue so we don't spam everyone :)
I'm glad you liked Pearley. It really is a direct port and the code is almost identical. I'll try to keep it aligned when new features are added to nearley. There is a minor difference, because I'm using an external library for lexing. But that's not significant.
I would be happy if you could explain line 67, but really I don't have a strong grasp on the algorithm anyway, so you may have to add a lot of context :) I would like to learn more about it, of course. I'm especially interested in making it faster, perhaps by pre-calculating some moves? I'm not sure.
As for ambiguity, I understand it can't be detected in the grammar. I still think it's possible to write code that will catch the common cases. Maybe I will try it some day. Another solution which would be relatively satisfying is if we could catch the ambiguity as it happens, instead of at the end of the parse. Perhaps that's impossible for some reason, I'm not sure (see: my lack of understanding of the algorithm). As for automating the debugging process - that's a nice idea, which I'm afraid to attempt :)
Sorry for the wall of text! Let me know your thoughts.