| 1 |
Consider the definition of tt(input): |
| 2 |
verb( |
| 3 |
input: |
| 4 |
// empty |
| 5 |
| |
| 6 |
input line |
| 7 |
; |
| 8 |
) |
| 9 |
This definition should be read as follows: em(A complete input is either |
| 10 |
an empty string, or a complete input followed by an input line). Notice that |
| 11 |
`complete input' is defined in terms of itself. This definition is said to be |
| 12 |
em(left recursive) since the rule's nonterminal (tt(input)) appears as the |
| 13 |
leftmost symbol in the production rule. See section ref(RECURSIVE). |
| 14 |
|
| 15 |
The first alternative is empty: there are no symbols between the colon and the |
| 16 |
first `tt(|)'; this means that input can match an empty string of input (no |
| 17 |
tokens). We write the rules this way because it is legitimate to type |
| 18 |
tt(Ctrl-d) (end of input) immediately after starting the calculator. By |
| 19 |
convention empty alternatives are provided with the comment `tt(// empty)'. |
| 20 |
|
| 21 |
The second production rule (`tt(input line)') handles all nontrivial input. It |
| 22 |
means em(after reading any number of lines, read one more line). The left |
| 23 |
recursion turns this rule into a loop: it processes any number of lines. |
| 24 |
|
| 25 |
The parser's parsing function continues to process input until a grammatical |
| 26 |
error is encountered or untilthe lexical analyzer returns the end-of-file |
| 27 |
token. |
| 28 |
|