华南农业大学编译原理题库.doc

标准华南农业大学期末考试银行(包括参考答案)考试科目：编辑原则考试时间：120分钟学号名年级专业文豪一个第二个三个45总分计分审查人计分第一，这个问题共6个问题，每个问题5分，共30分。1，写出与下面右边线性正则语法对应的正则表达式。语法对应的正则表达式如下：A(b|aa)*bS aDD bD | aA | bA aD2、提供以下语言集的上下文无关语法：(2010年2014年)语法：S aS | DD aDb | abL1= anbm | nm12，正则集L2=anbm CK | n1，m1，k1右线性正则语法配置。(2010年)S aS | aAA bA | bBB cB | c3、按照编译过程的5个阶段，编译程序的逻辑结构框图如下：拷贝4、编译过程的第5阶段，简要说明每个阶段的主要功能。(多年一定要考试)编译过程是指从输入源程序开始到输出目标程序的整个过程，这是一个非常复杂的过程，通常可以分为五个会话。词汇分析，扫描和分解构成源程序的字符串，识别一个单词。语法分析，根据语言的语法规则，将单词符号字符串组合成各种语法单位；语义分析和中间代码产生各种语法单位，分析其意义，进行初步翻译。代码优化，代码等效转换，以便更有效地生成代码；生成对象代码，将中间代码转换为特定机器的低级语言指令形式。5、“包含优化部分的编译程序运行得更有效。”这句话对吧？怎么了？即可从workspace页面中移除物件。这句话错了。优化不是编译器不可或缺的组成部分，包含更强、更复杂算法的优化编译器降低了开发效率和执行效率，但通常目标代码更有效。6、语法归纳翻译技术的基本思路简述。(2013年)语法诱导翻译技术的基本思想是在语法的每个生成中附加一个语义动作或语义子程序，在进行语法分析的过程中派生或签约时执行相应的语义动作，以完成预定的翻译工作。7、简短说明运算符优先分析方法。(2013年)运算符优先分析方法是一种移动-返回语法分析方法，它根据语法确定终结器之间的优先级，然后在移动-返回过程中比较相邻终结器之间的优先级关系，以确定句子模式中的可折叠字符串(最左边的语法)，并将它们重新分类。不是规范化分析方法，仅适用于分析运算符优先语法。8、简述翻译程序和编译程序的异同，以及编译程序和解释程序的异同。(2011年)翻译器是将一种语言程序(源)转换为另一种语言程序(目标)，对源语言和目标语言没有特殊要求，编译器是指将高级语言的源程序转换为低级语言程序，特别是在高级语言中。翻译器的一种类型。编译和解释器都将高级语言翻译为低级语言，但是编译程序首先运行，而不生成目标代码、运行目标代码、转换解释器边缘或生成目标代码。9，确定下图中的FA是NFA还是DFA，并以正则表达式说明它识别的语言。DFA(1点)，其正则表达式为：1*01*(01*01*)* (4点)1ab00110，确定下图中的FA是NFA还是DFA，并以正则表达式描述标识它的语言。(2011年)0ab0，10如果在a状态中输入0，则为NFA，因为它可以转换为a或b状态。等价正则表达式：0*(0|1)(00*(0|1)*11、语法和语义子程序如下：S T print(T.h)T T 1*E T.h=T 1.h E.hT E T.h=E.hE(T) E.h=T.hE a E.h=1使用减少分析方法，在分析器的输入为(a)*(a*a)时绘制相应的语法树(包含注释或不包含注释)，然后查找输出结果。语法树(稍)，输入为(a)*(a*a)，则输出结果为：312(2014)，型腔圆柱的表面积计算公式为s=2 * 3.1416 *(r)*(r-r)2 * 3.1416 *(r r)* h使用LR语法归纳翻译技术生成相应的3个地址代码，然后使用DAG编写优化的3个地址代码序列，从而生成最佳目标代码。使用合并已知量、删除公共子表达式、删除无用分配、交换语句位置等优化方法，可以获得以下三个地址代码序列：(1)t1=r(2)T2=6.2832 * t1(3)T3=T2 * h(4) T4=R-r (5) T5=T2*T4 (6) S=T5 T3查找13，A B*(-C) B/(-C)的后缀和3个地址代码。(2011年)后缀：ABC-* BC-/三个地址代码：T1=-C T2=B*T1 T3=A T2T4=-C T5=B/T4 T6=T3 T514、考虑以下三个地址语句顺序：(2011)l 1: read C；a=0；b=1；l 23360 a=a b；if BC goto L3；B=B 1；goto L2；goto L1；l 3: write A；HaltB1B2B3多馀的门，删除B4(1)将代码序列分为基本块，然后为每个基本块指定序列号。(2)。绘制每个基本块由(1)的序列号表示的代码序列的流程图。(3)。如果存在回路，则列出组成回路的节点(基本块)。(10分)(1)图分为四个基本块B1、B2、B3和B4B1(2)。流程图：B4B3B2(3)。构成循环的基本块是B2，B315、有以下翻译模式：S S print(S.h)S a S.h=0S(T) S.h=T.h 1T T 1，S T.h=T 1.h S.hT S T.h=S.h使用递减分析方法，在分析器的输入为(a) (a)时绘制相应的语法树(包含注释或不包含注释)，并查找输出结果。(2011年)结果如下：2s哟t)，以获取详细信息t而且，ssa哟t)，以获取详细信息sa语法树：计分其次，配置标识以下语言的最小DFA(共20分):1，一般1(0 | 1)* 0 | 0；(7点)111dba0010cNFA错误地发现4点，6点，最小DFA状态为1点，圆弧为0.5点。以2，101结尾的二进制字符串；(8点)00bad0c11110NFA错误地发现4点，6点，最小DFA状态为1点，圆弧为0.5点。不以3，101结尾的二进制字符串。(5分)00cba111100d计分构建最低DFA以识别以下语言(共15分钟):(2011)4，常规(0 | 1)*(00 | 11)(0 | 1)*；(5分)包含5、奇数1或奇数0的二进制字符串；(5分)可被6，2整除的二进制字符串。(5分)1、abc0000111d102、acbd01111003、1ab010以下常规相应状态转换图(DFA)(15)(2008)(7) 1(0 | 1)*10，1(8) 0*10*10*10*1(9) letter(letter | digit)*31021(7)0051(8)104130211Letter(9)2Letter1Digit计分7、确定下图NFA。(10点)(2013)bbb2a10bb3b23a结晶：(可以重命名状态)ba0，1，3a1，21，2，3bb(确定后重新设置简不会扣分，但必须有说明)8、将下图简化为DFA。(5分)(2013)0100100deabc11首先，退出DFA的状态集和非退出集E，A，B，C，D ；A，B，C，D0=B，C，C，E，因此将其细分为A，B，C，D。输入符号1，a，B，c 1=，d，d，因此再次A，B，C ；分割为B，C0=C，C，B，C1=D，D，因此无需进一步区分。b、c处于同等状态。最小的DFA包括：010ae0db1019.语法如下：S a | b | (T)T TeS | Ss指定语法树、短语、直接短语、素短语和句柄(Sebe(a)。(10分)语法树：(5分)(两点)球体：(Sebe(a)，Sebe(a)，Seb、(a)、s、b、a(1点)直线球：s，b，a(1点)子面域：b，a(1点)控制柄：s)，以获取详细信息t哟s)，以获取详细信息tetset哟bssa定义算术表达式的语法如下：(2011)E E T | E-T | TT T*F | T/F | FF PF | PP (E) | I构成句型E T*PP-i的语法树；表示句型中的所有短语、直球、小球和句柄。(10分)语法分析树：所有词组：E T*PP-i，E T*PP，I，T*PP，PP，p直接球体：p，I小球：PP，I句柄：pfpee-tttp* *ffpeI11、语法如下： (共15分)S aSe | AE(1)语法识别标准句型活性前缀的DFA构成。(2)创建上一步骤中DFA每个状态标识的每个活动前缀。(3)要给符号字符串吗？-嗯？-嗯？-嗯？LR移动-收缩过程，包括状态堆栈、符号堆栈、输入字符串和分析操作。(1)。(6点)扩展语法和生成编号：lightsssasesAE语法识别标准句型活动前缀DFA:aI 53360SaSe。I3: S aS.eaI 4: s a eeseI 23360s a.seS a.eS 。aSeS 。aesI 1: s SI 0: s sS aseS ae(2)。语法的所有标准句型的有效前缀是在上一步骤中由DFA的每个状态标识的符号字符串。 | s | a * | a * as | a * AE | a * ase(三点)(3) lr (0)分析表如下(6点):ACTION加藤ae#s0S211Acc2S2S433S54R2R2R25R1R1R1空格表示错误。计分定义算术表达式的语法如下：E E T | E-T | TT T*F | T/F | FF PF | PP (E) | I构成