Parsing arithmentic expressions

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Parsing arithmentic expressions

Glurk
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 :)

Reply | Threaded
Open this post in threaded view
|

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
> [hidden email]
> http://www.haskell.org/mailman/listinfo/beginners