编译器的语法分析

‘壹’ 编译原理

编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。 编译原理是计算机专业设置的一门重要的专业课程。编译原理课程是计算机相关专业学生的必修课程和高等学校培养计算机专业人才的基础及核心课程，同时也是计算机专业课程中最难及最挑战学习能力的课程之一。编译原理课程内容主要是原理性质，高度抽象[1]。

中文名
编译原理[1]
外文名
Compilers: Principles, Techniques, and Tools[1]
领域
计算机专业的一门重要专业课[1]
快速
导航
编译器

编译原理课程

编译技术的发展

编译的基本流程

编译过程概述
基本概念
编译原理即是对高级程序语言进行翻译的一门科学技术, 我们都知道计算机程序由程序语言编写而成, 在早期计算机程序语言发展较为缓慢, 因为计算机存储的数据和执行的程序都是由0、1代码组合而成的, 那么在早期程序员编写计算机程序时必须十分了解计算机的底层指令代码通过将这些微程序指令组合排列从而完成一个特定功能的程序, 这就对程序员的要求非常高了。人们一直在研究如何如何高效的开发计算机程序, 使编程的门槛降低。[2]
编译器
C语言编译器是一种现代化的设备, 其需要借助计算机编译程序, C语言编译器的设计是一项专业性比较强的工作, 设计人员需要考虑计算机程序繁琐的设计流程, 还要考虑计算机用户的需求。计算机的种类在不断增加, 所以, 在对C语言编译器进行设计时, 一定要增加其适用性。C语言具有较强的处理能力, 其属于结构化语言, 而且在计算机系统维护中应用比较多, C语言具有高效率的优点, 在其不同类型的计算机中应用比较多。[3]
C语言编译器前端设计
编译过程一般是在计算机系统中实现的, 是将源代码转化为计算机通用语言的过程。编译器中包含入口点的地址、名称以及机器代码。编译器是计算机程序中应用比较多的工具, 在对编译器进行前端设计时, 一定要充分考虑影响因素, 还要对词法、语法、语义进行分析。[3]
1 词法分析[3]
词法分析是编译器前端设计的基础阶段, 在这一阶段, 编译器会根据设定的语法规则, 对源程序进行标记, 在标记的过程中, 每一处记号都代表着一类单词, 在做记号的过程中, 主要有标识符、关键字、特殊符号等类型, 编译器中包含词法分析器、输入源程序、输出识别记号符, 利用这些功能可以将字号转化为熟悉的单词。[3]
2 语法分析[3]
语法分析是指利用设定的语法规则, 对记号中的结构进行标识, 这包括句子、短语等方式, 在标识的过程中, 可以形成特殊的结构语法树。语法分析对编译器功能的发挥有着重要影响, 在设计的过程中, 一定要保证标识的准确性。[3]
3 语义分析[3]
语义分析也需要借助语法规则, 在对语法单元的静态语义进行检查时, 要保证语法规则设定的准确性。在对词法或者语法进行转化时, 一定要保证语法结构设置的合法性。在对语法、词法进行检查时, 语法结构设定不合理, 则会出现编译错误的问题。前端设计对精确性要求比较好, 设计人员能够要做好校对工作, 这会影响到编译的准确性, 如果前端设计存在失误, 则会影响C语言编译的效果。[3]

‘贰’ 3-8译码器的工作原理

3-8译码器的功能就是把输入的3位2进制数翻译成10进制的输出。

简单介绍：

3-8译码器的输入是3个脚,输出是8个脚。用高低电平来表示输入和输出。

1、输入是二进制。3只脚也就是3位二进制数。输入可以3位二进制数。3位二进制最大是111 也就是8。

2、输出是8个脚，表示10进制。是根据输入的二进制数来输出。如果输入是101 那么就是第5只脚高电平，表示二进制数是5。

3、3-8线译码器是一种全译码器（二进制译码器）。全译码器的输入是3位二进制代码，3位二进制代码共有8种组合，故输出是与这8种组合一一对应的8个输出信号。

(2)编译器的语法分析扩展阅读：

译码器工作方法：

1、首先编译器进行语法分析，也就是要把那些字符串分离出来。

2、然后进行语义分析，就是把各个由语法分析分析出的语法单元的意义搞清楚。

3、最后生成的是目标文件，也称为obj文件。

4、再经过链接器的链接就可以生成最后的EXE文件了。

有些时候需要把多个文件产生的目标文件进行链接，产生最后的代码。这一过程称为交叉链接。

‘叁’ 编译器笔记10-语法分析-FIRST集和FOLLOW集的计算

FIRST(X)：可以从X推导出的所有串首终结符，如果 X=>*ε，那么ε∈FIRST(X)。

不断应用下列规则，直到没有新的终结符或ε可以被加入到任何FIRST集合中为止

FOLLOW(A)：可能在某个句型中紧跟在A后边的终结符a的集合

如果A是某个句型的的最右符号，则将结束符“$”添加到FOLLOW(A) 中。

不断应用下列规则，直到没有新的终结符可以被加入到任何FOLLOW

注意说明：

‘肆’ 编译器笔记14-语法分析-SLR分析

当在状态2时输入符号为 * 时候，可以采取移入操作也可以采取归约操作。那到底选用哪一个操作呢？归根结底还是一个如何识别句柄的问题。如果栈顶的T为句柄的话就使用归约操作，否则的话就不能使用归约操作。由此可见LR(0)的信息已经不能帮助我们确定是否进行归约。

事实上LR(0)分析在构造时，向前查看了零个符号，也就是没有向前查看符号，即没有考虑文法符号的上下环境。

上图例子中状态2在下一个符号是*时，如果把栈顶的T归约成E。由上图可知 * 不在FOLLOW(E)中，所以即便归约成E，E后也不可能跟 * ，所以不应该归约，T不是句柄。由此可见FOLLOW集可以帮助判断在哪些情况下不能进行归约，这也是SLR分析法的基本思想。

解决LR(0)文法的移入归约冲突，其实就是加强对文法的约束以避免冲突，其实分析方法中并没因此做出任何改变。

如果给定文法的SLR分析表中不存在有冲突的动作，那么该文法成为SLR文法。

由上图可知当状态2遇到等号时遇到了移入归约冲突。某些情况下仅利用FOLLOW集的信息去化解冲突是不够的。为了消解这种冲突需要使用更强大的 LR(1)分析法 。

‘伍’ 编译器的功能是什么

1、编译器就是将“一种语言（通常为高级语言）”翻译为“另一种语言（通常为低级语言）”的程序。一个现代编译器的主要工作流程：源代码 (source code) → 预处理器 (preprocessor) → 编译器 (compiler) → 目标代码 (object code) → 链接器(Linker) → 可执行程序 (executables)。
2、工作方法：
1）、首先编译器进行语法分析，也就是要把那些字符串分离出来。
2）、然后进行语义分析，就是把各个由语法分析分析出的语法单元的意义搞清楚。
3）、最后生成的是目标文件，也称为obj文件。
4）、再经过链接器的链接就可以生成最后的EXE文件了。
5）、有些时候需要把多个文件产生的目标文件进行链接，产生最后的代码。这一过程称为交叉链接。

‘陆’ 编译器的组成及各部分的功能及作用

1. 词法分析 词法分析器根据词法规则识别出源程序中的各个记号（token），每个记号代表一类单词（lexeme）。源程序中常见的记号可以归为几大类：关键字、标识符、字面量和特殊符号。词法分析器的输入是源程序，输出是识别的记号流。词法分析器的任务是把源文件的字符流转换成记号流。本质上它查看连续的字符然后把它们识别为“单词”。 2. 语法分析 语法分析器根据语法规则识别出记号流中的结构（短语、句子），并构造一棵能够正确反映该结构的语法树。 3. 语义分析 语义分析器根据语义规则对语法树中的语法单元进行静态语义检查，如果类型检查和转换等，其目的在于保证语法正确的结构在语义上也是合法的。 4. 中间代码生成 中间代码生成器根据语义分析器的输出生成中间代码。中间代码可以有若干种形式，它们的共同特征是与具体机器无关。最常用的一种中间代码是三地址码，它的一种实现方式是四元式。三地址码的优点是便于阅读、便于优化。 5. 中间代码优化 优化是编译器的一个重要组成部分，由于编译器将源程序翻译成中间代码的工作是机械的、按固定模式进行的，因此，生成的中间代码往往在时间和空间上有很大浪费。当需要生成高效目标代码时，就必须进行优化。 6. 目标代码生成 目标代码生成是编译器的最后一个阶段。在生成目标代码时要考虑以下几个问题：计算机的系统结构、指令系统、寄存器的分配以及内存的组织等。编译器生成的目标程序代码可以有多种形式：汇编语言、可重定位二进制代码、内存形式。 7 符号表管理 符号表的作用是记录源程序中符号的必要信息，并加以合理组织，从而在编译器的各个阶段能对它们进行快速、准确的查找和操作。符号表中的某些内容甚至要保留到程序的运行阶段。 8 出错处理用户编写的源程序中往往会有一些错误，可分为静态错误和动态错误两类。所谓动态错误，是指源程序中的逻辑错误，它们发生在程序运行的时候，也被称作动态语义错误，如变量取值为零时作为除数，数组元素引用时下标出界等。静态错误又可分为语法错误和静态语义错误。语法错误是指有关语言结构上的错误，如单词拼写错、表达式中缺少操作数、begin和end不匹配等。静态语义错误是指分析源程序时可以发现的语言意义上的错误，如加法的两个操作数中一个是整型变量名，而另一个是数组名等。

‘柒’ 把编译的过程划分为词法分析和语法分析的原因

将编译器的工作过程划分为词法分析，语义分析，中间代码生成，代码优化和目标代码生成时，语法分析阶段的输入是( 记号流 )若程序中的括号不配对，则会在( 语法分析 )阶段检查出错误。

‘捌’ 语法分析器可以发现语法错误

可以。语法分析器通常是作为编译器或解释器的组件出现的，它的作用是进行语法检查、并构建由输入的单词组成的数据结构。语法分析器可以发现语法错误，语法分析器使用一个独立的词法分析器从输入字符流中分离出一个个的“单词”，并将单词流作为其输。语法是语言学的一个分支，研究按确定用法来运用的"词类"、"词"的曲折变化或表示相互关系的其他手段以及词在句中的功能和关系。

‘玖’ 一般设计编译器要将词法分析和语法分析分开的原因是什么

1. 简单性——词法分析技术不如语法分析技术技术复杂，分开之后词法分析过程更简单。(这里还有一些意思差不多的话)

2. 效率——词法分析占用的时间是整个编译时间的一大部分，所以将它们分开有利于优化词法分析，而提高编译效率

3. 可移植性——词法分析通常平台相关，语法分析器可以是平台无关的。分开了对移植有利。

（引自《程序设计语言概念》(第9版) Sebesta着）

‘拾’ 编译器笔记13-语法分析-LR分析法概述

可以用LR分析法分析的文法可以称为LR分析法。LR文法（ Knuth ，1963）是最大的、可以构造出相应移入- 归约语法分析器的文法类。

LR(k)分析，需要向前查看k个输入符号的LR分析，k=0 和 k=1 这两种情况具有实践意义，当省略(k)时，表示k=1。而在LR(k)这样的名称中，k代表的是分析时所需前瞻符号（lookahead symbol）的数量，也就是除了当前处理到的输入符号之外，还得再向右引用几个符号之意；省略 （k）时即视为LR(1)，而非LR(0)。

作为对比这里列出LL(1)文法的含义：

问：自底向上分析的关键问题是什么？
答：如何正确地识别句柄，句柄是逐步形成的，用“状态”表示句柄识别的进展程度。例如在 自底向上分析概述 中所提及到句柄识别错误的例子，通过状态跟下一个输入符号就可以判断出应该做出哪一个动作，而状态相当于一种记忆功能记录当前句柄识别到什么程度。

与移入分析器不同的是LR分析器多了一个与符号栈平行的状态栈。

之后的分析过程与上图类似，直至到如下状态，分析成功。可见分析时进行什么动作是由栈状态栈栈顶的状态和下一个输入符号决定。

输入：串w和LR语法分析表，该表描述了文法G的ACTION函数和GOTO函数。
输出：如果w在L(G)中，则输出w的自底向上语法分析过程中的归约步骤；否则给出一个错误指示。
方法：初始时，语法分析器栈中的内容为初始状态s0 ，输入缓冲区中的内容为w$。然后，语法分析器执行下面的程序：

先了解LR(0)项目和增广文法这两个概念

右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目（简称为项目）：A → α1·α2

文法开始符号S表示的是语言中的最大成分。如下图当b出现时可以将它移入到分析栈中。b移进栈后我们期待归约出B。当归约出B时我们还期待再归约一个B。

如果G是一个以S为开始符号的文法，则G的增广文法G'就是在G中加上新开始符号S'和产生式S'→S而得到的文法

引入这个新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边，从而使得分析器只有一个接受状态。

项目可以分为以下几类：

上图中S'对应的第一个项目称为初始项目，而S'对应的最后一个项目称之为接收项目在此状态下文法的开始符号已经被归约出来，因此可以接收了故称为接收项目。红色方框中的项目则被称为归约项目。

项目集闭包(Closure of Item Sets)

可以把等价的项目组成一个项目集(I)，称为项目集闭包，每个项目集闭包对应着自动机的一个状态。

先了解CLOSURE和GOTO这两个函数

项目集I的闭包的数学定义：

返回项目集I对应于文法符号X的后继项目集闭包

规范LR(0)项集族(Canonical LR(0) Collection)

说明： 该自动机的初始状态就是文法的初始项目的项目集闭包，其终止状态集合只有一个状态就是文法的接收项目的项目集闭包。

如果LR(0)分析表中没有语法分析动作冲突，那么给定的文法就称为LR(0)。不是所有CFG都能用LR(0)方法进行分析，也就是说，CFG不总是LR(0)文法。

为了解决移进/归约冲突和归约/归约冲突需要使用到 SLR分析法 和 LR(1)分析法 。

问: 为什么没有移进/移进冲突？
答: 首先只有在移进状态和待约状态下的项目才会有使用到移进操作。在0状态时所有项目都是移进状态根据LL文法显然不会产生移进/移进操作，因为每个产生式左部的SELECT集是没有交集的。而在其他具有待约状态项目的状态中，所有集合都是等价的。假若在某状态下输入终结符y时发生移进/移进冲突，即存在两个这样的项目A0→α0·yβ0，A1→α1·yβ1，但显然这两个项目是不等价的显然与同一状态下所有项目等价相矛盾，因此这种移进/移进冲突是不存在的。假若在某状态下输入非终结符X时发生移进/移进冲突，即存在两个这样的项目A0→α0·Xβ0，A1→α1·Xβ1，而A0与A1在同一状态下是等价的则两项目要么是A0→α0·Xβ0与X→.Xβ1(原项目A1变为X，α1变为ε)要么是A1→α1·Xβ1与X→.Xβ0(原项目A0变为X，α0变为ε)。显然X→Xβ0|Xβ1（左递归）是不符合LL文法的因此这种情况也是不可能出现。

综上移进/移进冲突在LR分析下是不存在的。