Hacker News Reader

Comment by shakna | Hacker News Reader

> Many low-level parsers ‘in the wild’ are written by hand, often because they need to deal with binary formats, or in a quest for better performance.

I think the main reason for hand-rolled parsers, at least in my experience, has been error reporting.

Most parsing frameworks make it difficult for you to tell the user simple things like misspelled variables, something does exist, but it isn't in-scope when its being called, and basically helpful messages like that.

Error management is only briefly mentioned, and sort of glossed over in Nom's [0] paper. Mostly because Nom was designed for efficiency... But efficiency is not why GCC rolled their own parsers.

[0] http://spw15.langsec.org/papers/couprie-nom.pdf

View on HN

It's possible to provide rich information and flexible error reporting using error combinators, which merge results from failed parser combinators. The error combinators are in some sense dual to the parser combinators.

How could an error combinator possibly approach something like a misnamed variable? It would need access to the current scope's environment, or a version of it, to suggest what the spelling error might be. Not-yet-in-scope errors are similar, but need both past and future scopes as well.

I don't know of any parser combinator that can handle those very human mistakes, because they require partial evaluation to understand.

I might be mistaken, but if I'm not, parser combinators are great for saving time, but if you have the time to do it right, then a hand-rolled parser will give your users a much better experience.

Misnamed variables are actually one of the simplest problems to deal with ehile parsing. The solution is simple - you don't! The purpose of the parser is to parse the syntax, so you can simply use it to build a syntax tree and postpone the resolution of names until the next step in compiler's pipeline (also useful if you language supports macros).

C is a well-known exception to this. The grammar depends on typedef name resolution. `foo * bar` and `(foo)-1` parse as different things depending on whether `foo` is a typedef or a variable.

In some areas of the world (VHDL/Ada), you have to maintain symbol table for correct lexing.

These languages have constructions like OBJECT_NAME'ATTRIBUTE (object name can be anything with visible name in the scope and attributes depend on its kind) and RECORD_TYPE_NAME'SLICE where we create value of RECORD_TYPE_NAME using slice, which is collection of values of record fields.

There are also character literals, which have form like 'a', '1', '#', ''''. Just as you can expect here.

The combination of record value construction and lexer forms for character literals makes it hard to parse something like MY_RECORD'('1','0',false, 10).

Symbol table and/or dynamic parse construction allows you to parse these texts easily and specify the syntax straightforwardly. The other approach with construction of separate AST complicates things a lot.

>Most parsing frameworks make it difficult for you to tell the user simple things like misspelled variables, something does exist, but it isn't in-scope when its being called, and basically helpful messages like that.

I agree that generated parsers make error reporting difficult, but do not think these examples are relevent. If the problem is a misspelled or out of scope identifier, the parser should should still be able to parse the program, which would be syntactically valid.

> which would be syntactically valid.

Not necessarily.

Usually, we're used to seeing something like:

    print("Something")

But there are statement based languages where instead you have:

    print "Something"

Still simple enough to parse.

However, what about user function calls?

    something 1 2
    3 4

If a newline doesn't break a call, and you don't depend on indenting, but actually the arity of the original function definition, accidentally writing:

    someting 1, 2
    3 4

Can be impossible to parse correctly, especially if said language also supports first-class functions.

    func apply with func:caller array:values
      do
        ...code...
      done

    aply + list
      do
        10 10 10 10
      done

The syntax in the above example is still correct, but because the arity of 'aply' can't be determined, the parser can't actually continue.

The grammar might be a little insane, but I've had to work with similar grammars in several financial languages. And the parser does poop out, and when it does, you really want a nice error to result.

> If the problem is a misspelled or out of scope identifier, the parser should should still be able to parse the program

That's not necessarily true for all languages. For example, in C, "(e1)&e2" is parsed differently depending on how e1 is declared. If e1 is declared as

    typedef int* e1;

then the "&" in "(e1)&e2" is parsed as the address-of operator, but if e1 is declared as

    int e1;

then "(e1)&e2" is parsed as a bitwise AND.

This is a problem for a lot of languages, unfortunately, and it breaks the clean separation between syntax and semantics that we're hoping for when we write a formal grammar.

I've had some success in the past with using GLR or another algorithm that can handle ambiguity, and then choosing among the possible parse trees in another pass that takes semantic information into account. How applicable that is really depends on the language, though; if things are so ambiguous that you're getting an exponential growth in possible parse trees, you may not want to use this approach.

Reply on news.ycombinator.com