Hacker News Reader

Comment by chubot | Hacker News Reader

I agree he is wrong on that point. The recursive descent is easy to see here:

http://minnie.tuhs.org/cgi-bin/utree.pl?file=V6/usr/source/c...

Search for statement() and forstmt().

(This site has a more modern, easier-to-read version of the Github files, which at least has #defines rather than hard-coded ints!!!)

But a large part of it is also Dijikstra's shunting yard algorithm:

http://minnie.tuhs.org/cgi-bin/utree.pl?file=V6/usr/source/c...

Read an expression and return a pointer to its tree. It's the classical bottom-up, priority-driven scheme. The initflg prevents the parse from going past "," or ":" because those delimitesrs are special in initializer (and some other) expressions.

    tree()

Related post: Code for the Shunting Yard Algorithm, and More http://www.oilshell.org/blog/2017/04/22.html

View on HN

Precedence parsing is surprisingly robust and error tolerant, as well as being bottom up. Sans braces, it can be used for much of your expression syntax depending on how overloaded your terminals are.

You can use it for braces too, with some relatively simple additional rules. Braces the way they're used in most languages are "just" a special case of parentheses: You need to recurse, and the closing parenthesis/brace needs to trigger reduce all the way to a single value.

If you're willing to sacrifice a bit more generality you can parse a lot more. E.g. my (very much in-progress and incomplete) Ruby compiler uses precedence parsing with tweaks to parse most of the Ruby grammar, including blocks (do/end, {/}), array indices and initializers (foo[1], vs [1,2,3]) and more.

It's been hell to adjust the priorities, and it's not correct yet, but I also think it can be cleaned up quite a bit more. The biggest pain point, actually, is tidying up the generated tree to remove superfluous nodes and flaten various bits, and that's where I'll need to do the most work to simplify.

There are of course ugly parts of this with Ruby that ruined my originally quite nice and clean generic shunting yard code. E.g. if "foo" is a local variable "foo [1]" should parse as "foo.[](1)" (that is '[]' is a method name), while if "foo" is not a local variable, it is implicitly a method call, and "foo [1]" should parse as "foo([1])" with "self" as implicit receiver. I've for now resolved that by having a few "artificial" terminals to handle this and a few other ambiguities that are picked based on context and resolved later, but I'm really not happy about it. Worst case is I "surrender" and convert it to a recursive descent like the higher levels of the grammar, but I want to see what I can do with the current one first.

Currently the full parser, which still lacks some parts of Ruby is about 1600 lines of Ruby (including the lexical tokenizer and some generic parser/scanner utility classes), which I'm distinctly displeased about - it's much smaller than MRI, but not as much smaller as I think should be possible, especially since it's still missing pieces; granted there's a lot of comments, but I think parsing Ruby in Ruby should be doable in <1000 lines of Ruby code using recursive descent + precedence parsing despite Ruby's many idiosyncracies. Less if you exclude the code for a decent generic parser library. I think that says a lot of the simplicity of applying both recursive descent and precedence parsing..

Note I was using brace synonymously with paren (to me, parens are just a special kind of brace, I assume you are equating brace with bracket).

Sure, you can also deal with terminal overloading using adjacency if you want. However, the parser gets more complex and it becomes less worth it. In the parsers I build, I match braces in a separate earlier phase anyways (you don’t need a parser to do that, and it makes the parser much more robust if you do).

However, the main drawback of a precedence parser is that you don’t get any parse errors out of it, and you have to manually go back and check that your trees are actually well formed. So I’ve went back to pure recursive descent.

> However, the parser gets more complex and it becomes less worth it.

It really doesn't change much. Here's a simple one that can handle simple function call syntax: https://gist.github.com/vidarh/a109c3788044736568bd71e79e842...

Apart from the operator definitions, to handle parentheses it contains two checks for the ":lp" operator type I used for left parentheses / any other tokens like brackets that'd behave the same, and one line to force :rp (right/closing parenthesis) to trigger a reduce. 40-something of those lines are the actual shunting yard/precedence parsing.

The variant I use for my Ruby parser does have some extra (ugly) hacks needed to deal with Ruby ambiguities, and "fun" stuff like variable arity operators (e.g. to handle method calls or things like "return") but the above is pretty much what you need to deal with saner grammars in a fairly generic way.

> you don’t need a parser to do that, and it makes the parser much more robust if you do

That very much depends on the language. In Ruby for example, the meaning of both parenthesis and curly/square brackets is context-sensitive. E.g. {} is a Hash literal. "foo {}" is a method call with a block. Or one of my "favorites": foo(5,1) is valid and has two arguments. foo(5,:bar => :baz) is valid. foo(:bar => :baz,5) is a syntax error ( "=>" is expected rather than ")" as the first "=>" turned it and all following elements of the argument list into an implicit Hash literal (so the last two ones are equivalent to foo(5, {:bar => :baz) and foo({:bar => :baz, 5}) respectively). There are more caveats, but I don't remember all of them off the top of my head. Some of them you could probably handle quite easily while pre-parsing, but you'd need to apply at least some grammar rules as many constructs acts very differently depending on whether or not an operator is used as prefix or infix for example. E.g. "% foo " is the literal quoted string "foo" (space acts as the quote character) while (foo % bar) is foo modulo bar, so you can't even safely tokenize Ruby without some thought to the preceding token at a minimum.

> However, the main drawback of a precedence parser is that you don’t get any parse errors out of it, and you have to manually go back and check that your trees are actually well formed.

Sure you do. If the value stack contains fewer arguments than the current operator requires after any reduce step that the priorities require, you have an error, and the cause is generally straightforward enough to place.

Constructing precise errors from that can be a bit painful, but it usually points at the "correct" spot if you record the locations of tokens, and the priorities lets you process the priorities of the operators and easily enough determine what would be valid.

I'm not sure how you'd use it to end up with invalid trees. In the contexts I've used it, the tokenizer combined with the precedence table is enough to ensure that the trees are syntactically well formed. If you want to apply semantic checks, you can just as easily call out to do those tests with a precedence parser as with a recursive descent one.

Braces sound like they are always balanced in Ruby, so you can match them outside of the parser even if you don’t know how they will be used. You still have to “parse”, but freeing your parser from matching leads to more robust parses.

The only place where a pre match step doesn’t work is when you have tokens that are overloaded to sometimes be braces or not; I.e. < and > in most languages after C++ that has generics. Actually, you need non deterministic parsing in most cases with these, which is a pain and I wish new languages wouldn’t keep copying this mistake (typescript).

It looks like you are checking correctness in your precedence parser, which is fine, but it’s not possible to do that for many languages.

> Braces sound like they are always balanced in Ruby, so you can match them outside of the parser even if you don’t know how they will be used. You still have to “parse”, but freeing your parser from matching leads to more robust parses.

I don't see what you mean when you say it makes it more robust. They're no different than other operators and punctuation.

With respect to balancing, I'm actually not sure, There are sufficient corner cases to try to exploit that it's not obvious to me if you can or can't construct cases that'd be hard to get right. Writing a Ruby parser keeps teaching me corners of the grammar that I've never touched in 13 years of using the grammar... Many of them are dark corners I've never seen in the wild, and hope I never do.

With respect to "<>", you certainly can do %<foo> in Ruby, but that's easy enough to handle in the tokenizer, assuming you add a token lookbehind so I don't think it changes things (needed to know if "%" is the modulo operator or starting a quoted string). Meanwhile "%>foo>" means the same ("<[{(" after "%" starts a quoted string that ends with the "closing" sybol, but most other non-alphabetic symbols starts a quoted string that ends with the same symbol - unfortunately this includes whitespace)

I'm starting to think you may be right they'll be ok to handle separately, though I still don't see a reason to do it.

> It looks like you are checking correctness in your precedence parser, which is fine, but it’s not possible to do that for many languages.

Depends what you mean by "checking for correctness". In the simplest form, such as the example I posted, it is applying one very basic check: Does the number of available values on the value stack match what is required by the operator currently being processed?

The only thing you need to be able to do in order to do that is to be able to split the tokens into operators and other symbols (which are all values/operands as far as the precedence parser is concerned), and match the operators against a list of operator types and priorities. If you can do that, you can construct a well formed tree as per the rules specified by the precedence parser configuration. If you can't, you probably shouldn't parse it with that parser, but should instead either augment the parser to support what you need, or use something else.

It sounds to me as if you're checking the trees afterwards because you've shoehorned a grammar that's beyond the capabilities of the specific precedence parser into using it anyway but deliver trees that matches what you've actually specified but not what you want, and that this is what you don't consider well formed. That's fair enough, and I've done post-processing myself too, but generally I've come to think it's better to push capabilities to build the tree the way you want it in the first place to the parser. In any case I don't really consider that "fixing" malformed trees: The parser will only accept trees that are syntactically valid according to the classification of the tokens and the precedence rules.

> I don't see what you mean when you say it makes it more robust. They're no different than other operators and punctuation.

Error recovery mainly. An unpaired brace can simply be flagged and then ignored during parsing. Maybe not so interesting for a batch parser, but it works really well in an IDE where transient errors like this are common. The other thing is that you know exactly where your brace constructions end, so you don't need to parse beyond them. Likewise, if you have parsed all that you can inside the brace area and still haven't reached the end, you can just flag the remaining tokens as unexpected junk and move on to the end of the brace, recovering very gracefully. Finally, to if you type ( inside (....) to get (...(...), you can use the fact that the outer parens to were previously matched to flag that the inner paren just typed is the one unmatched, not the outer ones.

For live programming contexts where you are constantly parsing and type checking, this is useful.

> Depends what you mean by "checking for correctness". In the simplest form, such as the example I posted, it is applying one very basic check: Does the number of available values on the value stack match what is required by the operator currently being processed?

That is basically a check, I'm not really versed in Ruby's grammar, in many languages the grammars are quite complicated and BNF-style enforcements is very necessary...you also need to consider construction of your AST for type checking and execution (which you might not need for your case).

> The parser will only accept trees that are syntactically valid according to the classification of the tokens and the precedence rules.

Given just precedence rules, it should be clear that syntactic validity isn't really a thing.

> An unpaired brace can simply be flagged and then ignored during parsing.

I don't see what that'd generally buy vs. simply trying the parse until it fails, though.

> The other thing is that you know exactly where your brace constructions end, so you don't need to parse beyond them.

That's automatically handled simply by adding the closing braces to the operator table, and terminating when the right type is reached, or when a symbol is hit that is not valid within the context. E.g. the example parser I linked to will automatically terminate that way if you invoke it the right way.

> Likewise, if you have parsed all that you can inside the brace area and still haven't reached the end, you can just flag the remaining tokens as unexpected junk and move on to the end of the brace, recovering very gracefully.

That's a line or two to catch the exceptions the example code throws and the read tokens until the specified closing brace/bracket type.

> Finally, to if you type ( inside (....) to get (...(...), you can use the fact that the outer parens to were previously matched to flag that the inner paren just typed is the one unmatched, not the outer ones.

That sounds specific to an IDE, and not really something I've looked at, and does sound like it might be useful. The other ones don't really convince me, but I guess for an interactive parser this one could be. Of course it's trivial to combine that with a precedence parser too, and still handle it in the parser.

> That is basically a check, I'm not really versed in Ruby's grammar, in many languages the grammars are quite complicated and BNF-style enforcements is very necessary...you also need to consider construction of your AST for type checking and execution (which you might not need for your case).

It's a check that is inherent to the precedence parser. The entire point of the parser is "shunt" tokens onto an operand and operator stack effective sort them into reverse polish notation. You can't do that without knowing if the operator is prefix, postfix or infix and what arity the operator has (though most preced check if the token stream matches the rules in the operator table, and if so output expressions. ence parsers will just assume an arity of 1 for prefix/postfix and 2 for infix, that's easy to overcome).

The operator table is a specification of the grammar according to those rules. If you get a malformed tree, either the parser in question doesn't support your grammar, or your grammar specification in the form of the operator table is malformed.

> BNF-style enforcements is very necessary..

There are certainly subsets that are awkward or requires you to augment a precedence parser. E.g. as I described elsewhere, in a past experiment where I did parse a whole Pascal-like language this way, I had to add a bunch of extra operator types, but really it just boils down to specifying minimum and maximum arity to the left and right of the operator, and you can handle very complex structures, but certainly not all.

You probably could extend a precedence parser to handle most languages in their entirety with a relatively small set of rules, but we agree it's probably not worth it. My point is not to try to parse every construct with a precedence parser, but that I've yet to see a grammar that doesn't have the typical highly recursive expression subset of the grammar that a precedence parser is a great fit for, but also that even surrounding that, a precedence parser is often easy enough to extend to a fairly large additional subset of the grammar.

E.g. my Ruby parser handles 26 productions outside the precedence parser and 50 operators (some "synthetic" to handle special parser rules) in the precedence parser.. It'd be easy enough to handle most of the 26 in the precedence parser too, and in fact I've moved more things into the precedence parser than the other way, but some constructs like "class", "if/else/elsif/else/end", "case/when" etc. will probably never get added to it.

> you also need to consider construction of your AST for type checking and execution (which you might not need for your case).

The precedence parser itself does not need to put any limits on the AST construction. In fact, the example I posted explicitly decouple tree construction from the parsing, so you can pass it a builder class that can apply whatever additional constraints you want on the construction of the trees. I don't think the tree construction there would end up typically being any more complex than in a typical recursive descent parser.

> I don't see what that'd generally buy vs. simply trying the parse until it fails, though.

Brace completion that isn’t stupid for one.

Everything I’ve done is for IDEs, I don’t really believe in batch parsers anymore.

I'm not sure if this is what you meant, but yes the C compiler uses it for the entire expression syntax -- not just arithmetic. Because in C "declaration mimics use", it's used for type expressions too.

As for using it for the entire programming language, like for/while/switch, I see the discussion with vidarh below.

I haven't seen a parser written like this, so that's interesting.

However I consider the "opposite" sort of a mistake? Doug Crockford uses top-down operator precedence to parse ALL of JavaScript, not just the expression language.

Review of Pratt/TDOP Parsing Tutorials http://www.oilshell.org/blog/2016/11/02.html

I remember being confused by this, and I think it is still confusing. It seems to me that the statement language and expression language are separate things, and it makes sense to use recursive descent for the statement language and either top-down or bottom-up precedence for expressions. In other words, the architecture of the original C compiler is very clean, and no doubt influenced the language design. (On the other hand, it's probably also responsible for the fact that C has so many levels of precedence, some of which don't make sense!)

Also, the difference between "Pratt parsing" and "Precedence climbing" is sort of a code organization issue -- do you handle a[i] and x?a:b in the same place as a*b a+b etc.? I wondered if there is an analogous thing for bottom-up expression parsing. I like having each "form" in one function.

Pratt parsing is a nice complement to recursive descent; it's accurate to say that it's a variant of recursive descent with the additional input of numerical priorities.

> As for using it for the entire programming language, like for/while/switch, I see the discussion with vidarh below.

I've done a full Pascal-like language using bottom up precedence parsing in the past. It was my first compiler project about 25 years ago or so, and "invented" precedence parsing with the help of a symbolic expression evaluator in Prolog in a book I picked up that I tried to figure out how to translate to Pascal.

It was very disappointing to find out it was a well known algorithm, but it was very interesting to try to expand it to handle a full language, which involved funky things like handling operators with different structure than just simple single-operand prefix/postfix + infix operators. E.g. I implemented a dual-arity prefix operator to handle for/while/if/ternary for example. So "while" took two expressions: the condition and a block.

The hard part was not handling the control structures, but getting the priorities right.

I'm not sure I'd do that again. My Ruby parser uses recursive descent for the top level productions.

But it was fascinating to do, as it did make for a very compact parser.

> It seems to me that the statement language and expression language are separate things,

I think if you go down that route, then you are implicitly deciding that everything is an expression. In e.g. Ruby that is true, though many constructs just returns nil (e.g "somevar = while condition; end" is valid). But given that many of the "operators" are only allowed at specific levels, it makes less sense to use a precedence parser anyway (e.g. "class" can't occur in a method body for example).

For me, those two are the biggest considerations to whether or not I'd consider a precedence parser: Whether or not everything is an expression, and which keywords are only allowed in specific contexts.

But even if it's feasible without too many contortions, it may still be very painful.

Interesting, thanks for the feedback. It seems like the lesson is analogous to what I learned from Crockford's JavaScript parser.

That is, regardless of whether you're doing it top-down or bottom-up, using an operator precedence algorithm for statements is painful.

I think the reason is simply that there is a fundamental relationship between the language you are parsing (the data) the algorithm you choose to parse it with (the code). Those 2 things are tightly linked.

I think this isn't emphasized enough in introductory texts. They usually only have time to teach one parsing method, and the language being parsed is chosen to fit that. Or maybe you choose one problem like shift-reduce conflicts, but you don't get the comparison / contrast to other methods.

Reply on news.ycombinator.com