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)令牌作爲代理，但可能會被認爲不太可讀。