Precedence Issues

[bstrulo]

I may be missing something but I think there is a problem with precedence when there is more than one terminal in a rule. I have sample code which tries various permutations using either the first, last or both terminals in the precedence list. I don't get the results I expect. Seems to never do right associativity and sometimes other problems.

[bstrulo]

How do I attach a file? I've pasted it in below:

import yacc,lex

def t_ID(t):
r'[a-zA-Z_][a-zA-Z_0-9]*'
return t
tokens = [
'ID',
'PLUS',
'LSQUARE',
'RSQUARE',
]
t_PLUS = r'+'
t_LSQUARE = r'['
t_RSQUARE = r']'
def t_error(t):
pass
def p_error(t):
pass
def lexer():
return lex.lex()

def p_expr1(p):
'''expr : expr PLUS expr'''
p[0] = (p[1],p[2],p[3])

def p_expr2(p):
'''expr : expr LSQUARE expr RSQUARE'''
p[0] = (p[1],"*",p[3])

def p_expr_atom(p):
'''expr : ID'''
p[0] = p[1]

def parse(data):
lexer()
parser = yacc.yacc()
return parser.parse(data)

precedenceTest = [
(( # this is the precedence
('left', 'PLUS'),
('left','RSQUARE'),
),# this is the expected output - PLUS is lower priority
(('a', '', 'b'), '+', ('d', '', 'b'))), # Fails

((
('left', 'PLUS'),
('left','LSQUARE'),
),
(('a', '*', 'b'), '+', ('d', '*', 'b'))), # Works

((
('left', 'PLUS'),
('left','LSQUARE','RSQUARE'),
),
 (('a', '*', 'b'), '+', ('d', '*', 'b'))), # Works

((
('left',  'PLUS','RSQUARE'),
),# Now we expect left associativity
 ((('a', '*', 'b'), '+', 'd'), '*', 'b')), # Works

((
('left',  'PLUS','LSQUARE'),
),
 ((('a', '*', 'b'), '+', 'd'), '*', 'b')), # Works

((
('left',  'PLUS','LSQUARE','RSQUARE'),
),
 ((('a', '*', 'b'), '+', 'd'), '*', 'b')), # Works

((
('right',  'PLUS','RSQUARE'),
),# Now we expect right associativity
 ('a', '*',( 'b', '+',( 'd', '*', 'b')))), # Fails

((
('right',  'PLUS','LSQUARE'),
),
 ('a', '*',( 'b', '+',( 'd', '*', 'b')))), # Fails

((
('right',  'PLUS','LSQUARE','RSQUARE'),
),
 ('a', '*',( 'b', '+',( 'd', '*', 'b')))), # Fails

((
('left','RSQUARE'),
('left', 'PLUS'),
),
(('a', '*',( 'b', '+', 'd')), '*', 'b')), # Fails

((
('left','LSQUARE'),
('left', 'PLUS'),
),
(('a', '*',( 'b', '+', 'd')), '*', 'b')), # Fails

((
('left','LSQUARE','RSQUARE'),
('left', 'PLUS'),
),
(('a', '*',( 'b', '+', 'd')), '*', 'b')), # Fails


((
('right','RSQUARE'),
('left', 'PLUS'),
),
('a', '*',(( 'b', '+', 'd'), '*', 'b'))), # Fails

((
('right','LSQUARE'),
('left', 'PLUS'),
),
('a', '*',(( 'b', '+', 'd'), '*', 'b'))), # Fails

((
('right','LSQUARE','RSQUARE'),
('left', 'PLUS'),
),
('a', '*',(( 'b', '+', 'd'), '*', 'b'))), # Fails    
]

for p,t in precedenceTest:
precedence = p
ans = parse("a[b]+d[b]")
print ans == t,t,ans

[bstrulo]

Sorry that came out more rubbish than I expected. Anyway, if you cut and paste the code into your editor it should look OK.

[dabeaz]

The precedence table and associativity rules only come into play during the resolution of shift/reduce conflicts and even then, it's only the right-most terminal that matters. You would really need to sit down with the parser.out debugging output and study it to know for certain what's happening here.

[bstrulo]

OK good point - missed that.

However, firstly the parser is changing its output as the precedence changes, even though it doesn't have conflicts. So I don't really get that.

Secondly, if I make the operator infix, so we do get conflicts, I still have it coming out wrong. Program enclosed below.

Here, I've made the operator infix but with two terminals. I get shift/reduce conflicts. I use the right-most terminal and the conflicts are not being resolved in the way I would expect. I've cut it down to one example - just paste the examples in from the previous code to see the whole set;

The output looks like the operators are same precedence, left associative whereas I thought I was specifying that [] was higher priority.

It seems like maybe this is me being stupid but the example looks to me exactly like the usual expression example, but where the conflict is resolved by precedence, yet the precedence is not working here.

import yacc,lex

def t_ID(t):
r'[a-zA-Z_][a-zA-Z_0-9]*'
return t
tokens = [
'ID',
'PLUS',
'LSQUARE',
'RSQUARE',
]
t_PLUS = r'+'
t_LSQUARE = r'['
t_RSQUARE = r']'
def t_error(t):
pass
def p_error(t):
pass
def lexer():
return lex.lex()

def p_expr1(p):
'''expr : expr PLUS expr'''
p[0] = (p[1],p[2],p[3])

def p_expr2(p):
'''expr : expr LSQUARE RSQUARE expr'''
p[0] = (p[1],"*",p[4])

def p_expr_atom(p):
'''expr : ID'''
p[0] = p[1]

def parse(data):
lexer()
parser = yacc.yacc()
return parser.parse(data)

precedenceTest = [
(( # this is the precedence
('left', 'PLUS'),
('left','RSQUARE'),
),# this is the expected output - PLUS is lower priority
(('a', '', 'b'), '+', ('d', '', 'b'))), # Fails

]

for p,t in precedenceTest:
precedence = p
ans = parse("a[]b+d[]b")
print ans == t,t,ans

[bstrulo]

And, I've tried this example in bison now, and get the expected output with * having higher precedence. So it really seems like ply is doing something different to bison/yacc.

I have a feeling that it does the right thing when the multi-token operator is on the left, but not when it is on the right. But I'm not sure.

I have the bison input if you want it but I don't really want to paste it in here. Is there some way to attach files?

Ben

[bstrulo]

OK - I think I see where I am going wrong.

I need to put both terminals in the precedence list because the rightmost defines the precedence of the RULE, while the left terminal is the token which will appear in the lookahead. So I need to define the precedence of both the rule and the tokens separately (though presumably they should be the same in my case).

When I do that I get the same results with bison and ply, I think.

The fact that they differ in cases where I only specify one is probably no big deal, since the input is ambiguous in any case. In fact, if I turn on Bison's glr functionality then it rejects these ones as ambiguous.

So it looks like this is all just down to my misunderstanding. Just to be sure, I'm going to run through the comparisons again but I don't expect a problem.

Sorry for wasting your time and thanks for putting me on the right track.

Ben

[thomaspinckney3]

This issue bit me as well. I had assumed that if used a fictitious token and the %prec rule in the grammar then it would set the precedence correctly for the entire grammar rule. I had to explicitly set the precedence of the left-most terminal and the in addition to using the fictious terminal. I guess this set the precedence on the lookahead token and the rule is required when using multiple terminals.

Really appreciate PLY but I think the section on precedence could be expanded to cover this issue of multiple terminals.