parsing - yacc - 没有运算符的规则的优先级？

Question

考虑使用 yacc 解析正则表达式(我实际上使用的是 PLY)，一些规则如下所示:

expr : expr expr
expr : expr '|' expr
expr : expr '*'

问题是，第一条规则(串联)必须优先于第二条规则，但第三条规则不能。

但是，串联规则中没有运算符。

在这种情况下如何正确指定优先级？

谢谢!

编辑:

我修改了规则以避免这个问题，但我仍然很好奇问题出在哪里。

这是源代码:

tokens = ['PLEFT', 'PRIGHT', 'BAR', 'ASTERISK', 'NORMAL']

t_PLEFT = r'\('
t_PRIGHT = r'\)'
t_BAR = r'\|'
t_ASTERISK = '\*'
t_NORMAL = r'[a-zA-Z0-9]'

lex.lex()

precedence = (
  ('left', 'BAR'),
  ('left', 'CONCAT'),
  ('left', 'ASTERISK'),
)

def p_normal(p):
    '''expr : NORMAL'''
    p[0] = p[1]

def p_par(p):
    '''expr : PLEFT expr PRIGHT'''
    p[0] = p[2]

def p_or(p):
    '''expr : expr BAR expr'''
    p[0] = ('|', p[1], p[3])

def p_concat(p):
    '''expr : expr expr %prec CONCAT'''
    p[0] = ('CONCAT', p[1], p[2])

def p_repeat(p):
    '''expr : expr ASTERISK'''
    p[0] = ('*', p[1])

yacc.yacc()

'ab|cd*'解析结果为('CONCAT', ('|', ('CONCAT', 'a', 'b'), 'c '), ('*', 'd')).

Answer 1

您没有义务使用优先顺序来消除歧义；你可以简单地编写一个明确的语法:

term : CHAR | '(' expr ')'
rept : term | term '*' | term '+' | term '?'
conc : rept | conc rept
expr : conc | expr '|' conc

如果您确实想使用优先级，可以使用带有 %prec 注释的“虚构”标记。请参阅manual了解详情。 (此功能来自 yacc，因此您也可以在任何 yacc/bison 文档中阅读有关它的信息。)

请记住，优先级始终是产生式(位于解析器堆栈顶部)和先行标记之间的比较。通常，产生式的优先级取自产生式中最后一个终端的优先级(并且通常每个适用的产生式中只有一个终端)，因此它看起来是终端之间的比较。但为了获得使用“不可见”运算符的优先级，您需要分别考虑生产优先级和先行标记优先级。

如上所述，可以使用“虚构”标记来设置产生式的优先级。但是不存在与不可见运算符相对应的前瞻标记；前瞻标记将是以下操作数中的第一个标记。换句话说，它可以是 expr 的 FIRST 集中的任何标记，在本例中是 {NORMAL, PRIGHT}；该集合必须添加到优先级声明中，就好像它们是串联运算符:

precedence = (
  ('left', 'BAR'),
  ('left', 'CONCAT', 'NORMAL', 'PLEFT'),
  ('left', 'ASTERISK'),
)

完成此操作后，您可以节省虚构的 CONCAT token ，因为您可以使用任何 FIRST(expr) token 作为代理，但这可能被认为可读性较差。