编译原理复习

第一章词法分析 1. 给出下面的正规表达式： (1) 以01结尾的二进制数串 (2) 能被5整除的十进制整数 (3) 包含奇数个1和奇数个0的二进制数串 (4) 不包含字串abb的由a和b组成的符号串的全体 2. 构造下列正规式相应的DFA（要求状态最少） (1) 1(0|1)*101 (2) 1(1010*|1(010)*1)*0 (3) a((a|b)*|ab*a)*b (4) b((ab)*|bb)*ab 3. 将下图的(a)确定化；(b)最小化

01a,baa

02143

5b

baaaa

bbb

ba

a

(a) (b) 4. 浮点数的定义如下：它只含有一个小数点，小数点前后至少有一位数字。指数用E表示，后面跟一个符号（+或-）或者无此符号，再后面跟一个或一个以上的数字串。（例如，1.175494351 E – 38和3.402823466 E 38都是浮点数）(10分) (1) 构造出产生该浮点数的正规文法 (2) 用正规式表示上述浮点数 (3) 构造接受该浮点数的有限自动机（NFA和DFA都可以）

第二章语法分析 本章主要掌握下面的一些内容。 1． 文法和语言的基本知识。 2． 自上而下的分析方法：预测分析器(递归下降分析方法)，非递归的预测分析器（分析表方法)，LL(1)文法。 3． 算符优先分析方法。现在的编译器很少用这种方法了，了解即可。 4． 自下而上的分析方法：SLR(1)方法，规范LR(1)方法和LALR(1)方法。这三种方法中，重点是规范LR(1)方法，规范LR(1)方法了解透彻了，其它两种就不难了。 5． LR方法如何用于二义文法。 6．语法分析的错误恢复方法。 文法方面的习题： 1． 文法 S→aSbS | bSaS |ε 产生的语言是什么?该文法去是否二义？

语法分析方面的习题： 1.消除下列文法的左递归性。 (1) S→SA S→A A→SB A→B A→(S) A→( ) B→［S］ B→［ ］ (2) S→AS S→b A→SA A→a (3) S→(T) S→a S→ε T→S T→T,S 2.设已给文法： S→AbB S→d A→CAb A→Bf B→CSd B→d C→ed C→a 试写出对符号串eddfbbd进行带回溯的自顶向下语法分析的过程。 3.对于如下的文法，求出各个FIRST集和FOLLOW集。 S→aAB S→bA S→ε A→aAb A→ε B→bB B→ε 4.验证下列文法是否为LL(1)文法。 (1) S→AB S→CDa A→ab A→c B→dE C→eC C→ε D→fD D→f E→dE E→ε (2) S→aABbCD S→ε A→ASd A→ε B→Sac B→eC B→ε C→Sf C→Cg C→ε D→aBD D→ε 5.对于如下的文法G［S］： S→Sb S→Ab S→b A→Aa A→a (1) 构造一个与G等价的LL(1)文法G′； (2) 对于G′，构造相应的LL(1)分析表。 6.设已给文法 S→SaB S→bB A→S A→a B→Ac (1) 求出各个FIRST集和FOLLOW集； (2) 将它改写为LL(1)文法。 7.将下面的文法改写为LL(1)文法。 〈布尔表达式〉→〈布尔表达式〉∨〈布尔因子〉 〈布尔表达式〉→〈布尔因子〉 〈布尔因子〉→〈布尔因子〉∧〈布尔二次量〉 〈布尔因子〉→〈布尔二次量〉 〈布尔二次量〉→〈布尔初等量〉 〈布尔二次量〉→〈布尔初等量〉 〈布尔初等量〉→(〈布尔表达式〉) 〈布尔初等量〉→true | false 8．设文法G(S): S → S+aF | aF | +aF F → *aF | *a (1) 消除左递归和回溯； (2) 构造相应的FIRST和FOLLOW集合； (3) 构造预测分析表 9.对于下列的文法，试分别构造它们的LR(0)项目集规范族及识别全部活前缀的DFA。 (1) S→aSb S→aSc S→ab (2) S→cA S→ccB A→cA A→a B→ccB B→b (3) S→aSSb S→aSSS S→c (4) S→A A→Ab A→a 10.下列文法是否为SLR(1)文法?若是，构造相应的SLR(1)分析表，若不是，则阐明其理由。 (1) S→Sab S→bR R→S R→a (2)S→aSAB S→BA A→aA A→B B→b (3)S→aSb S→bSa S→ab (4)S→aA S→bB A→cAd A→ε B→cBdd B→ε (5) 〈程序〉→〈分程序〉 〈程序〉→〈复合语句〉 〈分程序〉→〈分程序首部〉；〈复合尾部〉 〈分程序首部〉→begin D 〈分程序首部〉→〈分程序首部〉；D 〈复合尾部〉→Send 〈复合尾部〉→S；〈复合尾部〉 〈复合语句〉→begin〈复合尾部〉 (6) 〈程序〉→begin 〈说明表〉〈语句表〉end 〈说明表〉→〈说明表〉d； 〈说明表〉→ε 〈语句表〉→〈语句表〉；〈语句〉 〈语句表〉→〈语句〉 〈语句〉→S 〈语句〉→ε 11对于文法 S→A A→BA A→ε B→aB B→b (1) 构造LR(1)分析表； (2) 给出用LR(1)分析表对输入符号串abab的分析过程。 12.对于如下的文法，构造LR(1)项目集族，并判断它们是否为LR(1)文法。 (1)S→A A→AB A→ε B→aB B→b (2) E→E+T E→T T→(E) T→a 13.下列文法是否为LR(1)文法?若不是，能否将它们改写为等价的LR(1)文法。 (1) E→E+E E→E*E E→i (2) S→aSa S→bSb S→a S→b (3) S→V∶=E S→LS L→I: V→I (4) 〈程序〉→begin〈说明表〉；〈语句表〉end 〈说明表〉→d;〈说明表〉 〈说明表〉→d 〈语句表〉→S;〈语句表〉 〈语句表〉→S 14.设已给文法G［S］: S→AaAb S→BbBa A→e B→ε 试证明G是LL(1)文法，但不是SLR(1)文法。 15.设已给文法 (1) G1［S］： S→Aa|bAc|dc|bda A→d (2) G2［S］： S→Aa|bAc|Bc|bBa A→d B→d 试证明： G1是LALR(1)文法但不是SLR(1)文法；G2是LR(1)文法但不是LALR(1)文法。 16.试为如下的文法构造LALR(1)分析表。 E→E+T|T T→TF|F F→F*|a|b 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

编译原理复习范文编译原理是计算机科学中的一门重要课程，它涉及将高级程序代码翻译成低级可执行代码的理论和技术。

下面将对编译原理的基本概念、各个阶段和常见算法进行复习。

1.编译原理的基本概念编译原理研究的是编译程序的设计、实现和理论问题。

编译器是将源程序转换为目标程序的程序，包括编译器前端和后端两个部分。

编译器前端主要完成词法分析、语法分析和语义分析等功能；编译器后端主要完成中间代码生成、代码优化和代码生成等功能。

2.编译原理的各个阶段编译原理的各个阶段包括词法分析、语法分析、语义分析、中间代码生成、代码优化和代码生成。

（1）词法分析：将源代码分解成一个个的单词或记号，例如标识符、关键字、运算符等，生成一个词法单元序列。

（2）语法分析：根据给定的语法规则，将词法单元序列进行分析，构造语法树。

常用的语法分析算法包括递归下降法和LR分析法等。

（3）语义分析：对语法树进行语义检查，包括类型检查、作用域检查等。

在语义分析阶段还可以生成中间代码。

（4）中间代码生成：将源代码转化为一个中间表示，一般是三地址码、四地址码或虚拟机代码。

中间代码是高级语言和机器语言之间的过渡形式。

（5）代码优化：对中间代码进行优化，以改进程序的执行效率。

常用的优化技术包括公共子表达式消除、死代码消除、循环优化等。

（6）代码生成：将优化后的中间代码转化成目标代码。

代码生成的目标可以是汇编语言、机器代码或其他可执行代码。

3.常见的编译原理算法（1）递归下降算法：递归下降算法是一种自顶向下分析的方法，它通过递归地调用与语法规则相对应的子过程来分析输入的源程序。

递归下降算法的实现简单直观，但对左递归和回溯有一定的限制。

（2）LL分析法：LL分析法是自顶向下的一种语法分析方法，它通过查找输入串的前缀和产生式的右部来构造语法树。

LL分析法包括LL(1)和LL(k)两种变体，其中LL(1)分析法是指使用一个符号后看一个输入符号来进行分析。

（3）LR分析法：LR分析法是自底向上的一种语法分析方法，它通过维护一个状态栈和一个符号栈，依据预定义的语法规则进行规约和移进操作来构造语法树。

三种语言涉及的三类人：源语言（设计者），编译语言（实现者），目标语言（使用者）变量：对存储单元的抽象（变量是对一个(或若干个)存储单元的抽象，赋值语句则是修改存储单元内容的抽象。

）。

属性：变量的作用域，变量的生存期，值，类型静态绑定：凡是在编译时能确定的属性，称为静态属性；若绑定在编译时完成，运行时不改变，称为静态绑定。

动态绑定：凡是在运行时才能确定的属性称为动态的。

若绑定在运行时完成，称为动态绑定。

定义：虚拟机是由软件实现的机器。

（实际机器+程序）程序单元：1,程序单元: 程序执行过程中的独立调用单元；2.单元的表示在编译时，单元表示是该单元的源程序。

运行时，单元表示由一个代码段和一个活动记录组成，称为单元实例。

3.活动记录:执行单元所需要的信息,以及该单元的局部变量所绑定的数据对象的存储区。

4.非局部变量:一个程序单元可以引用未被本单元说明而被其它单元说明的变量。

5.引用环境:局部变量+非局部变量。

6.别名:同一单元的引用环境中有两个变量绑定于同一数据对象，称这些变量具有别名。

7.副作用:对绑定于一个非局部变量的对象进行修改时，将产生副作用。

8.程序单元可以递归激活,从而一个单元可以有很多个实例,但代码段相同。

不同的仅仅是活动记录（所以绑定必须是动态的）。

数据类型：数据类型实质上是对存储器中所存储的数据进行的抽象。

它包含了一组值的集合和一组操作。

数据类型的作用1.实现了数据抽象2.使程序员从机器的具体特征中解脱出来3.提高了编程效率聚合的六种方式：笛卡尔积，有限映像，序列，判定或，递归，幂集2.抽象数据类型的定义：满足下述特性的用户定义类型称为抽象数据类型:1.在实现该类型的程序单元中,建立与表示有关的基本操作;2.对使用该类型的程序单元来说,该类型的表示是隐蔽的。

类型等价：若T1和T2是两个类型，且T1的任何值都可以赋予T2类型的变量，T1类型的实参可以对应类型T2的形参，反之亦然，则称T1和T2是相容的，或等价的；有两种类型的相容性概念：①名字等价②结构等价两种相容性实现时的比较①名字等价的实现比较简单②结构等价的实现需要的模式匹配过程可能十分复杂编译时与类型相关的三个重要工作：1.类型检查12.类型转换3.类型等价语句级控制：顺序，选择，重复四种单元级控制结构：显式调用异常处理协同程序并发单元语言的定义：程序设计语言是用来描述计算机所执行的算法的形式表示；语言＝语法＋语义语法:用以构造程序及其成分的一组规则的集合语义:用以规定语法正确的程序或其成分的含义的一组规则的集合文法定义：文法是描述语言的语法结构的形式规则, 必须准确,易于理解,且描述能力强。

编译原理复习重点含答案编译原理复习重点编译原理是计算机科学中的一门重要课程，它研究的是如何将高级语言程序转化为机器语言的过程。

在编译原理的学习中，我们需要掌握一些重要的概念和技术，以便能够理解和应用编译器的工作原理。

本文将重点介绍编译原理的几个重要主题，并提供相应的答案供参考。

一、词法分析词法分析是编译器的第一个阶段，它的任务是将输入的字符序列划分为一个个有意义的词素（token）。

词法分析器通常使用有限自动机（DFA）来实现，其工作原理是将输入字符序列逐个读入，并根据事先定义好的词法规则进行匹配和识别。

常见的词法单元包括关键字、标识符、常量、运算符等。

常见的词法规则包括：1. 关键字：例如if、while、for等。

2. 标识符：由字母、数字和下划线组成，且以字母或下划线开头。

3. 常量：包括整数常量、浮点数常量、字符常量和字符串常量等。

4. 运算符：例如加法运算符+、减法运算符-等。

5. 分隔符：例如逗号、分号等。

词法分析的结果是一个个词法单元，每个词法单元包含一个词素和对应的词法单元类型。

例如，对于输入程序"int a = 10;"，词法分析的结果可能是[("int", "关键字"), ("a", "标识符"), ("=", "运算符"), ("10", "整数常量"), (";", "分隔符")]。

二、语法分析语法分析是编译器的第二个阶段，它的任务是将词法分析器输出的词法单元序列转化为抽象语法树（AST）。

语法分析器通常使用上下文无关文法（CFG）来描述语言的语法结构，并使用递归下降、LL(1)分析、LR分析等算法进行分析。

常见的语法规则包括：1. 表达式：例如算术表达式、布尔表达式等。

《编译原理》期末考试复习题一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）×1．计算机高级语言翻译成低级语言只有解释一种方式。

()×2．在编译中进行语法检查的目的是为了发觉程序中所有错误。

()√3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。

()×4．正则文法其产生式为 A->a ， A->Bb, A,B∈VN ， a 、 b∈VT 。

()√5．每个文法都能改写为 LL(1) 文法。

()√6．递归下降法允许任一非终极符是直接左递归的。

()×7．算符优先关系表不一定存在对应的优先函数。

()×8．自底而上语法分析方法的要紧问题是候选式的抉择。

()×9．LR 法是自顶向下语法分析方法。

()×10．简单优先文法允许任意两个产生式具有相同右部。

()三、填空题(每空1分，共10分)1．编译程序的工作过程一般能够划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本时期,同时还会伴有__ ___和 ___ _。

表格治理出错处理_2．若源程序是用高级语言编写的,__ __是机器语言程序或汇编程序,则其翻译程序称为 __ __ 。

_目标程序 _编译程序3．编译方式与解释方式的全然区别在于__ __。

是否生成目标代码_4．对编译程序而言,输入数据是__ __, 输出结果是__ ___。

_源程序 目标程序5．产生式是用于定义__ __的一种书写规则。

_语法成分6．语法分析最常用的两类方法是___ __和__ __分析法。

自上而下 _自下而上四、简答题（20分）1. 什么是句子？ 什么是语言 ?答：(1)设G是一个给定的文法，S是文法的开始符号，假如S x(其中x∈VT*),则称x是文法的一个句子。

(2)设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│S x,x∈VT*} 。

《编译原理》复习考试题型选择2’x15判断1’x10大题10’x61.句子一定是句型，句型不一定是句子。

句子只有终结符；句型既有终结符，也有非终结符。

2.一个文法所有句子的集合构成该文法定义的语言3.所有句子都是规范句型4.将编译程序分成若干个“遍”是为了使程序的结构更加清晰5.编译程序的功能是将高级语言源程序编译成目标程序6.编译程序完成高级语言程序到低级语言程序的等价翻译7.编译程序绝大多数时间花在表格管理上8.与高级语言相比，汇编语言编写的程序通常执行效率更高9.正则表达式和自动机在接受语言的能力上是等价的,并且一个正则表达式有可能等价于多个自动机10.由文法定义可知,文法所定义的语言是由该文法的开始符推导出的所有的终极符串的集合11.句柄：最左直接短语12.一个句型的直接短语不是唯一的13.一个文法的句型的句柄可能是不唯一的14.一个无二义文法的句型的句柄是唯一的15.如果文法G是无二义性的，则它的任何句子α：最左推导和最右推导对应的语法树必定相同16.四种文法的四种语言之间的关系是：L3⊆L2⊆L1⊆L017.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的18.不存在一个算法，它能在有限步骤内确切判定任给的一个文法是否为二义的19.文法的二义性是不可判定的20.将识别各类单词的有限自动机合并后得到的有限自动机可能是DFA，也可能是NFA21.与DFA相比，NFA的非确定性体现在允许有多个开始状态、在没有任何输入的情况下允许进行状态转换22.NFA等价的DFA可以有多个,但最简DFA就一个23.不是DFA的构成成分的是初始状态集合，根据DFA的状态可知，DFA只能唯一确定的起始状态24.一个DFA识别的语言是一个无限集合,则该DFA的状态图一定含有回路25.有限自动机M和N等价是指M和N识别的字符串集合相同26.一个句型的直接短语可能不只一个，但句柄是唯一的27.句柄对应的是文法某个产生式的右部28.由文法的开始符号出发经过若干步(包括0步)推导产生的文法符号序列称为句型29.词法分析器的输入是源程序30.词法分析器的输出结果是单词的种别编码和自身值31.词法分析器不可以发现括号不匹配、操作数类型不匹配、标识符重复声明、除法溢出，可以识别出数值常量、过滤源程序中的注释、扫描源程序并识别单词、出现非法符号错误（语法错误）32.编译程序中的语法分析器接受以单词为单位的输入,并产生有关信息供以后各阶段使用33.在语法分析处理中，FIRST 集合、FOLLOW 集合、SELECT 集合均是终极符集34.采用自上而下分析，必须消除回溯35.简单优先分析法（自底向上）是一种规范归约，但效率较低，需要考虑文法的所有符号，包括终结符与非终结符的优先关系36.算法优先分析法不是规范归约方法，但效率较高，只考虑终结符之间的优先关系37.一个LL(1)文法一定是无二义的38.每个基本块都可以用一个DAG（有向无环图）表示39.每个过程的活动记录的体积在编译时可静态确定40.采用三元式实现三地址码时，不利于对中间代码进行优化41.一个优先表不一定存在相应的优先函数42.正规文法产生的语言都可以用上下文无关文法来描述43.3型文法（正规）一定是2型文法（上下文无关）44.如果一个语言的句子是无穷的，则定义该语言的文法一定是递归的45.正规式的等价性：若正规式R1与R2描述的正规集相同，则R1与R2等价46.若L(R1) = L(R2)，则R1与R2等价47.设r和s分别是正规式，则有L（rs）=L(r)L(s)48.设r 和s 分别是正规式，则有L(r|s)=L(r)∪L(s)49.NFA相较于DFA，允许初态不唯一，多值映射，允许空移50.DFA用一条确定的路径来识别某一字符串51.DFA与NFA的特例52.两个状态s和t等价的条件：一致性条件、蔓延性条件53.规范规约（最左）和规范推导（最右）是互逆的两个过程54.在规范规约过程中，若符号栈中出现了句柄，则栈顶一定出现了某个规则式的右部（一个句型的句柄一定是某产生式的右部）55.反之，若一个句型中出现了某产生式的右部，则此右部不一定是该句型的句柄56.3型文法：A->aB B->bA(右线性) 或者A->Ba B->Ab（左线性），两者不可以混合）57.对任意一个右线性文法G，都存在一个NFA/DFA M，满足L(G)=L(M)58.一个正规语言可以对应多个正规文法59.一个正规语言可以对应多个DFA60.一个状态转换图可用于识别一定的字符串61.一个有限状态自动机中，不只有一个的初态62.下推自动机识别的语言是2型语言63.两个正规集相等的必要条件是他们产生的符号串是相同的64.并不是每个文法都能改写成LL(1)文法65.含有公共左因子的不是LL(1)文法，递归、右递归、2型文法是LL(1)文法66.算符优先文法：任何两个终结符之间至多只有一种优先关系67.一个优先关系表对应的优先函数f和g的值不是唯一的68.如果重复过程中有一个值大于2n，则表明该算符优先文法不存在优先函数（n为终结符的个数）69.当用产生式A→α归约时，LR(0)无论面临什么输入符号都进行归约；SLR(1)则仅当面临的输入符号a∈FOLLOW(A)时进行归约；LR(1)则在把α归约为A的规范句型的前缀βAα的前提下，当α后跟终结符a时，才进行归约。

一、单选题（每题2分，共20分）1. 编译器的（）阶段可将源程序的字符流收集到若干记号中。

A. 语法分析B. 语义分析C. 代码生成D. 词法分析2. 文法A aA | b属于正则文法，正则文法在乔姆斯基层次中对应于（）文法。

A. 1型B. 2型C. 3型D. 0型3. 某C语言源代码文件包含#include <stdio.h>，（）将对源代码进行处理，把文件stdio.h 包含进去。

A.编译器B.解释器C.汇编器D.预处理器4. LL(1)文法的充要条件是（）。

A.对于文法中的每条产生式Uα1|α2|…|αn，要求FIRST(αi)∩FIRST(αj)＝Φ（i≠j）B.该文法对应的LL(1)分析表中每个项目最多只有一条产生式。

C.A和BD.都不是5. 以下说法中正确的是（）。

A.任何语言都可以描述为一个正则表达式。

B.对于任何一个NFA M，都存在一个DFA M’，满足L(M)= L(M’)。

C.任何一个DFA只有一个终态。

D.NFA的弧上标记只含输入字母表中的元素。

6.合成属性的计算可以通过对语法树进行（）遍历进行。

A. 前序B.中序C.后序D.任意7.乔姆斯基的2型文法是这样一种语言，其产生式限制为（）。

A. α->βB. P->βC. P->a或P->aβD. αPγ->αβγ8. 正则式的“*”读作（）。

A. 并且B.连接C.正则闭包D.闭包9. 编译程序中的语义分析器接受以（）为单位的输入，并产生信息供以后各阶段使用。

A. 语法树B.子程序C.单词D.语句10.文法A->aAb|ab生成的语言是（）。

A. {ab}B.{aAb}C. {anbn|n≥1}D.{anbn|n≥0}二、判断题（每题2分，共10分，对的打√，错的打×）1. 一个LR(0)文法一定是SLR(1)文法。

（）2. 在类型声明文法中，类型属性type是继承属性。

编译原理复习题### 编译原理复习题#### 一、选择题1. 编译器的主要功能是什么？- A. 代码优化- B. 语法分析- C. 词法分析- D. 所有以上2. 词法分析器的主要任务是什么？- A. 识别关键字- B. 识别标识符- C. 将源代码分解成词素- D. 检查语法错误3. 下列哪个不是语法分析树？- A. 抽象语法树（AST）- B. 具体语法树（CST）- C. 语法分析树（GT）- D. 控制流图（CFG）4. 语义分析的主要目的是：- A. 检查类型正确性- B. 生成中间代码- C. 进行代码优化- D. 将源代码转换为目标代码5. 中间代码生成阶段通常采用哪种形式的代码？- A. 三地址代码- B. 汇编代码- C. 机器代码- D. 高级语言代码#### 二、简答题1. 简述词法分析器和语法分析器的区别。

2. 描述编译过程中的代码优化可能包括哪些方面。

3. 解释什么是抽象语法树（AST）以及它在编译过程中的作用。

#### 三、论述题1. 论述编译原理中的错误检测和恢复机制的重要性及其实现方式。

2. 分析静态和动态语义分析的区别，并讨论它们在编译过程中的作用。

#### 四、计算题1. 给定一个简单的算术表达式，如 `3 + 4 * 2 - 5`，请使用算术运算符优先级规则，描述其语法分析过程。

2. 假设有一个简单的编程语言，其语法规则如下：```S -> EE -> E + T | TT -> T * F | FF -> ( E ) | num```请写出表达式 `(3 + 4) * 5 - 6` 的语法分析树。

#### 五、案例分析题1. 考虑一个简单的C语言程序，分析其编译过程中可能遇到的常见错误类型，并讨论编译器如何处理这些错误。

以上复习题覆盖了编译原理的基本概念、关键组件以及编译过程中的一些高级主题。

通过这些题目，学生可以检验自己对编译原理的理解程度，并为进一步的学习打下坚实的基础。

编译原理期末考试复习整理(详细列出考试重点+重点例题)本页仅作为文档封面，使用时可以删除This document is for reference only-rar21year.March目录第一章 (3)词法分析： (3)语义法分析 (3)中间代码 (3)第二章 (3)1.根据语言写出文法 (4)2.根据文法写语，描述其特点(必考大题2-3类型) (4)3.文法的规范推导、语法树、短语、句柄（必考大题，2-7，2-11） (6)第三章 (11)1.给出一个正规文法 (左线性、右线性方法），写出其状态转换图(必考) (11)1.1右线性文法写出状态转换图 (必考) (11)1.2状态转换图写出右线性文法G (12)1.3左线性文法写出状态转换图 (必考) (13)2.非确定自动机的确定化 (14)第四章 (15)第五章 (15)属性文法与属性翻译文法 (15)逆波兰式（大题） (16)四元式（大题） (16)第一章词法分析：分析源程序的结构，判断它是否是相应程序设计语言的合法程序语义法分析的任务是根据语言的语义规则对语法分析得到的语法结构进行静态的语义检查（确定类型、类型与运算合法性检查、识别含义等），并且转换成另一种内部形式（语义树）表示出来或者直接用目标语言表示出来。

中间代码是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的设计原则为两点：一是容易生成；二是便于优化、移值；三是容易将它翻译成目标代码第二章文法G定义为四元组(V N，V→，P，S )其中V N为非终结符号(或语法实体，或变量)集；V→为终结符号集；P为产生式(也称规则)的集合； V N，V→和P是非空有穷集。

S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。

V N和V→不含公共的元素，即V N ∩V→ = φ,通常用V 表示V N∪ V→，V称为文法G的字母表或字汇表。