[Haskell-beginners] Parsing arithmentic expressions
Glurk
streborg at hotmail.com
Sat Nov 15 19:15:29 EST 2008
Hi,
I'm just trying to learn how to use Parsec and am experimenting with parsing
arithmetic expressions.
This article gives a good example ->
http://www.haskell.org/haskellwiki/Parsing_expressions_and_statements
However, like most other examples I could find, the grammar for the expression
doesn't take operator precedence into account, and allows for expressions of
any size by defining expr recursively, eg :-
expr ::= var | const | ( expr ) | unop expr | expr duop expr
So, you can keep extending the expression by adding another operator and
expression.
The data to hold the expression is then very easily derived :-
data Expr = Var String | Con Bool | Uno Unop Expr | Duo Duop Expr Expr
The grammar I want to parse is slightly different in that it allows for
operator precendence. Part of the grammar is something like :-
expression = SimpleExpression {relation SimpleExpression}.
SimpleExpression = ["+"|"-"] term {AddOperator term}.
So, instead of recursively defining expression, it is made up of multiples
occurrences of SimpleExpression joined together with Relation operators.
Where I am confused is how I should best represent this stucture in my data.
Should I have something like :-
data Expr = Expr SimpleExpr [(RelOp, SimpleExpression)]
ie, an initial SimpleExpr, followed by a list of operator and SimpleExpression
pairs.
I haven't seen any example similar to this, so I was wondering if I'm going
down the wrong track ?
Perhaps another alternative is to modify the grammar somehow ?
I guess, the question is, in general how do you handle such repeated elements
as definied in an EBNF grammar, in structuring your data ?
Any advice appreciated !
Thanks :)
More information about the Beginners
mailing list