[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