Under The Bonnet: Parser, Lexer… ANTLR

Sometimes it goes like this: you start to make your well defined contribution (type inference), and as you start to assess the job to be done, you realize that some parts are bigger than you thought. So you start looking in to them time to time, and only after a while you realize that you’re step further down in the heart of the project. At this time, I fell in to the parser but for a reason: At work, I was working on a toy parser for a server with the good ol’ hand-crafted way. And I found it fun. Originally, I had the idea to  use bison, ANTLR or something similar to generate a parser, but I rejected the idea because I was afraid I couldn’t learn enough about the compiler generators to finish my task in reasonable time.

In the recent weeks, I tried to get my head around the core of the DDT.  I’ve found the current visitor accessibility unfortunately narrow for semantic analysis, type deduction or type inference, and ran in to some artefacts in the AST design. Well, this is always good news as someone has to deal with these issues. Soon enough I found that the lack of direct parser to our AST is a source of unnecessary complexity, not to mention the possible overheads. I say possible, because I couldn’t make my self carry out detailed measures. OK, OK, I’m lazy! Anyway, so the obvious choice was to look in to the question of the ANTLR parser.

Some initial experiments taught me that I shouldn’t follow Walter’s BNF-kinda description because 1. it is heavy of left-recursive rules definitions, which needs serious re-factoring, 2. there are too many differences between our current AST hierarchy and D documentation’s for explaining the language.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s