下载文档原格式
编译原理期末考试试题及答案一、选择题（每题2分，共20分）1. 编译器的前端主要负责以下哪项工作？A. 代码优化B. 目标代码生成C. 词法分析和语法分析D. 运行时支持2. 词法分析器的主要任务是什么？A. 识别语法结构B. 识别词法单元C. 构建语法树D. 代码优化3. 语法分析中，使用哪种方法可以避免回溯？A. 递归下降分析B. LR分析C. LL分析D. 自顶向下分析4. 下列哪个选项不是中间代码的形式？A. 三地址代码B. 四元组C. 抽象语法树D. 汇编语言5. 代码优化的目标不包括以下哪项？A. 提高代码执行速度B. 减少程序占用的内存C. 增加程序的可读性D. 减少程序的执行时间二、简答题（每题10分，共30分）1. 简述编译器的主要组成部分及其功能。
2. 解释什么是语法制导翻译，并举例说明其在编译过程中的应用。
3. 描述静态作用域规则和动态作用域规则的区别。
三、计算题（每题15分，共30分）1. 给定一个简单的算术表达式 `3 + (4 * 5) - 2`，请使用逆波兰表示法表示，并说明其转换过程。
2. 假设有一个简单的文法如下：```S -> A BA -> a A | εB -> b B | ε```请写出使用该文法生成字符串 "ab" 的所有派生树。
四、论述题（每题20分，共20分）1. 论述编译器中代码优化的重要性，并举例说明常见的优化技术。
参考答案一、选择题1. C2. B3. B4. D5. C二、简答题1. 编译器的主要组成部分包括前端、中端和后端。
前端负责词法分析和语法分析，中端进行语义分析和中间代码生成，后端则负责代码优化和目标代码生成。
2. 语法制导翻译是一种基于文法规则的翻译技术，它将源程序的语法结构映射到相应的语义操作上。
例如，在编译过程中，语法制导翻译可以用于将源代码中的条件语句转换为中间代码中的跳转指令。
3. 静态作用域规则是指变量的作用域在编译时确定，而动态作用域规则是指变量的作用域在运行时确定。
《编译原理》期末试题（一）一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）1．编译程序是对高级语言程序的解释执行。
(× )2．一个有限状态自动机中，有且仅有一个唯一的终态。
(×)3．一个算符优先文法可能不存在算符优先函数与之对应。
(√ )4．语法分析时必须先消除文法中的左递归。
(×)5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。
(√)6．逆波兰表示法表示表达式时无须使用括号。
(√ )7．静态数组的存储空间可以在编译时确定。
(×)8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。
(×) 9．两个正规集相等的必要条件是他们对应的正规式等价。
(× )10．一个语义子程序描述了一个文法所对应的翻译工作。
(×)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．词法分析器的输出结果是_____。
A．( ) 单词的种别编码B．( ) 单词在符号表中的位置C．( ) 单词的种别编码和自身值D．( ) 单词自身值2．正规式M 1 和M 2 等价是指_____。
A．( ) M1和M2的状态数相等B．( ) M1和M2的有向边条数相等C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等3．文法G：S→xSx|y所识别的语言是_____。
A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx*4．如果文法G是无二义的，则它的任何句子α_____。
A．( )最左推导和最右推导对应的语法树必定相同B．( ) 最左推导和最右推导对应的语法树可能不同C．( ) 最左推导和最右推导必定相同D．( )可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握______。
编译原理复习题有答案编译原理复习题及答案一、选择题1. 编译器的主要功能是什么？A. 代码格式化B. 代码优化C. 将源代码转换为机器码D. 错误检测和修复答案：C2. 词法分析阶段的主要任务是什么？A. 语法分析B. 语义分析C. 识别源程序中的词法单元D. 代码生成答案：C3. 下列哪个不是编译原理中的常见数据结构？A. 栈B. 队列C. 哈希表D. 链表答案：D4. 语法分析通常采用哪种方法？A. 递归下降分析B. 动态规划C. 贪心算法D. 深度优先搜索答案：A5. 代码优化的目的是什么？A. 增加程序长度B. 减少程序运行时间C. 提高程序的可读性D. 增加程序的复杂性答案：B二、简答题1. 简述编译过程的主要阶段。
答案：编译过程主要分为四个阶段：词法分析、语法分析、语义分析和代码生成。
词法分析负责将源代码分解成词法单元；语法分析构建语法树，检查源代码的语法结构；语义分析检查程序的语义正确性；代码生成将源代码转换成目标代码或机器码。
2. 什么是自底向上的语法分析方法？答案：自底向上的语法分析方法是一种从叶子节点开始，逐步向上构建语法树的方法。
它通常使用移进-归约分析技术，通过将输入符号与栈顶符号进行匹配，不断地将它们归约成非终结符，直到整个输入被归约为起始符号。
3. 请解释什么是中间代码，并说明其作用。
答案：中间代码是一种介于源代码和目标代码之间的代码形式，通常用于代码优化和目标代码生成。
它具有高级语言的可读性，同时又能表达程序的控制流和数据流信息。
中间代码使得编译器可以在不同的阶段对程序进行优化，提高程序的执行效率。
三、论述题1. 论述编译原理中的错误处理机制。
答案：编译原理中的错误处理机制主要包括错误检测、错误恢复和错误报告。
错误检测是指在编译过程中识别出源代码中的语法或语义错误；错误恢复是指在检测到错误后，编译器采取的措施以继续编译过程，避免因单个错误而中断整个编译；错误报告则是向程序员提供错误信息，帮助其定位和修复错误。
《编译原理》期末复习题一、简答题1.DFA和NFA的区别是什么？答：dfa与nfa的区别表现为两个方面:一是nfa可以若干个开始状态，而dfa仅只一个开始状态。
另一方面，dfa的映象m是从k×∑到k，而nfa的映象m是从k×∑到k的子集，即映象m将产生一个状态集合（可能为空集），而不是单个状态。
2、何谓优化？按所涉及的程序范围可分为哪几级优化？1）优化：对程序进行各种等效转换，以便从转换后的程序开始，生成更有效的目标代码。
（2）三个层次：局部优化、循环优化和全局优化。
3.短语、简单短语和句柄之间的关系？语法树子树的末端节点符号串既是语法树所描述与对子子树的根的短语；简单子树的标点符号串既是简单短语；最左简单子树的末端符合既是句柄。
4、语法分析的任务是什么？输入、输出分别是什么？任务是在词法分析识别出单词符号串的基础上。
分析并判定程序的语法结构是否符合语法规则；输入：源程序；输出：单词符号串。
5.静态链和动态链分别存储哪些值？为了什么？静态链是指向静态直接外层最新活动记录地址的指针，作用是用来访问非局部数据；动态链是指向调用该过程前的最新活动记录的指针。
作用是运行时使运行栈上个数据区按动态建立次序结成链。
6.综合属性和继承属性的区别是什么？它的值在语法树中的传递方向是什么？区别：综合属性用于自上而下传递信息，继承属性用于自上而下传递信息。
方向：在语法树中，一个节点的综合属性的值由其子节点的综合属性值决定;一个节点的继承属性由此节点的父节点和/或兄弟节点的属性确定的。
7.什么是优化？优化效果的两个方面是什么？对程序进行各种等价变换，使得从变化后的程序出发，能生成更有效的目标代码。
通称为优化。
①、在目标代码生成以前，对语法分析后的中间代码进行的，这类优化不依赖于具体的计算机；②、在目标代码生成时进行的，它在很大程度上依赖于具体的计算机。
8、编译程序和解释程序的区别？哪个更通用？区别：编译器是一种程序，其中源语言是高级语言，目标语言是汇编语言或机器语言的低级语言。
《编译原理》复习题（看完必过）一、单项选择题1．将编译程序分成若干个“遍”是为了( B )A．提高程序的执行效率B. 使程序的结构更加清晰C．利用有限的机器内存并提高机器的执行效率D．利用有限的机器内存但降低了机器的执行效率2．不可能是目标代码的是( D )A．汇编指令代码 B．可重定位指令代码C．绝对指令代码 D．中间代码3．词法分析器的输入是( B )A．单词符号串 B．源程序C．语法单位 D．目标程序4．中间代码生成时所遵循的是( C )A．语法规则 B．词法规则C．语义规则 D．等价变换规则5．编译程序是对( D )A．汇编程序的翻译 B．高级语言程序的解释执行C．机器语言的执行 D．高级语言的翻译6．词法分析应遵循( C )A．语义规则 B．语法规则C．构词规则 D．等价变换规则7．词法分析器的输出结果是( C )A．单词的种别编码 B．单词在符号表中的位置C．单词的种别编码和属性值 D．单词属性值8．正规式M1和M2等价是指( C )A．M1和M2的状态数相等 B．M1和M2的有向弧条数相等C．M1和M2所识别的语言集相等 D．M1和M2状态数和有向弧条数相等9．词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，( B ) A．词法分析器应作为独立的一遍B．词法分析器作为子程序较好C．词法分析器分解为多个过程，由语法分析器选择使用．D．词法分析器并不作为一个独立的阶段10．如果L(M1)=L(M2)，则M1与M2( A )A ．等价B ．都是二义的C ．都是无二义的D ．它们的状态数相等 11．文法G ：S →xSx|y 所识别的语言是( C )A ．xyxB ．(xyx)* c ．x n yx n (n ≥0) d ．x *yx *12．文法G 描述的语言L(G)是指( A ) A．⎭⎬⎫⎩⎨⎧∈⇒=+*,|)(T V S G L αααB ．⎭⎬⎫⎩⎨⎧⋃∈⇒=+*)(,|)(N T V V S G L ααα C ．⎭⎬⎫⎩⎨⎧∈⇒=**,|)(T V S G L αααD ．⎭⎬⎫⎩⎨⎧⋃∈⇒=**)(,|)(N T V V S G L ααα 13．有限状态自动机能识别( C )A ．上下文无关文法B ．上下文有关文法C ．正规文法D ．短语文法14．如果文法G 是无二义的，则它的任何句子( A ) A ．最左推导和最右推导对应的语法树必定相同 B ．最左推导和最右推导对应的语法树可能不同 C ．最左推导和最右推导必定相同D ．可能存在两个不同的最左推导，但它们对应的语法树相同 15．由文法的开始符经0步或多步推导产生的文法符号序列是( C ) A ．短语 B ．句柄 C ．句型 D ．句子 16．文法G ：E →E+T|T T →T*P|P P →(E)|i则句型P+T+i 的句柄为( B )A ．P+TB ．PC ．P+T+iD ．i 17．文法G ：S →b|∧|(T) T →T ∨S|S 则FIRSTVT(T)=( C )A ．{ b ，∧，( }B ．{ b ，∧，) }C ．{ b ，∧，(，∨ }D ．{ b ，∧，），∨ } 18．产生正规语言的文法为( D )A ．0型B ．1型C ．2型D ．3型19．任何算符优先文法( D )优先函数。
此文档下载后即可编辑编译原理考试题及答案汇总一、选择1．将编译程序分成若干个“遍”是为了_B__。
A . 提高程序的执行效率B.使程序的结构更加清晰C. 利用有限的机器内存并提高机器的执行效率D.利用有限的机器内存但降低了机器的执行效率2．正规式 MI 和 M2 等价是指__C__。
A . MI 和 M2 的状态数相等和 M2 的有向弧条数相等。
C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等3．中间代码生成时所依据的是 _C_。
A．语法规则 B．词法规则 C．语义规则 D．等价变换规则4．后缀式 ab+cd+/可用表达式__B_来表示。
A． a+b/c+d B．(a+b)/(c+d) C． a+b/(c+d) D． a+b+c/d6．一个编译程序中，不仅包含词法分析，_A____，中间代码生成，代码优化，目标代码生成等五个部分。
A．( ) 语法分析 B．( )文法分析 C．( )语言分析 D．( )解释分析7．词法分析器用于识别__C___。
A．( ) 字符串 B．( )语句 C．( )单词 D．( )标识符8．语法分析器则可以发现源程序中的___D__。
A．( ) 语义错误 B．( ) 语法和语义错误C．( ) 错误并校正 D．( ) 语法错误9．下面关于解释程序的描述正确的是__B___。
(1) 解释程序的特点是处理程序时不产生目标代码(2) 解释程序适用于 COBOL 和 FORTRAN 语言(3) 解释程序是为打开编译程序技术的僵局而开发的A．( ) (1)(2) B．( ) (1) C．( ) (1)(2)(3) D．( ) (2)(3)10．解释程序处理语言时 , 大多数采用的是__B___方法。
A．( ) 源程序命令被逐个直接解释执行B．( ) 先将源程序转化为中间代码 , 再解释执行C．( ) 先将源程序解释转化为目标程序 , 再执行D．( ) 以上方法都可以11．编译过程中 , 语法分析器的任务就是__B___。
《编译原理》期末复习资料【题1】1.（a|b）*（aa|bb）（a|b）*画出状态转换图。
Ia Ib①1,2,3 2,3,4 2,3,5②2,3,4 2,3,4,6,7,8 2,3,5③2,3,5 2,3,4 2,,3,5,6,7,8④2,3,4,6,7,8 2,3,4,6,7,8 2,3,5,7,8⑤2,3,5,6,7,8 2,3,4,7,8 2,3,5,6,7,8⑥2,3,5,7,8 2,3,4,7,8 2,3,5,6,7,8⑦2,3,4,7,8 2,3,4,6,7,8 2,3,5,7,8Ia Ib1 2 32 4 33 2 54 4 65 7 56 7 57 4 6新的状态转换图如下：（1）A={1,2,3}，B={4,5,6,7} Aa={2,4} ×（2）A={1,3}，B={2}，C={4,5,6,7} Aa={2}⊂B，Ab={3,5} ×（3）A={1}，B={2}，C={3},D={4,5,6,7}（单元素可以不用看，必有，古先看D）Da={4,7}⊂D，Db={5,6}⊂D，Aa={2}⊂B，Ab={3}⊂C，Ba={4}⊂D，Bb={3}⊂C，Ca={2}⊂B，Cb={5}⊂C，则有baA B CB D CC B DD D D2.（a*|b*）b（ba）*的状态转换图。
Ia Ib①1,2,3,4 2,4 3,4,5,6,8②2,4 2,4 5,6,8③3,4,5,6,8 --- 3,4,5,6,7,8④5,6,8 --- 7⑤3,4,5,6,7,8 6,8 3,4,5,6,7,8⑥7 6,8 ---⑦6,8 --- 7Ia Ib1 2 32 2 43 --- 54 --- 65 7 56 7 ---7 --- 6新的状态转换图如下：化简：（用终结状态与非终结状态，然后输出状态一致分一类）。
（1）A={1,2,6}，B={3,4,5,7} Aa={2} ×（2）A={1,2}，B={6}，C={3,4,7}，D={5} Cb={5,6} ×（只要有一个不属于任何一个集合，就不行） （3）A={1,2}，B={6}，C={3}，D={4,7}，E={5} Ab={3,4} × （4） A={1}，B={2}，C={6}，D={3}，E={4,7}，F={5} Aa={2}⊂B ，Ab={3}⊂D ，Ba={2}⊂B ，Bb={4}⊂E ，Ca={7}⊂E ，Db={5}⊂F ，Eb={6}⊂C ，Fa={7}⊂E ，Fb={5}⊂Fa b A B D B B E C E --- D --- F E --- C FEF[注意事项]：[知识要点]：正则表达式：******|,|,)|(,)|(,)(,,|,ab a b a a b a a b a ab ab b a a{}a a aaa aa a a ,,,,*ε⇔；{}b a a b a ,)b (|⇔或；{}ab b a ab ⇔)(和；(){},,,,*ababab abab ab ab ε⇔；()()()(){} ,,,,,,||||*baba aabb aab b a b a b a b a b a ε⇔⇔()*|b a a 是最左边一个字母一定是a ，其余字母为b a 、的任意组合，不包括ε。
第八节习题一、单项选择题1、将编译程序分成若干个“遍”是为了 b 。
a．提高程序的执行效率b．使程序的结构更加清晰c．利用有限的机器存并提高机器的执行效率d．利用有限的机器存但降低了机器的执行效率2、构造编译程序应掌握 d 。
a．源程序b．目标语言c．编译方法d．以上三项都是3、变量应当 c 。
a．持有左值b．持有右值c．既持有左值又持有右值d．既不持有左值也不持有右值4、编译程序绝大多数时间花在 b 上。
a．出错处理b．词法分析c．目标代码生成d．管理表格5、 d 不可能是目标代码。
a．汇编指令代码b．可重定位指令代码c．绝对指令代码d．中间代码6、使用 a 可以定义一个程序的意义。
a．语义规则b．词法规则c．产生规则d．词法规则7、词法分析器的输入是 a 。
a．单词符号串b．源程序c．语法单位d．目标程序8、中间代码生成时所遵循的是- d 。
a．语法规则b．词法规则c．语义规则d．等价变换规则9、编译程序是对 d 。
a．汇编程序的翻译b．高级语言程序的解释执行c．机器语言的执行d．高级语言的翻译10、语法分析应遵循 b 。
a．语义规则b．语法规则c．构词规则d．等价变换规则解答1、将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选b。
2、构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选d。
3、对编译而言，变量既持有左值又持有右值，故选c。
4、编译程序打交道最多的就是各种表格，因此选d。
5、目标代码包括汇编指令代码、可重定位指令代码和绝对指令代码3种，因此不是目标代码的只能选d。
6、词法分析遵循的是构词规则，语法分析遵循的是语法规则，中间代码生成遵循的是语义规则，并且语义规则可以定义一个程序的意义。
因此选a。
7、b 8、c 9、d 10、c二、多项选择题1、编译程序各阶段的工作都涉及到bc 。
a．语法分析b．表格管理c．出错处理d．语义分析e．词法分析2、编译程序工作时，通常有abce 阶段。
---------------------------------------------------------------最新资料推荐------------------------------------------------------编译原理期末复习题一、名词解释（每小题６分，共５ *６分=３ 0 分） 1、什么叫编译程序？什么叫解释程序？它们两者的区别是什么？编译程序是把源程序翻译成目标语言的程序.编译得到的目标程序再经过连接装配形成可执行程序文件.用户运行可执行程序文件时不再需要源程序和编译程序. 解释程序是把源程序翻译成目标语言并执行的程序.解释程序的工作方式是逐条读入源程序中的语句,将该语句翻译成目标语言并执行.用户每次执行同样的程序都需要源程序文件和解释程序. 2、请解释源程序，目标程序，遍。
源程序是一种计算机的代码。
它会符合一定的语法，经过编译器编译或解释后生成具有一定功能的可执行文件或组件，也可以是某种接口。
是用程序设计语言编写的程序。
目标程序又称目的程序。
由语言处理程序（汇编程序，编译程序，解释程序）将源程序处理（汇编，编译，解释）成与之等价的由机器码构成的，计算机能够直接运行的程序，该程序叫目标程序。
遍指游历，即指令的顺序。
有三种顺序：左根右，左右根，根左右。
3、请解释字母表，符号串，推导。
1 / 4字母表是符号的非空有穷集合。
符号串是由字母表中的符号所组成的任何有穷序列。
推导：分直接推导产生式右部代替左部。
4、请解释正规式。
５、请解释句子，句型，上下文无关文法。
二、填空题（每空 2 分，共 10*２分=２ 0 分）1、有穷自动机分为：和２、 .有穷自动机接受的是语言. 3、已知文法 G[S]的产生式如下：S(L) ∣ a L L, S∣ S 属于 L（G[S]）的句子是 A ，（a， a）是 L（G[S]）的句子，这个句子的最左推导是 B ，最右推导是C ，语法树是 D 。
编译原理-期末复习编译原理⼀、单选题1、将编译程序分为若⼲个“遍”是为了（）。
BA.提⾼程序的执⾏效率B.使程序的结构更加清晰C.利⽤有限的机器内存并提⾼机器的执⾏效率D.利⽤有限的机器内存但降低了机器的执⾏效率2、构造编译程序应掌握（）。
DA.源程序B.⽬标语⾔C.编译⽅法D.以上三项都是3、变量应当（）。
CA.持有左值B.持有右值C.既持有左值⼜持有右值D.既不持有左值也不持有右值4、编译程序绝⼤多数时间花在（）上。
DA.出错处理B.词法分析C.⽬标代码⽣成D.管理表格5、（）不可能是⽬标代码。
DA.汇编指令代码B.可重定位指令代码C.绝对指令代码D.中间代码6、编译程序是对（）。
DA.汇编程序的翻译B.⾼级语⾔程序的解释执⾏C.机器语⾔的执⾏D.⾼级语⾔的翻译7、正规式M1和M2等价是指（）。
CA.M1和M2的状态数相等B.M1和M2的有象弧条数相等C.M1和M2所识别的语⾔集相等D.M1和M2状态数和有象弧条数相等8、如果⽂法G是⽆⼆义的，则它的任何句⼦（）。
AA.最左推导和最右推导对应的语法树必定相同。
B.最左推导和最右推导对应的语法树可能相同。
C.最左推导和最右推导必定相同。
D.可能存在两个不同的最左推导，但它们对应的语法树相同。
9、⽂法G：S→S+T|TT→T*P|PP→(S)|i句型P+T+i的短语有（）BA.i，P+TB. P，P+T，i，P+T +iB.P+T + i D. P，P+T，i10、产⽣正规语⾔的⽂法为（）。
DA.0型B.1型C.2型D.3型11、⽂法G：S→b|?|(T)T→T?S|S则FIRSTVT(T)=() CA.{b，?，(}B.{b，?，)}C.{b，?，(，?}D.{b，?，)，?}12、给定⽂法：A→bA | cc，下⾯的符号串中，为该⽂法句⼦的是（）。
A①cc ②bcbc ③bcbcc ④bccbcc ⑤bbbcc可选项有：A.①B.①③④⑤C.①④D.①④⑤13、采⽤⾃上⽽下分析，必须（）。
第一章：1.编译程序的步骤和任务：1）词法分析：从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词。
2）语法分析：是在词法分析基础上将单词序列分解成各类语法短语(比如程序、语句、表达式等），通过语法分析确定整个输入串是否构成一个语法上正确的程序。
3）语义分析：是审查源程序有无语义错误，为代码生成阶段收集类型信息。
4）中间代码产生：将源程序变成一种易于翻译成目标代码的内部表示形式。
5）代码优化：对前阶段生成的中间代码进行变换或改造，使生成的目标代码更为高效6）目标代码生成：把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。
2.前端和后端的概念，试问前端通常包括那些阶段，后端包括那些阶段？答：前端只依赖于源语言，与目标机无关。
编译程序的前端通常包括词法分析程序、语法分析程序、语义分析程序、中间代码生成程序及相关的表格管理程序和出错处理程序。
后端是指编译器中依赖于目标机器的部分,只与中间代码有关。
通常包括目标代码生成程序、代码优化程序以及相关的表格管理程序和出错处理程序。
遍（PASS)：对输入文件（源程序或其等价的中间语言程序）从头到尾扫视，完成预定处理的过程。
一个多遍的编译程序较之一遍的编译程序可能少占内存，逻辑结构可能清晰些，但效率相对可能差点3.程序的正确与否：结构上的语法规则，语义上的语义规则。
翻译程序：汇编，解释，编译。
4.解释程序及其与编译程序的比较解释程序功能：源程序+初始数据=计算结果解释与编译的区别：工作模式：这是根本区别，编译把源程序翻译成目标代码，而解释直接得到计算结果，不生成目标代码。
存储区内容：编译方式翻译和执行分开，解释方式翻译和执行同时并允许修改源程序，因此二者存储组织不同。
效率：解释慢于编译，很多语言两种方式都有。
标识符：=表达式第三章：文法和语言1.文法的直观概念：一组判定规则。
在实践中，文法不包含多余产生式。
2.文法G定义为四元组（VT，VN ,S, P ），其中：VT是一个非空有穷终结符号集合；VN是一个非空有穷的非终结符号集合，且VT∩VN＝Φ；P是一个产生式的非空有穷集合（注意：产生式左部至少含有一个非终结符）；S VN ，称为开始符号，且S至少必须在某个产生式的左部出现一次。
通常用V表示VN∪ VT,V称为文法G的字母表或字汇表.3.句型、句子：设文法G，如果符号串x是从识别符号推导出来的，即S→x,x∈V*，则称x是一个句型。
仅含终结符号的句型是一个句子。
4.语言：语言 L(G）是由文法G产生的所有句子所组成的集合。
5文法的类型：逐渐对产生式施加限制四种类型：0型，1型，2型，3型0型：G=(VT,VN,S,P)，规则形式：β→αα,∈β (VT⋃VN)*, α中至少有一个非终结符1型（上下文有关）：∣β∣≤∣α∣,仅S->ε除外规则形式：α A β→αγβA ∈VN, α，γ，β∈ (VT⋃VN)*, γε≠2型（上下文无关）：规则形式： Aβ→ A ∈VN，β∈ (VT⋃VN)*3型正规文法（右线性）： A→ aB 或 A → a A,B ∈VN（左线性） A→ Ba 或 A → a a ∈VT⋃{ε}6.最左（最右）推导在推导的任何一步α⇒β，其中α、β是句型，都是对α中的最左（右）非终结符进行替换规范推导：即最右推导。
规范句型：由规范推导所得的句型。
7.文法的二义性如果一个文法存在某个句子对应两棵不同的语法树,或者说,若一个文法中存在某个句子,它有两个不同的最左(最右)推导,则说这个文法是二义的.如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。
8.自上而下的分析方法：自上而下分析法,是从文法开始符号出发,反复使用各种产生式,逐步进行推导，直至推导出输入符号串。
过程：自上而下方法是从文法识别符号开始，将它作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。
关键问题：假定要被代换的最左非终结符号是A,且有n条产生式:A → a1|a2|…|an,那么如何确定用哪个产生式右部去替代A?9.自下而上的分析方法：自下而上分析法，是从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。
过程：自下而上方法是从输入符号串开始，以它作为语法树的末端结点，自底向上地构造语法树，使语法树的根结点正好是文法的开始符号。
关键问题：因为分析工作的每一步都是从当前串中选择一个子串,将它归约到某个非终结符,暂且把这个子串称为可归约串,问题是,每一步如何确定这个可归约串?10.短语：若S⇒* αAδ且 A ⇒ +β，则称β是句型αβδ相对于非终结符A的短语。
直接短语：若S⇒* αAδ且A⇒β，则称β是句型αβδ相对于非终结符A 的直接短语。
句柄：一个句型的最左直接短语。
（产生式的右部）11.子树：一棵语法树中一个特有的结点连同它的全部后裔，连接这些后裔的边以及这些结点的标记，称为子树。
子树与短语的关系(1) 短语：子树的末端结点(即树叶)组成的符号串；(2) 直接短语：简单子树的末端结点组成的符号串；(3) 句柄：最左简单子树的末端结点组成的符号串；左图所示的关于句型E+E*i的语法树来说：它有3棵子树，即3个短语分别为i、E*i和E+E*i；直接短语、句柄均为i。
从语法树中可以看出，所有树叶的组合就是其相对应的父结点的短语。
34251X 6εεa b a b a b εεab 2Y句型i+i*i 的语法树有5棵子树，短语和直接短语如下：直接短语：i1， i2 ， i3短语：i1，i2，i3，i1*i2，i1*i2+i3 句柄：i1注意：i2+i3不是短语不是某棵子树的结果 12.有关文法的实用限制：有害规则是指形为U->U 的产生式。
会引起文法二义性。
多余规则是指文法中那些任何句子推导都用不到的规则,包括两种规则,即不可到达的和不可终止的。
不可达到的：不在文法的任何规则右部出现的非终结符。
不可终止的：文法中那些不能从其推出终结符号串的非终结符。
第四章：词法分析1.任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析 2、接口方式：（1）词法分析工作可以组织成独立的一遍,把字符流的源程序变为单词序列，输出在一个中间文件上，这个文件作为语法分析程序的输入而继续编译过程。
（2）将词法分析程序设计成一个子程序，当语法分析程序需要一个单词时，则调用该子程序，从源程序中读入一些字符，直到识别出一个单词，或说直到下一个单词的第一个字符为止，这种设计方案是把词法分析和语法分析程序放在同一遍，省掉了中间文件。
单词符号的输出形式：二元组：（单词种别，单词自身的值）单词符号的分类：关键字，标识符 ，常数，运算符，界符等（这种分类不是唯一的） 3. 正规文法与正规式的转换（若两个正规式x 和y 所表示的正规集相同，则说x 和y 等价，写作x=y 。
） 4.NFA 转换为DFA ：DFA 的表示（1）用转换函数；（2）状态转换矩阵；（3）状态转换图 NFA 与DFA 的主要区别：允许有多个初始状态。
允许状态在其输出边上有相同的符号(多值映射)。
允许输出边上有空串符号ε 。
NFA 特点:在给定状态和符号的情况下，不能唯一的确定下一个状态。
NFA 的确定化基本方法 基本方法:ε边合并,符号合并 (NFA 转化成的DFA 不是唯一的) 【 例 】 NFA M 如右图所示，试将其确定化为DFA M'。
【解答】 （1）用子集法将图所示的NFA M 确定化为表1。
（2）对表1中的所有子集重新命名 得到表2的状态转换矩阵ε_closure(S 05.DFA 化简：通过消除多余状态和合并等价状态将一个DFA M 转换成一个最小的与之等价的DFA M`多余状态是指，从该自动机的开始状态出发，任何输入串都不能到达的那个状态。
在有穷自动机中，两个状态s 和t 等价的条件是： 1）一致性条件：即s 和t 必须同为终态或同为非终态2）蔓延性条件：即对所有输入符号，s 和t 必须转换到等价的状态里。
有穷自动机的状态s 和t 不等价，则称这两个状态是可区别的。
6.正规式转换为有穷自动机：r=s|tr=s*第五章：自顶向下语法分析方法 求FIRST 集，FOLLOW 集 LL （1）文法判定1、语法分析是编译程序的核心部分：在词法分析的基础上，识别单词符号序列是否是给定文法的正确句子（程序）。
自上而下分析的前提： 消除左递规和 消除回溯。
自顶向下分析法就是 从文法的开始符号xyεεεεN (s ) xyN (t )N (s ) ε εε ε出发，试图推导出与 输入的单词串完全 匹配的句子。
如果能够推导出，则该输入串是给定文法的句子。
如果不能推导出，则该输入串不是给定文法的句子。
2.自顶向下分析法分两种：不确定的自顶向下分析法：是带有回溯的分析方法，效率低，代价高，极少使用。
确定的自顶向下分析法：对文法有一定的限制，但实现简单直观，便于手工或自动构造。
3.确定的自顶向下分析思想：判定是否为LL （1）文法首符号FIRST 集：设G =（ V T ，V N ，S ，P ）是上下文无关文法F I R S T (α)={a | α→a β,a ∈ V T , α，β∈V *} 若α→ε，则规定ε∈ F I R S T (α).后跟符号FOLLOW 集：F O L L O W (A )={a ∣S →… A a …,a ∈ V T , A ∈ V N }若S →...A , 则规定#∈F o l l o w (A ).选择集合S E L E C T 集：给定上下文无关文法的产生式A ->α,A ∈ V N , α∈V *，若α→﹨ε，则S E L E C T （A -> α）=F I R S T （α）如果α→ε ，则S E L E C T (A ->α)=(F I R S T ( α)-{ε})⋃F O L L O W (A ) 4.LL(1)的含义：LL(1)文法是无二义的、LL(1)文法不含左递归 第1个L ：从左到右扫描输入串 第2个L ：生成的是最左推导1 ：向右看1个输入符号便可决定选择哪个产生式 一个上下文无关文法是LL(1)文法的充分必要条件是：对每个非终结符A 的任两个不同产生式 A →α，A →β，满足：Select(A →α)∩Select(A →β)=∅,其中：α、β不同时推导出ε 注：对LL(1)文法进行语法分析时不会产生回溯。
5.某些非LL(1)文法到LL(1)文法的等价变换: 1. 提取左公因子2. 消除左递归（如果一个文法是左递归时，则不能采用自顶向下分析法。
