| 1 |
B() can generate parsers for languages that are em(context-free). This means |
| 2 |
that you define one or more em(constructs), commonly called em(nonterminal |
| 3 |
symbols), and define em(rules) by which they are recognized (or defined). |
| 4 |
|
| 5 |
For example, bf(C++) defines an `tt(expression)' nonterminal. One rule |
| 6 |
defining an expression might be, |
| 7 |
quote( |
| 8 |
"An expression consists of a minus sign and another expression". |
| 9 |
) |
| 10 |
Another rule could be |
| 11 |
quote( |
| 12 |
"An expression can be an integer". |
| 13 |
) |
| 14 |
Rules often are recursive, but there must be at least one rule ending the |
| 15 |
recursion. |
| 16 |
|
| 17 |
A commonly used formal system for describing such rules is the em(Backus-Naur |
| 18 |
Form) or `BNF', which was developed for specifying the language Algol 60. Any |
| 19 |
grammar expressed in BNF is a context-free grammar. The input to b() is |
| 20 |
essentially machine-readable BNF. |
| 21 |
|
| 22 |
Not all context-free languages can be handled by b(), only those that are |
| 23 |
LALR(1). In brief, this means that it must be possible to tell how to parse |
| 24 |
input while `looking ahead' to just a single token. Strictly speaking, that is |
| 25 |
a description of an LR(1) grammar, and LALR(1) involves some additional |
| 26 |
restrictions which are not further elaborated in the current context; but it |
| 27 |
in real life almost all LR(1) grammars are also LALR(1) grammars. See section |
| 28 |
ref(MYSTERIOUS) for more information on this. |
| 29 |
|
| 30 |
In the formal rules defining a language's grammar, the grammar's constructs |
| 31 |
are called nonterminals. Some symbols are not further defined, but are |
| 32 |
directly made available when matching the input to a series of regular |
| 33 |
expressions. Matching the input to regular expressions is not the task of a |
| 34 |
parser, but of a em(lexical scanner) (e.g., bf(flexc++)(1)). Lexical scanners |
| 35 |
provide the parser with symbols, called em(tokens) or em(terminal symbols), |
| 36 |
which are taken for granted by the parser. |
| 37 |
|
| 38 |
Terminal and nonterminal symbols are used to define the rules of grammars. |
| 39 |
|
| 40 |
|
| 41 |
We can use examples from bf(C++) to illustrate terminal and nonterminal |
| 42 |
symbols. bf(C++)'s terminal symbols are identifiers, constants (numeric and |
| 43 |
string), various keywords, arithmetic operators, and other simple character |
| 44 |
tokens. So the terminal symbols of a grammar for bf(C++) can thus be |
| 45 |
`IDENTIFIER', `NUMBER', `STRING', as wel as tokens for keywords |
| 46 |
(e.g., tt(FOR, SWITCH), operators (tt('+', BIT_OR)), |
| 47 |
and character tokens like tt(';', ':', '(', ')') ). |
| 48 |
|
| 49 |
Here is a simple bf(C++) function subdivided into tokens: |
| 50 |
verb( |
| 51 |
int square(int x) // INT IDENTIFIER '(' INT IDENTIFIER ')' |
| 52 |
{ // '{' |
| 53 |
return x * x; // RETURN IDENTIFIER '*' IDENTIFIER ';' |
| 54 |
} // '}' |
| 55 |
) |
| 56 |
|
| 57 |
bf(C++) rules include expression rules, statement rules, rules defining |
| 58 |
declarations, and rules defining functions. These are defined in bf(C++)'s |
| 59 |
grammar as nonterminal symbols `expression', `statement', `declaration' and |
| 60 |
`function_definition'. The above example shows a function definition as well |
| 61 |
as the sequence of tokens (starting from tt(INT), ending at tt('}')), received |
| 62 |
by the parser when that definition shows up in its input. |
| 63 |
|
| 64 |
Each nonterminal symbol must be defined by at least one so-called |
| 65 |
em(production rule), defining the sequence of symbols that must have been |
| 66 |
observed before it can be decided that the nonterminal symbol has been |
| 67 |
encountered. For example, one kind of bf(C++) statement is the return |
| 68 |
statement; it could be described by the following informal rule: |
| 69 |
|
| 70 |
quote( |
| 71 |
A `statement' can be made of a `return' keyword, an `expression' and a |
| 72 |
`semicolon'. |
| 73 |
) |
| 74 |
|
| 75 |
Formally, such a rule is written like this: |
| 76 |
verb( |
| 77 |
statement: |
| 78 |
RETURN expression ';' |
| 79 |
; |
| 80 |
) |
| 81 |
and in general grammar rules have the following form: |
| 82 |
verb( |
| 83 |
nonterminal: |
| 84 |
production(s) |
| 85 |
; |
| 86 |
) |
| 87 |
where em(nonterminal) is the nonterminal symbol defined by the rule and |
| 88 |
em(productions(s)) are one or more sequences of terminal and nonterminal |
| 89 |
symbols that define how tt(nonterminal) can be recognized. Concentrating on a |
| 90 |
single production rule, the rule's nonterminal is called the rule's left-hand |
| 91 |
side (LHS), the production rule itself is called the rule's right-hand side |
| 92 |
(RHS). In the tt(statement) example the LHS equals tt(statement), the RHS |
| 93 |
equals tt(RETURN expression ';'). The RHS consists of three elements, |
| 94 |
numbered, respectively, 1 through 3. |
| 95 |
|
| 96 |
One nonterminal symbol is special in that it defines a syntactically correct |
| 97 |
specification of the defined language. It is called the em(start symbol). In a |
| 98 |
compiler this means a complete input program. In bf(C++), a nonterminal symbol |
| 99 |
`optional-sequence-of-definitions-and-declarations' could be used for this. |
| 100 |
|
| 101 |
The parser generated by b() reads a sequence of tokens, and combines the |
| 102 |
tokens using the rules of the specified grammar. If the input is valid, the |
| 103 |
end result is that the entire token sequence reduces to the start symbol |
| 104 |
nonterminal. If we use bf(C++)'s grammar, then the entire input must reducible |
| 105 |
to `optional-sequence-of-definitions-and-declarations'. If not, the parser |
| 106 |
reports a syntax error. |
| 107 |
|