课程名称︰编译程式设计 课程性质︰系必修 课程教师︰陈俊良 开课学院：电资学院 开课系所︰资讯系 考试日期（年月日）︰2011/04/28 考试时限（分钟）：120 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : Consider the following grammar for questions 1~7. The reference figure in the next page is generated by "bison --graph". 1. ExaminationPreparation -> TheoryForScanner scanner E -> TscP contextFreeGrama Parsers 2. TheoryForScanner -> regularExpression T -> r 3. TheoryForScanner -> null (学过了) T -> null 4. Parsers -> topDownParser BottomUpParsers P -> tB 5. Parsers -> BottomUpParsers topDownParser P -> Bt 6. BottomUpParsers -> MoreBottomUpParsers bottomUpParser B -> Mb 7. MoreBottomUpParsers -> bottomUpParser MoreBottomUpParsers M -> bM 8. MoreBottomUpParsers -> null M -> null 1. Complete the SetSetSet table. (15%) 2. The reference figure has 16 states. How many states does LR(1) state machine have? (5%) 3. Complete the LALR(1) item sets, including non-kernel items. (20%) 4. Are SLR(1) table and LALR(1) table the same? Explain your reason briefly. (2+3%) 5. Is the grammar LL(1)? Explain your reason briefly. (2+3%) 6. Is the grammar LALR(1)? Explain your reason briefly. (2+3%) 7. Is the grammar LR(1)? Explain your reason briefly. (2+3%) 8. Today, many language compliers are written in the languages themselves. For example. GCC is written in C and javac is written in Java. This raises something of a "chicken and eggs" problem. Now, you are asked to create the first C compiler for system NEW. And, you are given a C compiler source written in C for system OLD as well as a C compiler executable for system OLD. Explain how to develop the first C compiler for system NEW efficiently. (20%) 9. Let n be the number of input tokens. What is the time complexity of LR(1) shift-reduce parsing? Explain your reason. [hint: number of push/pop operations] (5+15%) == 图扫描後补上。 --

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