3

I'm interested in writing a parser (syntax analyser) from a BNF grammar without using a generator tool like yacc or bison.

I take as example the BNF for simple arithmetic expression : (extracted from the Dragon Book 2.2.6)

expr -> expr + term | expire - term | term
term -> term * factor | term / factor | factor
factor -> number | (expr)

Suppose I would like to create the equivalent code.

I guess I should create three functions called parseExpr, parseTerm and parseFactor.

How do I construct these functions regarding to the BNF defined upwards ?

For the parseFactor it seems to be obvious :

  1. Get the token type
  2. If type number return a node for number type
  3. If the token represents an opening parenthesis, get the node returned by parseExpr
  4. Check that next token is a closing parenthesis. If yes, return the node obtained at 3. If no, throw an error

For the parseExpr, I'm a little bit confused about how to start and interpret the production : expr -> expr + term | expire - term | term

How to translate this production ? How to detect which case applies ? Same question for the last production ?

yageek
  • 4,115
  • 3
  • 30
  • 48
  • Could you supply a sample input and output for these functions? – ShellFish Jan 15 '15 at 02:09
  • 1
    See this SO answer for how to manually code a recursive descent parser directly from a grammar: http://stackoverflow.com/questions/2245962/is-there-an-alternative-for-flex-bison-that-is-usable-on-8-bit-embedded-systems/2336769#2336769 – Ira Baxter Jan 15 '15 at 05:12
  • This link sounds really good :) Could you add explanation about it : why should we remove left recursion and how do you do it ? – yageek Jan 15 '15 at 07:03
  • You can take a look at [libmarpa](https://github.com/jeffreykegler/libmarpa) which implements the [Marpa parsing algorithm](http://savage.net.au/Marpa.html), is not a parser generator, you need to create the grammar and write a lexer. – rns Jan 15 '15 at 11:41

0 Answers0