《编译原理本科试卷a》由会员分享，可在线阅读，更多相关《编译原理本科试卷a（9页珍藏版）》请在金锄头文库上搜索。
1、编译原理试卷 A 第 1 页 共 10 页诚信应考,考试作弊将带来严重后果！华南理工大学期末考试 编译原理 试卷 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.
2、They are Scanner Grammar parser, _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
3、_, _, _. 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 第 2 页 共 10 页a) “int” is a _b) “printf” is a _ c) “s” is a (an) _ d) “= =” is a _ e) “0” is a _d.
4、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 编译原理试卷 A 第 3 页 共 10 页3. (Scanning;
5、 20%)(a) (10%) Construct an NFA that recognizes the same language as defined by the following regular expression: (a*ba*b)*ba*076543218 bbb aaa(b) (10%) Using the subset construction, convert the NFA into a DFA. a bA=0,1,2,5 B CB=2 B DC=3,6, 7,8 E FD=3 D FE=3,7, 8 E FF=1,2,4,5 B C4. (LL parsing; 25%
6、) 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)”编译原理试卷 A 第 4 页 共 10 页(b) 8%Please convert the grammar G into a LL(
7、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. 编译原理试卷 A 第 5 页 共 10 页5. (LR parsing; 25%)Consider the following grammar GS: E(L)|a LEL |EWhere a ,” (”， ” )” are terminal symbols and the others
8、 are non-terminal symbols.(a) 5%. Construct the DFA of LR(0) items of this grammar.(b) 10% Construct the SLR(1) parsing table.编译原理试卷 A 第 6 页 共 10 页(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. _Gramm
9、ar_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.
10、 Terminal symbol Non-Terminal symbol, start symbol ,and _Product Rules2. (Terms Translation, 12%)a) Compiler 一种应用程序，将源代码转换为指定的目标代码。b) Source code 文本文件，其中内容是按照指定的文法规则描述特定的算法，c) Scanner 将文本字符串按照词法规则，转换为特定的内部标识，供编译器后续分析。d) Tokens 源文件中最基本的信息单元编译原理试卷 A 第 7 页 共 10 页e) Terminal symbol 文法规则中不需要产生式定义的符号f) Am
11、biguous Grammar 使用不同推导方法，推导出不同语法树，就称该文法为二义文法。3. (Scanning; 20%)(a) (10%)076543218 bbb aaa(b) (10%)a bA=0,1,2,5 B CB=2 B DC=3,6, 7,8 E FD=3 D FE=3,7, 8 E FF=1,2,4,5 B CABCDEaaba abbbFaa编译原理试卷 A 第 8 页 共 10 页4. (LL parsing; 25%)(a) (7%)S -List-(Seq)-(Seq,S)-(S,S)-(number, S)-(4,S)-(4,List)-(4,(Seq)-(4,
12、(S)-(4,(number)-(4, (34)(b) (8%) S-number | ListList - (Seq)Seq - S Seq1Seq1-,S Seq1|(c)(10%)FIRSTSET FOLLOWSET ( ) , number $Seq number,( ) S Seq1 S Seq1Seq1 , , ) ,S Seq1List ( $,), , (Seq)S number,( $,), , L number5. (LR parsing; 25%)（a）(5%)编译原理试卷 A 第 9 页 共 10 页(b)(10%)(c) (10%)123456Parsing stac
13、k Input Action编译原理试卷 A 第 10 页 共 10 页7891011121314151617$ 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 L -E$ 0(1E4(1E4L6 ) $ r L-EL$ 0(1E4(1L5 ) $ shift7$ 0(1E4(1L)7 ) $ r E-(L) $ 0(1E4E4 ) $ r L-E$ 0(1E4L6
