Comment puis-je supprimer certains termes lors de l'analyse de cette BNF?

Question

Je tente d'analyser une expression booléenne en utilisant la bibliothèque Happy. Le problème est que le résultat n'est pas aussi bon que je le voudrais quand j'introduis des parenthèses. J'ai fait la grammaire suivante.

Query  : Expr    { $1 } 

Expr  : Expr "OR" Term   { ActOp Or $1 $3 } 
      | Expr "AND" Term   { ActOp And $1 $3 } 
      | Term      { Term $1 } 


Term  : '"' string '"'   { QuotedWord $2 } 
      | string     { Word $1 } 
      | '(' Expr ')'    { Brack $2} 

Voici la chaîne à analyser et le résultat.

"(computer AND science) OR cs" -> ActOp Or (Term (Brack (ActOp And (Term (Word "computer")) (Word "science")))) (Word "cs") 

Je préférerais que c'était quelque chose comme ce qui suit, car il serait plus facile à interpréter:

ActOp Or (ActOp And (Word "computer") (Word "science")) (Word "cs") 

Modifier - code complet

{ 
module BoolAst where 
import Data.Char 
import Data.List 
} 

%name translate 
%tokentype { Token } 

%token 
     string   { TokenString $$ } 
     '"'    { TokenQuote} 
     "AND"    { TokenAnd } 
     "OR"    { TokenOr } 
     '('    { TokenOb } 
     ')'    { TokenCb } 

%% 

Query  : Expr      { $1 } 

Expr  : Expr "OR" Term   { ActOp Or $1 $3 } 
      | Expr "AND" Term   { ActOp And $1 $3 } 
      | Term      { Term $1 } 


Term  : '"' string '"'   { QuotedWord $2 } 
      | string     { Word $1 } 
      | '(' Expr ')'    { Brack $2} 


{ 
happyError :: [Token] -> a 
happyError _ = error ("Parse error\n") 

type Query 
     = Expr 

data Expr 
     = ActOp Op Expr Term 
     | Term Term 
     deriving Show 

data Op 
     = Or 
     | And 
     deriving Show 

data Term 
     = QuotedWord String 
     | Word String 
     | Brack Expr 
     deriving Show 

data Token 
     = TokenQuote 
     | TokenAnd 
     | TokenOr 
     | TokenString String 
     | TokenOb 
     | TokenCb 
deriving Show 


lexer :: String -> [Token] 
lexer [] = [] 
lexer cs 
     | isPrefixOf "AND" cs = TokenAnd : (lexer $ drop 3 cs) 
     | isPrefixOf "OR" cs = TokenOr : (lexer $ drop 2 cs) 
lexer (c:cs) 
     | isSpace c = lexer cs 
     | isAlpha c = lexVar (c:cs) 
lexer ('"':cs) = TokenQuote : lexer cs 
lexer ('(':cs) = TokenOb : lexer cs 
lexer (')':cs) = TokenCb : lexer cs 

lexVar cs = 
    case span isAlphaNum cs of 
    (var,rest) -> TokenString var : lexer rest 

main = print $ translate . lexer $ "computer AND science OR cs" 

Answer 1

Vos types de données ne doivent correspondre directement aux règles de grammaire. Il est parfaitement possible que le terme non-terminal produise une valeur Expr. Par exemple

data Expr 
    = ActOp Op Expr Expr 
    | QuotedWord String 
    | Word String 
    deriving Show 

... 

Expr  : Expr "OR" Term   { ActOp Or $1 $3 } 
      | Expr "AND" Term   { ActOp And $1 $3 } 
      | Term      { $1 } -- no need to wrap in a constructor 

Term  : '"' string '"'   { QuotedWord $2 } 
      | string     { Word $1 } 
      | '(' Expr ')'    { $2 } -- no need to wrap in a constructor