1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
A rule is called em(recursive) when its em(result) nonterminal appears also in
its production rules. Nearly all b() grammars use recursion, because
that is the only way to define a sequence of any number of
somethings. Consider this recursive definition of a comma-separated sequence
of one or more expressions:
verb(
expseq1:
expseq1 ',' exp
|
exp
;
)
Since the recursive use of expseq1 is the leftmost symbol in the right
hand side, we call this em(left recursion). By contrast, here the same
construct is defined using em(right recursion):
verb(
expseq1:
exp ',' expseq1
|
exp
;
)
Any kind of sequence can be defined using either left recursion or right
recursion, but whenever possible use left recursion, because it can parse a
sequence of any number of elements given a limited stack space. Right
recursion consumes stack space proportionally to the number of
elements in the sequence, because all elements must be pushed on the
stack before the rule can be applied even once. See chapter ref(ALGORITHM) for
further explanation of this phenomenon.
em(Indirect) or em(mutual) recursion occurs when the result of the rule does
not appear directly on its right hand side, but does appear in rules for other
nonterminals which do appear on its right hand side. For example:
verb(
expr:
primary '+' primary
|
primary
;
primary:
constant
|
'(' expr ')'
;
)
defines two mutually-recursive nonterminals, since each refers to the
other.
|
