Writing a recursive ascent parser by hand
abubalay.com
abubalay.com
At least in the Scala community, FastParse is used quite a lot. Works great for parsing source code, obscure data-formats (textual or binary), user query-languages, etc.. As long as you're not parsing gigabytes of big data, you probably won't even notice the 5-10x performance hit.
I can see myself using it for expression parsing, though, since that's almost inherently left-recursive. I usually use top-down operator precedence (AKA pratt parsing) for that, but recursive ascent might simplify it in some ways.
A left-associative operator means a Kleene star in the grammar, while a right-associative operator means right-recursion. I think the common view that it's left-recursive is just a weakness of the most common scheme for semantic actions. (I mean, yes, if you need to go through a parse tree first then the tree needs to be left-recursive -- but it seems simpler not to do that.)
And it's not a weakness, either- just one way to think about the problem which happens to map fairly naturally to how people think about expressions.
You even get to pick the encapsulation. Most people go with hashtable based objects, but you can use lists or even strings instead. It's a really good language to see how OO works under the covers.
Never understood this backwards way of thinking. You first write/immagine the grammar that you want to write, whatever is most intuitive for you.
Then you figure out what kind of parser your grammar needs.
Why would one contort a grammar? I mean, even "contorting it to not be context-dependent" is already a limitation enough...
For this, you want (as much as possible) for local edits to result in local modifications to the syntax tree, and ensuring that can require thinking carefully both about lexical syntax and abstract syntax. At the lexical level, if the literal syntax forbids newlines in string literals, then the changes to the token stream on a single-character edit are limited to changes to the tokens on the same line. Likewise, in the abstract syntax, if top-level declarations have a keyword, then the effect of a single-token change (eg, adding a mismatched paren) are limited to the declaration it occurs in.
There are a lot of tricks like this (eg, setting things up so you can find and parse the type declarations without having to parse a whole expression), but it's reasonable not to want to learn them. In that case, a really good heuristic is to make your language LL(1) parseable. It's not perfect, but it will rule out the vast majority of things that make incrementalization hard.
Left recursion in things like expressions is completely trivial to eliminate. If you want to e.g. embed a DSL in a language, something that's really easy to do with recursive descent, it's worth spending 30 seconds or so to remove left recursion from your expression rules. Etc.
> You first write/immagine the grammar that you want to write, whatever is most intuitive for you.
IMO this is the road to hard to parse languages; if you genuinely advocate this path, you'll end up needing a GLR parser before you know it. I think it's much better to ensure your grammar is parseable with LL(1); not only is the tooling simpler, but the language will be less ambiguous for human users too. Follow the example of Pascal, not C++. This is what I'd advocate even for people doing hand-written recursive descent on a new language: validate your grammar with an LL(k) tool even if you don't use the generated parser.
(You've ended up sounding a bit like Ira Baxter, who's often seen around the net selling his DMS toolkit. He has a strong self-interest in people writing complicated grammars, so that he can sell them his services...)
I'd bet against this. The human brain works very differently, we always keeps something like "trees of contexts" in our head. And why would you thing left recursions is less intuitive to a human user than other kinds of recursion.
> ended up sounding a bit like Ira Baxter
Now I gotta take time and google who this guy is :P
Haha, I was thinking about him too. He does have a point, though, that on 2018 machines we might be able to afford parsing technology a bit more expensive than the 1970s approaches commonly used today.
Tooling is still very useful for grammar validation though, and it's the way to go for ad hoc parsing of a simple or new language.
https://github.com/mozilla/narcissus/blob/master/lib/parser....
I played with this code like 8 years ago and remember being pretty confused by this style of parser. I was expecting recursive descent but it was something else.
It's a matter of whether the children are resolved before the parents, or the parents are resolved before the children.
The pushTarget() calls all over makes it look like bottom-up parsing. That doesn't appear in recursive descent (top down) parsers.
Yep, and Narcissus resolves the parents before the children by virtue of `Script` calling `Statements`, `Statements` calling `Statement`, etc. before ever actually seeing the bodies of their corresponding production rules.
A bottom-up parser doesn't work that way at all. Its states aren't determined by what they're about to parse, but by what has already been parsed. The `pushTarget` function in Narcissus is completely unrelated to bottom-up parsing.
I used to mess around with the ROSE C++ source-to-source transformation framework (http://rosecompiler.org/). One of the files in there (defining the AST structure for representing C++ programs) was about 100,000 lines of autogenerated code. It wasn't heavily templated, I think, but it did pull in a bunch of standard C++ headers. I could imagine the whole preprocessed thing approaching a gigabyte.
Um, you're right of course. I did do the same math in my head but somehow got confused by two orders of magnitude.
Bottoms-up parsing on the other hand typically requires creating the AST first, only to traverse it top-down in a manner resembling recursive descent. The speed advantages of bottoms-up are often lost in the inefficiencies of the AST.
Of course this doesn't always apply. It depends on the language.