使用 PLY 解析 elif 时出现问题

Question

我正在继续使用 PLY 进行解析的旅程。我在解析 IF 和 ELSE IF 语句时遇到了运行问题。

这是我的代码，我删除了不相关的部分，只保留了基础知识（这将运行在 Python 2.7 上）。

from ply import lex, yacc

tokens = [
    'ELSE',
    'IF',
    'LPAREN',
    'RPAREN',
    'LCURLY',
    'RCURLY'
    ]


t_IF = r'IF'
t_ELSE = r'ELSE'
t_LPAREN = r'\('
t_RPAREN = r'\)'
t_LCURLY = r'\{'
t_RCURLY = r'\}'
t_ignore = '\r\t '


def t_error(t):
    print t


def t_newline(t):
    r'\n+'
    t.lexer.lineno += len(t.value)


def p_error(p):
    print ('error', p)


def p_empty(p):
    'empty :'
    p[0] = None


def p_if_statement(p):
    'if_statement : IF LPAREN RPAREN LCURLY RCURLY elif_statements_or_empty else_statement_or_empty'
    p[0] = ('if_statement', (p[6]))
    print p[0]


def p_else_statement(p):
    'else_statement : ELSE LCURLY RCURLY'
    p[0] = ('else_statement')


def p_else_statement_or_empty(p):
    '''else_statement_or_empty : else_statement
                               | empty'''
    p[0] = p[1]


def p_elif_statement(p):
    'elif_statement : ELSE IF LPAREN RPAREN LCURLY RCURLY'
    p[0] = ('elif_statement')


def p_elif_statements_1(p):
    'elif_statements : elif_statement'
    p[0] = [p[1]]


def p_elif_statements_2(p):
    'elif_statements : elif_statements elif_statement'
    p[0] = p[1] + [p[2]]


def p_elif_statements_or_empty(p):
    '''elif_statements_or_empty : elif_statements
                                | empty'''
    p[0] = p[1]


lexer = lex.lex()

s = 'IF(){}ELSE IF(){}ELSE{}'

parser = yacc.yacc(start='if_statement')
parser.parse(s)  # ('error', LexToken(LCURLY,'{',1,21))

本质上，问题是我正在搜索无限量的 elif_statement。当它遇到 ELSE { 时，它认为存在解析错误，因为它期望在 ELSE.

之后出现 IF

这就是所谓的"shift/reduce error"吗？我可以通过哪些方式解决此问题？

非常感谢任何帮助！

Answer 1

是的，这是 shift/reduce 冲突的结果。 PLY 警告您，您有其中两个，它们都与 else 子句有些相关。

但是，问题与 else if 子句的潜在无限序列无关。那不是问题。问题更微妙，与您使用空作品有关。

LR(1)最重要的方面，从解决问题的角度来说，就是每个non-terminal都需要约化（即，从其 right-hand 侧创建）在紧随其后的标记被移动之前。考虑到这一点，让我们看一下 if_statement:

的语法

if_statement : IF LPAREN RPAREN LCURLY RCURLY 
               elif_statements_or_empty
               else_statement_or_empty

假设我们已经看到 IF(){}，那么下一个标记是 ELSE。此时在 right-hand 端（这是此时解析中唯一的活动项）我们知道下一个标记必须是 ELSE 或输入的末尾。在后一种情况下，很清楚必须做什么：必须减少 empty，然后必须从 empty 减少 elif_statements_or_empty；接下来必须减少另一个 empty，并且必须从 empty 减少一个 else_statement_or_empty。一切正常。

但假设下一个标记是 ELSE。怎么办？由于我们看不到 ELSE 以外的任何东西，我们不知道它后面是 IF 还是 (。但我们必须在两个选项之间做出决定：

减少一个empty然后一个elif_statements_or_empty。如果 ELSE 是 else_statement_or_empty 的开头（在这种情况下不能为空），那将是正确的。
Shift ELSE 只能作为 elif_statements_or_empty 的开始，不能为空，必须为elif_statements。如果 ELSE 是 ELSE IF 子句的一部分，那将是正确的。

所以这是一个 shift/reduce 冲突。 Bison 总是选择 shift/reduce 冲突中的移位，因此它会假定 IF 之后的第一个 ELSE 是 ELSE IF 子句的开始。让我们继续这个假设（在提供的输入的情况下恰好是正确的），并继续直到我们达到以下 ELSE。我们现在看到了 IF(){}ELSE IF(){}，我们再次盯着 ELSE。

至此，绝对清楚ELSE IF(){}必须减少到else_if_statement并且也清楚else_if_statement必须减少到else_if_statements。到目前为止，一切都很好。但是现在问题来了。如果还有另一个 ELSE IF，这就足够减少了，我们应该 shift ELSE 成为以下 else_if_statement 的一部分。但是如果ELSE是最后一个else_statement的开始，那么我们需要reduce我们刚刚创建的else_if_statements变成一个else_if_statements_or_empty，因为在我们可以移动开始于 else_statement_or_empty.

的 ELSE 之前需要减少

再说一次，野牛总是去换班。但这意味着它永远无法决定启动 else_statement_or_empty.

那么，怎么办？

首先要注意的是 elif_statements_or_empty 生产实际上根本没有增加任何价值。（实际上，empty 也不是，我打算默默地删除它，但我会留下这个括号讣告。）如果我们只是把 elif_statements 放在 if_statement 中，那么我们不需要在 elif_statements 和 elif_statements_or_empty 之间做出决定。当然，我们需要 elif_statements 来匹配一个空字符串，但这很简单：我们只是为递归基本情况提供一个空的 right-hand 边。也就是说，而不是

elif_statements: elif_statement | elif_statements elif_statement

我们将使用

elif_statements: | elif_statements elif_statement

我们现在将匹配包括零个 elif_statement 在内的任何数字，而不是至少匹配一个 elif_statement。这正是我们想要的。

现在 elif_statements 基本情况是空的，我们不再需要在 IF(){} 之后决定我们是否会有 elif_statements 的空集。我们可以只减少一个空的 elif_statements，然后看看接下来是 elif_statement 还是 else_statement。因此，通过这种简化，我们实际上消除了两个 shift-reduce 冲突。

总而言之，新的 PLY 文件：（仅解析器规则，其他未更改）：

def p_error(p):
    print ('error', p)

# Fixed to return both elif and else statements    
def p_if_statement(p):
    'if_statement : IF LPAREN RPAREN LCURLY RCURLY elif_statements else_statement'
    p[0] = ('if_statement', (p[6] + p[7]))
    print p[0]

# This needs to return a list because it could be empty
def p_else_statement(p):
    'else_statement : ELSE LCURLY RCURLY'
    p[0] = ['else_statement']

def p_elif_statement(p):
    'elif_statement : ELSE IF LPAREN RPAREN LCURLY RCURLY'
    p[0] = 'elif_statement'

def p_elif_statements(p):
    'elif_statements : elif_statements elif_statement'
    p[0] = p[1] + [p[2]]

# This handles both empty elif_statements and an empty else
# by reducing to an empty list
def p_empty(p):
    '''elif_statements : 
       else_statement  :'''
    p[0] = []

使用 PLY 解析 elif 时出现问题

Trouble parsing elif using PLY

python

yacc

bnf

ply