Usando Parsec para analizar expresiones regulares

Question

Estoy tratando de aprender Parsec implementando un pequeño analizador de expresiones regulares. En BNF, mi gramática se ve algo como:

EXP : EXP * 
    | LIT EXP 
    | LIT 

He tratado de implementar esto en Haskell como:

expr = try star 
     <|> try litE 
     <|> lit 

litE = do c <- noneOf "*" 
      rest <- expr 
      return (c : rest) 

lit = do c <- noneOf "*" 
      return [c] 

star = do content <- expr 
      char '*' 
      return (content ++ "*") 

Hay algunos bucles infinitos aquí, sin embargo (por ejemplo expr -> estrella -> expr sin consumir ningún token) que hace que el analizador bucle por siempre. Aunque no estoy seguro de cómo solucionarlo, porque la naturaleza misma de star es que consume su token obligatorio al final.

¿Alguna idea?

Answer 1

Debe usar Parsec.Expr.buildExprParser; es ideal para este propósito. Simplemente describa sus operadores, su precedencia y asociatividad, y cómo analizar un átomo, ¡y el combinador crea el analizador para usted!

Probablemente también desee agregar la capacidad de agrupar términos con parens para que pueda aplicar * a más de un solo literal.

Aquí está mi intento (me tiró en |, + y ? por si acaso):

import Control.Applicative 
import Control.Monad 
import Text.ParserCombinators.Parsec 
import Text.ParserCombinators.Parsec.Expr 

data Term = Literal Char 
      | Sequence [Term] 
      | Repeat (Int, Maybe Int) Term 
      | Choice [Term] 
    deriving (Show) 

term :: Parser Term 
term = buildExpressionParser ops atom where 

    ops = [ [ Postfix (Repeat (0, Nothing) <$ char '*') 
      , Postfix (Repeat (1, Nothing) <$ char '+') 
      , Postfix (Repeat (0, Just 1) <$ char '?') 
      ] 
     , [ Infix (return sequence) AssocRight 
      ] 
     , [ Infix (choice <$ char '|') AssocRight 
      ] 
     ] 

    atom = msum [ Literal <$> lit 
       , parens term 
       ] 

    lit = noneOf "*+?|()" 
    sequence a b = Sequence $ (seqTerms a) ++ (seqTerms b) 
    choice a b = Choice $ (choiceTerms a) ++ (choiceTerms b) 
    parens = between (char '(') (char ')') 

    seqTerms (Sequence ts) = ts 
    seqTerms t = [t] 

    choiceTerms (Choice ts) = ts 
    choiceTerms t = [t] 

main = parseTest term "he(llo)*|wor+ld?" 

Answer 2

Su gramática es recursiva a la izquierda, lo cual no funciona bien con try, ya que Parsec retrocederá varias veces. Hay algunas formas de evitar esto. Probablemente el más simple es sólo hacer la * opcional en otra regla:

lit :: Parser (Char, Maybe Char) 
lit = do 
    c <- noneOf "*" 
    s <- optionMaybe $ char '*' 
    return (c, s) 

Por supuesto, es probable que terminan envolviendo las cosas en un tipo de datos de todos modos, y hay muchas maneras de ir sobre él. Aquí hay uno, de la parte superior de mi cabeza:

import Control.Applicative ((<$>)) 

data Term = Literal Char 
      | Sequence [Term] 
      | Star Term 

expr :: Parser Term 
expr = Sequence <$> many term 

term :: Parser Term 
term = do 
    c <- lit 
    s <- optionMaybe $ char '*' -- Easily extended for +, ?, etc. 
    return $ if isNothing s 
    then Literal c 
    else Star $ Literal c 

Tal vez un Haskeller más experiencia vendrá junto con una mejor solución.