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 :) |
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 |
Free forum by Nabble | Edit this page |