编译原理龙书课后部分答案英文

1、1) What is the difference between a compiler and an interpreter?· A compiler is a program that can read a program in one language - the source language - and translate it into an equivalent program in another language the target language and report any errors in the source program that it detec

2、ts during the translation process.· Interpreter directly executes the operations specified in the source program on inputs supplied by the user.2) What are the advantages of:(a) a compiler over an interpretera. The machine-language target program produced by a compiler is usually much faster th

3、an an interpreter at mapping inputs to outputs.(b) an interpreter over a compiler?b. An interpreter can usually give better error diagnostics than a compiler, because it executes the source program statement by statement.3) What advantages are there to a language-processing system in which the compi

4、lerproduces assembly language rather than machine language?The compiler may produce an assembly-language program as its output, becauseassembly language is easier to produce as output and is easier to debug. Design grammars for the following languages:a) The set of all strings of 0s and 1s such that

5、 every 0 is immediately followed by at least 1.S -> SS | 1 | 01 | e The following is a grammar for the regular expressions over symbols a and b only, using + in place of | for unions, to avoid conflict with the use of vertical bar as meta-symbol in grammars:rexpr -> rexpr + rterm | rtermrterm

6、-> rterm rfactor | rfactorrfactor -> rfactor * | rprimaryrprimary -> a | ba) Left factor this grammar.rexpr -> rexpr + rterm | rtermrterm -> rterm rfactor | rfactorrfactor -> rfactor * | rprimaryrprimary -> a | bb) Does left factoring make the grammar suitable for top-down parsi

7、ng?No, left recursion is still in the grammar.c) In addition to left factoring, eliminate left recursion from the original grammar.rexpr -> rterm rexprrexpr -> + rterm rexpr | erterm -> rfactor rtermrterm -> rfactor rterm | erfactor -> rprimary rfactorrfactor -> * rfactor | erprima

8、ry -> a | bd) Is the resulting grammar suitable for top-down parsing?Yes.Exercise For each of the following grammars, derive predictive parsers and show the parsing tables. You may left-factor and/or eliminate left-recursion from your grammars first. A predictive parser may be derived by recursiv

9、e decent or by the table driven approach. Either way you must also show the predictive parse table.a) The grammar of exercise (a). 4.2.2 a) S -> 0S1 | 01 This grammar has no left recursion. It could possibly benefit from left factoring. Here is the recursive decent PP code.s() match(0);if (lookah

10、ead = 0)s();match(1);OrLeft factoring the grammar first:S -> 0SS -> S1 | 1s() match(0); s();s() if (lookahead = 0)s(); match(1);elsematch(1);Now we will build the PP tableS -> 0SS -> S1 | 1First(S) = 0First(S) = 0, 1Follow(S) = 1, $Follow(S) = 1, $Non-TerminalInput Symbol01$SS->0SSS-&

11、gt;S1S->1The predictive parsing algorithm on page 227 (fig4.19 and 4.20) can use this table for non-recursive predictive parsing.b) The grammar of exercise (b). b) S -> +SS | *SS | a with string +*aaa.Left factoring does not apply and there is no left recursion to remove.s() if(lookahead = +)m

12、atch(+); s(); s();else if(lookahead = *)match(*); s(); s();else if(lookahead = a)match(a);elsereport(“syntax error”);First(S) = +, *, aFollow(S) = $, +, *, aNon-TerminalInput Symbol+*a$SS-> +SSS->*SSS->aThe predictive parsing algorithm on page 227 (fig4.19 and 4.20) can use this table for n

13、on-recursive predictive parsing.5.1.1 a, b, c: Investigating GraphViz as a solution to presenting trees5.1.2: Extend the SDD of Fig. 5.4 to handle expressions as in Fig. 5.1:1. L -> E N1. L.val = E.syn2. E -> F E'1. E.syn = E'.syn2. E'.inh = F.val3. E' -> + T Esubone

14、9;1. Esubone'.inh = E'.inh + T.syn2. E'.syn = Esubone'.syn4. T -> F T'1. T'.inh = F.val2. T.syn = T'.syn5. T' -> * F Tsubone'1. Tsubone'.inh = T'.inh * F.val2. T'.syn = Tsubone'.syn6. T' -> epsilon1. T'.syn = T'.inh7. E' -&

15、gt; epsilon1. E'.syn = E'.inh8. F -> digit1. F.val = digit.lexval9. F -> ( E )1. F.val = E.syn10. E -> T1. E.syn = T.syn5.1.3 a, b, c: Investigating GraphViz as a solution to presenting trees5.2.1: What are all the topological sorts for the dependency graph of Fig. 5.

16、7?1. 1, 2, 3, 4, 5, 6, 7, 8, 92. 1, 2, 3, 5, 4, 6, 7, 8, 93. 1, 2, 4, 3, 5, 6, 7, 8, 94. 1, 3, 2, 4, 5, 6, 7, 8, 95. 1, 3, 2, 5, 4, 6, 7, 8, 96. 1, 3, 5, 2, 4, 6, 7, 8, 97. 2, 1, 3, 4, 5, 6, 7, 8, 98. 2, 1, 3, 5, 4, 6, 7, 8, 99. 2, 1, 4, 3, 5, 6, 7, 8, 910. 2, 4, 1, 3, 5, 6, 7, 8, 95.2.2 a, b: Inves

17、tigating GraphViz as a solution to presenting trees5.2.3: Suppose that we have a production A -> BCD. Each of the four nonterminals A, B, C, and D have two attributes: s is a synthesized attribute, and i is an inherited attribute. For each of the sets of rules below, tell whet

18、her (1) the rules are consistent with an S-attributed definition (2) the rules are consistent with an L-attributed definition, and (3) whether the rules are consistent with any evaluation order at all?a) A.s = B.i + C.s1. No-contains inherited attribute2. Yes-"From above or from the left"3

19、. Yes-L-attributed so no cyclesb) A.s = B.i + C.s and D.i = A.i + B.s1. No-contains inherited attributes2. Yes-"From above or from the left"3. Yes-L-attributed so no cyclesc) A.s = B.s + D.s1. Yes-all attributes synthesized2. Yes-all attributes synthesized3. Yes-S- and L-attributed, so no

20、cyclesd)· A.s = D.i· B.i = A.s + C.s· C.i = B.s· D.i = B.i + C.i1. No-contains inherited attributes2. No-B.i uses A.s, which depends on D.i, which depends on B.i (cycle)3. No-Cycle implies no topological sorts (evaluation orders) using the rules5.3.1: Below is a grammar for

21、expressions involving operator + and integer or floating-point operands. Floating-point numbers are distinguished by having a decimal point.1. E -> E + T | T2. T -> num . num | numa) Give an SDD to determine the type of each term T and expression E.1. E -> Esub

22、one + T1. E.type = if (E.type = float | T.type = float) E.type = float  else E.type = integer 2. E -> T1. E.type = T.type3. T -> numsubone . numsubtwo1. T.type = float4. T -> num1. T.type = integerb) Extend your SDD of (a) to trans

23、late expressions into postfix notation. Use the binary operator intToFloat to turn an integer into an equivalent float.Note: I use character ',' to separate floating point numbers in the resulting postfix notation. Also, the symbol "|" implies concatenation.1. E -> Esu

24、bone + T1. E.val = Esubone.val | ',' | T.val | '+'2. E -> T1. E.val = T.val3. T -> numsubone . numsubtwo1. T.val = numsubone.val | '.' | numsubtwo.val4. T -> num1. T.val = intToFloat(num.val) Give an SDD to translate infix expressions wi

25、th + and * into equivalent expressions without redundant parenthesis. For example, since both operators associate from the left, and * takes precedence over +, (a*(b+c)*(d) translates into a*(b+c)*d. Note: symbol "|" implies concatenation.1. S -> E1. E.iop = nil2. S.equation =

26、 E.equation2. E -> Esubone + T1. Esubone.iop = E.iop2. T.iop = E.iop3. E.equation = Esubone.equation | '+' | T.equation4. E.sop = '+'3. E -> T1. T.iop = E.iop2. E.equation = T.equation3. E.sop = T.sop4. T -> Tsubone * F1. Tsubone.iop = '*'2. F.iop = '*'3. T.e

27、quation = Tsubone.equation | '*' | F.equation4. T.sop = '*'5. T -> F1. F.iop = T.iop2. T.equation = F.equation3. T.sop = F.sop6. F -> char1. F.equation = char.lexval2. F.sop = nil7. F -> ( E )1. if (F.iop = '*' && E.sop = '+') F.equation = '(' | E.equation | ')' else F.equation = E.equation 2. F.sop = nil: Give an SDD to differentiate expressions such as x * (3*x + x * x) involving the operators + and *, the variable x, and constants. Assume tha