yacc - Precedence of a rule with no operator?

Question

Thinking about parsing regular expressions using yacc (I'm actually using PLY), some of the rules would be like the following:

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

The problem is, the first rule(concatenation) must take precedence over the second rule, but not the third one.

However, the concatenation rule has no operator in it.

How can I specify the precedence correctly in this case?

Thank you!

EDIT:

I modified the rules to avoid the issue, but I'm still curious what was the problem.

Here is the source code:

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

Its parsing result of 'ab|cd*' is ('CONCAT', ('|', ('CONCAT', 'a', 'b'), 'c'), ('*', 'd')).

Answer 1

You are under no obligation to use precedence to disambiguate; you can simply write an unambiguous grammar:

term : CHAR | '(' expr ')'
rept : term | term '*' | term '+' | term '?'
conc : rept | conc rept
expr : conc | expr '|' conc

If you really want to use precedence, you can use a "fictitious" token with a %prec annotation. See the manual for details. (This feature comes from yacc, so you could read about it in any yacc/bison documentation as well.)

Bear in mind that precedence is always a comparison between a production (at the top of the parser stack) and the lookahead token. Normally, the precedence of productions is taken from the precedence of the last terminal in the production (and normally there is only one terminal in each applicable production), so it appears to be a comparison between terminals. But in order to get precedence to work with "invisible" operators, you need to separately consider both the production precedence and the lookahead token precedence.

The precedence of the production can be set with a "fictitious" token, as described above. But there is no lookahead token corresponding to an invisible operator; the lookahead token will be the first token in the following operand. In other words, it could be any token in the FIRST set of expr, which in this case is {NORMAL, PRIGHT}; this set must be added to the precedence declaration as though they were concatenation operators:

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

Once you do that, you could economize on the fictitious CONCAT token, since you could use any of the FIRST(expr) tokens as a proxy, but that might be considered less readable.