解决层yacc中的偏移/减少冲突

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

Ply报告说,在使用我输入的语法来构建LALR解析器时,它遇到了许多移位/减少冲突。

目前,我正在尝试解决这些冲突,但是我所做的一切都会使情况变得更糟。首先,我使用C语言(我的语法几乎与C和Python混合使用的编程语言语法相同)优先级表在解析器中将precedence tuple设置为与该顺序相同:

precedence = (
        # ('left', 'ELSE'),
        # ('left', 'ID')
        # ('left', 'INTEGERNUMBER')
        # ('left', 'FLOATNUMBER')
        # ('left', 'SEMICOLON')
        # ('left', 'ERROR')
        ('left', 'COMMA'),
        ('right', 'ASSIGN'),
        ('left', 'OR'),
        ('left', 'AND'),
        ('left', 'EQ', 'NE'),
        ('left', 'GE', 'GT'),
        ('left', 'LE', 'LT'),
        ('left', 'SUM', 'SUB'),
        ('left', 'MUL', 'DIV', 'MOD'),
        ('right', 'NOT'),
        ('left', 'LCB', 'RCB'), #left curly brace...
        ('left', 'LSB', 'RSB'), #left square bracket..
        ('left', 'LRB', 'RRB'), #left round bracket...
    )

它确实提供了帮助,消除了90个冲突中的40个。下一步,我尝试从包含左递归的语法中删除左递归。我使用在线工具为其中一两个作品制作了影片,但它增加了很多“减少-减少”冲突和一些“减少/减少”冲突,我对这些事情并不擅长,所以我怀疑是否应该继续消除所有产品的所有剩余递归都可以查看结果,或者早期的不良结果是一个停止信号。

[我也进行了一些搜索,发现左递归不会破坏LALR语法,precedenceassociativity足以解决这些冲突。

以下是发生许多冲突的州之一:

state 82

    (45) exp -> exp operator exp .
    (45) exp -> exp . operator exp
    (46) exp -> exp . relop exp
    (54) operator -> . OR
    (55) operator -> . AND
    (56) operator -> . SUM
    (57) operator -> . SUB
    (58) operator -> . MUL
    (59) operator -> . DIV
    (60) operator -> . MOD
    (65) relop -> . GT
    (66) relop -> . LT
    (67) relop -> . NE
    (68) relop -> . EQ
    (69) relop -> . LE
    (70) relop -> . GE

  ! shift/reduce conflict for OR resolved as shift
  ! shift/reduce conflict for AND resolved as shift
  ! shift/reduce conflict for SUM resolved as shift
  ! shift/reduce conflict for SUB resolved as shift
  ! shift/reduce conflict for MUL resolved as shift
  ! shift/reduce conflict for DIV resolved as shift
  ! shift/reduce conflict for MOD resolved as shift
  ! shift/reduce conflict for GT resolved as shift
  ! shift/reduce conflict for LT resolved as shift
  ! shift/reduce conflict for NE resolved as shift
  ! shift/reduce conflict for EQ resolved as shift
  ! shift/reduce conflict for LE resolved as shift
  ! shift/reduce conflict for GE resolved as shift
    RSB             reduce using rule 45 (exp -> exp operator exp .)
    SEMICOLON       reduce using rule 45 (exp -> exp operator exp .)
    COMMA           reduce using rule 45 (exp -> exp operator exp .)
    RRB             reduce using rule 45 (exp -> exp operator exp .)
    OR              shift and go to state 54
    AND             shift and go to state 55
    SUM             shift and go to state 56
    SUB             shift and go to state 57
    MUL             shift and go to state 58
    DIV             shift and go to state 59
    MOD             shift and go to state 60
    GT              shift and go to state 61
    LT              shift and go to state 62
    NE              shift and go to state 63
    EQ              shift and go to state 64
    LE              shift and go to state 65
    GE              shift and go to state 66

  ! OR              [ reduce using rule 45 (exp -> exp operator exp .) ]
  ! AND             [ reduce using rule 45 (exp -> exp operator exp .) ]
  ! SUM             [ reduce using rule 45 (exp -> exp operator exp .) ]
  ! SUB             [ reduce using rule 45 (exp -> exp operator exp .) ]
  ! MUL             [ reduce using rule 45 (exp -> exp operator exp .) ]
  ! DIV             [ reduce using rule 45 (exp -> exp operator exp .) ]
  ! MOD             [ reduce using rule 45 (exp -> exp operator exp .) ]
  ! GT              [ reduce using rule 45 (exp -> exp operator exp .) ]
  ! LT              [ reduce using rule 45 (exp -> exp operator exp .) ]
  ! NE              [ reduce using rule 45 (exp -> exp operator exp .) ]
  ! EQ              [ reduce using rule 45 (exp -> exp operator exp .) ]
  ! LE              [ reduce using rule 45 (exp -> exp operator exp .) ]
  ! GE              [ reduce using rule 45 (exp -> exp operator exp .) ]

    operator                       shift and go to state 52
    relop                          shift and go to state 53  

这是一些我认为与上述状态有关的作品:

exp → lvalue=exp | exp operator exp |exp relop exp|
const | lvalue | ID(explist) | LRB exp RRB | ID() | SUB exp | NOT exp

operator → OR | AND | SUM | SUB | MUL | DIV | MOD

relop → GE | LT | NE | EQ | LE | GE

const → INTEGERNUMBER | FLOATNUMBER | TRUE | FALSE

lvalue → ID | ID LSB exp RSB

EDIT:以下是警告的完整列表:

WARNING: Conflicts:
WARNING: 
WARNING: shift/reduce conflict for VOID in state 0 resolved as shift
WARNING: shift/reduce conflict for INTEGER in state 0 resolved as shift
WARNING: shift/reduce conflict for FLOAT in state 0 resolved as shift
WARNING: shift/reduce conflict for BOOLEAN in state 0 resolved as shift
WARNING: shift/reduce conflict for INTEGER in state 45 resolved as shift
WARNING: shift/reduce conflict for FLOAT in state 45 resolved as shift
WARNING: shift/reduce conflict for BOOLEAN in state 45 resolved as shift
WARNING: shift/reduce conflict for RETURN in state 72 resolved as shift
WARNING: shift/reduce conflict for WHILE in state 72 resolved as shift
WARNING: shift/reduce conflict for FOR in state 72 resolved as shift
WARNING: shift/reduce conflict for IF in state 72 resolved as shift
WARNING: shift/reduce conflict for PRINT in state 72 resolved as shift
WARNING: shift/reduce conflict for ID in state 72 resolved as shift
WARNING: shift/reduce conflict for LRB in state 72 resolved as shift
WARNING: shift/reduce conflict for SUB in state 72 resolved as shift
WARNING: shift/reduce conflict for NOT in state 72 resolved as shift
WARNING: shift/reduce conflict for LCB in state 72 resolved as shift
WARNING: shift/reduce conflict for INTEGERNUMBER in state 72 resolved as shift
WARNING: shift/reduce conflict for FLOATNUMBER in state 72 resolved as shift
WARNING: shift/reduce conflict for TRUE in state 72 resolved as shift
WARNING: shift/reduce conflict for FALSE in state 72 resolved as shift
WARNING: shift/reduce conflict for OR in state 82 resolved as shift
WARNING: shift/reduce conflict for AND in state 82 resolved as shift
WARNING: shift/reduce conflict for SUM in state 82 resolved as shift
WARNING: shift/reduce conflict for SUB in state 82 resolved as shift
WARNING: shift/reduce conflict for MUL in state 82 resolved as shift
WARNING: shift/reduce conflict for DIV in state 82 resolved as shift
WARNING: shift/reduce conflict for MOD in state 82 resolved as shift
WARNING: shift/reduce conflict for GT in state 82 resolved as shift
WARNING: shift/reduce conflict for LT in state 82 resolved as shift
WARNING: shift/reduce conflict for NE in state 82 resolved as shift
WARNING: shift/reduce conflict for EQ in state 82 resolved as shift
WARNING: shift/reduce conflict for LE in state 82 resolved as shift
WARNING: shift/reduce conflict for GE in state 82 resolved as shift
WARNING: shift/reduce conflict for OR in state 83 resolved as shift
WARNING: shift/reduce conflict for AND in state 83 resolved as shift
WARNING: shift/reduce conflict for SUM in state 83 resolved as shift
WARNING: shift/reduce conflict for SUB in state 83 resolved as shift
WARNING: shift/reduce conflict for MUL in state 83 resolved as shift
WARNING: shift/reduce conflict for DIV in state 83 resolved as shift
WARNING: shift/reduce conflict for MOD in state 83 resolved as shift
WARNING: shift/reduce conflict for GT in state 83 resolved as shift
WARNING: shift/reduce conflict for LT in state 83 resolved as shift
WARNING: shift/reduce conflict for NE in state 83 resolved as shift
WARNING: shift/reduce conflict for EQ in state 83 resolved as shift
WARNING: shift/reduce conflict for LE in state 83 resolved as shift
WARNING: shift/reduce conflict for GE in state 83 resolved as shift
WARNING: shift/reduce conflict for ELIF in state 121 resolved as shift

非常感谢。

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

问题至少是YACC是一个1超前解析器,因此,如果它看到exp,则无法在不同的operator之间做出决定。因为它们看起来都一样。您应该重写语法以打开终端。

据我所能回答,因为您没有提供完整的示例。

© www.soinside.com 2019 - 2024. All rights reserved.