Subscribe to dday9's Blog        RSS Feed
-----

Lexical Analysis - Required?

Icon Leave Comment
Introduction
If you have read any material on compiler creation then you know that there is essentially 2 phases of a compiler:
  • Front End
  • Back End


With both phases having multiple mini-phases. The front end will typically be comprised of a 3 mini-phases:
  • Lexical Analysis
  • Syntax Analysis
  • Semantic Analysis


Genesis
So when I first wanted to see if I could parse an existing language(JSON), I followed the suggested mini-phase model. I built a lexical analyzer to convert the source into tokens and then built a syntax analyzer to convert the tokens into an abstract syntax tree. I skipped the semantic analysis phase because in JSON you do not have any type checking or variables.

Short Excitement
However, after the jubilation of making my first parser wore off I realized that I could make my code shorter by removing the lexical analysis mini-phase. So I did just that, I built only a syntax analyzer that worked with the literals inside of the source code rather than working with tokens. I found that the overall size of my code was much shorter and that the time it took to parse long JSON files was quicker too, though not by much.

Pushing the Envelope
I decided that since I built an expression evaluator a while back using the same model that I would try to build the expression evaluator without a lexical analyzer. I easily created a scannerless shunting-yard algorithm expression evaluator. However, I found that whenever it came to allowing for things like functions and variables that it was much more difficult without the lexical analysis mini-phase, though it could be done.

Pushing too Far
Since I have now made a scannerless JSON parser and scannerless expression evaluator I decided to try and create a scannerless parser for my own little domain-specific language. This is where I found that it was too much work to not use a scanner. I was running into more problems trying to skip the lexical analysis min-phase than it was worth.

Conclusion
Lexical analyzers are not required... but they do make things simpler for languages that have a more robust grammar. When you are creating a parser, you need to weigh out whether or not it is simpler to just implement a lexical analyzer and sometimes you won't know this until you've tried to make a scannerless parser for your need.

0 Comments On This Entry

 

Trackbacks for this entry [ Trackback URL ]

There are no Trackbacks for this entry

October 2017

S M T W T F S
1234567
891011121314
1516171819 20 21
22232425262728
293031    

Tags

    Recent Entries

    Recent Comments

    Search My Blog

    0 user(s) viewing

    0 Guests
    0 member(s)
    0 anonymous member(s)

    Categories