Page 205 - DCAP507_SYSTEM_SOFTWARE

Unit 13: Formal Systems

Notes
Example: Consider the expression 10 - 2 * 5. We parse by primarily applying the production
E  E op E. The parse tree on the left selects to expand that first op to *, the one on the right to -. We
have two entirely different parse trees. Which one is correct?

Both trees are authorized in the grammar as affirmed and therefore either interpretation is
valid. Even though natural languages can stand some type of ambiguity (e.g., puns, plays on
words, etc.), it is not suitable in computer languages. We don't want the compiler just randomly
deciding which way to understand our expressions! Given our expectations from algebra about
precedence, only one of the trees appears to be right. The right-hand tree fits our anticipation
that * "binds tighter" and for that consequence to be calculated first then integrated in the outer
expression which has a lower preference operator. It's moderately simple for a grammar to turn
out to be ambiguous if you are not cautious in its construction. Regrettably, there is no
supernatural method that can be used to resolve all varieties of vagueness. It is an undecidable
difficulty to conclude whether any grammar is vague, much less to effort to mechanically take
away all ambiguity. Though, that doesn't signify in practice that we cannot notice vagueness or
do something regarding it. For programming language grammars, we typically take pains to
build an unambiguous grammar or initiate additional disambiguating rules to throw away the
unwanted parse trees, leaving only one for each sentence. By means of the above ambiguous
expression grammar, one method would leave the grammar as is, but add disambiguating rules
into the parser execution. We could code into the parser knowledge of precedence and
associatively to break the tie and force the parser to construct the tree on the right instead of the
left. The benefit of this is that the grammar remains easy and less complicated. But as a downside,
the syntactic structure of the language is no longer specified by the grammar alone.
Another strategy is to alter the grammar to only permit the one tree that appropriately reflects
our purpose and eradicate the others. For the expression grammar, we can disconnect expressions
into multiplicative and additive subgroups and force them to be prolonged in the preferred
order.
E  E
t_op E | T t_op  + | -
T  T
f_op T | F f_op  * | /
F  (E) | int
Terms are addition/subtraction expressions and factors utilized for multiplication and division.
As the base case for expression is a term, addition and subtraction will emerge higher in the
parse tree, and therefore obtain lower precedence. After confirming that the above rewritten
grammar has only one parse tree for the previous ambiguous expression, you might thing we
were home free, but now consider the expression 10 –2 –5. The recursion on both sides of the
binary operator permits either side to match repetitions. The arithmetic operators typically
connect to the left, so by substituting the right-hand side with the base case will force the
repetitive matches onto the left side. The concluding result is:

LOVELY PROFESSIONAL UNIVERSITY 199