解析器中的运算符优先级和关联性（Haskell） [英] Operator precedence and associativity in a parser (Haskell)

问题描述

我试图扩展一个递归下降解析器来处理新的操作符并使它们正确关联。最初只有四个运营商（+ - / *），它们都具有相同的优先级。我在看的函数是parseExpRec函数：

  parseExpRec :: Exp  - > [令牌]  - > （Exp，[Token]）
 parseExpRec e [] =（e，[]）
 parseExpRec e1（op：ts）= 
 let（e2，ts'）= parsePrimExp ts in 
 case 
 T_Power  - > parseExpRec（BinOpApp Power e1 e2）ts'
 T_Plus  - > parseExpRec（BinOpApp Plus e1 e2）ts'
 T_Minus  - > parseExpRec（BinOpApp Minus e1 e2）ts'
 T_Times  - > parseExpRec（BinOpApp Times e1 e2）ts'
 T_Divide  - > parseExpRec（BinOpApp Divide e1 e2）ts'
 T_GreaterThan  - > parseExpRec（BinOpApp GreaterThan e1 e2）ts'
 T_LessThan  - > parseExpRec（BinOpApp LessThan e1 e2）ts'
 T_GreaterOrEqual  - > parseExpRec（BinOpApp GreaterOrEqual e1 e2）ts'
 T_LessOrEqual  - > parseExpRec（BinOpApp LessOrEqual e1 e2）ts'
 T_EqualTo  - > parseExpRec（BinOpApp EqualTo e1 e2）ts'
 _  - > （e1，op：ts）
  

除T_Plus，T_Minus，T_Times和T_Divide外的所有模式匹配行已经被我添加了（因此有相关的令牌和对Exp数据类型的扩展）。但是，他们中没有一个似乎正确联系。例如，字符串3 ^ 4 + 2 ^ 3的计算结果为：

BinOpApp功率（BinOpApp Plus（BinOpApp功率（LitInt 3 ）（LitInt 4））（LitInt 2））（LitInt 3）

相当于这个中缀表示法（包含括号）：

lockquote
（（3 ^ 4）+2）^ 3

我会如何解决这个问题？ 我已经写了关于使用运算符优先级解析表达式的文章。本白皮书的附录中有一个用ML编写的运算符优先级解析器，您可以轻松地适应Haskell。代码可以从上面的页面下载。

虽然Haskell有许多很好的解析组合器的库，但我从来没有见过这样的解决方案：（a）足够简单我很容易理解，并且（b）支持优先级为任意优先级的运算符优先级解析。

I am trying to extend a recursive-descent parser to handle new operators and make them associate correctly. Originally there were only four operators (+ - / *) and they all had the same precedence. The function I am looking at is the parseExpRec function:

parseExpRec               :: Exp -> [Token] -> (Exp, [Token])    
parseExpRec e  []         =  (e, [])
parseExpRec e1 (op : ts)  = 
 let (e2, ts') = parsePrimExp ts in
   case op of
    T_Power     -> parseExpRec (BinOpApp Power  e1 e2) ts'
    T_Plus      -> parseExpRec (BinOpApp Plus   e1 e2) ts'
    T_Minus     -> parseExpRec (BinOpApp Minus  e1 e2) ts'
    T_Times     -> parseExpRec (BinOpApp Times  e1 e2) ts'
    T_Divide    -> parseExpRec (BinOpApp Divide e1 e2) ts'
    T_GreaterThan   -> parseExpRec (BinOpApp GreaterThan    e1 e2) ts'
    T_LessThan      -> parseExpRec (BinOpApp LessThan       e1 e2) ts'
    T_GreaterOrEqual -> parseExpRec (BinOpApp GreaterOrEqual e1 e2) ts'
    T_LessOrEqual   -> parseExpRec (BinOpApp LessOrEqual    e1 e2) ts'
    T_EqualTo       -> parseExpRec (BinOpApp EqualTo        e1 e2) ts'
    _           -> (e1, op : ts)

All of the pattern matching lines except T_Plus, T_Minus, T_Times and T_Divide have been added by me (and so have the associated tokens and extensions to the Exp datatype). However, none of them seem to associate correctly. For example, the string "3^4 + 2^3" evaluates to:

BinOpApp Power (BinOpApp Plus (BinOpApp Power (LitInt 3) (LitInt 4)) (LitInt 2)) (LitInt 3)

Which is equivalent to this in infix notation (with brackets included):

((3^4)+2)^3

How would I fix this?

解决方案

I've written a paper on unparsing expressions using operator precedence. The appendix to the paper has an operator-precedence parser written in ML, which you could easily adapt to Haskell. The code is downloadable from the page above.

While Haskell has many fine libraries of parsing combinators, I have never seen one that was both (a) simple enough for me to understand easily and (b) supported operator-precedence parsing with arbitrary levels of precedence.

这篇关于解析器中的运算符优先级和关联性（Haskell）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！