龙书第二章部分答案
第二章 2.2 Exercises for Section 2.2
2.2.1
Consider the context-free grammar:
S -> S S + | S S * | a
1 Show how the string aa+a* can be generated by this grammar.
2 Construct a parse tree for this string.
3 What language does this grammar generate? Justify your answer. answer
4 S -> S S * -> S S + S * -> a S + S * -> a a + S * -> a a + a *
5
6 L = {Postfix expression consisting of digits, plus and multiple signs}
2.2.2
What language is generated by the following grammars? In each case justify your answer.
7 S -> 0 S 1 | 0 1
8 S -> + S S | - S S | a
9 S -> S ( S ) S | ε
10 S -> a S b S | b S a S | ε
11 ⧗ S -> a | S + S | S S | S * | ( S )
answer
12 L = {0n 1n | n>=1}
13 L = {Prefix expression consisting of plus and minus signs}
14 L = {Matched brackets of arbitrary arrangement and nesting, includes ε} 15 L = {String has the same amount of a and b, includes ε}
16 ？
2.2.3
Which of the grammars in Exercise 2.2.2 are ambiguous
answer
17 No
18 No
Yes
Yes
Yes
2.2.4
Construct unambiguous context-free grammars for each of the following languages. In each case show that your grammar is correct.
19 Arithmetic expressions in postfix notation.
20 Left-associative lists of identifiers separated by commas.
21 Right-associative lists of identifiers separated by commas.
22 Arithmetic expressions of integers and identifiers with the four binary operators +, - , *, /.
answer
2.2.5
Show that all binary strings generated by the following grammar have values divisible by 3. Hint. Use induction on the number of nodes in a parse tree.
num -> 11 | 1001 | num 0 | num num
Does the grammar generate all binary strings with values divisible by 3?
answer
prove
any string derived from the grammar can be considered to be a sequence consisting of 11, 1001 and 0, and not prefixed with 0.
the sum of this string is:
sum
= Σn (21 + 20) * 2 n + Σm (23 + 20) * 2m
= Σn 3 * 2 n + Σm 9 * 2m
It is obviously can divisible by 3.
No. Consider string "10101", it is divisible by 3, but cannot derived from the grammar. Question: any general prove?
2.2.6
Construct a context-free grammar for roman numerals.
Note: we just consider a subset of roman numerals which is less than 4k.
answer
wikipedia: Roman_numerals
via wikipedia, we can categorize the single noman numerals into 4 groups:
then get the production:
and we can find a simple way to map roman to arabic numerals. For example:
o XII => X, II => 10 + 2 => 12
o CXCIX => C, XC, IX => 100 + 90 + 9 => 199
o MDCCCLXXX => M, DCCC, LXXX => 1000 + 800 + 80 => 1880
via the upper two rules, we can derive the production:
romanNum -> thousand hundred ten digit
thousand -> M | MM | MMM | ε
hundred -> smallHundred | C D | D smallHundred | C M
smallHundred -> C | CC | CCC | ε
ten -> smallTen | X L | L smallTen | X C
smallTen -> X | XX | XXX | ε
digit -> smallDigit | I V | V smallDigit | I X
smallDigit -> I | II | III | ε
2.3 Exercises for Section 2.3
2.3.1
Construct a syntax-directed translation scheme that trans lates arithmetic expressions from infix notation into prefix notation in which an operator appears before its operands; e.g. , -xy is the prefix notation for x - y . Give annotated parse trees for the inputs 9-5+2 and 9-5*2.。
answer
productions:
translation schemes:
2.3.2
Construct a syntax-directed translation scheme that trans lates arithmetic expressions from postfix notation into infix notation. Give annotated parse trees for the inputs 95-2* and 952*-.
answer
productions:
translation schemes:
Another reference answer
2.3.3
Construct a syntax-directed translation scheme that trans lates integers into roman numerals
answer
assistant function:
translation schemes:
2.3.4
Construct a syntax-directed translation scheme that trans lates roman numerals into integers.
answer
productions:
translation schemes:
2.3.5
Construct a syntax-directed translation scheme that trans lates postfix arithmetic expressions into equivalent prefix arithmetic expressions.
answer
production:
translation scheme:
Exercises for Section 2.4
2.4.1
Construct recursive-descent parsers, starting with the follow ing grammars: 23 S -> + S S | - S S | a
24 S -> S ( S ) S | ε
S -> 0 S 1 | 0 1
Answer
1） S -> + S S | - S S | a
2） S -> S ( S ) S | ε
3） S -> 0 S 1 | 0 1
Exercises for Section 2.6
2.6.1
Extend the lexical analyzer in Section 2.6.5 to remove com ments, defined as follows:
26 A comment begins with // and includes all characters until the end of that line. 27 A comment begins with /* and includes all characters through the next occurrence of the character sequence */.
2.6.2
Extend the lexical analyzer in Section 2.6.5 to recognize the relational operators =, >.
2.6.3
Extend the lexical analyzer in Section 2.6.5 to recognize float ing point numbers such as 2., 3.14, and . 5.
Answer
Source code: commit 8dd1a9a
Code snippet(src/lexer/Lexer.java)：
Exercises for Section 2.8
2.8.1
For-statements in C and Java have the form:
for ( exprl ; expr2 ; expr3 ) stmt
The first expression is executed before the loop; it is typically used for initializ ing the loop index. The second expression is a test made before each iteration of the loop; the loop is exited if the expression becomes O. The loop itself can be thought of as the statement {stmt expr3 ; }. The third expression is executed at the end of each iteration; it is typically used to increment the loop index. The meaning of the for-statement is similar to
expr1 ; while ( expr2 ) {stmt expr3 ; }
Define a class For for for-statements, similar to class If in Fig. 2.43.
Answer
class For extends Stmt{
Expr E1;
Expr E2;
Expr E3;
Stmt S;
public For(Expr expr1, Expr expr2, Expr expr3, Stmt stmt){
E1 = expr1;
E2 = expr2;
E3 = expr3;
S = stmt;
}
public void gen(){
E1.gen();
Label start = new Lable();
Lalel end = new Lable();
emit("ifFalse " + E2.rvalue().toString() + " goto " + end);
S.gen();
E3.gen();
emit("goto " + start);
emit(end + ":")
}
}
2.8.2
The programming language C does not have a boolean type. Show how a C compiler might translate an if-statement into three-address code.
Answer
Replace
emit("isFalse " + E.rvalue().toString() + " goto " + after);
with
emit("ifNotEqual " + E.rvalue().toString() + " 0 goto " + after);
or