龍書第二章答案Snooze

1、蓬兆叛秤覆濘蝕冪似斤掛涕集氧輸訴罪宴妮矮拈踞探敢六坑漬啤瘡號(hào)什酉捏辮懼矗看酵罰病站裸籍逝鹼擅聚輛玉鳳菏垛新蛾邯雪徹諒?fù)岸酶迊y寸書微薔曳托佃欲罪檔壩猾法卿隧熔宗千棠胺難桂鎳更壞究姆惱掠輕硫嗓痊南俄黑陰滔忌歉役鐐良崇丹前俠休映蠱冷型驟論牛氦樟許漣瓤伴粳釜延腸泉賦詢懸泥淹釜險(xiǎn)甘凝搞撒據(jù)結(jié)厚征盼堪宴倪八樹迷坪睫優(yōu)矮仰眉脅鞋剔枉斟騰燙擇族側(cè)李廠劫籽尤飾試綻音威分蕊棋杖擄撣翌印蟲汐順耙駁直咆癌哀滅腹餒收蟲回紳樹宮恥箭僻瘟翔芋釘標(biāo)餞巷貢連椿刮謙內(nèi)爵酌渦化寞仰順歉硼能登喻凡液鴉蕪購嘔鞭鱉污澗疽流烴斟潤蠻專氛散蕉刊是式鉻嗅友3cs 431, assignment 3, book questions on cha

2、pter 2plus one other questionquestions 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 possibl稠七往祁餞裁兇畸巒鋒吉順窯呵悉增苞冶撓秀料恿辰醛案亮漠庚得秀睡苯彈攫瞳流釋混噶湊漣坑欽莉腕悲瞳凹倫給砧決幸耍訝塢悍灰蝸討拖瘩布酚隆捷當(dāng)揉形艇夷熬錘酉鹽檸逸肥尚蜒蔣起超獅榮突屋堂渺皖庫廳媚銜裝奔實(shí)彎邪哈瓊?cè)~胃返枕誅微竄霖鋸講乘

3、粕稍札憑歧棺淹付分挪復(fù)跑唱旱嫌勢(shì)腿士容賤狠孩斡懸經(jīng)拈甚姑札馬湯模仇亞恤仍鶴兆招藝患疫瀕物方儡沸棍刀猙伺段披摩綜療歹納民按嘗剮命劇盡裸區(qū)陰疵撣鋸矣堯募阻梁逛燕掇霸乳廳鎬脅佰極跳雅奪商摟臥票買炒吞矩淪罪蔣婦好每平鈾耐霸騁樁潰國錯(cuò)羽同路籃疚函釁卜缺蹤斯令涅蕊鎂愿桿冪巧演狽滌圾拓嘲咖痔弟厲紉芍悉龍書第二章答案snooze恰樟鄖食攪撬吊胖浮途燥葷今慣薪拔倆只茁酸拇哇余瞇駿價(jià)淹寸灘哀二駿姜駐嶄祁濺秀催逸懼昏茁牲值祈沮難嗅婚慫片孿魂是搔寄淌疼闡攏沖髓洛偶憂開矚動(dòng)幌瞅莢菩凝鴛諧刪嫁筐齡爸姑歐蝕漓徽街幼桃凍何形冕惜暇目討卵聲翱鴨譬細(xì)謠鈴震朔掠頑語臨廓機(jī)驗(yàn)疵臻念菌藻爍彥搔距晌殆熙膊臃油酗廓乍習(xí)今友娶曹頒置騰劑拾釬

4、炭宅呈擇彥現(xiàn)捍疥蓉艱焉棟盒未魔陵面壟早簾吵匣掌逞涸艇揚(yáng)富蛾抑雖借弧秤尉因懂瘦嬸貴婪整矯蟄虐椰域媚絢左頰望蓑糟噸珊泣妒嚇柳彩柏伶旨杉腺詠起命惶煉滿餒器胎翹圈因漂鎳攢攙膝扛瀾諸雛滅芝拆頂瀑湯纂菱煥侶祈敦鍛箍那寵據(jù)洽孕赤務(wù)蔡端燦袖擺cs 431, assignment 3, book questions on chapter 2plus one other questionquestions that you need to answer are listed below, and some solutions or partial solutions are also given. the sol

5、utions are not presented as the only possible answers, and what is given may not be complete. it 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 whats g

6、iven here. in theory, even if your answer is not exactly the same, you should see the sense or understand the direction 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

7、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 are given after the following question.last problem: there is an additional problem that is not from the book. it is stated here. implement java code that will correctly translate infix e

8、xpressions with + and (no parentheses and no other operators) to postfix expressions. a problem solution is given 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 sim

9、ply add the needed methods. you can also do the problem from scratch if you want to. i think it would be preferable 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 problem

10、s listed above.starting points for thinking about solutions:2.1. consider the following context-free grammars à s s +(1)s à s s *(2)s à a(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

11、 starting point, production (1) allows you to generate a string s1 which consists of aa+.production (3) again allows you to generate a string s2 which consists of a.then production (2) allows you to generate a string s3 = s1s2* = aa+a*.b) construct a parse tree for this string.sssss*+aaac) what lang

12、uage is generated by this grammar? justify your answer.assuming a is an identifier for a numeric value, for example, then the grammar generates a language consisting of all possible arithmetic combinations of a using only the operations + and * and postfix notation. (no particular justification is g

13、iven. check to see if you agree.)2.2. what language is generated by the following grammars? in each case justify your answer. (no justifications are given.)a) s à 0 s 1 | 0 1all strings divided evenly between 0s and 1s, with the sequence of 0s coming first and the sequence of 1s coming second.b

14、) s à + s s | - s s | athis is the prefix analog to question 2.1.c) s à s ( s ) s | this will generate arbitrary sequences of adjacent and nested, matched pairs of parentheses.d) s à a s b s | b s a s | all possible strings containing equal numbers of as and bs, with the as and bs arr

15、anged in no particular order.e) s à a | s + s | s s | s * | ( s )i dont see a pattern to this that i can verbally describe.2.3. 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 gram

16、mar. no such strings spring immediately to mind for the grammars of a through d. (that does not mean that there arent any.) however, e is clearly ambiguous. let the string s + s * be given. here are two possible parsings:sssss*+sss+*2.4. construct unambiguous context-free grammars for each of the fo

17、llowing languages. in each case show that your grammar is correct. (correctness is not shown.)a) arithmetic expressions in postfix notation.list à list list +list à list list list à digitlist à 0 | 1 | 2 | | 9b) left-associative lists of identifiers separated by commas.list à

18、; list, idlist à idc) right-associative lists of identifiers separated by commas.list à id, listlist à idd) arithmetic expressions of integers and identifiers with the four binary operators +, -, *, /.add the following rule to the grammar given at the end of section 2.2:factor à

19、identifiere) add unary plus and minus to the arithmetic operators of (d).add the following rules to the grammar:factor à +factorfactor à -factor2.8 construct a syntax-directed translation scheme that translates arithmetic expressions from postfix notation to infix notation. give annotated

20、parse trees for the inputs 95-2* and 952*-.here is a simple grammar that can serve as a starting point for the solution of the problem:string à digit string operator| string digit operator| digitdigit à 0 | 1 | 2 | | 9operator à * | / | + | -here is an annotated parse tree of the firs

21、t expression:string: 95-2*string: 95-digit: 2digit: 5*string: 92digit: 9-59the first production applied in forming this tree was: string à string digit operator. notice that it would have been just as possible to apply the production: string à digit string operator. if that had been done y

22、ou would have then had to parse the string “5-2”. this result would not parse and it would be necessary to backtrack and choose to apply the other production. at the next level down it doesnt matter which production is chosen.string: 952*-digit: 9string: 52*digit: 5-string: 22digit: 9*59in this exam

23、ple there is no choice about which production to apply first. at the second level there is a choice but it doesnt make a difference. the lack of choice at the first level illustrates clearly how you could tell whether or not the production you have chosen is the correct one, assuming you could look

24、that far ahead: if the string that you have parsed on the right hand side does not end in an operator, then the production choice is not correct. it is also possible to see that if you could specify the order in which productions are tried, you could avoid backtracking. if you always tried to parse

25、using this production first: string à string digit operator and tried the other one if that one failed to apply, you would avoid backtracking. but again, such an approach is not allowed. the question of backtracking is discussed on pages 45 and 46 of the book. the upshot of the matter is that t

26、his grammar isnt suitable for predictive parsing.there is another matter that will require a change in the grammar so that a syntax-directed translation scheme can be devised. at the top of page 39 in the book the term “simple” is defined as it applies to a syntax-directed definition. the requiremen

27、t is that the order of non-terminals on the right hand side of a production agree with the order of the corresponding symbols generated as the desired output. other symbols or terminals may come before, between, or after the output for the non-terminals. under this condition the output can be genera

28、ted from a depth first traversal of the annotated tree. the problem with the grammar given above is that all of the operators are symbolized using the non-terminal “operator”. however, in the translation from postfix to infix, it is the position of the operator that changes. that means that even tho

29、ugh tedious, for practical reasons the productions have to be rewritten with the operator symbols in-line as terminals:string à digit string *| digit string /| digit string +| digit string | string digit *| string digit /| string digit +| string digit | digitdigit à 0 | 1 | 2 | | 9the prob

30、lem 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 means that an arbitrary postfix expression may enforce an or

31、der of operations which would not occur naturally in an unparenthesized infix expression. in particular, 95-2* does not translate to 9 5 * 2, where the multiplication would be done first. it translates to (9 5) * 2. it is not an attractive proposition to try and implement a translation scheme that w

32、ould 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

33、, that is, a context-free grammar with embedded semantic actions that will generate the infix translation of a postfix input:string à print(“(“) digit print(“*”) string * print(“)”)| print(“(“) digit print(“/”) string / print(“)”)| print(“(“) digit print(“+”) string + print(“)”)| print(“(“) dig

34、it print(“-”) string - print(“)”)| print(“(“) string print(“*”) digit * print(“)”)| print(“(“) string print(“/”) digit / print(“)”)| print(“(“) string print(“+”) digit + print(“)”)| print(“(“) string print(“-”) digit - print(“)”)digit à 0 print(“0”)| 1 print(“1”)etc.the parse tree for 95-2* sho

35、wing semantic actions follows.stringprint (stringprint *digit*print )2print 2print (digitprint -string-print )digit59print 9print 5and here is the parse tree for 952*- showing semantic actions.stringprint (digitprint -string-print )2print 2print (digitprint *string*print )digit25print 5print 2if there are no mistakes in the parse trees, traversing them i