Hacker News Reader

Comment by tom_mellior | Hacker News Reader

Yes, given a sufficiently powerful parser generator (more powerful than Yacc), you can do that. That's also the point of the talk I linked.

Ira Baxter makes a living out of selling proprietary technology based on GLR parsing. His opinion matters, but if there is no open source GLR parser generator available (is there? I don't know), the point he makes cannot apply to GCC or Clang.

View on HN

You don't necessarily need something more powerful than Yacc. I think the point was that you can encode errors directly into your grammar. So for some language with semicolon statement separators you can do something like this:

    PROGRAM -> STATEMENT*
    STATEMENT -> IF-STATEMENT | ASSIGN-STATEMENT | STATEMENT-ERROR
    IF-STATEMENT -> ...
    ASSIGN-STATEMENT -> ...
    STATEMENT-ERROR -> TOKEN* SEMICOLON

The idea being that if the if-statement and assignment statement rules fail you consume tokens until the next statement separator (semicolon in our case), produce an Error node in the AST and resume parsing the next statement. This allows your parser to actually catch multiple errors in one pass since it won't die the moment it encounters something it can't parse. After parsing you scan the AST and if it has any Error nodes you spit out the relevant error messages and exit. You can get as granular with the error rules as you want, although the more you add the more unwieldy the grammar becomes.

Naturally doing this in practice is harder than it sounds. Tweaking the Error rules is hard. If you consume too much or too little input you will resume in a spot that can have no chance of ever succeeding, giving way to a cascade of parse errors. I think we've probably all seen a compiler spit out a couple of dozen error messages all stemming from a single root error like a missing closing parentheses or brace.

I believe GNU Bison parser generator is capable of generating GLR parsers:

https://www.gnu.org/software/bison/manual/html_node/GLR-Pars...

Oh wow, that's pretty cool, wish I had known about it before. Unfortunately flex and bison, when used together in C++, cause a lot of headache (unless you create an "adapter" class that wraps your Flex parser and pass that to Bison). :/

Reply on news.ycombinator.com