Bulldozer — Builder of LL Parsers

The parser for the Jancy compiler is generated using Bulldozer, our in-house builder of table-driven LL parsers.

The main reason why we chose a generated parser while most production-level compilers favor recursive descent is this: we wanted to achieve the perfect syntax for our language. In order to succeed we had to go through a lot of trial and error experiments. We didn't want to be bogged down in the routine of adjusting a recursive-descent parser. In addition, the generated parser provides two more benefits:

  • EBNF grammar as a permanently relevant syntax reference
  • Natural constraints to not let us get too crazy with the syntax.

What's wrong with ANTLR, Coco, Yacc/Bison, Lemon and other undoubtedly respectable and tried-and-true parser generators is in itself an interesting subject. It is, however, the one for a separate article, as it would require detailed comparison with lots of code snippets. We will get to that some day. For now let's just say that we needed a top-down parser generator with predictable and configurable conflict resolution mechanism and we found that each existing parser generator couldn't quite cut it at one situation or another.

The collaboration model between the parser and the lexer was "lifted" from Lemon. The Bulldozer-generated parser does not call the lexer. Instead, the external loop asks the lexer to tokenize the next source chunk and feeds tokens into the table-driven parser. This model allows for an incremental parsing of incomplete compilation units (supports pause-and-resume, so to speak). Plus there is no need for artificial nesting level limitations due to the danger of a stack overflow (it's simply not an issue here).

Controllers

DS110x Family

Boards

EM1001