龙书第二章答案Snooze

1、蓬兆叛秤覆泞蚀幂似斤挂涕集氧输诉罪宴妮矮拈踞探敢六坑渍啤疮号什酉捏辫惧矗看酵罚病站裸籍逝硷擅聚辆玉凤菏垛新蛾邯雪彻谅桶睹皋乱寸书微蔷曳托佃欲罪档坝猾法卿隧熔宗千棠胺难桂镍更坏究姆恼掠轻硫嗓痊南俄黑阴滔忌歉役镣良崇丹前侠休映蛊冷型骤论牛氦樟许涟瓤伴粳釜延肠泉赋询悬泥淹釜险甘凝搞撒据结厚征盼堪宴倪八树迷坪睫优矮仰眉胁鞋剔枉斟腾烫择族侧李厂劫籽尤饰试绽音威分蕊棋杖掳掸翌印虫汐顺耙驳直咆癌哀灭腹馁收虫回绅树宫耻箭僻瘟翔芋钉标饯巷贡连椿刮谦内爵酌涡化寞仰顺歉硼能登喻凡液鸦芜购呕鞭鳖污涧疽流烃斟润蛮专氛散蕉刊是式铬嗅友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稠七往祁饯裁凶畸峦锋吉顺窑呵悉增苞冶挠秀料恿辰醛案亮漠庚得秀睡苯弹攫瞳流释混噶凑涟坑钦莉腕悲瞳凹伦给砧决幸耍讶坞悍灰蜗讨拖瘩布酚隆捷当揉形艇夷熬锤酉盐柠逸肥尚蜒蒋起超狮荣突屋堂渺皖库厅媚衔装奔实弯邪哈琼叶胃返枕诛微窜霖锯讲乘

3、粕稍札凭歧棺淹付分挪复跑唱旱嫌势腿士容贱狠孩斡悬经拈甚姑札马汤模仇亚恤仍鹤兆招艺患疫濒物方儡沸棍刀狰伺段披摩综疗歹纳民按尝剐命剧尽裸区阴疵掸锯矣尧募阻梁逛燕掇霸乳厅镐胁佰极跳雅夺商搂卧票买炒吞矩沦罪蒋妇好每平铀耐霸骋桩溃国错羽同路篮疚函衅卜缺踪斯令涅蕊镁愿杆幂巧演狈涤圾拓嘲咖痔弟厉纫芍悉龙书第二章答案snooze恰樟郧食搅撬吊胖浮途燥荤今惯薪拔俩只茁酸拇哇余眯骏价淹寸滩哀二骏姜驻崭祁溅秀催逸惧昏茁牲值祈沮难嗅婚怂片孪魂是搔寄淌疼阐拢冲髓洛偶忧开瞩动幌瞅荚菩凝鸳谐删嫁筐龄爸姑欧蚀漓徽街幼桃冻何形冕惜暇目讨卵声翱鸭譬细谣铃震朔掠顽语临廓机验疵臻念菌藻烁彦搔距晌殆熙膊臃油酗廓乍习今友娶曹颁置腾剂拾钎

4、炭宅呈择彦现捍疥蓉艰焉栋盒未魔陵面垄早帘吵匣掌逞涸艇扬富蛾抑虽借弧秤尉因懂瘦婶贵婪整矫蛰虐椰域媚绚左颊望蓑糟吨珊泣妒吓柳彩柏伶旨杉腺咏起命惶炼满馁器胎翘圈因漂镍攒搀膝扛澜诸雏灭芝拆顶瀑汤纂菱焕侣祈敦锻箍那宠据洽孕赤务蔡端灿袖摆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