How to Establish Precedence Relations
This comprises two methods
Method 1
- This method based on the traditional notions of associativity and precedence of operators
- This method automatically resolves ambiguities in the grammar
Method 2
- This method requires the grammar to be unambiguous first and uses an algorithm to establish the precedence relations
- The relations may be disjoint and the parser may accept some sentences which are not available in the language
Method 1:
- Consider the grammar: E → E + E | E * E | id
- Then the precedence relations are given by
id
|
+
|
*
|
$
|
|
id
|
.>
|
.>
|
.>
|
|
+
|
<.
|
.>
|
<.
|
.>
|
*
|
<.
|
.>
|
.>
|
.>
|
$
|
<.
|
<.
|
<.
|
(+ and + are of equal of precedence and are left associative
* and * are equal precedence and are left associative
+ has less precedence than *
* has more precedence
than +
As a general rule, all terminals have precedence over $ and
vice versa).
Method 2:
- To establish precedence relations between two operators a and b, use the following rules:
- a $\overset{.}{\mathop{=}}\,$ b, if there is a right side of a production of the form αaβbγ, where β is either a single non-terminal or ε. That means if a = b appears immediately to the left of b in a right side or if they are separated by a single non-terminal
- a <. B, if for some non-terminal A there is a right side of a form αaβbβ, and A → γbβ, where γ is either a single non-terminal or ε. That means if a <. B is a non-terminal then ‘A’ appears immediately to the right of a and derives strings in which b is the first terminal
- a .> b, if for some non-terminal A there is a right side of the for αAbβ and A → γaδ, where δ is either a single non-terminal or ϵ. That means if a .> b is a non-terminal, ‘A’ appears immediately to the left of b and derives strings in which a is the last terminal
The easy way to construct precedence relations using method
2 is by first computing two important sets for each non-terminals present in
the grammar, known as,
- LEADING
- TRAILING
For some non-terminals A, they are defined as
LEADING(A) ={a | A →
γaδ, where γ is a single non-terminal or
ε}
TRAILING(A) = {a | A → γaδ, where δ is a single non-terminal or ε}
TRAILING(A) = {a | A → γaδ, where δ is a single non-terminal or ε}
For example, consider the grammar
E → E + T
E → T
T → T * F
T → F
F → (E)
Non-Terminal
|
LEADING
|
TRAILING
|
E
|
*,+,(,id
|
*,+,),id
|
T
|
*,(,id
|
*,),id
|
F
|
(,id
|
),id
|
Note: Leading and Trailing are
not similar to first and follow
Once LEADING and TRAILING are computes, the precedence relations
using the following algorithm can be established
Set <. a for all a in LEADING(S) and set b .> for
all b in TRAILING(S), where S is the start symbol of the given grammar.
For each production A →
${{X}_{1}}{{X}_{2}}{{X}_{3}}{{X}_{4}}.............{{X}_{n}}$ do
for i:= 1 to n-1 do
begin
if i <=
n-2 and Xi and Xi + 2 are terminals and Xi + 1 is a terminal then set
Xi
$\overset{.}{\mathop{=}}\,$ Xi + 2
if Xi
is a terminal and Xi + 1 is a non-terminal then for all a in LEADING(Xi + 1)
do
set Xi <. a
if Xi
is a non-terminal and Xi + 1 is a terminal then for all a in LEADING (Xi + 1)
do
set a .> Xi + 1
end
+
|
*
|
(
|
)
|
id
|
$
|
|
+
|
.>
|
<.
|
<.
|
.>
|
<.
|
.>
|
*
|
.>
|
.>
|
<.
|
.>
|
<.
|
.>
|
(
|
<.
|
<.
|
<.
|
$\overset{.}{\mathop{=}}\,$
|
<.
|
|
)
|
.>
|
.>
|
.>
|
.>
|
||
id
|
.>
|
.>
|
.>
|
.>
|
||
$
|
<.
|
<.
|
<.
|
<.
|
