《编译原理龙书课后部分答案(英文版)》由会员分享，可在线阅读，更多相关《编译原理龙书课后部分答案(英文版)（9页珍藏版）》请在金锄头文库上搜索。
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 detects dur
2、ing 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 interp
3、reter 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 compilerproduces
4、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.4.2.3 Design grammars for the following languages:a) The set of all strings of 0s and 1s such that every
5、0 is immediately followed by at least 1.S - SS | 1 | 01 | e4.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 rf
6、actor | 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 parsing?No, left recursion is still in the
7、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 | erprimary - a | bd) Is the resulting grammar suitable for top-down pa
8、rsing?Yes.Exercise 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 mus
9、t also show the predictive parse table.a) The grammar of exercise 4.2.2(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 (lookahead = 0)s();match(1);OrLeft factoring the grammar first:S -
10、 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-S1S-1The predictive parsing algorithm on page 227 (fig4.19 and 4.20) can use thi
11、s table for non-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() if(lookahead = +)match(+); s(); s();else if(lookahead = *)match(*); s(); s();else if(lookahead = a)
12、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 non-recursive predictive parsing.5.1.1 a, b, c: Investigating GraphViz as a solution to presen
13、ting 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 E1. E.syn = E.syn2. E.inh = F.val3. E - + T Esubone1. Esubone.inh = E.inh + T.syn2. E.syn = Esubone.syn4. T - F T1. T.inh = F.val2. T.syn = T.syn5. T - * F Tsubone1. Tsubone.inh = T.inh
14、 * F.val2. T.syn = Tsubone.syn6. T - epsilon1. T.syn = T.inh7. E - 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.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
