A.W. Appel, J. Palsberg - Modern Compiler Implementation in Java (Second Edition), страница 11

Also,once we have abbreviations with recursion, we do not need alternation except at the top levelof expressions, because the definitioncan always be rewritten using an auxiliary definition asIn fact, instead of using the alternation mark at all, we can just write several allowableexpansions for the same symbol:The Kleene closure is not necessary, since we can rewrite it so thatbecomesWhat we have left is a very simple notation, called context-free grammars. Just as regularexpressions can be used to define lexical structure in a static, declarative way, grammarsdefine syntactic structure declaratively. But we will need something more powerful than finiteautomata to parse languages described by grammars.In fact, grammars can also be used to describe the structure of lexical tokens, although regularexpressions are adequate - and more concise - for that purpose.3.1 CONTEXT-FREE GRAMMARSAs before, we say that a language is a set of strings; each string is a finite sequence ofsymbols taken from a finite alphabet.

For parsing, the strings are source programs, thesymbols are lexical tokens, and the alphabet is the set of token-types returned by the lexicalanalyzer.A context-free grammar describes a language. A grammar has a set of productions of the formsymbol → symbol symbol … symbolwhere there are zero or more symbols on the right-hand side. Each symbol is either terminal,meaning that it is a token from the alphabet of strings in the language, or nonterminal,meaning that it appears on the left-hand side of some production.

No token can ever appear onthe left-hand side of a production. Finally, one of the nonterminals is distinguished as the startsymbol of the grammar.42Grammar 3.1 is an example of a grammar for straight-line programs. The start symbol is S(when the start symbol is not written explicitly it is conventional to assume that the left-handnonterminal in the first production is the start symbol).

The terminal symbols areid print num, + ( ) := ;GRAMMAR 3.1: A syntax for straight-line programs.1. S → S; S2. S → id := E3. S → print (L)4. E → id5. E → num6. E → E + E7. E → (S, E)8. L → E9. L → L, Eand the nonterminals are S, E, and L. One sentence in the language of this grammar isid := num; id := id + (id := num + num, id)where the source text (before lexical analysis) might have beena : = 7;b : = c + (d : = 5 + 6, d)The token-types (terminal symbols) are id, num, :=, and so on; the names (a,b,c,d) andnumbers (7, 5, 6) are semantic values associated with some of the tokens.DERIVATIONSTo show that this sentence is in the language of the grammar, we can perform a derivation:Start with the start symbol, then repeatedly replace any nonterminal by one of its right-handsides, as shown in Derivation 3.2.DERIVATION 3.2•••••••••••••SS;SS ; id := Eid := E; id := Eid := num ; id := Eid := num ; id := E + Eid := num ; id := E + (S, E)id := num ; id := id + (S, E)id := num ; id := id + (id := E, E)id := num ; id := id + (id := E + E, E)id := num ; id := id + (id := E + E, id )id := num ; id := id + (id := num + E, id)id := num ; id := id + (id := num + num, id)43There are many different derivations of the same sentence.

A leftmost derivation is one inwhich the leftmost nonterminal symbol is always the one expanded; in a rightmost derivation,the rightmost nonterminal is always the next to be expanded.Derivation 3.2 is neither leftmost nor rightmost; a leftmost derivation for this sentence wouldbegin,•••••••SS;Sid := E ; Sid := num ; Sid := num ; id := Eid := num ; id := E + E⋮PARSE TREESA parse tree is made by connecting each symbol in a derivation to the one from which it wasderived, as shown in Figure 3.3.

Two different derivations can have the same parse tree.Figure 3.3: Parse tree.AMBIGUOUS GRAMMARSA grammar is ambiguous if it can derive a sentence with two different parse trees. Grammar3.1 is ambiguous, since the sentence id := id+id+id has two parse trees (Figure 3.4).44Figure 3.4: Two parse trees for the same sentence using Grammar 3.1.Grammar 3.5 is also ambiguous; Figure 3.6 shows two parse trees for the sentence 1-2-3, andFigure 3.7 shows two trees for 1+2*3. Clearly, if we use parse trees to interpret the meaningof the expressions, the two parse trees for 1-2-3 mean different things: (1 − 2) − 3 D−4versus 1 − (2 − 3) D 2. Similarly, (1 + 2) × 3 is not the same as 1 + (2 × 3).

And indeed,compilers do use parse trees to derive meaning.Figure 3.6: Two parse trees for the sentence 1-2-3 in Grammar 3.5.Figure 3.7: Two parse trees for the sentence 1+2*3 in Grammar 3.5.GRAMMAR 3.5•E → id•E → num•E→E*E•E→E/E•E→E+E•E→E−E•E → (E)45GRAMMAR 3.8•E→E+T•T→T*F•F → id•E→E−T•T→T/F•F → num•E→T•T→F•F → (E)Therefore, ambiguous grammars are problematic for compiling: In general, we would preferto have unambiguous grammars.

Fortunately, we can often transform ambiguous grammars tounambiguous grammars.Let us find an unambiguous grammar that accepts the same language as Grammar 3.5. First,we would like to say that * binds tighter than +, or has higher precedence. Second, we want tosay that each operator associates to the left, so that we get (1 − 2) − 3 instead of 1 − (2 − 3).We do this by introducing new nonterminal symbols to get Grammar 3.8.The symbols E, T, and F stand for expression, term, and factor; conventionally, factors arethings you multiply and terms are things you add.This grammar accepts the same set of sentences as the ambiguous grammar, but now eachsentence has exactly one parse tree. Grammar 3.8 can never produce parse trees of the formshown in Figure 3.9 (see Exercise 3.17).Figure 3.9: Parse trees that Grammar 3.8 will never produce.Had we wanted to make * associate to the right, we could have written its production as T →F * T.We can usually eliminate ambiguity by transforming the grammar.

Though there are somelanguages (sets of strings) that have ambiguous grammars but no unambiguous grammar, suchlanguages may be problematic as programming languages because the syntactic ambiguitymay lead to problems in writing and understanding programs.END-OF-FILE MARKERParsers must read not only terminal symbols such as +, −, num, and so on, but also the end-offile marker. We will use $ to represent end of file.46Suppose S is the start symbol of a grammar. To indicate that $ must come after a complete Sphrase, we augment the grammar with a new start symbol S′ and a new production S′ → S$.In Grammar 3.8, E is the start symbol, so an augmented grammar is Grammar 3.10.GRAMMAR 3.10••S→E$•••E→E+TT→T*F•T→T/F•E→E−TT→F•E→T•••F → id•F → num•F → (E)3.2 PREDICTIVE PARSINGSome grammars are easy to parse using a simple algorithm known as recursive descent.

Inessence, each grammar production turns into one clause of a recursive function. We illustratethis by writing a recursive-descent parser for Grammar 3.11.GRAMMAR 3.11•S → if E then S else S•L → end•S → begin S LL→;SL••S → print E•••E → num = numA recursive-descent parser for this language has one function for each nonterminal and oneclause for each production.final int IF=1, THEN=2, ELSE=3, BEGIN=4, END=5, PRINT=6,SEMI=7, NUM=8, EQ=9;int tok = getToken();void advance() {tok=getToken();}void eat(int t) {if (tok==t) advance(); else error();}void S() {switch(tok) {case IF: eat(IF); E(); eat(THEN); S();eat(ELSE); S(); break;case BEGIN: eat(BEGIN); S(); L(); break;case PRINT: eat(PRINT); E(); break;default: error();}}void L() {switch(tok) {case END: eat(END); break;case SEMI: eat(SEMI); S(); L(); break;default: error();47}}void E() { eat(NUM); eat(EQ); eat(NUM); }With suitable definitions of error and getToken, this program will parse very nicely.Emboldened by success with this simple method, let us try it with Grammar 3.10:void S() { E(); eat(EOF); }void E() {switch (tok) {case ?: E(); eat(PLUS); T(); break;case ?: E(); eat(MINUS); T(); break;case ?: T(); break;default: error();}}void T() {switch (tok) {case ?: T(); eat(TIMES); F(); break;case ?: T(); eat(DIV); F(); break;case ?: F(); break;default: error();}}There is a conflict here: The E function has no way to know which clause to use.

Consider thestrings (1*2-3)+4 and (1*2-3). In the former case, the initial call to E should use the E → E+ T production, but the latter case should use E → T.Recursive-descent, or predictive, parsing works only on grammars where the first terminalsymbol of each subexpression provides enough information to choose which production touse. To understand this better, we will formalize the notion of FIRST sets, and then deriveconflict-free recursive-descent parsers using a simple algorithm.Just as lexical analyzers can be constructed from regular expressions, there are parsergenerator tools that build predictive parsers.

But if we are going to use a tool, then we mightas well use one based on the more powerful LR(1) parsing algorithm, which will be describedin Section 3.3.Sometimes it's inconvenient or impossible to use a parser-generator tool. The advantage ofpredictive parsing is that the algorithm is simple enough that we can use it to construct parsersby hand - we don't need automatic tools.FIRST AND FOLLOW SETSGiven a string γ of terminal and nonterminal symbols, FIRST(γ) is the set of all terminalsymbols that can begin any string derived from γ. For example, let γ = T * F.

Any string ofterminal symbols derived from γ must start with id, num, or (. Thus, FIRST(T * F) = {id,num, (}.If two different productions X → γ1 and X → γ2 have the same lefthand-side symbol (X) andtheir right-hand sides have overlapping FIRST sets, then the grammar cannot be parsed usingpredictive parsing. If some terminal symbol I is in FIRST(γ1) and also in FIRST(γ2), then theX function in a recursive-descent parser will not know what to do if the input token is I.48The computation of FIRST sets looks very simple: If γ = X Y Z, it seems as if Y and Z can beignored, and FIRST(X) is the only thing that matters. But consider Grammar 3.12.