0

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

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"
4

1 回答 1

3

您的数据类型不必直接对应于语法规则。让 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
于 2013-04-10T12:42:31.403 回答