Ply shift / reduce冲突：悬空的其他和空产品

问题描述 投票：0回答：1

我有很多冲突，其中大多数是由于运算符和关系运算符具有不同的优先级而引起的。但是我仍然面临一些我不知道如何解决它们的冲突。其中一些在下面。我怀疑也许我应该为stmtlist做ε消除，但是说实话我不确定。

状态70：

state 70

    (27) block -> LCB varlist . stmtlist RCB
    (25) varlist -> varlist . vardec
    (28) stmtlist -> . stmt
    (29) stmtlist -> . stmtlist stmt
    (30) stmtlist -> .
    (15) vardec -> . type idlist SEMICOLON
    (33) stmt -> . RETURN exp SEMICOLON
    (34) stmt -> . exp SEMICOLON
    (35) stmt -> . WHILE LRB exp RRB stmt
    (36) stmt -> . FOR LRB exp SEMICOLON exp SEMICOLON exp RRB stmt
    (37) stmt -> . IF LRB exp RRB stmt elseiflist
    (38) stmt -> . IF LRB exp RRB stmt elseiflist ELSE stmt
    (39) stmt -> . PRINT LRB ID RRB SEMICOLON
    (40) stmt -> . block
    (7) type -> . INTEGER
    (8) type -> . FLOAT
    (9) type -> . BOOLEAN
    (44) exp -> . lvalue ASSIGN exp
    (45) exp -> . exp SUM exp
    (46) exp -> . exp MUL exp
    (47) exp -> . exp SUB exp
    (48) exp -> . exp DIV exp
    (49) exp -> . exp MOD exp
    (50) exp -> . exp AND exp
    (51) exp -> . exp OR exp
    (52) exp -> . exp LT exp
    (53) exp -> . exp LE exp
    (54) exp -> . exp GT exp
    (55) exp -> . exp GE exp
    (56) exp -> . exp NE exp
    (57) exp -> . exp EQ exp
    (58) exp -> . const
    (59) exp -> . lvalue
    (60) exp -> . ID LRB explist RRB
    (61) exp -> . LRB exp RRB
    (62) exp -> . ID LRB RRB
    (63) exp -> . SUB exp
    (64) exp -> . NOT exp
    (27) block -> . LCB varlist stmtlist RCB
    (31) lvalue -> . ID
    (32) lvalue -> . ID LSB exp RSB
    (72) const -> . INTEGERNUMBER
    (73) const -> . FLOATNUMBER
    (74) const -> . TRUE
    (75) const -> . FALSE

  ! shift/reduce conflict for RETURN resolved as shift
  ! shift/reduce conflict for WHILE resolved as shift
  ! shift/reduce conflict for FOR resolved as shift
  ! shift/reduce conflict for IF resolved as shift
  ! shift/reduce conflict for PRINT resolved as shift
  ! shift/reduce conflict for ID resolved as shift
  ! shift/reduce conflict for LRB resolved as shift
  ! shift/reduce conflict for SUB resolved as shift
  ! shift/reduce conflict for NOT resolved as shift
  ! shift/reduce conflict for LCB resolved as shift
  ! shift/reduce conflict for INTEGERNUMBER resolved as shift
  ! shift/reduce conflict for FLOATNUMBER resolved as shift
  ! shift/reduce conflict for TRUE resolved as shift
  ! shift/reduce conflict for FALSE resolved as shift
    RCB             reduce using rule 30 (stmtlist -> .)
    RETURN          shift and go to state 99
    WHILE           shift and go to state 101
    FOR             shift and go to state 102
    IF              shift and go to state 103
    PRINT           shift and go to state 104
    INTEGER         shift and go to state 8
    FLOAT           shift and go to state 9
    BOOLEAN         shift and go to state 10
    ID              shift and go to state 31
    LRB             shift and go to state 36
    SUB             shift and go to state 34
    NOT             shift and go to state 37
    LCB             shift and go to state 45
    INTEGERNUMBER   shift and go to state 38
    FLOATNUMBER     shift and go to state 39
    TRUE            shift and go to state 40
    FALSE           shift and go to state 41

  ! RETURN          [ reduce using rule 30 (stmtlist -> .) ]
  ! WHILE           [ reduce using rule 30 (stmtlist -> .) ]
  ! FOR             [ reduce using rule 30 (stmtlist -> .) ]
  ! IF              [ reduce using rule 30 (stmtlist -> .) ]
  ! PRINT           [ reduce using rule 30 (stmtlist -> .) ]
  ! ID              [ reduce using rule 30 (stmtlist -> .) ]
  ! LRB             [ reduce using rule 30 (stmtlist -> .) ]
  ! SUB             [ reduce using rule 30 (stmtlist -> .) ]
  ! NOT             [ reduce using rule 30 (stmtlist -> .) ]
  ! LCB             [ reduce using rule 30 (stmtlist -> .) ]
  ! INTEGERNUMBER   [ reduce using rule 30 (stmtlist -> .) ]
  ! FLOATNUMBER     [ reduce using rule 30 (stmtlist -> .) ]
  ! TRUE            [ reduce using rule 30 (stmtlist -> .) ]
  ! FALSE           [ reduce using rule 30 (stmtlist -> .) ]

    stmtlist                       shift and go to state 96
    vardec                         shift and go to state 97
    stmt                           shift and go to state 98
    type                           shift and go to state 72
    exp                            shift and go to state 100
    block                          shift and go to state 105
    lvalue                         shift and go to state 33
    const                          shift and go to state 35

这里是所有作品的清单：

program → declist main ( ) block

declist → dec | declist dec | 𝜖

dec → vardec | funcdec

type → int | float | bool

iddec → id | id [ exp ] | id=exp

idlist → iddec | idlist , iddec

vardec → type idlist ;

funcdec → type id (paramdecs) block | void id (paramdecs) block

paramdecs → paramdecslist | 𝜖

paramdecslist → paramdec | paramdecslist , paramdec

paramdec → type id | type id []

Precedencevarlist → vardec | varlist vardec | 𝜖

block → { varlist stmtlist }

stmtlist → stmt | stmlist stmt | 𝜖

lvalue → id | id [exp]

stmt → return exp ; | exp ;| block |

while (exp) stmt |

for(exp ; exp ; exp) stmt |

if (exp) stmt elseiflist | if (exp) stmt elseiflist else stmt |

print ( id) ;

elseiflist → elif (exp) stmt | elseiflist elif (exp) stmt | 𝜖

exp → lvalue=exp | exp operator exp |exp relop exp|

const | lvalue | id(explist) | (exp) | id() | - exp | ! exp

operator → “||” | && | + | - | * | / | %

const → intnumber | floatnumber | true | false

relop → > | < | != | == | <= | >=

explist → exp | explist,exp

另一个问题是著名的悬空问题，我在优先级元组中添加了('nonassoc', 'IFP'), ('left', 'ELSE' , 'ELIF')并以这种方式更改了语法：

def p_stmt_5(self, p):
    """stmt : IF LRB exp RRB stmt elseiflist %prec IFP """
    print("""stmt : IF LRB exp RRB stmt elseiflist """)

def p_stmt_6(self, p):
    """stmt : IF LRB exp RRB stmt elseiflist ELSE stmt"""
    print("""stmt : IF LRB exp RRB stmt elseiflist else stmt """)

但是它并没有消失。下面是发生移位/减少冲突的状态。

状态130

    (37) stmt -> IF LRB exp RRB stmt . elseiflist
    (38) stmt -> IF LRB exp RRB stmt . elseiflist ELSE stmt
    (41) elseiflist -> . ELIF LRB exp RRB stmt
    (42) elseiflist -> . elseiflist ELIF LRB exp RRB stmt
    (43) elseiflist -> .

  ! shift/reduce conflict for ELIF resolved as shift
    ELIF            shift and go to state 134
    RCB             reduce using rule 43 (elseiflist -> .)
    RETURN          reduce using rule 43 (elseiflist -> .)
    WHILE           reduce using rule 43 (elseiflist -> .)
    FOR             reduce using rule 43 (elseiflist -> .)
    IF              reduce using rule 43 (elseiflist -> .)
    PRINT           reduce using rule 43 (elseiflist -> .)
    ID              reduce using rule 43 (elseiflist -> .)
    LRB             reduce using rule 43 (elseiflist -> .)
    SUB             reduce using rule 43 (elseiflist -> .)
    NOT             reduce using rule 43 (elseiflist -> .)
    LCB             reduce using rule 43 (elseiflist -> .)
    INTEGERNUMBER   reduce using rule 43 (elseiflist -> .)
    FLOATNUMBER     reduce using rule 43 (elseiflist -> .)
    TRUE            reduce using rule 43 (elseiflist -> .)
    FALSE           reduce using rule 43 (elseiflist -> .)
    ELSE            reduce using rule 43 (elseiflist -> .)

  ! ELIF            [ reduce using rule 43 (elseiflist -> .) ]

    elseiflist                     shift and go to state 133

最后还有另外两个带有移位/减少错误的状态，我在下面列出：

state 45

    (27) block -> LCB . varlist stmtlist RCB
    (24) varlist -> . vardec
    (25) varlist -> . varlist vardec
    (26) varlist -> .
    (15) vardec -> . type idlist SEMICOLON
    (7) type -> . INTEGER
    (8) type -> . FLOAT
    (9) type -> . BOOLEAN

  ! shift/reduce conflict for INTEGER resolved as shift
  ! shift/reduce conflict for FLOAT resolved as shift
  ! shift/reduce conflict for BOOLEAN resolved as shift
    RETURN          reduce using rule 26 (varlist -> .)
    WHILE           reduce using rule 26 (varlist -> .)
    FOR             reduce using rule 26 (varlist -> .)
    IF              reduce using rule 26 (varlist -> .)
    PRINT           reduce using rule 26 (varlist -> .)
    ID              reduce using rule 26 (varlist -> .)
    LRB             reduce using rule 26 (varlist -> .)
    SUB             reduce using rule 26 (varlist -> .)
    NOT             reduce using rule 26 (varlist -> .)
    LCB             reduce using rule 26 (varlist -> .)
    INTEGERNUMBER   reduce using rule 26 (varlist -> .)
    FLOATNUMBER     reduce using rule 26 (varlist -> .)
    TRUE            reduce using rule 26 (varlist -> .)
    FALSE           reduce using rule 26 (varlist -> .)
    RCB             reduce using rule 26 (varlist -> .)
    INTEGER         shift and go to state 8
    FLOAT           shift and go to state 9
    BOOLEAN         shift and go to state 10

  ! INTEGER         [ reduce using rule 26 (varlist -> .) ]
  ! FLOAT           [ reduce using rule 26 (varlist -> .) ]
  ! BOOLEAN         [ reduce using rule 26 (varlist -> .) ]

    varlist                        shift and go to state 70
    vardec                         shift and go to state 71
    type                           shift and go to state 72

和：

state 0

    (0) S' -> . program
    (1) program -> . declist MAIN LRB RRB block
    (2) declist -> . dec
    (3) declist -> . declist dec
    (4) declist -> .
    (5) dec -> . vardec
    (6) dec -> . funcdec
    (15) vardec -> . type idlist SEMICOLON
    (16) funcdec -> . type ID LRB paramdecs RRB block
    (17) funcdec -> . VOID ID LRB paramdecs RRB block
    (7) type -> . INTEGER
    (8) type -> . FLOAT
    (9) type -> . BOOLEAN

  ! shift/reduce conflict for VOID resolved as shift
  ! shift/reduce conflict for INTEGER resolved as shift
  ! shift/reduce conflict for FLOAT resolved as shift
  ! shift/reduce conflict for BOOLEAN resolved as shift
    MAIN            reduce using rule 4 (declist -> .)
    VOID            shift and go to state 7
    INTEGER         shift and go to state 8
    FLOAT           shift and go to state 9
    BOOLEAN         shift and go to state 10

  ! VOID            [ reduce using rule 4 (declist -> .) ]
  ! INTEGER         [ reduce using rule 4 (declist -> .) ]
  ! FLOAT           [ reduce using rule 4 (declist -> .) ]
  ! BOOLEAN         [ reduce using rule 4 (declist -> .) ]

    program                        shift and go to state 1
    declist                        shift and go to state 2
    dec                            shift and go to state 3
    vardec                         shift and go to state 4
    funcdec                        shift and go to state 5
    type                           shift and go to state 6

非常感谢。

parsing compiler-construction yacc ply lalr
1个回答
1
投票

这里实际上存在两个有点相关的问题，都与递归生产中重复基数引起的歧义有关：

1。 stmtlist中的歧义>

首先，正如您所暗示的，stmtlist存在问题。您的stmtlist语法为：

stmtlist → stmt | stmlist stmt | 𝜖

具有两个基本情况：stmtlist → stmt和stmtlist → 𝜖。此重复意味着可以通过两种方式解析单个stmt：

  1. stmtlist → stmt

  2. stmtlist → stmtlist stmt → 𝜖 stmt

    3. 语法歧义总是表现为冲突。为了消除冲突，消除歧义。如果希望stmtlist为空，请使用：

stmtlist → stmlist stmt | 𝜖

如果您要坚持[C0​​]至少包含一个stmtlist，请使用：
stmt
首先，请尝试理解上述建议的逻辑。

此外，您允许stmtlist → stmlist stmt | stmt 为空。显然，这将导致stmt中的歧义，因为无法知道列表中有多少空stmtlist。可能是3；可能是42;可能是八百万。空是看不见的。

stmt的潜在虚无也会使那些以stmt结尾的复合语句（例如stmt）产生歧义。如果"while" '(' exp ')' stmt可能为空，则

stmt
可能是两个语句：while (x) while(y) c;
带有空的重复语句，然后while(x)带有在while(y)上的循环。或者它可能具有c;循环的（可能是预期的）含义，该循环的重复语句是嵌套的while(x)。我建议没有人会期望第一个解释，而语法不应允许它。如果您想要一个空的while(y) c;目标，则可以使用while作为重复语句，而不是没有。

我确定您不希望;不能为空。允许将空语句写为stmt是很有意义的（也就是说，空语句后是分号），但这显然是一种不同的语法。 （在;…{内部，您可能希望什么都不允许，而不是坚持使用分号。要实现这一点，您需要一个空的}，而不是一个空的stmtlist。）

2。晃来晃去：实际上stmt]中的歧义

我认为这是您正在使用的语法：

elseiflist
与(37) stmt -> "if" '(' exp ')' stmt elseiflist %prec IFP
(38) stmt -> "if" '(' exp ')' stmt elseiflist "else" stmt
(41) elseiflist -> "elif" '(' exp ')' stmt
(42) elseiflist -> elseiflist "elif" '(' exp ')' stmt
(43) elseiflist ->
生产一样，stmtlist是具有两个基本情况的递归生产，其中一个是多余的。再次，有必要确定elseiflist是否真的可以为空（提示：可以为空），然后删除一个或多个基本情况，以避免进行模棱两可的解析。
话虽如此，我认为这不是为if语句编写语法的最佳方法；它构建的解析树可能与您期望的不一样。但我想它会起作用。
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.