如何重写语法以消除 shift-reduce 冲突（在 Haskell Happy parser 中）

Question

我正在尝试使用 Happy LALR 解析器生成器

为方法（java 等）定义语法

  1.  MD ::= some_prefix { list(VD) list(S) }
  2.  VD ::= T I
  3.  S ::= I = E | I [ E ] = E | etc...
  4.  T ::= I | byte | int | etc...
  5.  E ::= INT | E + E | etc...

这里，

MD：方法声明
VD：变量声明
S：声明
T：类型
我：标识符
E: 表达式

所有其他令牌都是终端。

在该方法中，变量声明在顶部和之后的语句中完成。

如您所见，VD 可以从 I 开始，因为可以有类型为标识符 (I) 的 class 变量声明。语句也可以从 I 开始，因为对变量的赋值和变量名称是 I
问题是 VD 和 S 都可以从 I 开始。因此，在第一个生产中它会导致 shift/reduce 冲突。

有没有办法重写语法或任何其他解析器生成器技巧来解决这个问题？

我已经指定了运算符的结合性和优先级。我只提到了解释问题的最少信息集。如果您需要更多信息，请与我们联系。

更新：

语法文件如下

{
module Issue where
import Lexer
}

%name parser
%tokentype { Token }
%error { parseError }

%token
--===========================================================================
  ';'         { TokenSemi }
  id          { TokenId $$ }
  '{'         { TokenLBrace }
  '}'         { TokenRBrace }
  public      { TokenPublickw }
  '('         { TokenLParen }
  ')'         { TokenRParen }
  int         { TokenInt $$ }
  plus        { TokenPlus }
  inttype     { TokenIntkw }
  '='         { TokenAssign }
--===========================================================================

--===========================================================================
-- Precedence and associativity. Reference:
-- http://introcs.cs.princeton.edu/java/11precedence/
%right '='
%left plus
--===========================================================================

%%

MethodDecl :
  public id '(' ')' '{' list(VarDecl) list(Statement) '}'
  { MethodDecl  (VarList ) (BlockStatement ) }

DataType :
  inttype
  { DataType TypeInt }
  | id
  { DataType (TypeClass ) }

VarDecl :
    DataType id ';'
  { VarDecl   }

Statement :
  id '=' Expression ';'
  { Assignment   }

Expression :
  int
  { IntLiteral  }

  | Expression plus Expression
  { PlusExp   }

--============================================================================

list1(p) :
    p
  { [] }
  | p list1(p)
  {  :  }


list(p) :
    list1(p)
  {  }
  | -- epsilon
  { [] }
--============================================================================

{
data AST =  Goal AST [AST]
          | BlockStatement [AST]
          | IntLiteral Int
          | PlusExp AST AST
          | MethodDecl String AST AST
          | DataType MJType
          | Identifier String
          | VarList [AST]
          | VarDecl AST String
          | Assignment String AST
          deriving Show

data MJType = TypeInt
      | TypeUnknown
      | TypeClass String
      deriving (Show,Eq)




parseError :: [Token] -> a
parseError (t:ts) = error ("Parser Error: " ++ (show t))
}

.info 文件由 Happy 解析器生成，包含 shift-reduce 冲突和状态的详细信息

-----------------------------------------------------------------------------
Info file generated by Happy Version 1.19.4 from issue.y
-----------------------------------------------------------------------------

state 7 contains 1 shift/reduce conflicts.
state 9 contains 1 shift/reduce conflicts.

-----------------------------------------------------------------------------
Grammar
-----------------------------------------------------------------------------
    %start_parser -> MethodDecl                        (0)
    MethodDecl -> public id '(' ')' '{' list(VarDecl) list(Statement) '}'   (1)
    DataType -> inttype                                (2)
    DataType -> id                                     (3)
    VarDecl -> DataType id ';'                         (4)
    Statement -> id '=' Expression ';'                 (5)
    Expression -> int                                  (6)
    Expression -> Expression plus Expression           (7)
    list(Statement) -> list1(Statement)                (8)
    list(Statement) ->                                 (9)
    list(VarDecl) -> list1(VarDecl)                    (10)
    list(VarDecl) ->                                   (11)
    list1(Statement) -> Statement                      (12)
    list1(Statement) -> Statement list1(Statement)     (13)
    list1(VarDecl) -> VarDecl                          (14)
    list1(VarDecl) -> VarDecl list1(VarDecl)           (15)

-----------------------------------------------------------------------------
Terminals
-----------------------------------------------------------------------------
    ';'            { TokenSemi }
    id             { TokenId $$ }
    '{'            { TokenLBrace }
    '}'            { TokenRBrace }
    public         { TokenPublickw }
    '('            { TokenLParen }
    ')'            { TokenRParen }
    int            { TokenInt $$ }
    plus           { TokenPlus }
    inttype        { TokenIntkw }
    '='            { TokenAssign }

-----------------------------------------------------------------------------
Non-terminals
-----------------------------------------------------------------------------
    %start_parser   rule  0
    MethodDecl      rule  1
    DataType        rules 2, 3
    VarDecl         rule  4
    Statement       rule  5
    Expression      rules 6, 7
    list(Statement) rules 8, 9
    list(VarDecl)   rules 10, 11
    list1(Statement) rules 12, 13
    list1(VarDecl)  rules 14, 15

-----------------------------------------------------------------------------
States
-----------------------------------------------------------------------------
State 0


    public         shift, and enter state 2

    MethodDecl     goto state 3

State 1


    public         shift, and enter state 2


State 2

    MethodDecl -> public . id '(' ')' '{' list(VarDecl) list(Statement) '}'    (rule 1)

    id             shift, and enter state 4


State 3

    %start_parser -> MethodDecl .                       (rule 0)

    %eof           accept


State 4

    MethodDecl -> public id . '(' ')' '{' list(VarDecl) list(Statement) '}'    (rule 1)

    '('            shift, and enter state 5


State 5

    MethodDecl -> public id '(' . ')' '{' list(VarDecl) list(Statement) '}'    (rule 1)

    ')'            shift, and enter state 6


State 6

    MethodDecl -> public id '(' ')' . '{' list(VarDecl) list(Statement) '}'    (rule 1)

    '{'            shift, and enter state 7


State 7

    MethodDecl -> public id '(' ')' '{' . list(VarDecl) list(Statement) '}'    (rule 1)

    id             shift, and enter state 12
            (reduce using rule 11)

    '}'            reduce using rule 11
    inttype        shift, and enter state 13

    DataType       goto state 8
    VarDecl        goto state 9
    list(VarDecl)  goto state 10
    list1(VarDecl) goto state 11

State 8

    VarDecl -> DataType . id ';'                        (rule 4)

    id             shift, and enter state 19


State 9

    list1(VarDecl) -> VarDecl .                         (rule 14)
    list1(VarDecl) -> VarDecl . list1(VarDecl)          (rule 15)

    id             shift, and enter state 12
            (reduce using rule 14)

    '}'            reduce using rule 14
    inttype        shift, and enter state 13

    DataType       goto state 8
    VarDecl        goto state 9
    list1(VarDecl) goto state 18

State 10

    MethodDecl -> public id '(' ')' '{' list(VarDecl) . list(Statement) '}'    (rule 1)

    id             shift, and enter state 17
    '}'            reduce using rule 9

    Statement      goto state 14
    list(Statement)goto state 15
    list1(Statement)goto state 16

State 11

    list(VarDecl) -> list1(VarDecl) .                   (rule 10)

    id             reduce using rule 10
    '}'            reduce using rule 10


State 12

    DataType -> id .                                    (rule 3)

    id             reduce using rule 3


State 13

    DataType -> inttype .                               (rule 2)

    id             reduce using rule 2


State 14

    list1(Statement) -> Statement .                     (rule 12)
    list1(Statement) -> Statement . list1(Statement)    (rule 13)

    id             shift, and enter state 17
    '}'            reduce using rule 12

    Statement      goto state 14
    list1(Statement)goto state 23

State 15

    MethodDecl -> public id '(' ')' '{' list(VarDecl) list(Statement) . '}'    (rule 1)

    '}'            shift, and enter state 22


State 16

    list(Statement) -> list1(Statement) .               (rule 8)

    '}'            reduce using rule 8


State 17

    Statement -> id . '=' Expression ';'                (rule 5)

    '='            shift, and enter state 21


State 18

    list1(VarDecl) -> VarDecl list1(VarDecl) .          (rule 15)

    id             reduce using rule 15
    '}'            reduce using rule 15


State 19

    VarDecl -> DataType id . ';'                        (rule 4)

    ';'            shift, and enter state 20


State 20

    VarDecl -> DataType id ';' .                        (rule 4)

    id             reduce using rule 4
    '}'            reduce using rule 4
    inttype        reduce using rule 4


State 21

    Statement -> id '=' . Expression ';'                (rule 5)

    int            shift, and enter state 25

    Expression     goto state 24

State 22

    MethodDecl -> public id '(' ')' '{' list(VarDecl) list(Statement) '}' .    (rule 1)

    %eof           reduce using rule 1


State 23

    list1(Statement) -> Statement list1(Statement) .    (rule 13)

    '}'            reduce using rule 13


State 24

    Statement -> id '=' Expression . ';'                (rule 5)
    Expression -> Expression . plus Expression          (rule 7)

    ';'            shift, and enter state 26
    plus           shift, and enter state 27


State 25

    Expression -> int .                                 (rule 6)

    ';'            reduce using rule 6
    plus           reduce using rule 6


State 26

    Statement -> id '=' Expression ';' .                (rule 5)

    id             reduce using rule 5
    '}'            reduce using rule 5


State 27

    Expression -> Expression plus . Expression          (rule 7)

    int            shift, and enter state 25

    Expression     goto state 28

State 28

    Expression -> Expression . plus Expression          (rule 7)
    Expression -> Expression plus Expression .          (rule 7)

    ';'            reduce using rule 7
    plus           reduce using rule 7


-----------------------------------------------------------------------------
Grammar Totals
-----------------------------------------------------------------------------
Number of rules: 16
Number of terminals: 11
Number of non-terminals: 10
Number of states: 29

Answer 1

乍一看，shift-reduce冲突可能是5中的表达式文法

查看快乐手册中的语法2.3 Using Precedences。您也可以使用经典方法：

E => E + T | T
T => T * F | F
F => INT | ( E )

Answer 2

我找到了解决办法。而不是使用 2 个不同的列表

list(VarDecl) list(Statement)

使用一个列表

ordered_lists(VarDecl,Statements)

下面是ordered_lists.

的定义

--A list of p followed by a list of q, where each list can be an empty list
ordered_lists(p,q) :
    ordered_lists1(p,q)
  {  }
  | -- epsilon
  { ([], []) }

--This list should contain atleast one of p or q. A list of p followed by a
--list of q, where at most one list can be an empty list
ordered_lists1(p,q) :
    p
  { ([], [])  }
  | q
  { ([], [])  }
  | p ordered_lists1(p,q)
  { (:fst(), snd())  }
  | q list1(q)
  { ([],  : ) }

问题描述中提供了 list1 的定义。请不要犹豫post一个更好的答案。

如何重写语法以消除 shift-reduce 冲突（在 Haskell Happy parser 中）

How rewrite grammar to eliminate shift-reduce conflict (in Haskell Happy parser)

haskell

parser-generator

shift-reduce-conflict

happy