Alex Rivera | Logout

Lemon power or not?

Asked 2010-12-24T13:03:47.080
18

For grammar parser, I used to "play" with Bison which have its pros/cons.

Last week, I noticed on SqLite site that the engine is done with another grammar parser: Lemon

Sounds great after reading the thin documentation.
Do you have some feedback about this parser?

Cannot really see pertinent information on Google and Wikipedia (just a few examples, same tutorials) It doesn't seem very popular. (there is no tag in Stack Overflow [ed: there is now :P])

c parsing bison parser-generator lemon
Edit
Report

1 Answer

18

Reasons we are using Lemon in our firmware project are:

  • Small size of generated code and memory footprint. It produces the smallest parser I found (I compared parsers of similar complexity generated by flex, bison, ANTLR, and Lemon);
  • Excellent support of embedded systems: Lemon doesn't depend on standard library, you can specify external memory management functions, debug logging is removable.
  • Public domain license. There is separate fork of Lemon licensed under GPLv2 that is not suitable for our needs because of viral license. So we get latest sqlite sources and compile Lemon out of them (it consists of only two files);
  • Pull-parsing. It makes code more straightforward to understand and maintain than Flex/Bison parsing code. Thread-safety as an additional bonus I admire.
  • Simple integration with tokenizers. Our project nature requires tokenizing of binary stream with variable tokens size. It was quite an easy to implemented tokenizer and integrate with parser API of only 3 functions and one feedback context variable. We investigated ways of integrating Lemon with re2c and Ragel and found them also quite easy to implement.
  • Very simple syntax fast to learn.
  • Lemon explicitly separate development of tokenizer and lexical analyzer(parser). My development flow starts with designing of parser grammar. I'm able to check complex rules with implicit token sequence by the means of several Parser(...) calls at this first stage. Tokenizer is implemented afterwards.

Surely Lemon is not a silver bullet, it has limited area of application. Among disadvantages:

  • Lemon requires to write more rules in comparison with Bison because of simplified syntax: no repetitions and optionals, one action per rule, etc.
  • Complete set of LALR(1) parser limitations.
  • Only the C language.

Weigh the pros and cons before making your choice. I've done mine ;-)

answered 2011-02-19T11:06:43.680

Your Answer