Page 207 - DCAP507_SYSTEM_SOFTWARE

Unit 13: Formal Systems

Notes

Task Illustrate how to define right-recursive production.

Left-factoring

The parser typically reads tokens from left to right and it is suitable if, upon reading a token, it
can make an instant decision regarding which production from the grammar to develop. However,
this can be difficulty if there are productions that have general first symbol(s) on the right side
of the productions.

Example: Here is an example we frequently observe in programming language grammars:
Stmt  if Cond then Stmt else Stmt | if Cond then Stmt | Other | ....
The common prefix is if Cond then Stmt. This causes troubles since when a parser encounter an
"if", it does not recognize which production to utilize. A functional technique known as left-
factoring allows us to reorganize the grammar to evade this circumstance. We rephrase the
productions to postpone the decision regarding which of the choices to choose until we have
seen sufficient of the input to make the suitable choice. We factor out the common division of the
two choices into a shared rule that both will utilize and then add a new rule that picks up where
the tokens deviate.
Stmt  if Cond then Stmt
OptElse | Other | … OptElse -> else S | 
In the rewritten grammar, upon reading an "if" we increase first production and stay until if
Cond then Stmt has been observed to decide whether to expand OptElse to else or ?

Hidden left-factors and Hidden left recursion

A grammar may not emerge to have left recursion or left factors, yet still have concerns that will
obstruct with parsing. This may be since the concerns are concealed and require to be first
exposed through replacement.

Example: Consider this grammar:
A  da | acB
B  abB | daA | Af
A brief examination of the grammar may not sense that the first and second productions of B
partly cover the third. We alternate the expansions for A into the third production to represent
at this:
A  da | acB
B  abB | daA | daf | acBf
This swaps the original third production of B for numerous new productions, one for every
productions for A. These directly demonstrate the overlap, and we can then left factor:
A  da | acB

B  aM | daN
M  bB | cBf
N  A | f

LOVELY PROFESSIONAL UNIVERSITY 201