Page 206 - DCAP507_SYSTEM_SOFTWARE

System Software

Notes

The comprehensible difficulty of modifying the grammar to take away ambiguity is that it may
make difficult and difficult to understand the original grammar definitions. There is no
mechanical means to alter any ambiguous grammar into an unmistakable one.

Notes Though, most programming languages have only restricted concerns with ambiguity
that can be resolved by means of ad hoc techniques.
Recursive Productions

Productions are frequently defined in terms of themselves.

Example: A list of variables in a programming language grammar could be declared by
this production:
variable_list  variable | variable_list , variable
Such productions are considered to be recursive. If the recursive nonterminal is at the left of the
right-side of the production, e.g. A  u | Av, we call the production left-recursive. Likewise, we
can define a right-recursive production: A  u | vA. Some parsing methods have trouble with
one or the other alternatives of recursive productions and so at times we have to massage the
grammar into a dissimilar but equivalent form.

!
Caution Left-recursive productions can be particularly troublesome in the top-down parsers.
Usefully, there is an easy technique for rewriting the grammar to shift the recursion to the other
side.

Example: Consider this left-recursive rule:
X  Xa | Xb | AB | C | DEF
To translate the rule, we introduce a new nonterminal X' that we attach to the end of all non-left-
recursive productions for X. The expansion for the new nonterminal is fundamentally the reverse
of the original left-recursive rule. The rewritten productions are:
X  ABX' | C

X' | DEFX' X'  aX' | bX' | 
It occurs we just exchanged the left-recursive rules for a corresponding right-recursive edition.
This might appears to be pointless, but some parsing algorithms favor or even need only left or
right recursion.

200 LOVELY PROFESSIONAL UNIVERSITY