课程名称︰ compiler 课程性质︰ 必修课 课程教师︰ 薛智文 开课学院： 电资学院 开课系所︰ 资讯工程学系 考试日期（年月日）︰ 2008/4/14 考试时限（分钟）： 180 是否需发放奖励金： yes , thx （如未明确表示，则不予发放） 试题 : Compiler Name: ________ 902 39200 01, Spring 2008 Score: /110/360 ID: ______________ Midterm, April 14th, 9:10 - 12:10 This is an openbook and open-lecture-note exam. Please do answer in the order of question number in one answer sheet. You can write in Chinese. Please sign your name andturn in this paperwith your answer sheet. Good luck. 1. Explain or compare the turns used in Compiler in the following: (a) DFA-based scanning; NFA-based scanning.[10%] (b) cycles;useless[10%] (c) synchronization in error handling [10%] (d) recursive-descent parser;predictive parser [10%] (e) lookahead propagation; [10%] (f) regular expression;context free grammar [10%] 2. Modify the following grammar so that the left most derivation and right most derivation are the same and is right associative, i.e 2-3-4 = 2-(3-4) =3 [20%]Note that operator precedence / < - , 8-4/2 = 8-4/2 =2 E-> int E-> E-E E-> E/E E-> (E) 3.Explain why LL(1) ≦ LR(1) ? Why SLR(1) and LALR(1) always have the same number of states[10%] 4.Give an example of a useage of lookahead operators in LEX [10%] How lookahead operators are inplemented in LEX?[10%] What does LEX do when multiple rules are matched at the same time for a given input. 5.Assume A->α·Xβ∈I During LR(0) parsing.why it is the case that closure(A->α·Xβ)≦Goto(I,X) not the case closure({A 'αX·β}) = GOTO(I,X). [10%] Use the following grammar and its LR(0) automaton to show how a GOTO(I, X) is the union of some closure({ A 'αX ·β})'s. [15%] E`->E E ->E+T T ->T*F F->(E)|id 6. Assume G is an LR(0) Grammer. Let F'εbe a production that is not currently in G. Assume F is a nonterminal that is already in G. Let G* be the new grammar from G by inserting the new production F->ε.Describe the possible impacts(in the areas of conflict,expressivepower and parsing complexities) of adding this new production[30%] 7. Eliminate left factor and left recursion from the following grammar[30%] A->Ac|Ad|e|xyC|r B->k|Ayy|yy|Bw|t C->Ax|y|id|Cee D->Auv|Buv|p 8.consider the following grammar with the starting nonterminal E E->E-T|T T->T(F)|F F->F*|id|w|[Q] Q->a|+E (a) compute the LR(0) automation[35%] (b) compute the LR(1) parsing table [35%] (c) using LR(1) parsing to parse the input id-[+w] [20%] 9.consider the following grammar with E being the starting nonterminal E->E'TR E'->TE'T'|(RH)|ε T->a|b|FFT' T'->*F(T')|ε F->char|int|[E]|ε R->E:T|ε H->x1|x2 (a) Compute FIRST for all nonterminals [15%] (b) Compute FIRST for all strings on the right hand side of a production.[20%] (c) Compute FOLLOW for all nonterminals. [20%] --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.4.234