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

Construct the LL(1) parsing table.b. Give evidence that this grammar is not LL(1).c. Modify the grammar as little as possible to make an LL(1) grammar thataccepts the same language.*3.7. Left-factor this grammar.1.S→G$2.G→P3.G → PG4.P → id : R5.R→786.••••R → id Ra. Show that the resulting grammar is LL(2). You can do this by constructingFIRST sets (etc.) containing two-symbol strings; but it is simpler to constructan LL(1) parsing table and then argue convincingly that any conflicts can beresolved by looking ahead one more symbol.b.

Show how the tok variable and advance function should be altered forrecursive-descent parsing with two-symbol lookahead.c. Use the grammar class hierarchy (Figure 3.29) to show that the (leftfactored)grammar is LR(2).d. Prove that no string has two parse trees according to this (left-factored)grammar.3.8 Make up a tiny grammar containing left recursion, and use it to demonstrate thatleft recursion is not a problem for LR parsing.

Then show a small example comparinggrowth of the LR parse stack with left recursion versus right recursion.3.9 Diagram the LR(0) states for Grammar 3.26, build the SLR parsing table, andidentify the conflicts.3.10 Diagram the LR(1) states for the grammar of Exercise 3.7 (without leftfactoring), and construct the LR(1) parsing table.

Indicate clearly any conflicts.3.11 Construct the LR(0) states for this grammar, and then determine whether it is anSLR grammar.0. S → B $1. B → id P2. B → id *(E ]3. P →4. P → (E)5. E → B•6. E → B, E3.12. Build the LR(0) DFA for this grammar:S→E$0.1.E → id2.E → id (E)3.•E → E + ida. Is this an LR(0) grammar? Give evidence.b.

Is this an SLR grammar? Give evidence.c. Is this an LR(1) grammar? Give evidence.3.13 Show that this grammar is LALR(1) but not SLR:0. S → X $1. X → Ma2. X → bMc3. X → dc4. X → bda•5. M → d3.14 Show that this grammar is LL(1) but not LALR(1):0. S → (X1. S → E]792. S → F)3. X → E)4. X → F]5.

E → A6. F → A•7. A →*3.15 Feed this grammar to Yacc; from the output description file, construct theLALR(1) parsing table for this grammar, with duplicate entries where there areconflicts. For each conflict, show whether shifting or reducing should be chosen sothat the different kinds of expressions have "conventional" precedence. Then show theYacc-style precedence directives that resolve the conflicts this way.0. S → E $1. E → while E do E2. E → id := E3. E → E + E•4.

E → id*3.16 Explain how to resolve the conflicts in this grammar, using precedencedirectives, or grammar transformations, or both. Use Yacc or SableCC as a tool inyour investigations, if you like.0. E → id1. E → EBE2. B → +3. B → −4. B → ו5.

B → /*3.17 Prove that Grammar 3.8 cannot generate parse trees of the form shown in Figure3.9. Hint: What nonterminals could possibly be where the ?X is shown? What doesthat tell us about what could be where the ?Y is shown?80Chapter 4: Abstract Syntaxab-stract: disassociated from any specific instanceWebster's DictionaryOVERVIEWA compiler must do more than recognize whether a sentence belongs to the language of agrammar - it must do something useful with that sentence.

The semantic actions of a parsercan do useful things with the phrases that are parsed.In a recursive-descent parser, semantic action code is interspersed with the control flow of theparsing actions. In a parser specified in JavaCC, semantic actions are fragments of Javaprogram code attached to grammar productions. SableCC, on the other hand, automaticallygenerates syntax trees as it parses.4.1 SEMANTIC ACTIONSEach terminal and nonterminal may be associated with its own type of semantic value.

Forexample, in a simple calculator using Grammar 3.37, the type associated with exp and INTmight be int; the other tokens would not need to carry a value. The type associated with atoken must, of course, match the type that the lexer returns with that token.For a rule A → B C D, the semantic action must return a value whose type is the oneassociated with the nonterminal A.

But it can build this value from the values associated withthe matched terminals and nonterminals B, C, D.RECURSIVE DESCENTIn a recursive-descent parser, the semantic actions are the values returned by parsingfunctions, or the side effects of those functions, or both. For each terminal and nonterminalsymbol, we associate a type (from the implementation language of the compiler) of semanticvalues representing phrases derived from that symbol.Program 4.1 is a recursive-descent interpreter for part of Grammar 3.15. The tokens ID andNUM must now carry values of type string and int, respectively.

We will assume there is alookup table mapping identifiers to integers. The type associated with E; T; F; etc., is int,and the semantic actions are easy to implement.PROGRAM 4.1: Recursive-descent interpreter for part of Grammar 3.15.class Token {int kind; Object val;Token(int k, Object v) {kind=k; val=v;}}final int EOF=0, ID=1, NUM=2, PLUS=3, MINUS=4, ...int lookup(String id) { ... }int F_follow[] = { PLUS, TIMES, RPAREN, EOF };int F() {switch (tok.kind) {case ID: int i=lookup((String)(tok.val)); advance(); return i;81case NUM: int i=((Integer)(tok.val)).intValue();advance(); return i;case LPAREN: eat(LPAREN);int i = E();eatOrSkipTo(RPAREN, F_follow);return i;case EOF:default:print("expected ID, NUM, or left-paren");skipto(F_follow); return 0;}}int T_follow[] = { PLUS, RPAREN, EOF };int T() {switch (tok.kind) {case ID:case NUM:case LPAREN: return Tprime(F());default: print("expected ID, NUM, or left-paren");skipto(T_follow);return 0;}}int Tprime(int a) {switch (tok.kind) {case TIMES: eat(TIMES); return Tprime(a*F());case PLUS:case RPAREN:case EOF: return a;default: ...}}void eatOrSkipTo(int expected, int[] stop) {if (tok.kind==expected)eat(expected);else {print(...); skipto(stop);}}The semantic action for an artificial symbol such as T′ (introduced in the elimination of leftrecursion) is a bit tricky.

Had the production been T → T * F, then the semantic action wouldhave beenint a = T(); eat(TIMES); int b=F(); return a*b;With the rearrangement of the grammar, the production T′ → *FT′ is missing the left operandof the *. One solution is for T to pass the left operand as an argument to T′, as shown inProgram 4.1.AUTOMATICALLY GENERATED PARSERSA parser specification for JavaCC consists of a set of grammar rules, each annotated with asemantic action that is a Java statement. Whenever the generated parser reduces by a rule, itwill execute the corresponding semantic action fragment.Program 4.2 shows how this works for a variant of Grammar 3.15.

Every INTEGER_CONSTANTterminal and every nonterminal (except Start) carries a value. To access this value, give theterminal or nonterminal a name in the grammar rule (such as i in Program 4.2), and accessthis name as a variable in the semantic action.82PROGRAM 4.2: JavaCC version of a variant of Grammar 3.15.void Start() :{ int i; }{ i=Exp() <EOF> { System.out.println(i); }}int Exp() :{ int a,i; }{ a=Term()( "+" i=Term() { a=a+i; }| "-" i=Term() { a=a-i; })*{ return a; }}int Term() :{ int a,i; }{ a=Factor()( "*" i=Factor() { a=a*i; }| "/" i=Factor() { a=a/i; })*{ return a; }}int Factor() :{ Token t; int i; }{ t=<IDENTIFIER>{ return lookup(t.image); }| t=<INTEGER_LITERAL> { return Integer.parseInt(t.image); }| "(" i=Exp() ")"{ return i; }}SableCC, unlike JavaCC, has no way to attach action code to productions. However, SableCCautomatically generates syntax tree classes, and a parser generated by SableCC will buildsyntax trees using those classes.

For JavaCC, there are several companion tools, includingJJTree and JTB (the Java Tree Builder), which, like SableCC, generate syntax tree classes andinsert action code into the grammar for building syntax trees.4.2 ABSTRACT PARSE TREESIt is possible to write an entire compiler that fits within the semantic action phrases of aJavaCC or SableCC parser. However, such a compiler is difficult to read and maintain, andthis approach constrains the compiler to analyze the program in exactly the order it is parsed.To improve modularity, it is better to separate issues of syntax (parsing) from issues ofsemantics (type-checking and translation to machine code).