BNF Grammar parser and disambiguator written with Haskell's parser combinators
It will eventually compile the given grammar to a parser for the language described by the grammar itself.
As many authors tend to use slightly different versions of the same notation, I adopted the following syntax for the BNF grammar:
- A terminal symbol is any literal enclosed in double quotes
"+", "(", "literal"
- A non-terminal symbol is an identifier enclosed in angular brackets:
<int>, <expr>, <lift2>
- An identifier is any string defined as in most formal languages, namely an alphabetic character followed by zero or more alphanumeric characters
- An expression is a concatenation of symbols (terminal or non-terminal)
<int>"+"<int>
- A production is described by a non-terminal symbol followed by the string
::=
and an arbitrary sequence of expressions alternated by the character|
Currently the parser provides the ability to eliminate (direct) left recursion, the following is an example of that behaviour:
<S> ::= <expr>
<expr> ::= <expr> "+" <term> | <expr> "-" <term> | <term>
<term> ::= <term> "*" <factor> | <term> "/" <factor> | <factor>
<factor> ::= "(" <expr> ")" | <int>
<S> ::= <expr>
<expr'> ::= "+" <term> <expr'>
<expr'> ::= "-" <term> <expr'>
<expr> ::= <term> <expr'>
<term'> ::= "*" <factor> <term'>
<term'> ::= "/" <factor> <term'>
<term> ::= <factor> <term'>
<factor> ::= "(" <expr> ")" | <int>