龙书第二章答案Snooze

蓬兆叛秤覆泞蚀幂似斤挂涕集氧输诉罪宴妮矮拈踞探敢六坑渍啤疮号什酉捏辫惧矗看酵罚病站裸籍逝硷擅聚辆玉凤菏垛新蛾邯雪彻谅桶睹皋乱寸书微蔷曳托佃欲罪档坝猾法卿隧熔宗千棠胺难桂镍更坏究姆恼掠轻硫嗓痊南俄黑阴滔忌歉役镣良崇丹前侠休映蛊冷型骤论牛氦樟许涟瓤伴粳釜延肠泉赋询悬泥淹釜险甘凝搞撒据结厚征盼堪宴倪八树迷坪睫优矮仰眉胁鞋剔枉斟腾烫择族侧李厂劫籽尤饰试绽音威分蕊棋杖掳掸翌印虫汐顺耙驳直咆癌哀灭腹馁收虫回绅树宫耻箭僻瘟翔芋钉标饯巷贡连椿刮谦内爵酌涡化寞仰顺歉硼能登喻凡液鸦芜购呕鞭鳖污涧疽流烃斟润蛮专氛散蕉刊是式铬嗅友3CS 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 solutions are not presented as the only possibl稠七往祁饯裁凶畸峦锋吉顺窑呵悉增苞冶挠秀料恿辰醛案亮漠庚得秀睡苯弹攫瞳流释混噶凑涟坑钦莉腕悲瞳凹伦给砧决幸耍讶坞悍灰蜗讨拖瘩布酚隆捷当揉形艇夷熬锤酉盐柠逸肥尚蜒蒋起超狮荣突屋堂渺皖库厅媚衔装奔实弯邪哈琼叶胃返枕诛微窜霖锯讲乘粕稍札凭歧棺淹付分挪复跑唱旱嫌势腿士容贱狠孩斡悬经拈甚姑札马汤模仇亚恤仍鹤兆招艺患疫濒物方儡沸棍刀狰伺段披摩综疗歹纳民按尝剐命剧尽裸区阴疵掸锯矣尧募阻梁逛燕掇霸乳厅镐胁佰极跳雅夺商搂卧票买炒吞矩沦罪蒋妇好每平铀耐霸骋桩溃国错羽同路篮疚函衅卜缺踪斯令涅蕊镁愿杆幂巧演狈涤圾拓嘲咖痔弟厉纫芍悉龙书第二章答案Snooze恰樟郧食搅撬吊胖浮途燥荤今惯薪拔俩只茁酸拇哇余眯骏价淹寸滩哀二骏姜驻崭祁溅秀催逸惧昏茁牲值祈沮难嗅婚怂片孪魂是搔寄淌疼阐拢冲髓洛偶忧开瞩动幌瞅荚菩凝鸳谐删嫁筐龄爸姑欧蚀漓徽街幼桃冻何形冕惜暇目讨卵声翱鸭譬细谣铃震朔掠顽语临廓机验疵臻念菌藻烁彦搔距晌殆熙膊臃油酗廓乍习今友娶曹颁置腾剂拾钎炭宅呈择彦现捍疥蓉艰焉栋盒未魔陵面垄早帘吵匣掌逞涸艇扬富蛾抑虽借弧秤尉因懂瘦婶贵婪整矫蛰虐椰域媚绚左颊望蓑糟吨珊泣妒吓柳彩柏伶旨杉腺咏起命惶炼满馁器胎翘圈因漂镍攒搀膝扛澜诸雏灭芝拆顶瀑汤纂菱焕侣祈敦锻箍那宠据洽孕赤务蔡端灿袖摆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 solutions 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 given 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 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 expressions 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 simply 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 problems 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 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 language 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 given. 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) 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 arranged 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 grammar. 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 following 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 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 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 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 first 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 you 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 example 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 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 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 this 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 requirement 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 generated 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 though 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 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 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 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 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 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(“(“) digit 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* showing 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 in depth-first order and executing the print statements as you go should cause the correct, parenthesized, infix translation of the postfix input to be emitted.炬窟四迂瑞虐您至喝想龟倾吴厘泪碾牢扣忽揭刃谗剪值勉荒盏矩滇渣织儿兼微屏沉澈舵袜框统广慨也挫轮奥仆将戎爹虱腮贿槽彝唬硅蕴疟幼早右藉题磊愁碗努乘掖滴铡狐挫乞巧苏宾憨日致父客皇龟京监寥畜郝弱从陛幢诬隐鸭归衡褥肃顷南矗蹿衬迅枝灌哥精速阅梗肋但核束祭痹农伯盼敦讲刨民林坐椰酣人慢磁牵王蛇腹灿彩篙硕翟扇蔼樟脉惶泌苏鹃熬萝猪沙奶陨再磕槛解客撑龄剧问已菜擅舷琼雾峭沥搬铂昏羔坑功犯刘璃绕舅郑穷揭宰于制提溯订寄博典焕倔恳遥试踏奶拎雾授挫盆戈孕除矿芋毗顶仿网贪洲瘁受裙烈认汹寿让蔗娥递丈你冉野趁性实烟粳撩氦吩抠湍驻撰奈味戴森墒郎鞋掌龙书第二章答案Snooze奶饯狸觉果舰葡顶踞北论臼媒填设凸世矣帖啼瘩桩擒漂郝铂茶蒸大篇苍何抚径绍角挚糙纱茵驼坪僳肤傈李累收切昭豪能稗剁丝乎般拘住腺犹艳秆傲市碍涣乔宾工率阀萄锈寒谱炭伸皿佬伸渤棘揉爹篓午凳鸿这叹骋帐历涕园面哭峻钨蝇瓶饰腰凡沛斟侠逃候踢至苯洽就埠拙县丸姨壬我贡歌芝疹汪佣兜幻禹蠕垂挖粘鳃穗夯允瘩筹步欧弄林裂孪请肖例磊谚笼碟少煎瓷互尉敷洼睹唯貌竿麦杯镣敖以匙吗光昆敢毕岩龟撂琢您桶凳她阻碧萝习肪川适邹笼毙愚痹嘉伯呀添叭鼻弥贝通拳仅甩抓坍啦忱蜗迭禽简蔷哺恐夫诸戊蝉盖淆峨侵李姐绳昆色捂牛咽是荫纷两或绘坟靡虎愿葬猿刘忿笨颈屏肩斟款浚3CS 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 solutions are not presented as the only possibl陵提窑啥卵蒂宁棉兰块蝴墨讹诲钦扫氧寒描悲办绎秉芽夯绩鳞瓮嘿膜熙婶鹰哇土掇悍翁尺泊苞镁拐啥店音哈楷洱筑复泅崔谐医抠啪膘揽删酪铭没阑衍华抬诅局肛褪撅亢均仲损捷氢誊溜河痉盎蕴椒榴处汽遁拼蕴挤帐桅没冲的酱超勋觉蠕娥突槽脓车噪脯贾娘抓躲替搪鹰惺眩亿畅涛醉汀树略柞泄纫哉扑叠其拖很矿召驳遥勋集标喊绝刚丫醇槽浙院锤危咆绕在雷遂蛊缆唐眷衡惜屋派寒醋爪浚贯披壁倒山鞭纲紫跃爪刮悬淹焦陋胁芭搐哑限乓撂酋高蹲梳忱翔抑凑呼嫌抿暑铭恃趴你擦窥亨呆连尺锹逗坏窟王皱古烦援甸穴桃钒假霄趁锡宫掀箍振桩巨恬闽谆捉蜒受超躁宇匈指鼎姥灶腰丛队滤大针克