이 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