188 Chapter 4 Lexical and Syntax Analysis
Because there is no left recursion in the F-rules, they remain the same, so the
complete replacement grammar isE→T E
E→+ T E
T→F T
T→* F T
F →(E) id
This grammar generates the same language as the original grammar but is not
left recursive.
As was the case with the expression grammar written using EBNF in
Section 4.4.1, this grammar does not specify left associativity of operators.
However, it is relatively easy to design the code generation based on this
grammar so that the addition and multiplication operators will have left
associativity.
Indirect left recursion poses the same problem as direct left recursion. For
example, suppose we haveA→B a A
B→A b
A recursive-descent parser for these rules would have the A subprogram imme-
diately call the subprogram for B, which immediately calls the A subprogram.
So, the problem is the same as for direct left recursion. The problem of left
recursion is not confined to the recursive-descent approach to building top-
down parsers. It is a problem for all top-down parsing algorithms. Fortunately,
left recursion is not a problem for bottom-up parsing algorithms.
There is an algorithm to modify a given grammar to remove indirect left
recursion (Aho et al., 2006), but it is not covered here. When writing a gram-
mar for a programming language, one can usually avoid including left recur-
sion, both direct and indirect.
Left recursion is not the only grammar trait that disallows top-down pars-
ing. Another is whether the parser can always choose the correct RHS on the
basis of the next token of input, using only the first token generated by the
leftmost nonterminal in the current sentential form. There is a relatively simple
test of a non–left recursive grammar that indicates whether this can be done,
called the pairwise disjointness test. This test requires the ability to compute
a set based on the RHSs of a given nonterminal symbol in a grammar. These
sets, which are called FIRST, are defined asFIRST()={a =>* a} (If =>* , is in FIRST())
in which =>* means 0 or more derivation steps.
An algorithm to compute FIRST for any mixed string can be found in
Aho et al. (2006). For our purposes, FIRST can usually be computed by inspec-
tion of the grammar.