Prioridad y asociatividad del operador en un analizador (Haskell)

Question

Estoy tratando de extender un analizador sintáctico descendente recursivo para manejar nuevos operadores y asociarlos correctamente. Originalmente solo había cuatro operadores (+ -/*) y todos tenían la misma precedencia. La función que estoy mirando es la función 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) 

Todo el patrón de las líneas excepto T_Plus, T_Minus, T_Times y T_Divide juego se han añadido por mí (y así tener la tokens y extensiones asociadas al tipo de datos Exp) Sin embargo, ninguno de ellos parece asociarse correctamente. Por ejemplo, la cadena "3^4 + 2^3" se evalúa como:

BinOpApp alimentación (BinOpApp Plus (BinOpApp alimentación (LitInt 3) (LitInt 4)) (LitInt 2)) (LitInt 3)

que es equivalente a esto en notación infija (con soportes incluidos):

((3^4) +2)^3

¿Cómo puedo solucionar este problema?

Answer 1

Creo que debería mirar una biblioteca de combinador de analizador existente. Por ejemplo, parsec, para ver cómo implementan la precedencia. En particular, el operator table

Answer 2

He escrito un paper on unparsing expressions using operator precedence. El apéndice del documento tiene un analizador de precedencia del operador escrito en ML, que puede adaptar fácilmente a Haskell. El código se puede descargar de la página anterior.

Mientras que Haskell tiene muchas bibliotecas finas de análisis combinadores, nunca he visto uno que era a la vez (a)   lo suficientemente simple para mí entender fácilmente y (b)   apoyado por precedencia de operadores de análisis con niveles arbitrarios de precedencia.