资源介绍
编译原理龙书答案 完整性高
第二章
2.2 Exercises for Section 2.2
2.2.1
Consider the context-free grammar:
S -> S S + | S S * | a
Show how the string aa+a* can be generated by this grammar.
Construct a parse tree for this string.
What language does this grammar generate? Justify your answer.
answer
S -> S S * -> S S + S * -> a S + S * -> a a + S * -> a a + a *
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.
S -> 0 S 1 | 0 1
S -> + S S | - S S | a
S -> S ( S ) S | ε
S -> a S b S | b S a S | ε
⧗ S -> a | S + S | S S | S * | ( S )
answer
L = {0n1n | n>=1}
L = {Prefix expression consisting of plus and minus signs}
L = {Matched brackets of arbitrary arrangement and nesting, includes ε}
L = {String has the same amount of a and b, includes ε}
？
2.2.3
Which of the grammars in Exercise 2.2.2 are ambiguous
answer
No
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.
Arithmetic expressions in postfix notation.
Left-associative lists of identifiers separated by commas.
Right-associative lists of identifiers separated by commas.
Arithmetic expressions of integers and identifiers with the four binary operators +, - , *, /.
answer
1. E -> E E op | num
2. list -> list , id | id
3. list -> id , list | id
4. expr -> expr + term | expr - term | term
term -> term * factor | term / factor | factor
factor -> id | num | (expr)
5. expr -> expr + term | expr - term | term
term -> term * unary | term / unary | unary
unary -> + factor | - factor
factor - > id | num | (expr)
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:
I, II, III | I V | V, V I, V II, V III | I X
then get the production:
digit -> smallDigit | I V | V smallDigit | I X
smallDigit -> I | II | III | ε
and we can find a simple way to map roman to arabic numerals. For example:
XII => X, II => 10 + 2 => 12
CXCIX => C, XC, IX => 100 + 90 + 9 => 199
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:
expr -> expr + term
| expr - term
| term
term -> term * factor
| term / factor
| factor
factor -> digit | (expr)
translation schemes:
expr -> {print("+")} expr + term
| {print("-")} expr - term
| term
term -> {print("*")} term * factor
| {print("/")} term / factor
| factor
factor -> digit {print(digit)}
| (expr)
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:
expr -> expr expr +
| expr expr -
| expr expr *
| expr expr /
| digit
translation schemes:
expr -> expr {print("+")} expr +
| expr {print("-")} expr -
| {print("(")} expr {print(")*(")} expr {print(")")} *
| {print("(")} expr {print(")/(")} expr {print(")")} /
| digit {print(digit)}
Another reference answer
E -> {print("(")} E {print(op)} E {print(")"}} op | digit {print(digit)}
2.3.3
Construct a syntax-directed translation scheme that trans lates integers into roman numerals
answer
assistant function:
repeat(sign, times) // repeat('a',2) = 'aa'
translation schemes:
num -> thousand hundred ten digit
{ num.roman = thousand.roman || hundred.roman || ten.roman || digit.roman;
print(num.roman)}
thousand -> low {thousand.roman = repeat('M', low.v)}
hundred -> low {hundred.roman = repeat('C', low.v)}
| 4 {hundred.roman = 'CD'}
| high {hundred.roman = 'D' || repeat('X', high.v - 5)}
| 9 {hundred.roman = 'CM'}
ten -> low {ten.roman = repeat('X', low.v)}
| 4 {ten.roman = 'XL'}
| high {ten.roman = 'L' || repeat('X', high.v - 5)}
| 9 {ten.roman = 'XC'}
digit -> low {digit.roman = repeat('I', low.v)}
| 4 {digit.roman = 'IV'}
| high {digit.roman = 'V' || repeat('I', high.v - 5)}
| 9 {digit.roman = 'IX'}
low -> 0 {low.v = 0}
| 1 {low.v = 1}
| 2 {low.v = 2}
| 3 {low.v = 3}
high -> 5 {high.v = 5}
| 6 {high.v = 6}
| 7 {high.v = 7}
| 8 {high.v = 8}
2.3.4
Construct a syntax-directed translation scheme that trans lates roman numerals into integers.
answer
productions:
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 | ε
translation schemes:
romanNum -> thousand hundred ten digit {romanNum.v = thousand.v || hundred.v || ten.v || digit.v; print(romanNun.v)}
thousand -> M {thousand.v = 1}
| MM {thousand.v = 2}
| MMM {thousand.v = 3}
| ε {thousand.v = 0}
hundred -> smallHundred {hundred.v = smallHundred.v}
| C D {hundred.v = smallHundred.v}
| D smallHundred {hundred.v = 5 + smallHundred.v}
| C M {hundred.v = 9}
smallHundred -> C {smallHundred.v = 1}
| CC {smallHundred.v = 2}
| CCC {smallHundred.v = 3}
| ε {hundred.v = 0}
ten -> smallTen {ten.v = smallTen.v}
| X L {ten.v = 4}
| L smallTen {ten.v = 5 + smallTen.v}
| X C {ten.v = 9}
smallTen -> X {smallTen.v = 1}
| XX {smallTen.v = 2}
| XXX {smallTen.v = 3}
| ε {smallTen.v = 0}
digit -> smallDigit {digit.v = smallDigit.v}
| I V {digit.v = 4}
| V smallDigit {digit.v = 5 + smallDigit.v}
| I X {digit.v = 9}
smallDigit -> I {smallDigit.v = 1}
| II {smallDigit.v = 2}
| III {smallDigit.v = 3}
| ε {smallDigit.v = 0}
2.3.5
Construct a syntax-directed translation scheme that trans lates postfix arithmetic expressions into equivalent prefix arithmetic expressions.
answer
production:
expr -> expr expr op | digit
translation scheme:
expr -> {print(op)} expr expr op | digit {print(digit)}
Exercises for Section 2.4
2.4.1
Construct recursive-descent parsers, starting with the follow ing grammars:
S -> + S S | - S S | a
S -> S ( S ) S | ε
S -> 0 S 1 | 0 1
Answer
1） S -> + S S | - S S | a
void S(){
switch(lookahead){
case "+":
match("+"); S(); S();
break;
case "-":
match("-"); S(); S();
break;
case "a":
match("a");
break;
default:
throw new SyntaxException();
}
}
void match(Terminal t){
if(lookahead = t){
lookahead = nextTerminal();
}else{
throw new SyntaxException()
}
}
2） S -> S ( S ) S | ε
void S(){
if(lookahead == "("){
S(); match("("); S(); match(")"); S();
}
}
3） S -> 0 S 1 | 0 1
void S(){
switch(lookahead){
case "0":
match("0"); S(); match("1");
break;
case "1":
// match(epsilon);
break;
default:
throw new SyntaxException();
}
}
Exercises for Section 2.6
2.6.1
Extend the lexical analyzer in Section 2.6.5 to remove com ments, defined as follows:
A comment begins with // and includes all characters until the end of that line.
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)：
public Token scan() throws IOException, SyntaxException{
for(;;peek = (char)stream.read()){
if(peek == ' ' || peek == '\t'){
continue;
}else if(peek == '\n'){
line = line + 1;
}else{
break;
}
}
// handle comment
if(peek == '/'){
peek = (char) stream.read();
if(peek == '/'){
// single line comment
for(;;peek = (char)stream.read()){
if(peek == '\n'){
break;
}
}
}else if(peek == '*'){
// block comment
char prevPeek = ' ';
for(;;prevPeek = peek, peek = (char)stream.read()){
if(prevPeek == '*' && peek == '/'){
break;
}
}
}else{
throw new SyntaxException();
}
}
// handle relation sign
if("<=!>".indexOf(peek) > -1){
StringBuffer b = new StringBuffer();
b.append(peek);
peek = (char)stream.read();
if(peek == '='){
b.append(peek);
}
return new Rel(b.toString());
}
// handle number, no type sensitive
if(Character.isDigit(peek) || peek == '.'){
Boolean isDotExist = false;
StringBuffer b = new StringBuffer();
do{
if(peek == '.'){
isDotExist = true;
}
b.append(peek);
peek = (char)stream.read();
}while(isDotExist == true ? Character.isDigit(peek) : Character.isDigit(peek) || peek == '.');
return new Num(new Float(b.toString()));
}
// handle word
if(Character.isLetter(peek)){
StringBuffer b = new StringBuffer();
do{
b.append(peek);
peek = (char)stream.read();
}while(Character.isLetterOrDigit(peek));
String s = b.toString();
Word w = words.get(s);
if(w == null){
w = new Word(Tag.ID, s);
words.put(s, w);
}
return w;
}
Token t = new Token(peek);
peek = ' ';
return t;
}
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
emit("isNotEqualZero " + E.rvalue().toString() + " goto " + after);