移位/減少在命題邏輯分析器衝突快樂

Question

我做的開心基於命題邏輯語法this BNF definition一個簡單的命題邏輯分析器，這是我的代碼

{ 
module FNC where 
import Data.Char 
import System.IO 
} 

-- Parser name, token types and error function name: 
-- 
%name parse Prop 
%tokentype { Token } 
%error { parseError } 

-- Token list: 
%token 
    var { TokenVar $$ } -- alphabetic identifier 
    or { TokenOr } 
    and { TokenAnd } 
    '¬' { TokenNot } 
    "=>" { TokenImp } -- Implication 
    "<=>" { TokenDImp } --double implication 
    '(' { TokenOB } --open bracket 
    ')' { TokenCB } --closing bracket 
    '.' {TokenEnd} 

%left "<=>" 
%left "=>" 
%left or 
%left and 
%left '¬' 
%left '(' ')' 
%% 

--Grammar 
Prop :: {Sentence} 
Prop : Sentence '.' {$1} 

Sentence :: {Sentence} 
Sentence : AtomSent {Atom $1} 
    | CompSent {Comp $1} 

AtomSent :: {AtomSent} 
AtomSent : var { Variable $1 } 

CompSent :: {CompSent} 
CompSent : '(' Sentence ')' { Bracket $2 } 
    | Sentence Connective Sentence {Bin $2 $1 $3} 
    | '¬' Sentence {Not $2} 

Connective :: {Connective} 
Connective : and {And} 
    | or {Or} 
    | "=>" {Imp} 
    | "<=>" {DImp} 


{ 
--Error function 
parseError :: [Token] -> a 
parseError _ = error ("parseError: Syntax analysis error.\n") 

--Data types to represent the grammar 
data Sentence 
    = Atom AtomSent 
    | Comp CompSent 
    deriving Show 

data AtomSent = Variable String deriving Show 

data CompSent 
     = Bin Connective Sentence Sentence 
     | Not Sentence 
     | Bracket Sentence 
     deriving Show 

data Connective 
    = And 
    | Or 
    | Imp 
    | DImp 
    deriving Show 

--Data types for the tokens 
data Token 
     = TokenVar String 
     | TokenOr 
     | TokenAnd 
     | TokenNot 
     | TokenImp 
     | TokenDImp 
     | TokenOB 
     | TokenCB 
     | TokenEnd 
     deriving Show 

--Lexer 
lexer :: String -> [Token] 
lexer [] = [] -- cadena vacia 
lexer (c:cs) -- cadena es un caracter, c, seguido de caracteres, cs. 
     | isSpace c = lexer cs 
     | isAlpha c = lexVar (c:cs) 
     | isSymbol c = lexSym (c:cs) 
     | c== '(' = TokenOB : lexer cs 
     | c== ')' = TokenCB : lexer cs 
     | c== '¬' = TokenNot : lexer cs --solved 
     | c== '.' = [TokenEnd] 
     | otherwise = error "lexer: Token invalido" 

lexVar cs = 
    case span isAlpha cs of 
     ("or",rest) -> TokenOr : lexer rest 
     ("and",rest) -> TokenAnd : lexer rest 
     (var,rest) -> TokenVar var : lexer rest 

lexSym cs = 
    case span isSymbol cs of 
     ("=>",rest) -> TokenImp : lexer rest 
     ("<=>",rest) -> TokenDImp : lexer rest 
} 

現在，我有兩個這裏

1. 出於某種原因，我的問題得到4移位/減少衝突，我真的不知道，因爲我以爲會優先解決他們，他們可能是（我想我正確執行了BNF語法）.. 。
2. （這是一個Haskell問題）在我的詞法分析器函數中，出於某種原因，我得到了解釋錯誤的地方，我說如何處理'¬'，如果我刪除該行它是行得通的，爲什麼會這樣呢？ （這個問題已解決）

任何幫助將是偉大的。

Answer 1

我可以回答第2號：

| c== '¬' == TokenNot : lexer cs --problem here 
--  ^^ 

你有一個==有，你應該有一個=。

Answer 2

如果您使用-i開心，它會生成一個信息文件。該文件列出瞭解析器所具有的所有狀態。它還會列出每個州的所有可能的轉換。您可以使用這些信息來確定轉換/減少衝突是否是您關心的問題。

有關調用快樂和衝突的信息：

• http://www.haskell.org/happy/doc/html/sec-invoking.html
• http://www.haskell.org/happy/doc/html/sec-conflict-tips.html

下面是一些-i輸出。我已經刪除了除17之外的所有內容。您需要獲取此文件的副本，以便您可以正確調試問題。你在這裏看到的只是幫助談論它：

----------------------------------------------------------------------------- 
Info file generated by Happy Version 1.18.10 from FNC.y 
----------------------------------------------------------------------------- 

state 17 contains 4 shift/reduce conflicts. 

----------------------------------------------------------------------------- 
Grammar 
----------------------------------------------------------------------------- 
    %start_parse -> Prop        (0) 
    Prop -> Sentence '.'        (1) 
    Sentence -> AtomSent        (2) 
    Sentence -> CompSent        (3) 
    AtomSent -> var         (4) 
    CompSent -> '(' Sentence ')'      (5) 
    CompSent -> Sentence Connective Sentence   (6) 
    CompSent -> '¬' Sentence       (7) 
    Connective -> and         (8) 
    Connective -> or         (9) 
    Connective -> "=>"         (10) 
    Connective -> "<=>"        (11) 

----------------------------------------------------------------------------- 
Terminals 
----------------------------------------------------------------------------- 
    var   { TokenVar $$ } 
    or    { TokenOr } 
    and   { TokenAnd } 
    '¬'   { TokenNot } 
    "=>"   { TokenImp } 
    "<=>"   { TokenDImp } 
    '('   { TokenOB } 
    ')'   { TokenCB } 
    '.'   { TokenEnd } 

----------------------------------------------------------------------------- 
Non-terminals 
----------------------------------------------------------------------------- 
    %start_parse rule 0 
    Prop   rule 1 
    Sentence  rules 2, 3 
    AtomSent  rule 4 
    CompSent  rules 5, 6, 7 
    Connective  rules 8, 9, 10, 11 

----------------------------------------------------------------------------- 
States 
----------------------------------------------------------------------------- 
State 17 

    CompSent -> Sentence . Connective Sentence   (rule 6) 
    CompSent -> Sentence Connective Sentence .   (rule 6) 

    or    shift, and enter state 12 
      (reduce using rule 6) 

    and   shift, and enter state 13 
      (reduce using rule 6) 

    "=>"   shift, and enter state 14 
      (reduce using rule 6) 

    "<=>"   shift, and enter state 15 
      (reduce using rule 6) 

    ')'   reduce using rule 6 
    '.'   reduce using rule 6 

    Connective  goto state 11 

----------------------------------------------------------------------------- 
Grammar Totals 
----------------------------------------------------------------------------- 
Number of rules: 12 
Number of terminals: 9 
Number of non-terminals: 6 
Number of states: 19 

這基本上輸出說，它運行到有點含糊，當它在看連接詞。事實證明，您鏈接的幻燈片提到了這個（幻燈片11），「歧義通過優先¬∧∨⇒⇔⇔或圓括號解決」。

在這一點上，我會建議看看shift/reduce衝突和你想要的優先級，看看你的解析器是否會做正確的事情。如果是這樣，那麼你可以放心地忽略這些警告。如果沒有，你會爲自己做更多的工作。