[Haskell-beginners] Parsing arithmentic expressions

[Bernie Pope]

Hi,

Have you seen the buildExpressionParser combinator in Parsec?

    http://legacy.cs.uu.nl/daan/download/parsec/parsec.html#buildExpressionParser

It allows you to specify precedence and associativity for operator  
parsers declaratively, and it generally saves you from lots of  
refactoring in the grammar.

You could probably stick with the straightforward data representation  
of expressions.

Cheers,
Bernie.

On 16/11/2008, at 11:15 AM, Glurk wrote:

> 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 :)
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners