如何解析这个BNF时删除一些术语？

Question

我正在尝试使用快乐库分析布尔表达式。问题是，当我引入括号时，结果不如我想要的那么好。我做了以下语法。

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} 

下面是要解析的字符串和结果。

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

我宁愿如果它是类似于下面的，因为它会更容易解释：

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

编辑 - 全码

{ 
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

你的数据类型不必须直接对应于语法规则。 Term非终结符产生一个Expr值是完全有效的。例如

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