yacc - 연산자가없는 규칙의 우선 순위? (실제로 PLY을 사용하고 있습니다)은 yacc을 사용하여 정규 표현식을 구문 분석에 대한 생각

Question

, 규칙 중 일부는 같은 것 다음

는

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 문서에서도 읽을 수 있습니다.)

우선 순위는 항상 (파서 스택의 맨 위에있는) 프로덕션과 미리보기 토큰. 일반적으로 프로덕션의 우선 순위는 프로덕션에서 마지막 터미널의 우선 순위에서 취해집니다 (일반적으로 각 해당 프로덕션에는 하나의 터미널 만 있음). 따라서 터미널 간의 비교 인 것으로 보입니다. 그러나 "보이지 않는"연산자로 작업 할 우선 순위를 얻으려면 프로덕션 우선 순위와 미리보기 토큰 우선 순위를 별도로 고려해야합니다.

위에서 설명한대로 "가상의"토큰을 사용하여 프로덕션의 우선 순위를 설정할 수 있습니다. 그러나 보이지 않는 연산자에 해당하는 미리보기 토큰이 없습니다. lookahead 토큰은 다음 피연산자의 첫 번째 토큰이됩니다. 다시 말해서, FIRST 집합이 expr 인이 토큰은이 경우 {NORMAL, PRIGHT}입니다. 그들은 연결 운영자 인 것처럼이 세트는 우선 순위 선언 에 추가해야합니다 : 당신이 그렇게하면 당신이로 FIRST(expr) 토큰을 사용할 수 있기 때문에

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

, 당신은 가상 CONCAT 토큰을 절약 할 수 프록시,하지만 그것은 덜 읽을 것으로 간주 될 수 있습니다.