Debian Codegraph @

documentation/manual/grammar/recursive.yo

raw
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