Consider the definition of
input: /* empty */ | input line ;
This definition reads as follows: “A complete input is either an empty
string, or a complete input followed by an input line”. Notice that
“complete input” is defined in terms of itself. This definition is said
to be left recursive since
input appears always as the
leftmost symbol in the sequence. See Recursive Rules.
The first alternative is empty because there are no symbols between the
colon and the first ‘|’; this means that
input can match an
empty string of input (no tokens). We write the rules this way because it
is legitimate to type Ctrl-d right after you start the calculator.
It's conventional to put an empty alternative first and write the comment
‘/* empty */’ in it.
The second alternate rule (
input line) handles all nontrivial input.
It means, “After reading any number of lines, read one more line if
possible.” The left recursion makes this rule into a loop. Since the
first alternative matches empty input, the loop can be executed zero or
The parser function
yyparse continues to process input until a
grammatical error is seen or the lexical analyzer says there are no more
input tokens; we will arrange for the latter to happen at end-of-input.