编译原理课程作业

《编译原理》作业参考答案一、填空1．图二图一。

2．文法是无ε产生式，且任意两个终结符之间至多有一种优先关系的算符文法。

3．最右推导最右推导。

4．对于循环中的有些代码，如果它产生的结果在循环中是不变的，就把它提到循环外来。

把程序中执行时间较长的运算替换为执行时间较短的运算。

5．对于文法中的每个非终结符A的各个产生式的候选首符集两两不相交；对文法中的每个非终结符A，若它存在某个候选首符集包含ε，则FIRST（A）∩FOLLOW（A）= ø6．控制。

7．语义分析和中间代码产生8．自上而下自下而上自上而下9．自下而上表达式10．自下而上11．源程序单词符号12． DFA初态唯一，NFA初态不唯一；DFA弧标记为Σ上的元素，NFA弧标记为Σ*上的元素；DFA的函数为单射，NFA函数不是单射13．词法，词法分析器，子程序，语法14．ε，a，ab，ab15．终结符号，非终结符号，产生式16．L(G)={a n | n≥1}17．1型，2型，3型18．二义的19．快20．终态，输入字21．单词符号，终结符22．归约23．必须24．直接25．终结符，更快26．E→E+∙T， E→E∙+T， E→∙E+T， E→E+T∙27．归约—归约28．类型检查，一致性检查29．词法分析、词法30．语法分析程序、语法31。

终结符号、产生式、开始符号、非终结符32．2、2、333．不需要避开34．符合、不符合35．推导36．包括37．Ass38．一定没有、一定没有、至多只有一个39．SLR（1）40．移进——归约41．a.控制流检查、b.一致性检查、c.相关名字检查二、判断下面语法是否正确1 ×2 ×3 √4 ×5 √6 ×三、简答题1．词法分析的任务是对输入的源程序进行单词及其属性的识别，为下一步的语法分析进行铺垫；有两种方法可以实现词法分析器：一，手工编写词法分析程序。

二，由词法分析器自动生成程序生成。

编译原理独立作业2010.5一、简答题1、 构造一个文法使其生成的语言是不允许0打头的偶正整数集合。

2、文法][E G ：T T E T E E -+→，F F T F T T /*→，i E F )(→，构造句型i T T T *+-的语法树，并指出该句型的短语、直接短语、句柄、素短语和最左素短语。

3、 某LL(1)文法的预测分析表如下，请在下述分析过程表中填入输入串（ a , a ）$ 的分析过程。

4、 文法][S G ：R L S =→，R S →，R L *→，i L →，L R →，求增广文法中LR(1)项目集的初态项目集I 0。

5、文法][S G ：G G S S ;→，()G G t H →，)(S a H →，求出各非终结符的FISTVT 和LASTVT 集合。

二、分析题：1、构造自动机，使得它能识别字母表{0,1}上以00结尾的符号串，将构造的自动机确定化，并写出相应的正规文法。

2、文法][S G ：RT eT S → εDR T → εdR R → bd a D →，写出每个非终结符的FIRST 集和FOLLOW 集，并判断该文法是否为LL(1)文法。

3、若有文法][S G ：AB S → εaBa A → εb A b B → (1)试证明该文法是SLR(1) 文法，并构造SLR(1)分析表。

（2）给出输入串aa # 的分析过程。

参考答案一、简答题1、构造一个文法使其生成的语言是不允许0打头的偶正整数集合。

8|6|4|2|ABC Z → 9|8|7|6|5|4|3|2|1→A ε|0|B AB B → |8|6|4|2|0→C2、文法][E G ：T T E T E E -+→，F F T F T T /*→，i E F )(→，构造句型i T T T *+-的语法树，并指出该句型的短语、直接短语、句柄、素短语和最左素短语。

短语：T ，T-T ，i ，T*i ，T-T+T*i直接短语：T ， i 句柄： T素短语（P72）：T-T,i 最左素短语：T-T3 某LL(1)文法的预测分析表如下，请在下述分析过程表中填入输入串（ a , a ）$ 的分析过程。

编译原理作业
1.设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及A+
2. 令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，(xy)3
3. 设有文法G[S]：S::=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语法树。

4. 已知文法G[Z]：Z::=U0∣V1 、U∷=Z1∣1 、V::=Z0∣0 ,请写出全部由此文法描述的只含有四个符号的句子。

5. 已知文法G[S]：S::=AB A::=aA︱εB::=bBc︱bc , 写出该文法描述的语言。

6.已知文法E::=T∣E+T∣E-T 、T::=F∣T*F∣T/F 、F::=(E)∣i，写出该文法的开始符号、终结符号集合V T、非终结符号集合V N。

7. 对6题的文法，写出句型T+T*F+i的短语、简单短语以及句柄。

8. 设有文法G[S]：S::=S*S|S+S|(S)|a，该文法是二义性文法吗？给出分析过程。

9. 写一文法，使其语言是奇正整数集合。

10.给出语言{a n b m|n,m≥1}的文法。

编译原理作业集1 第二章词法分析1. C或Java语言的标示符是字母和数字组成的序列，第一个字符必须是字母，下划线视为字母，且大小写字母不同。

请写出匹配C或Java语言标示符的正规表达式。

2.为下边所描述的串写正规式，字母表是 {0, 1}. a) 以11 结尾的所有串 b) 只包含一个1的所有串2 第三章上下文无关文法1. ________是描述程序设计语言语法结构的形式工具。

2. 设G=(VN，VT，P，S)是一文法，且V= VN∪VT，若S =>*α，α∈V，则称α为文法G的，若S=>*α，α∈VT，则称α为文法G的。

3. 给出语言L={ab|j>i>=1}的上下文无关文法。

4. 文法G[S]的产生式如下：S?SaS | SbS | cS | Sd | t 对于输入串 tbctat: (1) 给出一个推导；(2) 画出(1)中推导对应的分析树；ij**(3) 文法G是否是二义性的，请证明你的结论。

3 第四章语法分析1. 考虑文法G[S]:S-> A��B A->a|b B->(C) C->CS|S 1) 消除上述文法的左递归，重写该文法。

2) 求消除左递归后的文法的非终结符构造First集合和Follow集合。

3) 为消除左递归后的文法构造LL(1)分析表。

4) 并写出对句子 (ab) 的LL(1)分析过程。

2. 给定文法G[S]: S->SaSb��c给出句子 cacbacb 的规范推导，画出该句子的语法推导树，指出该句子的句柄。

3. 给定文法G[S]:S->S b A��A A->a 1) 造文法G[S]的LR(1)项目的DFA。

2) 上述文法构造LR(1)分析表。

3) 写出句子 ababa的分析过程。

4 第五章语义分析1.通过下面文法给出的十进制数的浮点数值，写出一个属性文法(提示：使用一个属性count计算小数点右面数字的个数)。

秋兰大编译原理课程作业B————————————————————————————————作者：————————————————————————————————日期：单选题编译程序使用_____区别标识符的作用域。

A: 说明标识符的过程或函数名B: 说明标识符的过程或函数的静态层次C: 说明标识符的过程或函数的动态层次D: 标识符的行号单选题编译程序是一种常用的______软件。

A: 应用B: 系统单选题扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即( ) A: 字符B: 单词C: 句子D: 句型单选题栈式动态分配与管理在过程返回时应做的工作有（）。

A: 保护SPB: 恢复SPC: 保护TOPD: 恢复TOP单选题语言是( )A: 句子的集合B: 产生式的集合C: 符号串的集合D: 句型的集合单选题编译程序是对_____。

A: 汇编程序的翻译B: 高级语言程序的解释执行C: 机器语言的执行D: 高级语言的翻译单选题构造编译程序应掌握____。

A: 源程序B: 目标语言C: 编译方法D: 以上三项都是单选题一个LR（1）文法合并同心集后,如果不是LALR(1)文法必定存在( )A: 移进--归约冲突B: 归约--归约冲突单选题下推自动机识别的语言是( )A: 0型语言B: 1型语言C: 2型语言D: 3型语言单选题若文法 G 定义的语言是无限集，则文法必然是 _____。

A: 递归的B: 前后文无关的C: 二义性的D: 无二义性的单选题四元式之间的联系是通过（）实现的。

A: 指示器B: 临时变量C: 符号表D: 程序变量单选题间接三元式表示法的优点为_____。

A: 采用间接码表，便于代码优化处理B: 节省存储空间，不便于表的修改C: 便于代码优化处理，节省存储空间D: 节省存储空间，不便于代码优化处理单选题文法G[N]=（{b}，{N，B}，N，{N→b│bB，B→bN}），该文法所描述的语言是 ____。

第3章作业【编辑人：陈芳芳】1.写一文法，使其语言是偶正整数的集合。

要求：（1）允许0打头；（2）不允许0打头。

【解】：(1)允许0打头且含0的偶正整数集合的文法为：N—>(0|D|E)N|(E|0)D—>1|3|5|7|9E—>2|4|6|8(2) 不允许0打头的偶正整数集合的文法为：R—>(D|E)N|EN—>(0|D|E)N|(E|0)D—>1|3|5|7|9E—>2|4|6|82.一个上下文无关文法生成句子abbaa的推导树如下：SA B Sa S B B A aƐ b b a（1）给出该句子的相应的最左推导，最右推导。

（2）该文法的产生式集合P可能有哪些元素？（3）找出该句子的所有短语，简单短语，句柄。

【解】：（1）最左推导：S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa最右推导：S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa (2) 产生式集合P：S—>ABS | Aa| ƐA—>aB—>SBB | b(3) 短语：a , Ɛ , b , bb , aa , abbaa直接短语：a , Ɛ , b句柄：a3、给出生成下述语言的上下文无关文法：(1){a n b n a m b m | n, m >= 0}(2){1n0m1m0n | n, m >= 0}【解】：（1）S—>AAA—>aAb | Ɛ（2）S—>1S0 | AA—>0A1 | Ɛ第4章课后作业1. 构造一个状态数最小的DFA，它接受∑={0,1}上所有倒数第二个字符为1的字符串。

【编辑人：胡志高】【解】：（1）构造相应的正规式：（0|1）* 1（0|1）（2）由正规式构造NFA，如下图：（3）NFA转化DFA① T0=ε-closure({0})={0}②运用子集构造法求DFA状态，如下表，其中T0为初态，T2、T3为终态：ε-closure(move(Ti,0))ε-closure(move(Ti,1)) T0={0}{0} {0,1}T1={0,1} {0，2} {0，1，2}T2={0,2} {0} {0,1}T3={0，1，2} {0,2} {0,1，2}③分别用0,1,2,3代表T0，T1，T2,T3,得DFA如下图：（4）最小化DFA①找DFA中等价状态，分析过程如下：P0=({0,1}，{2,3})P1=（{0}，{1}，{2}，{3}）经以上分析可知：0无等价状态。

习题11.1解释名词：源语言、目标语言、翻译器、编译器和解释器。

答：源语言是指待翻译的语言，和目标语言相对。

目标语言是指被翻译的语言，与源语言相对。

能够完成从一种语言到另一种语言的变换的软件称为翻译器，这两种语言分别叫做该翻译器的源语言和目标语言。

编译器是一种特殊的翻译器，它进行语言变换的特点是目标语言比源语言低级。

解释器是不同于编译器的另一类语言处理器。

它不像编译器那样通过翻译来生成目标程序，而是直接执行源程序所指定的运算。

它的执行方式是一边翻译一边执行，因此其执行效率一般偏低。

1.2典型的编译器可以划分成几个主要的逻辑阶段？各阶段的主要功能是什么？答：典型的编译器可以划分成七个主要的逻辑阶段，分别是词法分析器、语法分析器、语义分析器、中间代码生成器、独立于机器的代码优化器、代码生成器、依赖于机器的代码优化器。

各阶段的主要功能：（1）词法分析器：词法分析阅读构成源程序的字符流，按编程语言的词法规则把它们组成词法记号流。

（2）语法分析器：按编程语言的语法规则检查词法分析输出的记号流是否符合这些规则，并依据这些规则所体现出的该语言的各种语言构造的层次性，用各记号的第一元建成一种树形的中间表示，这个中间表示用抽象语法的方式描绘了该记号流的语法情况。

（3）语义分析器：使用语法树和符号表中的信息，依据语言定义来检查源程序的语义一致性，以保证程序各部分能有意义地结合在一起。

它还收集类型信息，把它们保存在符号表或语法树中。

（4）中间代码生成器:为源程序产生更低级的显示中间表示，可以认为这种中间表示是一种抽象机的程序。

（5）独立于机器的代码优化器：试图改进中间代码，以便产生较好的目标代码。

通常，较好是指执行较快，但也可能是其他目标，如目标代码较短或目标代码执行时能耗较低。

（6）代码生成器：取源程序的一种中间表示作为输入并把它映射到一种目标语言。

如果目标语言是机器代码，则需要为源程序所用的变量选择寄存器或内存单元，然后把中间指令序列翻译为完成同样任务的机器指令序列。

编译原理作业题整理一、概述编译原理是计算机科学与技术领域的重要基础课程，主要研究编译器的设计与实现。

编译器是将高级语言程序翻译成机器语言的工具，它在软件开辟过程中起着至关重要的作用。

为了匡助学生更好地理解和掌握编译原理的相关知识，以下是一些编译原理作业题整理。

二、词法分析1. 请编写一个正则表达式，用于匹配所有以字母开头，后跟零个或者多个字母或者数字的标识符。

2. 请编写一个正则表达式，用于匹配所有以0开头的八进制数。

3. 请编写一个正则表达式，用于匹配所有以1开头的二进制数。

三、语法分析1. 请给出以下文法的FIRST集和FOLLOW集：S -> aAB | bCDA -> cA | εB -> dC -> eC | εD -> f2. 请构造以下文法的LL(1)分析表：文法:S -> aAB | bCDA -> cA | εB -> dC -> eC | εD -> f3. 请给出以下文法的LR(0)项集族和DFA：文法:S -> L = RL -> * R | iR -> L四、语义分析1. 请给出以下语义规则的翻译方案：E -> E + T { E.val = E1.val + T.val }E -> T { E.val = T.val }T -> T * F { T.val = T1.val * F.val }T -> F { T.val = F.val }F -> ( E ) { F.val = E.val }F -> num { F.val = num.val }2. 请给出以下语义规则的中间代码生成方案：E -> E + T { t = newtemp(); gen(t, '+', E1.val, T.val); E.val = t; }E -> T { E.val = T.val }T -> T * F { t = newtemp(); gen(t, '*', T1.val, F.val); T.val = t; }T -> F { T.val = F.val }F -> ( E ) { F.val = E.val }F -> num { F.val = num.val }五、运行时环境1. 请简述静态作用域和动态作用域的区别。

《编译原理》作业题库1. 单选题1. 下列哪一项不是与机器有关的代码优化（）。

A. 寄存器优化B. 多处理优化C. 特殊的指令优化D. 有用的指令消除正确答案：D2. 处理冲突的方法不包括以下哪种方法（）。

A. 开放定址法B. 再哈希法C. 链地址法D. 建立一个私有溢出区正确答案：D3. 优化可生成（）的目标代码。

A. 运行时间较短B. 占用存储空间较小C. 运行时间短但占用内存空间大D. 运行时间短且占用存储空间小正确答案：D4. 一个文法是递归的，则它产生的语言的句子个数（）。

A. 必定无穷B. 必定有限C. 可能无穷，也可能有限D. 说不准正确答案：A5. 已知文法G：S→WZ W→X|Y X→a|aX Y→b|bY Z→c|cZ,G定义的语言的相应正规式为（）。

A. aa*|bb*|cc*B. （aa*|bb*）cc*C. aa*(bb*|cc*)D. (a|b|c)*正确答案：B6. 设G 是一个给定的文法，S 是文法的开始符号，如果S->x( 其中x∈V*), 则称x 是文法G 的一个（）。

A. 候选式B. 句型C. 单词D. 产生式正确答案：B7. 词法分析器用于识别（）。

A. 字符串B. 语句C. 单词D. 标识符正确答案：C8. 给定文法G[E]:E→E+T∣T T→T*F∣F F→(E)∣i, 则以下（）全都不是规范句型的活前缀①T+ ②T* ③ε④T*F ⑤E+E ⑥E* ⑦E+ T* ⑧i ⑨（E+T）⑩（i）A. ②④⑥B. ⑤⑥⑩C. ①②③④D. ⑦⑧⑨正确答案：A9. 下列（）不属于程序设计语言中的低级语言？A. 机器语言B. 汇编语言C. C语言D. 面向机器的程序设计语言正确答案：C10. 设已给文法G=（VN，VT，P，S），其中：VN={S} VT={a1,a2,…,an,∨,∧,~,[,]} P={S→ai∣i=1,2,…,n}∪{S→~S,S→[S∨S],S→[S∧S]} 此文法所产生的语言是( )。

塔里木大学信息工程学院课程论文基于 c 语言的简单词法分析器的设计课程名称编译原理所属学院信息工程学院班级计算机16-6学生姓名李鹏宇学号 5011212611二零一四年十二月目录一、引言 (1)二、基于c 语言词法分析器的设计 (1)2.1词法分析器的设计原则 (1)2.2词法分析器的设计对象 (2)2.3词法分析器的任务及功能 (2)2.3.1词法分析器的任务 (2)2.3.2 词法分析程序的功能： (2)2.4各种单词符号对应的种别码： (2)三、基于c 语言词法分析器的实现 (3)3.1词法分析程序的算法思想： (3)3.2主程序示意图： (3)3.3函数定义说明 (4)3.4程序设计实现及功能说明 (4)3.4.1关键字的定义 (4)3.4.2符合的关键字的查找 (4)四、词法分析程序的C语言程序源代码 (5)五、结果分析： (10)六、结束语 (11)参考文献 (7)摘要：词法分析器构造技术起源于编译器前端的词法分析需求，是编译的第一阶段。

其主要任务是读入输入字符，产生记号序列，并提交给语法分析使用。

词法分析器技术也经常应用于其他领域，如查询语言与信息检索系统。

在每个应用中，最基本的问题是如何设计与说明一种特殊的程序，它能够完成由字符串的模式触发的动作。

本文通过实际构造FineC语言（作者设计的一个C语言的轻量子集）的词法分析器对词法分析器的构造原理做了基于实践的探讨。

关键字：词法分析器，双缓冲区，符号表，正则表达式，状态转换图一、引言词法分析顾名思义，就是分词。

它是用程序设计语言编制出的源程序作为输入，以单词的序列作为输出。

分词的过程可以通过编制程序让其自动完成，我们通常把这个分词程序称为词法分析器。

词法分析器分析的源程序可以是现有的各类程序设计语言源程序也可以是人为给定的模型语言的源程序。

它一般有五个阶段:词法分析,语法分析,语义分析和中间代码产生及优化,目标的代码生成。

完成计算机翻译过程的重要阶段,它为以后的语义分析、语法分析打好基础, 做好准备,以便高效的、高质量的生成目标语言的程序。