Operator Precedence Grammar:
- It is an operator grammar for which the precedence relations constructed using method 2 are disjoint. That means for any pair of terminals a and b, at any time, only one of the relations a <. b, a $\overset{.}{\mathop{=}}\,$ b and a .> b is true
- Consider the operator grammar: E → E + E | E * E | (E) | id
- This is not an operator grammar, because more than one precedence relation holds between certain pair of terminals
- For example + and + i.e., + +.> and + + <.
Problems
Check whether the following grammars are operator precedence
or not,
E → E + E |
E * E | (E) | id
S → a | b |
(T)
T → T , S |
S
Algorithm overview:
- Once precedence relations are define, take the input string to be parsed and write the relations between the terminal present in it
- For example, consider the string id + id * id to be parsed by the precedence relations table
id
|
+
|
*
|
$
|
|
id
|
.>
|
.>
|
.>
|
|
+
|
<.
|
.>
|
<.
|
.>
|
*
|
<.
|
.>
|
.>
|
.>
|
$
|
<.
|
<.
|
<.
|
- After establishing precedence relations, the string becomes
$<.id.>+<.id.>*<.id.>$
- Now scan the string until the first .> is seen
- Go back from the position in step1 until the first <. Is seen (cross over $\overset{.}{\mathop{=}}\,$ )
- Now everything between <. and .> is the handle
- Reduce the handle, re-establish relations after ignoring non-terminals and goto step1 until the string remained is $$
- The first handle in the string is id. After reducing it to E and ignoring E, we get, $\$+id*id\$$ and after re-establishing relations and after two more reductions, we get $\$+*\$$ and after re-establishing relations we get, $\$<.+<.*.>\$$
- Now, we need to reduce * and then after + to finally announce successful parsing (when we reduce * or + there are non-terminals surrounding them. We can assume them generally as ignored)
Home
|
