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 注释的 "fictitious" 标记。有关详细信息，请参阅 manual。（此功能来自 yacc，因此您也可以在任何 yacc/bison 文档中阅读它。）

请记住，优先级始终是产生式（位于解析器堆栈的顶部）与先行标记之间的比较。通常，产生式的优先级取自产生式中最后一个终端的优先级（通常每个适用的产生式中只有一个终端），所以它看起来是终端之间的比较。但是为了获得与 "invisible" 运算符一起使用的优先级，您需要分别考虑生产优先级和先行标记优先级。

可以使用 "fictitious" 标记设置产生式的优先级，如上所述。但是没有对应于不可见运算符的前瞻标记；先行标记将是后续操作数中的第一个标记。换句话说，它可以是 expr 的 FIRST 集合中的任何标记，在本例中是 {NORMAL, PRIGHT}；必须将此集合添加到优先级声明中 ，就像它们是串联运算符一样:

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

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

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

yacc - Precedence of a rule with no operator?

parsing

ply