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

1、1) What is the difference between a compiler and an interpreter一theA compiler is a program that can read a program in one language - the sourcethat it detects duringlanguage - and translate it into an equivalent program in another language target language and report any errors in the source program

2、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 than an interpreter

3、 at mapping inputs to outputs.(b) an interpreter over a compiler(c) 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 compilerproduces assem

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

5、immediately followed by at least 1.S - SS | 1 | 01 |4.3.1 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- rterm rfactor | r

6、factorr factor - rfactor * | rprimary r primary - a | ba) Left factor this grammar.rexpr - rexpr + rterm | rterm rterm - rterm rfactor | rfactor r factor - rfactor * | rprimary rprimary - a | bb) Does left factoring make the grammar suitable for top-down parsing No, left recursion is still in the gr

7、ammar.c) In addition to left factoring, eliminate left recursion from the original grammar.rexpr -rterm rexpr rexpr - +rterm rexpr |rterm -rfactor rtermrterm-rfactor rterm |rfactor -rprimary rfactor，r factor -* rfactor |r primary -a | bd) Is the resulting grammar suitable for top-down parsing Yes.pa

8、rseleftExercise 4.4.1 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 recursive decent or by the table driven approach. Either way you must a

9、lso show the predictive table.a) The grammar of exercise 4.2.2(a).4.2.2 a) S - 0S1 | 01This grammar has no left recursion. It could possibly benefit from factoring. Here is the recursive decent PP code.s() match( 0);i f (lookahead =0)s();match( 1);OrLeft factoring the grammar first:S - 0SS- S1 | 1s(

10、) match( 0 ); s (); s () i f (lookahead = 0)s(); match( 1 ); elsematch( 1 );9Now we will build the PP tableS-0SS - S1 | 1First(S) = 0First(S ) = 0,1Follow(S) = 1, $Follow(S ) = 1, $Non-TermiInput Symbolnal01$SS-0SS，S -S1S -1The predictive parsing algorithm on page 227 and can use this table for non-

11、recursive predictive parsing.b) The grammar of exercise 4.2.2(b).4.2.2 b) S - +SS | *SS | a with string +*aaa.Left factoring does not apply and there is no left recursion to remove.s() i f(lookahead =+)match( +，); s(); s();else i f(lookahead =*)match( * ); s(); s();else if(lookahead =a)match( a);els

12、ereport(syntax error );First(S) = +, *, aFollow(S) = $, +, *, aNon-Termi nalInput Symbol+*a$SS- +SSS-*SSS-aThe predictive parsing algorithm on page 227 and can use this table for non-recursive predictive parsing.5.1.1 a, b, c: Investigating GraphViz as a solution to presenting treesExtend the SDD of

13、 Fig. to handle expressions as in Fig.:1. L - E N1. =2. E -FE1. = E.syn2. E.inh =3. E -+TEsubone1. Esubone.inh = E.inh +2. E.syn = Esubone.syn4. T - F T1. T.inh =2. = T.syn5. T - * F Tsubone1. Tsubone.inh = T.inh *2. T.syn =Tsubone.syn6. T - epsilon1. T.syn =T.inh7. E - epsilon1. E.syn =E.inh8. F -d

14、igit1. =9. F -(E )1. =10. E -T1. =5.1.3 a, b, c: Investigating GraphViz as a solution to presenting treesWhat are all the topological sorts for the dependency graph of Fig.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

15、,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: Investigating GraphViz as a solution to presenting treesSuppose 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, an

16、di is aninherited attribute. For each of the sets of rules below, tell whether (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) = +1. No-contains in

17、herited attribute2. Yes-From above or from the left3. Yes-L-attributed so no cyclesb) = + and = +1. No-contains inherited attributes2. Yes-From above or from the left3. Yes-L-attributed so no cyclesc) = +1. Yes-all attributes synthesized2. Yes-all attributes synthesized3. Yes-S- and L-attributed, so

18、 no cyclesd) =+ =+1. No-contains inherited attributes2. uses , which depends on , which depends on (cycle)3. No-Cycle implies no topological sorts (evaluation orders) using the rulesBelow is a grammarfor expressions involving operator + and integer or floating-point operands. Floating-point numbers

19、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 - Esubone + T1. = if = float | = float ) = float else = integer 2. E - T1. =3. T -numsubone . numsubtwo1. =float4. T -egerb) Extend your

20、 SDD of (a) to translate expressions into postfix notation. Use the binary operator intToFloat to turn an integer into an equivalentI use character , to separate floating point numbers in the resulting postfix notation. Also, the symbol | implies concatenation.1. E - Esubone + T1. = | , | | +2. E -

21、T1. =3. T -numsubone . numsubtwo1. =| . |4. T -num1. =intToFloat5.3.2 Give an SDD to translate infix expressions with + 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. =nil2. =2. E - Esubone + T1. =2. =3. =|+|4. =+3. E - T1. =2. =3. =4. T - Tsubone * F1. =*2. =*3. =|*|4. =*