Comment implémenter des opérateurs d'indice dans Parsec?

Question

J'écris un analyseur dans Parsec. Les productions récursives à gauche telles que E -> E + E ne peuvent pas être écrites facilement dans un analyseur LL. Parsec fournit donc buildExpressionParser, qui prend en charge les opérateurs infixe, postfixe et préfixe. Mais qu'en est-il des opérateurs d'indice?

Comment E -> E [E] serait-il implémenté? Si je pouvais consommer le crochet de fermeture sans consommer la seconde expression, alors je pourrais l'émuler avec une entrée de table Infix pour buildExpressionParser. Pensées? Editer: Je sais qu'il existe un algorithme pour l'élimination de la récursivité gauche qui fonctionnera probablement pour ma grammaire. Je cherche quelque chose de facile, ou bien abstrait (comme buildExpressionParser). Sinon, je vais juste utiliser Happy.

Answer 1

Dans notre projet, nous avons éliminé manuellement la récursion gauche des expressions. Cela fonctionne de la manière suivante:

Nous avons créé une forme générique d'expressions, qui est paramétrés par l'analyseur terme:

expressionGen :: MParser (Expr LocInfo) -> MParser (Expr LocInfo) 
expressionGen term = buildExpressionParser precedenceTable term <?> "expression" 
    where precedenceTable = -- unary, binary expressions 

Nous avons un analyseur normal terme, et un analyseur à long terme sans règles récursives. Avec cela, nous pouvons analyser (multiples) opérateurs en indice:

term :: MParser (Expr LocInfo) 
term = do indBase <- termNoArray 
      indexes <- many $ (brackets expression >>= return) 
      return -- semantics 
     <?> "term" 

termNoArray :: MParser (Expr LocInfo) 
termNoArray = -- normal terms 

Enfin, nous avons un analyseur pour les expressions le plus élevé: expression = expressionGen term