编译原理本科试卷A.doc

姓名 学号 学院 班级 座位号 ( 密 封 线 内 不 答 题 )密封线线_ _ 诚信应考,考试作弊将带来严重后果！ 华南理工大学期末考试 编译原理 试卷A注意事项：1. 考前请将密封线内填写清楚； 2. 所有答案请直接答在试卷上； 3考试形式：闭卷； 4. 本试卷共 大题，满分100分，考试时间120分钟。题 号一二三四五总分得 分评卷人Note: Whether English or Chinese doesnt impact your score.1. Fill in the blanks (18%)a. Normally, A complier consists of a number of phases. They are Scanner Grammarparser, _Semantic analyzer_, _Source Code Optimizer_, Code Generator, and _target code optimizer _.b. The logical units the scanner generates are called Tokens. For a modern programming language, there are five types of token. They are _Identifier_, _Reserved Words_, _Number_, _, _. c. Based on the following C source code fragmentint gets(char *s) if (s = NULL) printf(“illegal point parameter n”); return -1; return 0;Please answer:a) “int” is a _b) “printf” is a _ c) “s” is a (an) _ d) “= =” is a _ e) “0” is a _d. A grammar G usually includes four components, they are _, _, _, and _.2. (Terms Translation, 12%)Please give a brief explanation to the following terms in compiler science domaina) Compiler b) Source code c) Scanner d) Tokens e) Terminal symbol f) Ambiguous Grammar 3. (Scanning; 20%)(a) (10%) Construct an NFA that recognizes the same language as defined by the following regular expression: (a*ba*b)*ba*(b) (10%) Using the subset construction, convert the NFA into a DFA. abA=0,1,2,5BCB=2BDC=3,6, 7,8EFD=3DFE=3,7, 8EFF=1,2,4,5BC4. (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)”(b) 8%Please convert the grammar G into a LL(1) grammar G1 by remove the left recursion.(c) 10%Based on your LL(1) grammar G1, please calculate the FOLLOW set and FIRST set, and build its LL(1) table. 5. (LR parsing; 25%)Consider the following grammar GS: E(L)|a LEL |EWhere a ,” (”，” )” are terminal symbols and the others are non-terminal symbols.(a) 5%. Construct the DFA of LR(0) items of this grammar.(b) 10% Construct the SLR(1) parsing table.(c) 10% Show the parsing stack and the action of a SLR(1) parser for the input string: (a (a a)华南理工大学期末考试答案 编译原理 试卷 A1. Fill in the blanks (18%)a. _Grammar_Parser_, _Sematic Analyzer_, _Source Code Optimizer_, _Target Code Optimizer _. b._Reserved Words_, _Identifier_, _Number_, _Operator_, _Special Symbol_c. a) “int” is a _ Reserved Wordb) “printf” is a _Reserved Word c) “s” is a (an) _ Identifier _ d) “= =” is a _ Operator_ e) “0” is a_ Number_ _d. Terminal symbol Non-Terminal symbol, start symbol ,and _Product Rules2. (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,1,2,5BCB=2BDC=3,6, 7,8EFD=3DFE=3,7, 8EFF=1,2,4,5BC4. (LL parsing; 25%)(a) (7%)S -List-(Seq)-(Seq,S)-(S,S)-(number, S)-(4,S)-(4,List)-(4,(Seq)-(4,(S)-(4,(number)-(4, (34)(b) (8%) S-number | ListList - (Seq)Seq - S Seq1Seq1-,S Seq1| (c)(10%)FIRSTSETFOLLOWSET(),number$Seqnumber,()S Seq1S Seq1Seq1, , ),S Seq1List($,), ,(Seq)Snumber,($,), ,Lnumber5. (LR parsing; 25%)（a）(5%)(b)(10%)(c) (10%)1234567891011121314151617Parsing stack Input Action$ 0 (a (a a) $ shift1$ 0 ( 1 a (a a)$ shift3 $ 0 ( 1a3 (a a) $ r E-a$ 0(1E4 (a a) $ shift1$ 0(1E4(1 a a) $ shift3$ 0(1E4(1 a 3 a) $ r E-a$ 0(1E4(1E4 a) $ shift3$ 0(1E4(1E4a3 ) $ r E-a$ 0(1E4(1E4E4 )$ r