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