如何重写语法以消除移位减少冲突（在Haskell Happy解析器中）

warunapww 发表于 Dev

Warunapww

我正在尝试使用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：类型
I：标识符
E：表情

所有其他令牌都是终端。

在该方法内，变量声明在语句的顶部和之后进行。

如您所见，VD可以从I开始，因为可以有类型为class的变量声明，其中类型是标识符（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文件，其中包含减少移位冲突和状态的详细信息

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

Warunapww

我找到了解决方案。而不是使用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)
  { $1 }
  | -- 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
  { ([$1], [])  }
  | q
  { ([], [$1])  }
  | p ordered_lists1(p,q)
  { ($1:fst($2), snd($2))  }
  | q list1(q)
  { ([], $1 : $2) }