ply を使用して LALR パーサーを作成していて、乗算を解析しようとしたときに矛盾に遭遇しました。
完全なパーサーリンクは数千行に及ぶため、ここには含めませんが、簡単なデモを作成しました。
import ply.lex as lex
import ply.yacc as yacc
tokens = (
'int',
'times',
'plus',
)
precedence = (
('left', 'plus'),
('left', 'times'),
)
t_ignore = ' \t\n '
t_int = r' \d+ '
t_plus = r' \+ '
t_times = ' \* '
def p_int(args):
'expr : int'
args[0] = int(args[1])
def p_times(args):
'''expr : expr times expr
| expr expr %prec times'''
if len(args) == 3:
args[0] = args[1] * args[2]
elif len(args) == 4:
args[0] = args[1] * args[3]
def p_plus(args):
'expr : expr plus expr'
args[0] = args[1] + args[3]
lex.lex()
parser = yacc.yacc()
while True:
s = raw_input('>> ')
print " = ", parser.parse(s)
PLY によって報告された shift/reduce の競合や reduce/reduce の競合はありませんが、次の矛盾が発生します。
>> 1 + 2 3
= 9
>> 1 + 2 * 3
= 7
明示的な時間ルールと暗黙の時間ルールの優先順位が同じであるため、これは奇妙に思えます。しかし、PLY が 'times' トークンに優先順位を割り当て、p_plus ルールで式を減らすことを優先してスタックにシフトするという事実が原因である可能性があると思います。どうすればこれを修正できますか?
編集:より簡単なデモンストレーション。