Mehmet Sefa Balık Mehmet Sefa Balık - 1 month ago 17
C++ Question

From BNF-like grammer to Java or C++

I searched the internet to find an answer, but I couldn't. Is there anyone who will help me?

expr ->term moreterms

moreterms -> +term {print(‘+’)} moreterms
|­‐term {print(‘‐’)} moreterms


term ->factor morefactors

morefactors ->*factor {print(‘*’)} morefactors
|/factor {print(‘/’)} morefactors


factor ->(expr)
|id {print(id)}
|num {print(num)}


I will use this code for a very basic calculator compiler and a interpreter.

How can I convert this grammer into C++ or Java?

Answer

There are many tools that take grammars and generate parsers, ranging from Yacc to boost spirit.

The art of writing parsers has been widely studied. It isn't trivial. One approach is to determine if you can make your BNF into an LR(1) grammar and write a LR parser for it.

An easy way to parse is to split your parsing into tokenizing (where you bundle things into identifiers), and syntax tree generation.

Wikipedia has a cursory description of LR parsing. Knuth's Canonical LR(1) parser is also worth looking at.

Teaching how to write an LR(1) parser (with whatever restrictions, let alone an LR(k) parser) is a matter of a short college course or a book chapter, not a stack overflow post.

But the general idea is you read from left to right. You look ahead k tokens (typically 1) to determine which rule to apply to the next token you encounter. You build the parse tree from the bottom-up.

There are lots of technical details, techniques, quirks and problems. Not every BNF grammar can be turned into a LR(1) grammar, let alone the restricted ones that many parse generators can handle.

As mentioend by @UnholySheep, The Dragon Book is the book that most people learn these techniques from.