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中的任何标记，其在这种情况下是{NORMAL, PRIGHT};这组必须添加到优先申报，仿佛它们是连接操作：

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

一旦你这样做，你可以节约虚拟CONCAT的道理，因为你可以使用任何FIRST(expr)令牌作为代理，但可能会被认为不太可读。