我正在尝试扩展递归下降解析器来处理新运算符并使它们正确关联。最初只有四个运算符(+ - / *),并且它们都具有相同的优先级。我正在查看的函数是 parseExpRec 函数:
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)
除了 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)
这相当于中缀表示法(包含括号):
((3^4)+2)^3
我该如何解决这个问题?
我写了一个纸上解解析使用运算符优先级的表达式 http://www.cs.tufts.edu/~nr/pubs/unparse-abstract.html。本文的附录有一个用 ML 编写的运算符优先级解析器,您可以轻松地适应 Haskell。该代码可从上面的页面下载。
虽然 Haskell 有许多优秀的解析组合器库,但我从未见过一个既 (a) 简单到我可以轻松理解,又 (b) 支持具有任意优先级级别的运算符优先级解析的库。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)