I was told there is a algorithm that always resolves ambiguity for grammars that have issues with precedence and associativity. I know ambiguity in general is undecidable, so I only want to resolve those two sources of ambiguity (precedence and associativity).
As far as I know from reading this course, the heuristic I have developed are the following:
higher precedence = appear lower in the tree always (so they are never produced by any rule bellow a symbol that is higher up). A different way to understand this is; higher precedence operators are evaluated first, so they appear lower in the parse/computation tree.
right-associativity = when two operators of the same type fight for an argument if its right associative then the op on the right wins. Thus, this means that immediate recursion of the same production rule generating that op must always appear on the right (and that symbol/op can never be produced on the other side/left).
however, these rules must be incomplete or slightly wrong because when I was trying to resolve a "tricky" grammar I got wrong answers or couldn't make sense of the right solution.
For example, imagine we have this:
<exp> ::= 0 | 1 | b<exp> | <exp>a | <exp>m<exp>
and we want to enforce:
Right associativity for
mand the following precedence inequality is the one we want: $ b >_p m >_p a$ which means b has higher precedence than m has higher precedence than a.
the solution given was:
<exp> ::= <no a m> | <not m>m<no a> | <exp>a
<no a> ::= <no a m> | <no a m>m<no a>
<not m> ::= <no a m> | <exp>a
<no a m> ::= b<no a m> | 0 | 1
However, according to the "rules" I came up this must be wrong. But since its the instructor solutions to its safer to assume I am wrong and need to refine my understanding.
The reason I think its wrong is that the first rule there is a <not m> to the left of m. That means we can generate an a. But a has lower precedence than m, so according to my rule it must never appear bellow the parse tree of m, but it does. So it seems I do not understand precedence properly or the algorithm to enforce it.
My understanding is that precedence means that if you have higher precedence then you bind tighter than other operators, so you steal the arguments from others. Even better, operators with higher precedence become the operands of operators with lower precedence, so the way I understand it is, if there are two operators and then the higher precedence one is computed first e.g. $2+3*4 \to 2+(3*4)$ if $* >_p +$. I was also told that means that you appear lower in the parse tree, which intuitively makes sense (but I am having issue algorithmically translating this to a way to build grammars). But that's too vague for me to really unambiguously and formally define a way to resolve precedence in any grammar (assuming I only want to resolve precedence and associativity only and solving that "solves the grammar").
So is my understanding correct? Can someone help me make my algorithms for resolving these issue more rigorous (and ideally bullet proof)?
Note, I am aware that resolving ambiguity is undecidable in general, but I was told precedence and associativity is not undecidable assuming thats all we want. So thats what Im looking for.
Appendix 1:
As an interesting string to ponder around from the given grammar is the following:
b0m0am1
which should have parse tree as follows:
((((b0)m0)a)m1)
Appendix2:
I was given the following example to help me (but its not helping to much, its still to vague):
<start> = <a>
<a> = <b> | <a> * <b>
<b> = <c> | <c> + <b>
<c> = 0 | 1 | ( <a> )
Now, assuming that is the start non-terminal, "+" has higher precedence than "" in the grammar. because when you start with , you do not need to go through any non-terminal to reach "", but when you start with , you will need to go through another non-terminal to reach "+" in the grammar. So the number of non-terminals that "+" goes through has a longer length than the number of non-terminals the "" goes through. That is why "+" has higher precedence than "".
Cross-posted:
