4

Exploring parsing libraries in Haskell I came across this project: haskell-parser-examples. Running some examples I found a problem with the operator precedence. It works fine when using Parsec:

$ echo "3*2+1" | dist/build/lambda-parsec/lambda-parsec
Op Add (Op Mul (Num 3) (Num 2)) (Num 1)
Num 7

But not with Happy/Alex:

$ echo "3*2+1" | dist/build/lambda-happy-alex/lambda-happy-alex
Op Mul (Num 3) (Op Add (Num 2) (Num 1))
Num 9

Even though the operator precedence seems well-defined. Excerpt from the parser:

%left '+' '-'
%left '*' '/'

%%

Exprs : Expr                             { $1 }
      | Exprs Expr                       { App $1 $2 }

Expr : Exprs                             { $1 }
     | let var '=' Expr in Expr end      { App (Abs $2 $6) $4 }
     | '\\' var '->' Expr                { Abs $2 $4 }
     | Expr op Expr                      { Op (opEnc $2) $1 $3 }
     | '(' Expr ')'                      { $2 }
     | int                               { Num $1 }

Any hint? (I opened a bug report some time ago, but no response).

[Using gch 7.6.3, alex 3.1.3, happy 1.19.4]

4

1 回答 1

2

This appears to be a bug in haskell-parser-examples' usage of token precedence. Happy's operator precedence only affects the rules that use the tokens directly. In the parser we want to apply precedence to the Expr rule, but the only applicable rule,

| Expr op Expr { Op (opEnc $2) $1 $3 }

doesn't use tokens itself, instead relying on opEnc to expand them. If opEnc is inlined into Expr,

| Expr '*' Expr { Op Mul $1 $3 }
| Expr '+' Expr { Op Add $1 $3 }
| Expr '-' Expr { Op Sub $1 $3 }

it should work properly.

于 2014-08-20T00:43:53.703 回答