编译原理知识点_理解语法分析在编译程序中的作用 在词法分析的基础上进行语法检查和结构分析

（一）引论

一、两类程序语言处理程序（翻译的两种方式）

1. 编译程序（编译器）：先将源程序翻译成汇编语言程序或机器语言程序（称为目标程序），然后再执行它。

2. 解释程序（解释器）：按解释方式进行翻译的翻译程序称为解释程序。解释程序的主要优点是便于对源程序进行调试和修改，但其加工处理过程的速度较慢。e.g. BASIC。

注：

（1）把汇编语言程序翻译成机器可执行的目标程序的工作是由汇编器完成的。

（2）编写一个计算机高级语言的源程序后，到正式上机运行之前，一般要经过编辑、编译、连接这三步。

（3）编译方式与解释方式的根本区别在于是否生成目标代码。

（4）与编译系统相比，解释系统比较简单，可移植性好，执行速度慢。

（5）编译程序生成的目标程序不一定是可执行的程序。

 

二、编译程序的种类

1. 可变目标编译程序：不需重写编译程序中与机器无关的部分就能改变目标机的编译程序。

2. 交叉编译程序：能产生不同于其宿主机的机器代码的编译程序。

3. 优化编译程序：着重于提高目标代码效率的编译程序。

4. 诊断编译程序：专门用于帮助程序开发和调试的编译程序。

 

三、编译程序的工作过程

1. 词法分析：词法分析是编译过程的基础，其任务是扫描源程序，根据语言的词法规则，分解和识别出每个单词，并把单词翻译成相应的机内表示。

2. 语法分析：语法分析是在词法分析的基础上进行的。其任务是根据语言的语法规则，把单词符号串分解成各类语法单位，如表达式、语句等。

3. 语义分析：语义分析的任务是对源程序进行语义检查，其目的是保证标识符和常数的正确使用，把必要的信息收集、保存到符号表或者中间代码程序中，并进行相应的处理。

4. 中间代码生成：对于编译程序而言并非必不可少的阶段。常用的中间代码有三元式、四元式和逆波兰式。

5. 中间代码优化：也不是编译程序的必要阶段。优化的任务在于对前端产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。

6. 目标代码生成：编译程序的最后阶段。

注：

（1）编译程序的工作过程一般可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化等几个基本阶段，同时还伴有表格处理和出错处理。

（2）编译程序绝大多数时间花在表格管理上。

（3）编译程序中包括词法分析、语法分析、语义分析和中间代码产生等主要与源程序有关但与目标机无关的那些部分叫编译前端；编译程序中包括目标代码生成、目标代码优化等与目标机有关而与源语言无关的那些部分叫编译后端。编译后端通常不依赖于源语言而仅仅依赖于中间语言。可以取编译程序的前端，改写其后端以生成不同目标机上的相同语言的编译程序。

（4）从编译程序的角度说，源程序中的错误通常分为语法错误和语义错误两大类。在使用高级语言编程时，首先可通过编译程序发现源程序的全部语法错误和部分语义错误。语法错误是指源程序中不符合语法（或词法）规则的错误，它们可在词法分析或语法分析时检测出来。例如，词法分析阶段能够检测出“非法字符”之类的错误；语法分析阶段能够检测出诸如“括号不匹配”、“缺少 ; ”之类的错误。语义错误是指源程序中不符合语义规则的错误，这些错误一般在语义分析时检测出来，有的语义错误要在运行时才能检测出来。语义错误通常包括：说明错误、作用域错误、类型不一致等。

（5）现代多数实用编译程序所产生的目标代码都是一种可重定位的指令代码，在运行前必须借助于一个连接装配程序把各个目标模块，包括系统提供的库模块连接在一起，确定程序变量或常数在主存中的位置，装入内存中制定的起始地址，使之成为一个可运行的绝对指令代码的程序。

（6）目标代码生成阶段所生成的目标代码的形式可以是绝对指令代码、可重定位的指令代码或汇编指令代码。

（7）编译过程可采用分遍的形式，即编译过程可以由一遍或多遍编译程序来完成。对于源程序或中间代码程序，从头到尾扫描一次并完成所规定的工作称为一遍。将编译程序分成若干个“遍”是为了使程序的结构更加清晰。

 

四、编译程序的结构

1. 词法分析器（扫描器）：输入源程序，进行词法分析，输出单词符号。

2. 语法分析器（分析器）：对单词符号串进行语法分析（根据语法规则进行推导或归约），识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。

3. 语义分析及中间代码产生器：按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。有的编译程序在识别出各类语法单位后，构造并输出一棵表示语法结构的语法树，然后，根据语法树进行语义分析和中间代码产生。还有许多编译程序在识别出语法单位后并不真正构造语法树，而是调用相应的语义子程序。在这种编译程序中，扫描器、分析器和中间代码生成器三者并非是截然分开的，而是相互穿插的。

4. 优化器：对中间代码进行优化处理。

5. 目标代码生成器：把中间代码翻译成目标程序。

 

五、其他

1. 为了使编译后的Java程序从一个平台移到另外一个平台上执行，Java定义了一种称为ByteCode的虚拟机代码。只要实际使用的操作平台上实现了执行ByteCode的Java解释器，这个操作平台就可以执行各种Java程序。这就是所谓Java语言的操作平台无关性。

2. 编译程序的自动化

• LEX：词法分析程序生成器（输入：正规表达式；输出：词法分析程序）
• YACC：语法分析程序生成器（输入：LALR(1)文法；输出：LALR(1)分析表和LALR(1)分析器）

3. 一个Lex源程序主要包括两部分，一部分是正规定义式，另一部分是识别规则。

4. 语言处理程序是一类系统软件的总称，而不是一种应用软件。语言处理程序可分为三种：汇编程序、编译程序和解释程序。

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

6. 支持程序设计人员进行程序计开发的工具，除了编译程序以外，还需要编辑程序、链接程序和调试程序等其他一些工具。

 

（二）形式语言概论

一、文法

一个上下文文法G的四个组成部分：开始符号、产生式集合、终结符集合、非终结符集合。Chomsky把文法分成四种类型：

1. 0型文法（短语结构文法）： 

• 等价描述：图灵机

2. 1型文法（上下文有关文法）：产生式左边至少有一个非终结符，且产生式左边的长度小于右边（S→ε除外）。

• 等价描述：线性带限自动机
• 线性带限自动机是一个确定的单带图灵机，其读写头不能超越原输入带上字符串的初始和终止位置，即线性带限自动机的存储空间被输入符号串的长度所限制。

3. 2型文法（上下文无关文法）：在1型文法的基础上，产生式左边只有一个非终结符。

• 等价描述：下推自动机
• 上下文无关文法比正规文法有更强的描述能力。
• 上下文无关文法可以用扩展的BNF来描述。

4. 3型文法（正规文法、正则文法）：在2型文法的前提下，产生式右边只有单个终结符或者是单个终结符和单个非终结符。

• 等价描述：确定型有穷自动机、非确定型有穷自动机、左线性正规文法、右线性正规文法
• 可分为右线性文法和左线性文法。
• 右线性文法：文法产生式为A→aB或A→a，其中A, B∈, a∈
• 左线性文法：文法产生式为A→Ba或A→a，其中A, B∈, a∈

5. 程序设计语言的词法规则属于3型文法，语法和语义部分一般属于1型文法，但实际上都是采用2型文法来描述语法。

 

二、句型、句子和语言

1. 句型：假设G是一个文法，α是由终结符和非终结符组成的串，S是文法的开始符号，如果Sα，则称α为句型。

2. 句子：对于文法G，仅含终结符号的句型称为句子。

3. 语言：由文法产生的句子集合是文法产生的语言。

0型文法产生的语言称为0型语言。

1型文法产生的语言称为1型语言，也称作上下文有关语言。

2型文法产生的语言称为2型语言，也称作上下文无关语言。

3型文法产生的语言称为3型语言，也称作正规语言。

注：

（1）语言L={αcα | α∈(a|b)*}不能由上下文无关文法产生，甚至连上下文有关文法也不能产生，只能由0型文法产生，所以是0型语言。

e.g. 请写出产生下列语言的文法。（考）

（1）

（2）

（3）可带符号位（2位以上且最高位不为0）的5的倍数的十进制集合。

（1）G[S]:

• S→ABC
• A→aA|ε
• B→bB|b
• C→cC|cc

（2）G[S]:

• S→aSb|ab

（3）G[Z]:

• Z→SABC
• S→+|-
• A→1|2|3|4|5|6|7|8|9
• B→0B|AB|ε
• C→0|5

 

三、推导和直接推导

1. 直接推导：设A→α是一个产生式，且α、β∈(VT∪VN)*，若αAβ⇒αγβ，则称αAβ直接推出αγβ；或者说，αγβ是αAβ的一个直接推导。

2. 推导：如果α1⇒α2⇒…⇒αn,则称这个序列是从α1到αn的一个推导，记为α1αn。归约是推导的逆过程，是从句型出发，逐步用产生式的左边去替换产生式的右边，直到开始符号为止。

3. 最左直接推导：对最左非终结符进行直接推导。最左推导：推导的每一步都是最左直接推导。

4. 最右直接推导：对最右非终结符进行直接推导。最右推导：推导的每一步都是最右直接推导。最右直接推导又称为规范直接推导，最右推导又称为规范推导。同理，最右归约又称为规范归约，所以规范归约是规范推导的逆过程。由规范推导得到的句型叫规范句型。

e.g. 文法G[Z]：

• Z→UV|VU
• U→Z1|1
• V→Z0|0

请写出01010110的最左推导和最右推导。（考）

从下往上画出语法树（归约图）：

最左推导：Z⇒UV⇒Z1V⇒VU1V⇒Z0U1V⇒VU0U1V⇒0U0U1V⇒010U1V⇒010Z11V⇒010UV11V⇒0101V11V⇒0101011V⇒01010110

最右推导：Z⇒UV⇒U0⇒Z10⇒VU10⇒VZ110⇒VUV110⇒VU0110⇒V10110⇒Z010110⇒VU010110⇒V1010110⇒01010110

 

四、文法压缩

1. 多余规则：（1）自产生式（U→U）；（2）无用非终结符；（3）不可达文法符号

2. 无用非终结符：不出现在文法的任何一个句型中，并且不能从它推导出终结符号串的非终结符。

3. 不可达文法符号：不出现在文法的任何一条产生式的右部的非终结符。

e.g. 压缩文法G[Z]:

• Z→E+T              
• E→E|S+F|T       
• F→F|FP|P
• P→G                    
• G→G|GG|F       
• T→T*i|i
• Q→E|E+F|T|S      
• S→i

（1）删除自产生式E→E, F→F, G→G

（2）不可达文法符号Q（删除Q→E|E+F|T|S）

（3）由于F, P, G陷入了循环转换，所以可删除无用非终结符F, P, G（删除F→F|FP|P, P→G, G→G|GG|F, E→S+F）

（4）之后S变为不可达，删除S→i，得：

• Z→E+T                  
• E→T                   
• T→T*i|i

（5）可压缩E→T得：

• Z→T+T                  
• T→T*i|i

 

五、其他

1. 强制式语言和声明式语言

（1）命令式编程（Imperative programming），即利用命令式语言（也叫强制式语言、指令式语言）进行编程的方式，是一种描述计算机所需作出的行为的编程范型。大部分的编程语言都是指令式的，如Fortran、C、Pascal等。大部分的命令式高级编程语言都支持四种基本的语句：运算语句、循环语句、条件分支语句、无条件分支语句。

（2）声明式编程（Declarative programming），即利用声明式语言进行编程的方式，与命令式编程相对立。它描述目标性质，让计算机明白目标，而非流程。声明式语言包括数据库查询语言（SQL，XQuery），正则表达式，逻辑编程，函数式编程和组态管理系统。这种编程方式通过函数、推论规则或项重写（term-rewriting）规则，来描述变量之间的关系。

2. 数据类型的三要素

• 用于区别这种类型的数据对象的属性
• 这种类型的数据对象可以具有的值
• 可以作用于这种类型的数据对象的操作

3. 在赋值语句中，赋值号 “:=” 左右两边的变量名扮演着两种不同的角色，为了区分一个名的这两种特征，我们把一个名字所代表的单元的地址称为该名的左值，把一个名字的值称为该名字的右值。

4. 若文法G定义的语言是无限集，则文法必然是递归的。

5. 可能有两个不同的文法G1和G2，其中一个是二义的而另一个是无二义的，但是却有L(G1)＝L(G2)。

6. 对于每一个左线性文法G1，都存在一个右线性文法G2，使得L(G1)=L(G2)。

7. 二义性是不可判定的，也就是说，无法编出这么一个程序，输入该文法后，该程序能确切地给出该文法是否二义的答案。

8. 说明语句旨在定义名字的性质。编译程序把这些性质登记在符号表中，并检查程序中名字的引用和说明是否一致。实际上，许多说明语句并不能翻译成相应的目标代码。

9. C语言不是一个允许子程序嵌套定义的语言；Algol 60/Pascal/Ada等支持嵌套子程序。

10. 如果两个正规式所表示的正规集相同，则认为这两个正规式等价。

11. 如果文法G是无二义性的，则它的任何句子α最左推导和最右推导对应的语法树必定相同。

12. 对于句型η的语法树，若它的一棵子树的根标记为A，且将此子树的末端结标记从左至右排列起来所形成的符号串为β，则β是句型η相对于A的一个短语；此时文法中必有推Aβ。

 

（三）有穷自动机

一、确定有穷自动机（DFA）、非确定有穷自动机（NFA）、ε自动机（εNFA）

1. DFA与NFA的区别：

• DFA只有一个开始状态，而NFA是有一个开始状态集；
• DFA的映射是一个单值映射，而NFA的映射是一个多值映射（即某个状态经过相同的字母可以到达不同的状态）。

2. 设NFA：A=(Q, ∑, t, Q0, F)是一个非确定有穷自动机，它的语言（即它能接受的符号串集合）为L(A)。那么，一定可以构造一个和它等价的确定有穷自动机DFA：A'=(Q', ∑, t', q0, F')，使得L(A)=L(A')。

3. 对于εNFA（或εDFA），总可以构造等价的NFA（或DFA)，使得L(εNFA) = L(NFA)。换句话说，可以消除ε自动机中的空移。

4. 一个DFA可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示转换函数（或δ(s, a)）的值，这个矩阵叫状态转换矩阵。

5. 一个确定性有限自动机DFA M的化简是指：寻找一个状态数比M少的DFA M’，使得L(M)=L(M')。

e.g. 对以下NFA进行确定化。（考）

状态转换矩阵（造表法）：

确定化后的状态转换图：

e.g. 对以下εNFA进行确定化。（考）

状态转换矩阵（造表法）：

确定化后的状态转换图：

e.g. 对以下DFA进行化简。（考）

对子集进行分解：

化简后的DFA：

e.g. 将以下正规文法G[S]转换为有穷自动机。

• S→aS | aA | bB
• A→bA | cC
• B→aB | dD
• C→cC | c
• D→dD | d 

e.g. 将以下有穷自动机转换为正规文法。

G[S]:

• S→xA | yB
• A→yA | yC | xB
• B→xC | yC | yA |ε
• C→ε

 

二、其他

1. 从接受语言的能力上来说，非确定型有穷自动机和左线性正规文法、右线性正规文法、确定型有穷自动机是等价的。

2. 对于Σ中的任何符号串α，如果存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符号连接起来形成的符号串等于α，则称α被该自动机所接受(识别)。

3. 从左线性文法构造有限自动机时，通常自动机状态个数比文法非终结符号数多1。

4. 一个状态转换图只包含有限个状态，其中有一个被认为是初态，而且实际上至少有一个终态。

5. 把状态转换图用程序实现时，对于含有回路的状态结点来说，可以让它对应一个由 if 和 while 语句构成的程序段。

6. 一个正规式可以对应不止一个有穷自动机。

 

（四）词法分析

一、扫描缓冲区&扫描器

1. 扫描缓冲区

（1）作用：缓存预处理的输入字符。

（2）缓冲区一分为二，每一半可容纳120个字符，两部分可互补使用（因为不论扫描缓冲区设得多大都不能保证单词符号不会被它的边界所打断，因此使用一分为二的区域）。

2. 扫描器（词法分析器）

（1）作用：扫描缓冲区，直接进行单词的识别

（2）编译过程中扫描器的任务

• 组织源程序的输入；
• 按词法规则分隔单词，识别出其属性，并转换成token串输出；
• 删除注释；
• 删除空格或无用字符；
• 行计数，列计数；
• 发现并定位词法错误；
• 建立符号表。建立符号表的过程涉及词法分析和语法分析，其中在词法分析过程中得到的各种常量要加入符号表，变量要到语法分析阶段才加入符号表。

（3）词法分析器对扫描缓冲区进行扫描时一般用两个指示器，一个指向当前正在识别的单词符号的开始位置；另一个用于向前搜索以寻找单词符号的终点。

（4）对于词法分析程序来说，当程序到达“错误处理”时，意味着现行状态和当前所面临的输入串不匹配。如果后面还有状态图，出现在这个地方的代码应该为：将搜索器回退一个位置，并令写一个状态图开始工作。

 

二、词法分析

1. 词法分析的理论基础是有穷自动机理论。

2. 单词符号是程序设计语言的基本语法单位和最小语义单位。可分为：

• 关键字（又称保留字或基本字）
• 标识符：用于表示变量名、过程名。
• 常数
• 运算符
• 界限符

3. 词法分析阶段的任务是从左到右扫描源程序，从而逐个识别单词。执行词法分析的程序称为词法分析器。词法分析器的输出结果是单词的种别编码和自身值，常表示成二元式：（单词种别，单词符号的属性值）。

4. 如果一个种别只含有一个单词符号，那么，对于这个单词符号，类别编码就可以完全代表它自身了。如果一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给出种别编码以外，还应给出有关单词符号的属性信息（属性值）。单词符号的属性是指单词符号的特性或特征，其属性值则是反映特性或特征的值。比如，对于某个标识符，常将存放它的有关信息的符号表项的指针作为其属性值；对于常数，常将存放它的常数表项的指针作为其属性值。

5. 标识符

（1）标识符是由字母或数字以及某些特殊符号（因不同的高级语言而不同）组成的，但是必须以字母开头的一个字符串。当给某标识符以确切的含义时，这个标识符就叫做名字。程序语言中的各种名字都是用标识符表示的。

（2）标识符的机内表示又称机内符，它包括标识符的全部信息。标识符的类型在机内可采用位向量形式表示。

（3）如果一个标识符包含的语义信息过多，在一个机器字内放不下，那么可以在一个机内符中存放部分语义信息，多余的语义信息则存放到一个信息表区中。

（4）符号表（标识符表）用于存放在程序中出现的各种标识符及其语义属性。符号表是编译程序进行各种语义检查（语义分析）的依据，是进行地址分配的依据。在目标代码生成阶段，符号表用于地址分配。

（5）标识符分为定义性标识符和使用性标识符。

（6）程序语言下面的单词符号中，标识符一般不需要超前搜索。

6. 无符号常数的识别和拼数工作通常都在词法分析阶段完成。

7. 在词法分析的状态转换图中，带星号的结点肯定是终态结点。

 

（五）自上而下语法分析

一、语法分析器

1. 语法分析器接收以单词为单位的输入，并产生有关信息供以后各阶段使用。

2. 语法分析器可以发现源程序中的语法错误。

3. 语法分析器的任务：

• 分析单词串是如何构成语句和说明的；
• 分析语句和说明是如何构成程序的；
• 分析程序的结构。

4. 语法分析的工作本质：按文法的产生式识别输入符号串是否为一个句子，这里所说的输入串是指由单词符号组成的有限序列。

5. 语法分析器的输入是单词符号，其输出是语法单位。

6. 语法分析基于上下文无关文法进行，即识别的是该类文法的句子。语法分析的有效工具是语法树。

 

二、自上而下分析

1. 主旨：对任何单词字符串，试图用一切可能的办法，从文法开始符号（根节点）触发，为输入串寻找最左推导。

2. 自上而下面临的问题：

• 需消除左递归；
• 存在回溯；
• 虚假匹配。
• 不能准确地确定输入串中出错的位置
• 效率低

3. 基本思想：从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。

 

三、消除左递归

1. 直接左递归：U→Ux | y；间接左递归：UUx

2. 用扩展的BNF消除多递归：

（1）花括号：{x}表示符号串x出现零次或多次。e.g. E→T | E+T的EBNF范式为E→T{+T}。

（2）方括号：[x]表示符号串x可有可无（只出现一次或不出现）。

（3）圆括号：可提出一个非终结符的多个产生式右部的公共因子。

3. 扩展的巴克斯范式描述语法的好处是，直观易懂，便于表示消去左递归和提取左因子。

4. 直接改写法：直接左递归产生式U→Ux | y可改写为U→yU', U'→xU' | ε。

更一般地，可改写为。

 

四、消除回溯

1. 消除回溯必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。也就是说，若此候选获得成功匹配，那么，这种匹配决不会是虚假的；若此候选无法完成匹配任务，则任何其它候选也肯定无法完成。

2. 把一个文法改造成任何非终结符的所有候选终结首符集两两不相交的办法是提取左因子。提取公共左因子的副产品是引进了大量非终结符和ε产生式。e.g. 可以把关于A的规则 （其中，不以开头）提取左因子改写为。

 

五、LL(k)文法

1. FIRST(α)的构造：

（1）α∈VT，FIRST(α) = {α}

（2）α∈VN，α→a···，a∈FIRST(α)；α→ε，ε∈FIRST(α)

（3）α∈VN，α→XY···，FIRST(X) - {ε} ⊂ FIRST(α)。若X ε，则FIRST(Y) - {ε} ⊂ FIRST(α)

 

2. FOLLOW(U)的构造：

（1）U是开始符号，则 #∈FOLLOW(U)

（2）A→xUy， 则 FIRST(y) - {ε} ⊂ FOLLOW(U)

（3）A→xUy，y ε (包括A→xU)，则 FOLLOW(A) ⊂ FOLLOW(U)

 

3. LL(1)分析表M的构造算法：

（1）对文法的每一条产生式U→α，若a∈FIRST(α)，则M[U, a] = 'U→α'

（2）若ε∈FIRST(α)，则M[U, b] = 'U→α'，其中，b∈FOLLOW(U)

（3）分析表M的其它元素均为出错标志error，通常用空白表示

 

4. LL(1)分析程序的总控算法

（1）最初，分析器把文法的开始符号S置于栈顶（假定输入串以 # 结束）。

（2）若栈顶为一终结符，而且与当前输入符号匹配，则读头前进一位置（扫描下一输入符号），并逐出栈顶符号；否则报错。(匹配动作)

（3）若栈顶符号是一非终结符U，且当前的输入符号为a，则查看分析表M，若M[U, a]置有关于U的产生式U→w，则先从栈中逐出U再把w下推进栈；若w=ε，则不推进任何信息进栈，仅逐出栈顶符号；若M[U, a]为空白，则调用出错处理子程序。(应用动作)

（4）重复步骤（2）（3），直至栈变为空。

（5） 该分析器停止于空栈。(接收)

e.g. 文法G[S]：

• S→A
• A→AiB | B
• B→B+C | C
• C→)A*|(

请使用LL(1)分析程序分析字符串"(i("。（考）

消除左递归：

A→AiB | B直接消除左递归：A→BA', A'→iBA'|ε

B→B+C | C直接消除左递归：B→CB', B'→+CB'|ε

所以文法G[S]可以改写成LL(1)文法如下：

• S→A
• A→BA'
• A'→iBA'|ε
• B→CB'
• B'→+CB'|ε
• C→)A*|(

构建FIRST和FOLLOW表：

构造LL(1)分析表：

使用总控程序分析输入串"(i("：

 

六、其他

1. 递归下降法（递归下降子程序分析法）是一种自顶向下的方法，所以不允许任一非终结符是直接左递归的。

2. 并不是所有文法都能改写为LL(1)文法。

3. 一个文法G的预测分析表不含多重入口，当且仅当该文法是LL(1)。所以，一个文法的预测分析表含有多重定义入口，说明该文法不是LL(1)的。

 

（六）自下而上分析和优先分析方法

一、自下而上分析

1. 句型 ：如果，则称是文法G的一个句型。

2. 短语：若，则称子串是句型相对于非终结符的短语。

3. 直接短语（简单短语）：如果，则称子串是句型相对于非终结符的直接短语或简单短语。

4. 素短语：至少包含一个终结符的短语，但它不能包含其他素短语。

5. 句柄：一个句型的最左直接短语（最左简单短语），称为该句型的句柄。

注：一个句型的句柄一定是文法某产生式的右部；一个句型中出现了某产生式的右部，但此右部不一定是该句型的句柄。

e.g. 设文法G[E]，E为其开始符号产生式如下：

• E→E+T | T
• T→T*F | F
• F→(E) | i

则句型E+T*F+i的句柄是 T*F 。（考）

符号串E+T*F+i的语法树为：

可以看到有且，所以T*F是句型E+T*F+i的句柄。（i也是该句型相对于F的直接短语，但由于不是最左直接短语所以就不是句柄）

6. 在自下而上的语法分析中，分析的关键是寻找句柄。

7. 在规范归约中，用句柄来刻画可规约串。所以归约规范的关键问题是寻找或确定一个句型的句柄。

8. 自下而上语法分析采用移进-归约分析法，常用的是自底向上语法分析有算符优先分析法和LR分析法。分析句型时，应用算符优先分析技术时，每步被直接归约的是最左素短语；而应用LR分析技术时，每步被直接归约的是句柄。

9. 移进-归约分析对符号串的使用有四类操作：移进、归约、接受和出错处理。

10. 自下而上分析方法的基本思想：从输入字符串开始，利用文法规则逐步进行直接归约，直至归约到文法的开始符号。

 

二、简单优先分析方法（越往左优先级越高）

1. Warshall算法：求关系传递闭包

for (int i = 0; i < n; i++){
    for (int j = 0; j < n; j++){
        if(M[j][i] == 1){
            for (int k = 0; k < n; k++){
                M[j][k] |= M[i][k];
            }
        }
    }
}

简单来说，就是可以遍历矩阵的每一列，如果M[j, i] = 1, M[i, k] = 1，那么M[j, k] = 1（传递性）。

求关系传递闭包：先执行Warshall算法，再将所有对角线元素置1（自反闭包）。

2. 三种优先关系（语法树越往下优先级越高，因为要先归约）：

（1）：当且仅当有

（2）：当且仅当有

（3）：当且仅当有

3. 简单优先文法不允许任意两个产生式具有相同的右部。

 

三、算符优先文法

1. 所谓算符优先分析法就是仿照算术四则运算的运算过程设计的一种语法分析方法。它首先要规定运算符之间的优先关系，然后利用这种关系确定句型的最左素短语，并进行归约。寻找最左素短语时，先找到最左素短语的末尾终结符，然后再向前搜索最左素短语的首终结符。

2. 终结符之间的三种优先关系（设）：

（1）：当且仅当有或

（2）：当且仅当有

（3）：当且仅当有

3. 算符文法（OG文法）：产生式右部不包含相邻非终结符的文法。

4. 算符优先文法（OPG文法）：任意两个终结符之间至多存在一种优先关系。

5. 算符优先文法不是一种规范归约法。

6. 算符优先关系表不一定存在对应的优先函数，即一个算符优先文法可能不存在算符优先函数与之对应。

7. 一个算符优先文法的句型的最左素短语是该句型中满足下列条件的最左子串：

8. 任何算符优先文法的句型中不会有两个相邻的非终结符号。

e.g. 已知文法G[E]:

• E→E+T | T
• T→T*F | F
• F→(E) | i

请使用算符优先分析方法，分析符号串i*(i+i)。（考）

符号串i*(i+i)的分析过程如下（其中V表示非终结符）：

 

四、优先函数

1. 对于优先矩阵M，如果存在函数f、g满足以下条件（如果是算符优先可对应为）：

（1）若，则f(L) = g(R)

（2）若，则f(L) < g(R)

（3）若，则f(L) > g(R)

 

2. Bell方法（有向图构造法）

（1）作两排结点：一排为，另一排为：

• 若，从L到R连一有向弧；
• 若，从R到L连一有向弧；
• 若，从L到R和从R到L各连一有向弧。

（2）计算各结点能到达的结点数（包括自己），作为该结点的值（可使用Warshall算法）。函数f(L)等于结点的值，函数g(R)等于结点的值。

（3）对照优先函数的定义进行检验，如果出现矛盾则说明该优先关系不存在优先函数。

e.g. 文法G[E]：

• 0  E→E+T | T
• 1  T→T*F | F
• 2  F→(E) | i

请使用Bell方法求文法G[E]的优先函数，并使用优先函数分析符号串i*(i+i)。（考）

算符优先关系矩阵如下：

构造有向图如下：

根据有向图得到邻接矩阵：

使用Warshall算法更新矩阵：

最后可以得到每个优先函数的值：

分析符号串i*(i+i)：

 

（七）自下而上的LR(k)分析方法

一、LR分析法

1. LR(k)分析法：从左到右扫描输入串（Left），自下而上规范归约（Reduction），向前查看k个输入符号。

LR(k)分析法中，L的含义是从左到右扫描输入串，R的含义是构造一个最右推导的逆过程，k的含义是查看k个符号

2. LR分析程序是一个确定的下推自动机，由一个输入串、一个下推栈和一个带有分析表的总控程序组成。

3. LR分析是寻找最右句型的句柄。

4. LR(k)分析方法中项目类型可分为四类：归约项目、接收项目、移进项目和待约项目。

5. 分析能力：LR(1) > LALR(1) > SLR(1) > LR(0)。

6. 在LR分析法中，分析栈中存放的状态是识别规范句型活前缀（可归前缀）的DFA状态

7. 在LR分析过程中的任何时候，栈里的文法符号从下往上应该构成活前缀，把输入串的剩余部分配上之后应成为规范句型。

8. LR分析器的任务是产生LR分析表。一个LR分析器包括两部分：一个总控程序和一张分析表。

9. LR(k)文法是无二义性的，而且满足LR(0)⊂SLR(1)⊂LALR(1)⊂LR(1)。此外，对所有的k都有LR(k)⊂LR(k+1)。

10. LR分析技术可以适用二义文法，即对于一些二义性文法也可构造其LR分析程序，只要加进足够的无二义性规则就行。所谓无二义性规则是指为消除二义性而引起的冲突动作的规则。

11. 给定文法G和某个固定的k，G是否是LR(k)文法的问题是可判定的。

12. 给定文法G，是否存在一个k使得G是一个LR(k)文法的问题是不可判定的。

 

二、LR(0)分析表

1. 前缀：字符串的任意首部，包括ε。活前缀：规范句型的一个前缀，它不包括该句型的句柄右边的任何符号。

2. 拓广文法：如果S的产生式有多个右部，或S出现在产生式的右部，则需另外加S'→S产生式，S'作为新的开始符号。

3. LR(0)项目：文法G的每个产生式右部的某个位置添加一个“·”。

• 初始项目：左部为开始符号，“·”在右部的最前位置。
• 接收项目：左部为开始符号，“·”在右部的最后位置。
• 归约项目：除了接收项目以外，“·”在右部的最后位置。
• 移进项目：形如A→α·xβ，x∈VT，α, β可空。
• 待移项目：形如A→α·xβ，x∈VN。

根据项目的定义，可给出文法中所有产生式的项，而每个项目都为识别活前缀的NFA的一个状态。

4. CLOSURE(I)函数：若A→α·Bβ属于CLOSURE(I)且B→γ是文法的一个产生式，则项目B→·γ也要加入到CLOSURE(I)中。

5. goto(I, X)函数：goto(I, X) = CLOSURE({所有形如[A→α·Xβ]的项目（A→αX·β∈I）})。

6. LR(0)文法：项目集中不存在以下冲突项目：

• 移进项目和归约项目并存
• 多个归约项目并存

即在LR(0)分析中，相容的项目集，必须满足的条件是移进项目和归约项目并存、多个归约项目并存。

7. 注意分析表中的列需要有#，但是没有开始符号。

e.g. 拓广文法G[Z]：

• 0  Z→A
• 1  A→BA
• 2  A→i
• 3  B→AB
• 4  B→j

请判断G[Z]是否为LR(0)文法。

状态转移图：

构造LR(0)分析表：

从状态I6和I7可以看到出现“移进-归约”冲突，所以该拓广文法G[Z]不是LR(0)文法。

 

三、SLR(1)分析表

1. SLR(1)文法：当输入符号属于可归约项目左边非终结符的FOLLOW集合时才归约，否则移进。

SLR(1)解决了LR(0)文法不能处理的“移进/归约”冲突问题。

在SLR（1）分析法的名称中，S的含义是简单的。

e.g. 拓广文法G[E']：

• 0  E'→E
• 1  E→E+T
• 2  E→T
• 3  T→T*F
• 4  T→F
• 5  F→(E)
• 6  F→id

请构造文法G[E]的SLR(1)分析表，并分析符号串id+id*id。（考）

状态转移图：

非终结符的FIRST集合与FOLLOW集合：

构造SLR(1)分析表：

分析符号串id+id*id：

 

四、LR(1)分析表

1. LR(1)分析中括号中的1是指，在选用产生式A→α进行分析，看当前读入符号是否在FIRST(α)中。

2. 同心集的合并解决了“移进/归约”冲突问题。

e.g. 拓广文法G[Z]：

• 0  Z→S
• 1  S→L=R
• 2  S→R
• 3  R→L
• 4  L→*R
• 5  L→i

请构造文法G[Z]的LR(1)分析表。

状态转移图：

LR(1)分析表：

 

五、其他

1. LR分析技术可以适用于二义性文法。

2. LR文法在自左到右扫描输入串时就能发现错误，但不能准确指出出错地点。

 

（八）语法制导翻译法

一、抽象语法树构造

1. 在一棵语法树中结点的继承属性和综合属性之间的相互依赖关系可以由语法规则来描述。

综合属性：自下而上；继承属性：自上而下

2. 生成三地址代码时，临时变量的名字对应抽象语法树的内部结点。

3. 后缀式是抽象语法树的线性表示形式，后缀式是树结点的一个序列，其中每个结点都是在所有子结点之后立即出现的。

 

二、中间代码形式

1. 中间代码

（1）对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。中间代码生成时所依据的是语义规则。

（2）在编译程序中安排中间代码生成的目的是便于代码优化和目标程序的移植。

（3）中间代码是独立于机器的，复杂性介于源语言和机器语言之间，便于进行与机器无关调换代码优化工作。

（4）常见的中间语言形式有逆波兰式、四元式、三元式、抽象语法树等等。

2. 逆波兰式（后缀表示法）

（1）运算符跟在运算量（操作数）的后面，逆波兰表示法表示表达式时无须使用括号。e.g. AB*表示A*B，AB*C+表示A*B+C，ABCD/+*表示A*(B+C/D)，AB*CD*+表示A*B+C*D，xab+-cd-/abc*+-:=表示x:=-(a+b)/(c-d)-(a+b*c)。

（2）赋值语句的逆波兰表示为<左部><表达式>:= ；转向语句的逆波兰表示为<序号> jump ；条件语句的逆波兰表示为<布尔表达式><序号> jumpf。

（3）赋值语句a:=b*-c+b*-c的后缀式为a b c uminus * b c uminus * + assign。

（4）如果E是一个常量或变量，则E的逆波兰式是E自身。

3. 四元式

（1）四元式实际上是一种“三地址语句”的等价表示，它的一般形式为(op, arg1, arg2, result)。

（2）四元式之间的联系是通过临时变量实现的。

（3）如果一条三地址语句为x:=y+z，则称对x定值并引用y和z。

4. 三元式

（1）三元式与四元式基本相同，所不同的是只是没有表示运算结果的部分，凡涉及运算结果的，均用相应的三元式的地址或序号来表示。三元式也是严格意义上的三地址代码。

（2）使用三元式是为了避免把临时变量填入符号表。

（3）为了便于优化处理，三元式可以表示成间接三元式。间接三元式表示法的优点为采用间接码表，便于优化处理。

（4）多目运算x:=y[i]的三元式表示为两部分：

• (0): ([]=, y, i)
• (1): (assign, x, (0))

（5）多目运算X[i]:=y的三元式表示为两部分：

• (0): (=[], x, i)
• (1): (assign, (0), y)

e.g. 写出以下程序段的四元式和逆波兰表达式：（考）

begin
    n:=1; t:=1; exp:=t;
    while t>0.000001 do
    begin
        n:=n+1;
        t:=1.0/n/n;
        exp:=exp+t;
    end
end

四元式：

逆波兰表达式：

 

三、其他

1. 一个名字的属性包括类型和作用域。

2. 编译程序使用说明标识符的过程或函数的静态层次来区别标识符的作用域。

3. 常用的参数传递方式有传地址、传值和传名。

4. 类型表达式

（1）一个类型表达式或者是基本类型，或者由类型构造符施加于其它类型表达式组成。类型构造符包括数组、笛卡尔积、记录、指针和函数。

（2）两个类型表达式要么是同样的基本类型，要么是同样的类型构造符作用于结构等价的类型，我们就说，这两个类型系统等价。所谓类型系统就是把类型表达式赋给语言各相关结构成分的规则的集合。同一种语言（比如C++语言）的编译程序，在不同的实现系统里（比如微软的Visual C++和Linux下的开源编译器TCC），可能使用不同的类型系统。

（3）在一些pascal的实现中，如果说明中出现了没有名字的类型表达式，编译器这样处理：建立一个隐含的类型名来和每个声明的变量标识符相联系。

（4）记录类型的各个域变量分配存储区域的地址的确定是相对于为记录类型变量所分配存储区域的首地址的，记录类型也应建立自己的符号表。

（5）类型表达式中可以出现类型变量，类型变量值也是类型表达式。

5. 在程序设计语言中，布尔表达式有两个基本的作用：一个是计算逻辑值；另一个是作控制流语句中的条件表达式。

6. 嵌套过程

（1）允许嵌套过程的语言，其过程说明语句的翻译用两个栈tblptr和offset分别保存尚未处理完的过程的符号表指针和它们的offset，这两个栈顶的元素分别是正在处理的过程的的符号表指针和相对地址。

（2）对于Pascal这样允许嵌套过程的语言，每当遇到过程说明D→proc id D1; S时，便创建一张新的符号表，也就是说，让每个过程说明都有自己一张独立的符号表。

7. 编译器遇到常量说明时，要把常量值登录入常量表并回送序号；在符号表中为等号左边的标识符建立新条目，在该条目中填入常量标志、相应类型和常量表序号。

8. 典型的转移条件语句:if E then S1 else S2中,作为转移条件的布尔表达式E,赋予它两种“出口”：一是“真”出口，转向S1；二是“假”出口，转向S2。

9. 通过一遍扫描来产生布尔表达式和控制流语句的代码存在一个问题，就是当生成某些转移语句时可能还不知道该语句将要转移到的语句的地址是什么，可以使用拉链-回填的办法来解决这个问题。

10. 程序中的表达式语句在语义翻译时不需要回填技术。

 

（九）优化

一、控制流图与基本块

1. 控制流分析：编译程序需要知道被编译程序实际运行时指令执行序列的所有可能。

2. 数据流分析：编译程序还应知道伴随控制流的各种数据变化情况。

3. 控制流图：将每条指令作为有向图中的结点，指令I到指令J有一条有向边，当且仅当指令J在运行时能紧随指令I之后。

4. 基本块：一组顺序执行的程序段，仅有一个入口和出口。基本块的入口语句集包括：

• 过程的第一条三地址指令；
• 有标号的指令（条件语句跳转到的指令）；
• 紧随条件转移语句之后的三地址指令。

5. 流图：通过构造一个有向图，可以将控制流的信息增加到基本快的集合上来表示一个程序。所谓变量A在某点d的定值到达另一点u，是指流图中从d有一通路且该通路上没有A的其他定值。

e.g. 给出三地址代码如下：（考）

（a）求基本块的入口语句集。

（b）画出基本块的控制流程图。

（a）每个语句可以得到的入口语句：

• （1）  {1}
• （3）  {4，7}
• （5）  {6，7}
• （6）  {7，10}
• （10）{11，12}
• （11）{12，15}
• （14）{15，6}

综上，入口语句集为{1，4，6，7，10，11，12，15}。

（b）基本块的控制流程图为：

二、优化

1. 代码优化的目标：减少目标代码的体积和增加目标代码的执行效率（多数优化通常两者可兼得）。

2. 就实施优化所涉及的范围来说，优化可分为局部优化、全局优化和循环优化三种。

3. 局部优化是在基本块范围内的一种优化。基本块内的优化为删除多余运算，删除无用赋值。构造基本块DAG的过程就是对该基本块进行优化的过程。

4. 编译程序进行数据流分析的目的是为了进行全局优化。

5. 循环优化主要采用的三项优化措施是代码外提，削减运算强度，删除归纳变量。强度削弱是指把程序中执行时间较长的运算替换为执行时间较短的运算。削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性。把循环中的乘法运算用递归加法运算来替换就是一种强度削弱。

6. 中间代码生成和代码优化部分不是每个编译程序都必需的。

e.g. 如下的基本块：

• A:=B*C
• D:=B/C
• E:=A+D
• F:=E*2
• G:=B*C
• H:=G*G
• F:=H*G
• L:=F
• M:=L

试利用DAG对其进行优化，并就以下两种情况分别写出优化后的四元式序列：（考）

（a）假设只有G、L、M在该基本块后面还要被引用；

（b）假设只有F在该基本块后面还要被引用。

（a）G:=B*C, H:=G*G, L:=H*G, M:=L

（b）G:=B*C, H:=G*G, F:=H*G

 

三、其他

1. 在一个基本块中的一个名字，所谓在程序中的某个给定点是活跃的，是指如果在程序中（包括在本基本块在其他基本块中）它的值在该点以后被引用。

2. 进行代码优化时不应着重考虑循环的代码优化。

3. 目标代码生成时不应考虑如何充分利用计算机的寄存器的问题。

 

参考博客：

【1】编译概述与引论

【2】语言处理程序

【3】自然语言处理——3.3 下推自动机与CFG（上下文无关文法）

【4】关于强制式（命令式）语言和声明式语言的区别

【5】第三章 文法和形式语言基础

【6】计算机科学概论

【7】子程序环境：嵌套子程序

【8】编译原理课程总结--第三章：词法分析

【9】语法分析：自上而下分析

【10】编译原理 语法树 句柄 简单短语 短语

【11】四元式_百度百科

【12】编译原理类型检查

【13】语法分析