運算符在解析器中的優先級和關聯性（Haskell）

我想要擴展一個遞歸下降解析器來處理新的運算符並使它們正確關聯。最初只有四個運營商（+ -/*），它們都具有相同的優先級。我在看的功能是parseExpRec功能：運算符在解析器中的優先級和關聯性（Haskell）

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加（BinOpApp功率（LitInt 3）（LitInt 4））（LitInt 2））（LitInt 3）

即相當於這中間符號（用方括號包含）：

（（3^4）+2）^ 3

將如何解決這個問題？

來源

2010-02-24 benwad

Haskell中有很多很棒的解析器組合器。是否可以選擇使用其中一種，而不是在遞歸函數中實現解析（這在一般情況下非常困難）？ – Martijn 2010-02-24 19:14:18

我想你應該看看現有的解析器組合庫。例如，parsec，以查看它們如何實現優先級。特別是，operator table

來源

2010-02-24 21:10:57

我寫了paper on unparsing expressions using operator precedence。本白皮書的附錄中有一個用ML編寫的運算符優先級解析器，您可以輕鬆地適應Haskell。代碼可以從上面的頁面下載。儘管Haskell有很多很好的解析組合器的庫，但我從來沒有見過一個既簡單又易於理解的（a），並且（b）支持具有任意優先級的運算符優先級解析。

來源

2010-02-25 03:49:15

運算符在解析器中的優先級和關聯性（Haskell）

回答

相關問題