4

Is it possible to use some kind of operator-precedence parser or shunting-yard algorithm for simple programming language? For example, if this language have only expressions, functions and declarations of variables.

What are cons and pros of this way? Can it be much faster than traditional LL/LR parsers?

8
  • Not likely to be faster; all parsers have to break the input into tokens ("lex") and that's where most of the "parsing" time actually goes. A operator-precedence driven grammer might have a smaller implementation (size) footprint, but I suspect these days that the tradeoff of space for the extra convenience that LL/LR parsers bring is not worth it in most cases. Finally, it is unclear how helpful operator precedence grammars are for the non-expression part of the language; the expresssion subgrammar is usually only a modest part of the whole grammar so it is unclear what the win really is.
    – Ira Baxter
    Mar 12, 2011 at 19:14
  • @IraBaxter Not only size footprint. Fredrik Lundh, who wrote about Pratt parsing, points out that you can save on stack depth during parsing. Whether or not this results in serious gains would depend on the particular grammar being implemented, though. effbot.org/zone/simple-top-down-parsing.htm
    – ThomasH
    Mar 21, 2012 at 18:11
  • @ThomasH: How deep does the stack get in parsing? If you have really complicated expressions, I doubt the stack gets more than 10-20 levels deep. (We have an on-the-fly code generator that processes several-million-line lisp-like programs, and it never blows its stack of some 128 slots). PS: Windows gives you 1 Mb if not more of stack space for a standard program. Does saving stack space matter?
    – Ira Baxter
    Mar 21, 2012 at 23:31
  • @IraBaxter I think this particular argument was not about the space consumed by the stack, but by the perfomance hit you get through pushing and poping stack frames.
    – ThomasH
    Mar 22, 2012 at 9:00
  • @ThomasH: Compared to the work of processing lexemes, the cost of creating new stack frames (a few machine instructions per call) in the parser (only a few stack frames per token likely, my LALR(1) parsers have zero but simulate a state state) is vanishingly small.
    – Ira Baxter
    Mar 22, 2012 at 9:09

1 Answer 1

4

To answer your first question, yes it is possible to do operator precedence parsing as part of the language. If you are interested in this you should look into Pratt parsers. This is usually a variant of top-down parsing so it should be in the same performance neighborhood as your other parsing options. Generally, I think people are overly concerned about parsing speed. A compiler is going to spend most of its time doing optimizations usually and sweating a few milliseconds on the parsing stage doesn't seem worth while to me.

There is a language, magpie, that has implemented a Pratt parser. So the big advantage is that they have defined all of the operators for the language in a library instead of the core language. This makes the core language incredibly compact and extensible. The downside though is this leaves other users always having to wonder what the precedence of a particular operator will be as the usual built-in norms may not apply.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.