Hacker News Reader

Comment by samatman | Hacker News Reader

I found the code for Instaparse (relatively) easy to follow.

I had considered leaving a comment here like "hey could you cover combinators and PEGs?", but after thinking it over, it's important to limit the scope for a class like this.

It would be pretty great to offer a "201" edition, covering ALL*, GLR, GLL, combinators/PEGs, Earley, parsing-with-derivatives, Marpa, and anything else I might have forgotten: basically a survey of modern parsing algorithms, which frankly, LR and LL are not.

But for your own learning, I bet you could take this course, and then spend some time with Instaparse and the GLL paper, and walk away with a solid understanding of GLL in practice.

View on HN

Great point on combinators, PEG, and GLL -- this potentially would be covered in 201 as suggested, since it's good having a foundation of the LL/LR, and then gradually moving to combinators if needed. LALR(1) covers a pretty wide range of the most practical languages.

To a significant degree, the arrow of causality runs LALR(1) -> practical languages, not the other direction!

The languages and formats we use have been heavily shaped by the practical parsing algorithms of the 20th century. An example: you can't have a struct field called "while" in C, because once the lexer declares a token to be a keyword, that's that.

Contextual keywords are a growing thing in modern languages. Modern compilers don't tend to have strictly separated lexers and parsers, but instead use a combined lexer/parser model that feeds information back and forth between them. If your language is designed such that you aren't often in multiple potential parse states, then it's easy to feed into the lexer "get me the next token, and by the way, expect function attributes to be keywords right now."

Note that the requirement to not be in multiple potential parse states also tends to boil down to "build a language that's usually LL(1) or LALR(1)."

TBH, that's not a problem of LALR(1), or any of the other, more old fashioned methods. I've written an LL(1) parser generator that (generates a function that) parses modern awk, without semicolons, but with operator-less concatenation, and that can deal with tokens that can be keywords and identifiers (which is also needed for e.g. FORTRAN). As long as your language is deterministic, it can be expressed as an LR grammar, although legibility might suffer.

Yes, to some degree -- Syntax tool normally support lexer states, and the same "while" token may mean a keyword or the property/field name of a struct. You can find more details of the lexer states in the docs.

What is GRR? Did you mean GLR?

Yep, that was a typo, fixed it

Ah okay. Note that GLR isn't exactly modern (1974). However, I would also remove "modern" as a requirement here... what really matters is how good the algorithm is, not how old it is. "Modern" algorithms easily end up being less powerful than the old ones... they just end up becoming popular due to other factors, e.g. simplicity.

"Advanced" would have been more expressive, agreed.

In the sense that LALR and LL with limited lookahead are the introductory parsing algorithms which everyone knows, and there's a reason for that.

Reply on news.ycombinator.com