编译原理复习资料整理

第一章

1 编译原理的工作过程（结合p6 图 1.3） 编译程序的主要功能是将源程序翻译成等价的目标程序，这个翻译过程（也称编译过程）十分复杂，所以它一般首先分析源程序，然后综合成目标程序。编译程序在分析阶段检查源程序的正确性后，再将其分解为若干基本成分。这其中的工作也包括建立一些表格，改造源程序为中间语言程序。

2 编译方式和解释方式的比较（结合p2图 1.1和p3图1.2）

编译方式中源程序的编译和目标程序的运行时分成两个阶段完成的。经编译所得的目标程序，计算机暂时还不能直接执行，必须由连接装配程序将目标程序和编译程序以及运行子程序连接成一个可执行程序，这个可执行程序才可直接被计算机执行。 解释方式并不先产生目标程序然后再执行之，而是对源程序边翻译边执行。解释程序的主要优点是便于对源程序进行调试和修改，但其加工处理过程速度较慢。 3 编译的特性

1.模块性 ○2 静态解释和动态解释 ○3机器无关性 ○4语言标准化 ○5程序语言特征 ○

第二章

1 文法的形式定义 G=（VN，VT，S，P）

VN:非空有限的非终结符号集（变量表） VT:非空有限终结符号集（符号表） S:开始识别符号 P:产生式的集合

觉得抽象的话，请看21页例题2.1 2 文法的分类（看产生式 P）

1 0型文法（PSG ：Phrase Structure Grammar---无限制的文法） ○ α->β，α∈（VN∪VT）+，β∈（VN∪VT）*，即产生式α至少有一个非终结符即可。 21 型文法（CSG: Context Sensitive Grammar---上下文有关文法） ○

α->β，α=γ1Aγ2，β=γ1Bγ2，γ1，γ2∈（VN∪VT）*，A∈VN，B∈（VN∪VT）+， 1≤|α|≤|β|

意思就是说当B的两边是γ1，γ2串,时才将B规约为γ1Aγ2。 32 型文法（CFG ：Context Free Grammar---上下文无关文法） ○

+

A->e，A∈VN，e∈（VN∪VT），意思就是说把e规约成A不需要管e的两边是什么。 43 型文法（RG: Regular Grammar---右线性文法和正规文法） ○

*

右线性文法：A→α或者A→αB，其中A,B∈VN，α∈VT, 正规文法：A→α或者A→αB，其中A,B∈VN，α∈VT, 即正规文法只能出现单个的终结符号，而右线性文法则可能出现若干个终结符号组成的串

*

拓展 左线性文法：A→α或者A→Bα，其中A,B∈VN，α∈VT, 他们的关系如下：

典型题型：构造文法生成下列语言（默认是CFG）

n2m-1

1{ab ○|n，m≥1}

n2m-1

由于符号串中a，b中的个数没有直接关系，所以将句子分成两步分：a和b，分别构造，所以得文法：（答题时只写出下面的文法即可，下同） G[S]: S→AB A→a|aA B→b|bbB

nn

2{ab|n≥1} ○

G[S]: S→aSb|ab

3能被5整除的整数的集合 ○

除符号位外可以分为首位不能为0，末尾只能是0或者5，中间是0到9的数三个部分 文法为：

G[S]:S→A|-A|0

A→1B|2B|3B|4B|5B|6B|7B|8B|9B

B→0B|1B|2B|3B|4B|5B|6B|7B|8B|9B|C C→0|5

解此类题目答案不唯一，只要能正确表达就行，不要想用一个文法就可以表示语言了，多举几个具体的例子找规律，做出题目后最好还要用具体的例子带进去检查。 3 句型，句子和语言 短语和句柄的概念（短语和句柄 为第6章的内容）

句型：任何能由开始符号推出的符号串。 句子：只含有终结符的句型。 语言：文法所有句子的集合。

短语：设αβδ是文法G[S]中的一个句型，如果有S=*>αAδ且A=+>β，则称β是句型αβδ相对于非终结符A的短语。

直接短语：特别的如有A=>β，则称β是句型αβδ相对于规则A→β的直接短语（简单短语）。

句柄：一个句型的最左直接短语称为该句型的句柄。句柄就是“可归约串”。 4 构造句型的语法树，书上P29页写得比较详细，还有具体的例子，再此不在赘述 5 最左、最右推导和规范推导

*

最左推导：在直接推导xUy=>xuy直接推导中，x∈VT，U∈VN，即U是符号串xUy中最左非终结符，则此直接推导为最左直接推导。若一个推导的每一步直接推导都最左直接推导，那么此推导为最左推导。

*

最右推导=规范推导：在直接推导xUy=>xuy直接推导中，y∈VT，U∈VN，即U是符号串xUy中最右非终结符，则此直接推导为最右直接推导。若一个推导的每一步直接推导都最右直接推导，那么此推导为最右推导。

典型考题 设文法G=（{N，D},{0,1,2,3,4,5,6,7}，P，N）

其中 P={N→ND|D,D→0|1|2|3|4|5|6|7},写出3274的最左推导和最右推导 最左推导如下：N=>ND=>NDD=>NDDD=>3DDD=>32DD=>327D=>3274 最右推导如下：N=>ND=>N4=>ND4=>N74=>ND74=>N274=>D274=>3274 6 二义性

句子的二义性：一个文法，如果它的一个句子有两颗或以上的语法树 文法的二义性：至少含有一个二义性的句子

语言的二义性：存在二义性的文法描述它

７ 自上而下分析方法：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。

自下而上分析方法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号 第三章

１有穷自动机（FSA：Finaite State Automaton）的形式定义

有穷自动机分为确定的有穷自动机（DFSA： Deterministic Finate State Automaton）和非确定有穷的自动机（NDFSA: NonDeterministic Finate State Automaton）

DFSA=(Q,∑,t，q0，F)

Q是非空有穷状态集，其中的没歌元素成为一个状态；∑是有穷输入字母表，它的每一

,

个元素称为一个输入符号；t是一个单值映射Q×∑→Q，也称状态转换函数，t（q，x）=q

,,

意值：当现行状态为q面临的输入符号位x时，将转到下一个状态q，q称为q的一个后继状态；q0∈Q称为开始状态；F ?Q称为终止状态集，它至少由一个终止状态组成。 NDFSA=(Q,∑,t，q0，F)

Q是非空有穷状态集，其中的没歌元素成为一个状态；∑是有穷输入字母表，它的每一个元素称为一个输入符号；t为映射Q×∑→Q的一个子集，即t为一个多值映射；q0∈Q称为开始状态；F ?Q称为终止状态集，它至少由一个终止状态组成。 它们之间的主要区别有

1NDFSA有一个开始状态集，而DFSA只有一个开始状态 ○

2NDFSA的映射是Q×∑→Q的一个子集，○是一个多值映射，而DFSA的映射是Q×∑→Q，是一个单值映射。

3NDFSA在没有扫描符号的情况下，也可以进行移动，成为空移。 ○

8 利用造表法将NDFSA确定化

结合书上的例子3.6 P61页

I 表示当前状态集，Ia表示当前状态面临a时可以到达的状态集或者空移到的状态集，如果这一行产生了新的状态集，则将其加入到下一行中，作为另一个新的状态集。表造好后，将I这列依次赋予新的状态号，如0,1，?，如果某个状态包含以前的终结状态，则这个状态就位新的终结状态。最后根据确定后的状态转换表，画出新的状态转换图即可。

如 I={S,5,1},为初始状态集，5→5a，3→1a，1→ε5，5→εS，所以Ia={5,3,1，{5,3，1}没有在前面出现过，为新的状态。其他的状态同理可求。表建好后，将所有I这一列从新编号，依次为0,1?，由于H为终态，所以包含H的状态集都未终态。Ia和Ib这两列中用I列中相应的编号表示即可。确定后就可以画状态转换图了。 9 DFSA的化简：将相同的状态和为一个

何为相同的状态，就是值如果两个状态面临所有的不同输入符时，得到的结果都一样。

算法描述：P65页 我的理解：首先将所有的状态分为终态组和非终态组两部分分别检测这两组中面临所有不同的输入符时是不是还在同一组，如果是就有可能是相同的状态，如果不是，则一定不是相同的状态，重复这个过程，直到不能再分为止

结合62页 图3.12，首先将其分为两组，即终态组{3,4,5,6}和非终态组{0,1,2} {3,4,5,6}a=（3,6,6,3）∈{3,4,5,6} {3,4,5,6}b=（4,5,5,4）∈{3,4,5,6}，所以{3,4,5,6}应该属于同一个状态

{0,1,2}a=（1,3,1），不在同一个组中，应该将其分开为{1}和{0,2}

{0,2}b=（2,5）也不在同一个组中，应该将其分开为{0}，{2}，化简后如书上图3.14 P66

10 从正规文法到FSA的转换

结合书上P69页 例题3.10 注意F是增设的终态 书上说的比较详细，在此不在赘述 11从FSA到正规文法（考的概率较小） 结合书上P70页 例题3.11 注意如果是终态 Z，要加上 Z→ε； 12 正规表达式到FSA 规则：书上P73 图3.20 ，注意，对于构造的自动机，不要出现太多的空移

13 从正规文法到正规表达式（考的概率小） 转换规则P80页 第四章

1词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则

从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位， 并转换成统一的内部表示(token)，送给语法分析程序。

第五章

1 消除左递归

对于直接左递归（形如 U→Ux）可根据如下所示消除： U→Ux1|Ux2|Ux3|?|Uxm|y1|y2|?|yn，则 U→y1U’|y2U’|?|ynU’

U’→x1 U’|x2 U’|?|xm U’|ε

多于间接左递归，要采用会带的方式，使之变为直接左 2 LL(1)分析表的构造

首先要会构造FIRST,FOLLOW集合，构造规则在书上P116到P117,构造这两个集合，要理解这两个集合表示什么FIRST（U）表示U串中的第一个符号的集合，FOLLOW（U）表示跟在U串中的第一个符号的集合，SELECT集合表示当前读头为某个字符时应该选择哪个产生式。搞清楚它们的本质，那就好求了。

例题 设文法G[E]:

1E->TE' ○

2E'->+E| ε ○

3T->FT' ○

4T' ->T| ε ○

5F-> PF' ○

6F'-> *F'| ε ○

7 P->(E)|a|b|^ ○

FOLLOW集合有： （除了识别符号，主要看产生式的右部） FOLLOW(E)={),$};

1，○2和○7，由○1，○2知{$}∈FOLLOW(E)，由○7知{ )}∈FOLLOW(E) //出现E的有○

FOLLOW(E')=FOLLOW(E)={),$}; 2知 FOLLOW(E) ? FOLLOW(E') //由○

FOLLOW(T)=（FIRST(E')-{ ε}）∪FOLLOW(E)={+,), $};

1知道（FIRST(E')-{ 2知道E'可为ε，//由○ε}）? FOLLOW(T)，由○所以FOLLOW(E) ? //FOLLOW(T)

FOLLOW(T')=FOLLOW(T)= {+,), $};

3知FOLLOW(T) ? FOLLOW(T') //由○

FOLLOW(F)=（FIRST(T')-{ ε}）∪FOLLOW(T)={(,a,b,^,+,), $};

3知（FIRST(T')-{ 4知道，T’可为ε，所以FOLLOW(T) //由○ε}）? FOLLOW(F)，又由○//? FOLLOW(F)

FOLLOW(F')=FOLLOW(F) ={(,a,b,^,+,), $};

5知 FOLLOW(F) ? FOLLOW(F') //○

FOLLOW(P)= （FIRST(F')-{ ε}）∪FOLLOW(F)={*,(,a,b,^,+,), $};

5知（FIRST(F')-{ ε}）? FOLLOW(P)，又○6知F'可为ε，所以FOLLOW(F) ? //由○

//FOLLOW(P)

各产生式的SELECT集合有：

SELECT(E->TE')=FIRST(T)={(,a,b,^}; SELECT(E'->+E)={+};

SELECT(E'->ε)=FOLLOW(E')={),$} SELECT(T->FT')=FIRST(F)={(,a,b,^}; SELECT(T'->T)=FIRST(T)={(,a,b,^}; SELECT(T'->ε)=FOLLOW(T')={+,),$}; SELECT(F->PF')=FIRST(P)={(,a,b,^}; SELECT(F'->*F')={*};

SELECT(F'->ε)=FOLLOW(F')={(,a,b,^,+,), $}; SELECT(P->(E))={(} SELECT(P->a)={a} SELECT(P->b)={b} SELECT(P->^)={^}

分析表如下所示

第六章

1 简单优先分析方法

1FIRST与LAST的求法 ○FIRST: A→Bα，A∈VN，B∈（VN∪VT），α∈（VN∪VT）*,也就是说B是A的产生

本文来源：https://www.bwwdw.com/article/svvf.html