yacc - Приоритет правила без оператора?

Question

Думая о разборе регулярных выражений с помощью Yacc (я на самом деле с помощью корда), некоторые из правил будет иметь следующий вид:

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

Проблема, первое правило (конкатенация) должны иметь приоритет над второе правило, но не третье.

Однако в правиле конкатенации в нем нет оператора.

Как я могу правильно определить приоритет в этом случае?

Спасибо!

EDIT:

Я изменил правила, чтобы избежать проблемы, но я все еще интересно, в чем была проблема.

Вот исходный код:

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.)

Помните, что приоритет всегда является сопоставлением между производством (вверху стека анализатора) и контрольный токен. Как правило, приоритет производств берется из приоритета последнего терминала в производстве (и, как правило, в каждом применимом производстве есть только один терминал), поэтому, похоже, это сравнение между терминалами. Но для того, чтобы получить приоритет для работы с «невидимыми» операторами, вам необходимо отдельно рассмотреть как приоритет производства, так и приоритет маркера списка.

Приоритет производства может быть установлен с помощью «фиктивного» токена, как описано выше. Но нет указателя вида, соответствующего невидимому оператору; токен lookahead будет первым токеном в следующем операнде. Другими словами, это может быть любой знак в FIRST набор expr, который в этом случае равен {NORMAL, PRIGHT}; этот набор должен быть добавлен к декларации старшинства , как если бы они были операторами конкатенации:

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

После того, как вы сделаете это, вы могли бы сэкономить на фиктивном CONCAT знака, так как вы можете использовать любого из FIRST(expr) лексем как прокси, но это может считаться менее читаемым.