使用 PLY 解析 elif 时出现问题
Trouble parsing elif using PLY
我正在继续使用 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"吗?我可以通过哪些方式解决此问题?
非常感谢任何帮助!
是的,这是 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 进行解析的旅程。我在解析 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"吗?我可以通过哪些方式解决此问题?
非常感谢任何帮助!
是的,这是 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] = []