haskell - 如何重写语法来消除移位归约冲突(在 Haskell Happy 解析器中)

Question

我正在尝试使用Happy定义方法的语法(类似java) LALR 解析器生成器

  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:类型
• I:标识符
• E:表达式

所有其他 token 都是终端。

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

正如您所看到的，VD 可以从 I 开始，因为可以有类型类的变量声明，其中类型是标识符 (I)。语句也可以从 I 开始，因为变量的赋值和变量名是 I
问题是VD和S都可以从I开始。因此，在第一个产生式中会导致移位/归约冲突。

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

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

<小时/>

更新:

以下是语法文件

{
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 $2 (VarList $6) (BlockStatement $7) }

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

VarDecl :
    DataType id ';'
  { VarDecl $1 $2 }

Statement :
  id '=' Expression ';'
  { Assignment $1 $3 }

Expression :
  int
  { IntLiteral $1 }

  | Expression plus Expression
  { PlusExp $1 $3 }

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

list1(p) :
    p
  { [$1] }
  | p list1(p)
  { $1 : $2 }


list(p) :
    list1(p)
  { $1 }
  | -- 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))
}

Happy解析器生成的.info文件，其中包含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 )