Debian Codegraph @

documentation/manual/concepts/languages.yo

raw
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