配套资料 计算机编译原理编译原理本科试卷A.docx

《配套资料 计算机编译原理编译原理本科试卷A.docx》由会员分享，可在线阅读，更多相关《配套资料 计算机编译原理编译原理本科试卷A.docx（10页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、华南理工大学期末考试编译原理试卷A考前须知：1.考前请将密封线内填写清楚;2.所有答案请直接答在试卷上;3.考试形式：闭卷；4.本试卷共大题，总分值100分，考试时间120分钟。题号A四五总分得分评卷人Note: Whether English or Chinese doesn t impact your score.Fill in the blanks (18%)a. Normally, A compiler consists of a number of phases. They are Scanner Grammar parser, Semantic analyzer, Sourer C

2、ode Optimizer. , Code Generator, and target code optimizerThe logical units the scanner generates are called Tokens. For a modern programming language, there are five types of token. They are Identifier , ReservedWords,Number,b. Based on the following C source code fragmentint gets(char *s)(if(s = N

3、ULL)(printfCillegal point parameter n); return -1;return 0;)Please answer:a) int is a aprintf? is ab) “s” is a (an)“= = is ac) U is aA grammar G usually includes four components, they are, and.1. (Terms Translation, 12%)Please give a brief explanation to the following terms in compiler science domai

4、na) Compilerb) Source codec) Scannerd) Tokens e) Terminal symbol f) Ambiguous Grammar2. (Scanning; 20%)(10%) Construct an NFA that recognizes the same language as defined by the following regular expression:(a*ba*b)*ba*(a) (10%) Using the subset construction, convert the NFA into a DFA.abA=01,2,5BCB

5、=2BDC=3,6, 7,8)EFD=3DFE=3,7, 8EFF=1,2,4,5(LL parsing; 25%) Consider the following grammar G(S):S-number | ListList - (Seq)Seq - Seq, S | SWhere number and are terminal symbols, and the others symbols are non-terminal.(a) (7%) Please write the left-most derivation for sentence (4, (34)”8%Please conve

6、rt the grammar G into a LL(1) grammar G1 by remove the left recursion.(b) 10%Based on your LL(1) grammar Gl, please calculate the FOLLOW setand FIRST set, and build its LL(1) table.3. (LR parsing; 25%)Consider the following grammar GS:E(L) | a L-EL |EWhere a J (“，) are terminal symbols and the other

7、s are non-terminal symbols.(a) 5%. Construct the DFA of LR(O) items of this grammar.(b) 10% Construct the SLR(l) parsing table.(c) 10% Show the parsing stack and the action of a SLR(l) parser for the input string: (a (a a)华南理工大学期末考试答案编译原理试卷A1 Fill in the blanks (18%)a. Grammar Parser , Sematic Analy

8、zer , Source Codr Optimizer Target Code OptimizerReserved Words , Identifier, Number, Operator Special Symbola) inf9 is a Reserved Wordb) printf9 is aReserved Wordc) s is a (an) Identifierd) “= 廿 is a Operatore) “CT is a Numberd. Terminal symbol Non-Terminal symbol, start symbol ,and Product Rules2.

9、 (Terms Translation, 12%)a) Compiler一种应用程序，将源代码转换为指定的目标代码。b) Source code文本文件，其中内容是按照指定的文法规那么描述特定的算法，c) Scanner将文本字符串按照词法规那么，转换为特定的内部标识，供编译器后续分析。d) Tokens源文件中最基本的信息单元e) Terminal symbol文法规那么中不需要产生式定义的符号f) Ambiguous Grammar使用不同推导方法，推导出不同语法树，就称该文法为二义文法。3. (Scanning; 20%) (a) (10%)(b) (10%)abA=0,l,2,5BCB

10、=2BDC=3,6, 7,8EFD=3DFE=3,7, 8)EFF=1,2,4,5BC4. (LL parsing; 25%)(a) (7%)S -List-(Seq)-(Seq,S)-(S,S)-(number, S)-(4,S)-(49List)-(4,(Seq)-(4,(S)-(4,(number)-(4, (34)(b) (8%)S-number | ListList - (Seq)Seq - S SeqlSeql-,S Seql| (c)(10%)5. (LR parsing; 25%)FIRSTSETFOLLOWSET()number$Seqnumber/)SSeqlSSeqlSe

11、ql , ),S SeqlList()$,),(Seq)Snumber,($,),Lnumber(a) (5%)1()a$Es1S32s1S345accr2r2r2r2s1r4S346s7r3r1r1r1r1Parsing stack InputAction1234567891011121314151617$0 $0(1 $0( la3 $O(1E4 $O(1E4(1 $O(1E4(1 a3$O(1E4(1E4 $0(lE4(lE4a3$O(1E4(1E4E4 $O(1E4(1E4L6 $O(1E4(1L5 $O(1E4(1L)7 $ O(1E4E4 $ O(1E4L6 $O(1L5 $O(1L5)7 $0E2(a (a a) $a (a a)$(a a)$(a a) $a a) $ a)$ a)$)$ )$ )$)$ )$ )$ )$ )$ $shift 1shift3r E-a shiftl shift3r E-a shift3 r E-a rL-Er L-EL shift7r E-(L) r L-E r L-EL shift7r E-(L) acc