龙书答案Snooze

1、8CS 431, Assignment 3, Book Questions on Chapter 2 Plus One Other Questions given here. IQuestions that you need to answer are listed below, and some solutions or partial solutions are also given. The solutions are not presented as the only possible answers, and what is given may not be complete. It

2、 may only be a starting point for thinking about a complete, correct answer. Your goal in working the problems should be to come up with a solution, and if in doubt about your answer, compare with what theory, even if your answer is not exactly the same, you should see the sense or understand the di

3、rection of the suggestions. If your answer is at odds with what I have suggested you might want to check with me. It is possible that I am off base. It is also possible that you need some things clarified.Book problems: 2.1, a-c; 2.2, a-e; 2.3; 2.4, a-e, and 2.8. Suggested answers to these questions

4、 are given after the following question.Last problem: There is an additional problem that is not from the book. It is stated here.Impleme nt Java code that will correctly tran slate infix expressi ons with + and(no parentheses and no other operators) to postfix expressions. A problem solution is giv

5、en in the book in C code, so your task is mainly one of adaptation. A starting point for this problem is posted on the Web page. You may use the file InfixToPostfixCut.java as given and simply add the needed methods. You can also do the problem from scratch if you want to. I think it would be prefer

6、able if you left your implementation recursive rather than changing it to a loop, but that is your choice. Hand in a printout of the methods you added along with your answers to the problems listed above.Starting points for thinking about solutions:2.1. Consider the following context-free grammarSS

7、S +(1)SS S *(2)Sa(3)a) Show how the string aa+a* can be generated by this grammar.Production (3) allows you to generate a string S0 which consists of a.Using S0 as a starting point, production (1) allows you to generate a string 1Swhich consists of aa+.Production (3) again allows you to generate a s

8、tring 2Swhich consists of a. Then production (2) allows you to generate a string S3 = S1S2* = aa+a*.b) Construct a parse tree for this string.SSSS + ac) What Ian guage is gen erated by this grammar? Justify your an swer.Assu ming a is an ide ntifier for a nu meric value, for example, the n the gramm

9、ar gen erates a Ian guage con sisti ng of all possible arithmetic comb in ati ons oa using only the operations + and * and postfix notation. (No particular justification is given. Check to see if you agree.)2.2. What Ian guage is gen erated by the followi ng grammars? In each case justify your an sw

10、er. (No justificati ons are give n.)a) S 0 S 1 | 0 1s coming fiiAll strings divided evenly between 0' s and 1 ' s, with the sequenee of 0the sequenee of 1' s coming second.b) S + S S | - S S | aThis is the prefix analog to question 2.1.c) S S ( S ) S |&This will gen erate arbitrary s

11、eque nces of adjace nt and n ested, matched pairs of pare ntheses.d) S a S b S | b S a S |&s and bAll possible strings containing equal numbers of a' s and b ' s, with the aarran ged in no particular order.e) S a | S + S | S S | S * | ( S )I don ' t see a pattern to this that I can v

12、erbally describe.23 Which of the grammars in Exercise 2.2 are ambiguous?To show ambiguity it is sufficient to find any single string that can be parsed in more than one way using the grammar. No such stri ngs spri ng immediately to mind for the grammars of a through d. (That does not mea n that ther

13、e aren Howbaey.is clearly ambiguous. Let the stri ng S + S * be give n. Here are two possible pars in gs:S + SSS + SS2.4. Con struct un ambiguous con text-free grammars for each of the followi ng Ian guages. In each case show that your grammar is correct. (Correct ness is not show n.)a) Arithmetic e

14、xpressions in postfix notation.list list list +listlist list -listdigitlist0 | 1 | 2|9b) Left-associative lists of ide ntifiers separated by commas. list list, idlist idc) Right-associative lists of ide ntifiers separated by commas. list id, listlist idd) Arithmetic expressions of integers and ident

15、ifiers with the four binary operators +,-,Add the following rule to the grammar given at the end of section 2.2: factor ide ntifiere) Add unary plus and minus to the arithmetic operators of (d).Add the following rules to the grammar: factor +factorfactor -factor2.8 Con struct a syn tax-directed tran

16、 slati on scheme that tran slates arithmetic expressi ons from postfix no tati on to infix no tati on. Give anno tated parse trees for the in puts 95-2* and 952*-.Here is a simple grammar that can serve as a starting point for the solution of the problem:stri ngdigit stri ng operator| stri ng digit

17、operator | digitdigit 0 | 1 | 2 | 9operator * | / | + | -Here is an anno tated parse tree of the first expressi on:The first production applied in forming this tree was: stringstring digitt matter whichoperator. Notice that it would have bee n just as possible to apply the producti on: stri ng digit

18、 stri ng operator. If that had bee n done you would have the n had to parse the string -2”5 . Thisesult would not parse and it would be necessary to backtrack and choose to apply the other product ion. At the n ext level dow n it does n product ion is chose n.stri ng: 952*-digit: 9stri ng: 52*-9digi

19、t: 5stri ng: 25digit: 9In this example there is no choice about which producti on to apply first. At the second level there is a choice but it doesn' t make a differenee. The lack of choice at thefirst level illustrates clearly how you could tell whether or not the product ion you have chose n i

20、s the correct one, assu ming you could look that far ahead: If the stri ng that you have parsed on the right hand side does not end in an operator, the n the producti on choice is not correct. It is also possible to see that if you could specify the order in which product ions are tried, you could a

21、void backtrack ing. If you always tried to parse using this production first: stringstring digit operator and tried the other one if that onefailed to apply, you would avoid backtrack ing. But aga in, such an approach is not allowed. The questi on of backtrack ing is discussed on pages 45 and 46 of

22、the book. The upshot of the matter is that this grammar isn' t suitable for predictive parsing.There is another matter that will require a change in the grammar so that a syntax- directed tran slati on scheme can be devised. At the top of page 39 in the book the term “ simple ” is defined as it

23、applies to a sydteected definition. The requirement is that the order of non-term in als on the right hand side of a producti on agree with the order of the corresp onding symbols gen erated as the desired output. Other symbols or term in als may come before, between, or after the output for the non

24、-terminals. Under this con diti on the output can be gen erated from a depth first traversal of the anno tated tree. The problem with the grammar given above is that all of the operators are symbolized using the non term inal“ operatdHowev er, i n the tran slati on from postfix to in fix, it isthe p

25、ositi on of the operator that cha nges. That means that eve n though tedious, for practical reas ons the product ions have to be rewritte n with the operator symbols in-li ne as termi nals:stri ng digit stri ng *| digit stri ng /| digit string +| digit stri ng -| string digit *| string digit /| stri

26、ng digit +| string digit -| digitdigit 0 | 1 | 2 | 9The problem only gets better and better, or worse and worse, depending on your point of view. Postfix notation does not require parentheses. The relative positions of the operands and operators unambiguously determine the order of operations. This

27、means that an arbitrary postfix expression may enforce an order of operations which would not occur naturally in an unparenthesized infix expression. In particular, 95-2* does not tran slate to 95 * 2, where the multiplicatio n would be done first. It tran slates to (9 5) * 2. It is not an attractiv

28、e propositi on to try and impleme nt a tran slati on scheme that would only insert parentheses when needed. It is much more convenient to fully parenthesize the infix translation whether needed or not. The unneeded parentheses do not adversely affect the meaning of the arithmetic.Having said all of the above, here is my suggested syntax-directed translation scheme, that is, a context-free grammar with embedded semantic actions that will