编译原理结构图
㈠ 编译原理由正规式构造DFA
先画出NFA，如图：（我就是传说当中的灵魂画师）
这个DFA本身就已经是最简的了，无法再简化，最简化过程我就直接省了
㈡ 编译原理——LR分析表
自底向上的语法分析
LR分析表的结构如上，其分为两个部分 Action Goto
两个参数状态i，终结符号a（s(i)代表第i个状态，r(i)代表第i条表达式）
Goto[i,A]=j
文法
容易得知这个文法可以推出 0 1 00 01 等的字符串。因为它是 左递归 。不适用于 LL 文法分析，只能使用 LR 分析。
因为本题入口有两个—— S → L·L S → L ，所以需要构造额外的产生式 S'->S
2.1 第一次遍历
我们从 [S -> . L·L] 开始，构造这个状态的闭包，也就是加上所有能从这个产生式推出的表项。
首先，判断 . 后面是否为 非终结符号A 。如果是，那我们就得找所有由 A-> 推出的产生式，并将它们添加进入 闭包 里(也就是State包里)。循环做即可。
因此我们可以得到 State 0 有
下一步，就是我的 . 往下一位移动。对每个符号X后有个 . 的项，都可以从 State 0 过渡到其他状态。
由以上6条式子可以得知下一位符号可以是 S L B 0 1 。所以自然可以得到5个状态。
State 1 是由 State 0 通过 S 转移到这里的，所以我们找出所有 State 0 中在 S 前有 . 的项。
此状态作为结束状态 Accept ，不需要继续状态转移了。
State 2 是由 State 0 通过 L 转移到这里的，所以我们找出所有 State 0 中在 L 前有 . 的项。
S -> . L·L S -> . L L -> . LB
有3条式子，现在我们将 . 向后推一格，就得到 State 1 的项了。
但是 . 之后的符号分别是 · $ B ， B 为非终结符号，我们得包含 B -> 的项
State 3 是由 State 0 通过 B 转移到这里的，所以我们找出所有 State 0 中在 B 前有 . 的项。
因为 . 后没有其他符号了，因此这个状态不需要继续转移了。
State 4 是由 State 0 通过 0 转移到这里的，所以我们找出所有 State 0 中在 0 前有 . 的项。
因为 . 后没有其他符号了，因此这个状态不需要继续转移了。
很简单，同样的道理找 State 5
State 5 是由 State 0 通过 1 转移到这里的，所以我们找出所有 State 0 中在 1 前有 . 的项。
因为 . 后没有其他符号了，因此这个状态不需要继续转移了。
好的，现在我们第一次遍历完成。
2.2 第二次遍历
第二次遍历自然从 State 2 开始。
我们回到 State2 ，可以看出 . 之后的符号有 · B 0 1 。
State 6 是由 State 2 通过 · 转移到这里的，所以我们找出所有 State 2 中在 · 前有 . 的项。
S -> L. ·L 只有1条，我们往后移发现 L 又为非终结符号，参考 State 0 做的操作，我们得找出所有的式子。
共有5条式子，共同组成 State 6 ，由上面的式子可以看出我们还得继续下一次遍历。先不管着，我们进行下一次状态查找。
State 7 是由 State 2 通过 B 转移到这里的，所以我们找出所有 State 2 中在 B 前有 . 的项。
L -> L. B 也是只有1条，我们往后移发现没有非终结符号了，那就不需要再继续添加其他式子了。
这个状态也不需要继续进行转移了。
接下来很关键，因为我们通过 State2 的 . 后的符号找出了 State 6 State 7 ，接下来还差符号 0 1 ，那么是否像之前一样按例添加状态呢， 答案是不是的 ，因为我们发现通过 0 1 找到的闭包集分别是 B -> 0 B -> 1 ，这与我们的之前的 State 4 State 5 相同。所以我们得将其整合起来，相当于 State 2 通过 0 1 符号找到了 State 4 State 5 状态。
2.3 第三次遍历
回头看第二次遍历，可以看出只有 State 6 可以进行状态转移了。
那么就将 State 6 作为第三次遍历的源头，可以看出 . 之后的符号有 L B 0 1 。
State 8 是由 State 6 通过 L 转移到这里的，所以我们找出所有 State 6 在 L 前有 . 的项。
S -> L· .L L -> . LB 有两条式子，往后移发现有非终结符号 B ，所以经过整合可以得到
可以看出 . 的后面还有一个符号，所以这里我们还得再进行一次遍历。
接下来，又是遇到重复的包的情况，可以看出我们由 State 6 通过 B 0 1 得到的闭包分别是 L->B B->0 B->1 ，很明显，这分别对应于 State 3 State 4 State 5 。
第三次遍历也就结束了。
2.4 第四次遍历
回看第三次遍历，可以看出只有 State 8 可以进行状态转移，其 . 之后的符号分别是 B 0 1 。
诶，感觉很熟悉，就是上面几行刚说的情况，也就是说通过这三个符号找到的闭包是我们之前遇到的状态，分别是 State 3 State 4 State 5 。
做到这里，我们发现我们已经全部遍历完毕！
总共有8个状态，通过以上流程做成个图是什么样子的？来看看！
这么一看就很清晰明了了，我们就可以通过这个图做出我们的 LR分析表
其实就是我们之前呈现的表
在状态 I2 和 I8 中，既有 移入 项目，也有 规约 项目，存在 移入 - 规约的冲突 ，所以不是 LR(0) 文法，但是因为 FOLLOW(S) ∩ {0, 1} = ∅，所以可以用 FOLLOW 集解决冲突，所以该文法是 SLR(1) 文法。
上表我们发现还有 r1，r2，r3 等。这个其实就是代表状态停止转移时为 第几条表达式 ，r3代表第三条表达式 L -> LB 。
当我们构建了表之后，我们如何运用起来呢？
下面我们通过一个例子来说明
以上字符串是如何被SLR分析器识别的呢？
㈢ 编译原理
编译原理)：利用编译程序从源语言编写的源程序产生目标程序的过程； 用编译程序产生目标程序的动作。 编译就是把高级语言变成计算机可以识别的2进制语言，计算机只认识1和0，编译程序把人们熟悉的语言换成2进制的。
编译程序把一个源程序翻译成目标程序的工作过程分为五个阶段：词法分析；语法分析；语义检查和中间代码生成
(3)编译原理结构图扩展阅读：
编译程序的语法分析器以单词符号作为输入，分析单词符号串是否形成符合语法规则的语法单位，如表达式、赋值、循环等，最后看是否构成一个符合要求的程序，按该语言使用的语法规则分析检查每条语句是否有正确的逻辑结构，程序是最终的一个语法单位。
编译程序的语法规则可用上下文无关文法来刻画。语法分析的方法分为两种：自上而下分析法和自下而上分析法。自上而下就是从文法的开始符号出发，向下推导，推出句子。
而自下而上分析法采用的是移进归约法，基本思想是：用一个寄存符号的先进后出栈，把输入符号一个一个地移进栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分归约成该产生式的左邻符号。
㈣ C语言编译原理
编译共分为四个阶段：预处理阶段、编译阶段、汇编阶段、链接阶段。
1、预处理阶段：
主要工作是将头文件插入到所写的代码中，生成扩展名为“.i”的文件替换原来的扩展名为“.c”的文件，但是原来的文件仍然保留，只是执行过程中的实际文件发生了改变。（这里所说的替换并不是指原来的文件被删除）
2、汇编阶段：
插入汇编语言程序，将代码翻译成汇编语言。编译器首先要检查代码的规范性、是否有语法错误等，以确定代码的实际要做的工作，在检查无误后，编译器把代码翻译成汇编语言，同时将扩展名为“.i”的文件翻译成扩展名为“.s”的文件。
3、编译阶段：
将汇编语言翻译成机器语言指令，并将指令打包封存成可重定位目标程序的格式,将扩展名为“.s”的文件翻译成扩展名为“.o”的二进制文件。
4、链接阶段：
在示例代码中，改代码文件调用了标准库中printf函数。而printf函数的实际存储位置是一个单独编译的目标文件（编译的结果也是扩展名为“.o”的文件），所以此时主函数调用的时候，需要将该文件（即printf函数所在的编译文件）与hello world文件整合到一起，此时链接器就可以大显神通了，将两个文件合并后生成一个可执行目标文件。
㈤ 编译详细资料大全
编译(compilation , compile) 1、利用编译程式从源语言编写的源程式产生目标程式的过程。 2、用编译程式产生目标程式的动作。 编译就是把高级语言变成计算机可以识别的2进制语言，计算机只认识1和0，编译程式把人们熟悉的语言换成2进制的。 编译程式把一个源程式翻译成目标程式的工作过程分为五个阶段：词法分析；语法分析；语义检查和中间代码生成；代码最佳化；目标代码生成。主要是进行词法分析和语法分析，又称为源程式分析，分析过程中发现有语法错误，给出提示信息。
编译语言是一种以编译器来实现的程式语言。它不像直译语言一样，由解释器将代码一句一句运行，而是以编译器，先将代码编译为机器码，再加以运行。理论上，任何程式语言都可以是编译式，或直译式的。它们之间的区别，仅与程式的套用有关。
基本介绍
- 中文名 ：编译
- 外文名 ：compilation
- 学科 ：计算机科学
- 用途 ：编译程式
- 解释 ：编写的源程式产生目标程式的过程
- 领域 ：编译原理
编译程式
将某一种程式设计语言写的程式翻译成等价的另一种语言的程式的程式, 称之为编译程式(compiler) .词法分析
词法分析的任务是对由字符组成的单词进行处理，从左至右逐个字符地对源程式进行扫描，产生一个个的单词符号，把作为字符串的源程式改造成为单词符号串的中间程式。执行词法分析的程式称为词法分析程式或扫描器。 源程式中的单词符号经扫描器分析，一般产生二元式：单词种别；单词自身的值。单词种别通常用整数编码，如果一个种别只含一个单词符号，那么对这个单词符号，种别编码就完全代表它自身的值了。若一个种别含有许多个单词符号，那么，对于它的每个单词符号，除了给出种别编码以外，还应给出自身的值。 词法分析器一般来说有两种方法构造：手工构造和自动生成。手工构造可使用状态图进行工作，自动生成使用确定的有限自动机来实现。语法分析
编译程式的语法分析器以单词符号作为输入，分析单词符号串是否形成符合语法规则的语法单位，如表达式、赋值、循环等，最后看是否构成一个符合要求的程式，按该语言使用的语法规则分析检查每条语句是否有正确的逻辑结构，程式是最终的一个语法单位。编译程式的语法规则可用上下文无关文法来刻画。 语法分析的方法分为两种：自上而下分析法和自下而上分析法。自上而下就是从文法的开始符号出发，向下推导，推出句子。而自下而上分析法采用的是移进归约法，基本思想是：用一个暂存符号的先进后出栈，把输入符号一个一个地移进栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分归约成该产生式的左邻符号。中间代码
中间代码是源程式的一种内部表示，或称中间语言。中间代码的作用是可使编译程式的结构在逻辑上更为简单明确，特别是可使目标代码的最佳化比较容易实现中间代码，即为中间语言程式，中间语言的复杂性介于源程式语言和机器语言之间。中间语言有多种形式，常见的有逆波兰记号、四元式、三元式和树。代码最佳化
代码最佳化是指对程式进行多种等价变换，使得从变换后的程式出发，能生成更有效的目标代码。所谓等价，是指不改变程式的运行结果。所谓有效，主要指目标代码运行时间较短，以及占用的存储空间较小。这种变换称为最佳化。 有两类最佳化：一类是对语法分析后的中间代码进行最佳化，它不依赖于具体的计算机；另一类是在生成目标代码时进行的，它在很大程度上依赖于具体的计算机。对于前一类最佳化，根据它所涉及的程式范围可分为局部最佳化、循环最佳化和全局最佳化三个不同的级别。目标代码
目标代码生成是编译的最后一个阶段。目标代码生成器把语法分析后或最佳化后的中间代码变换成目标代码。目标代码有三种形式： ① 可以立即执行的机器语言代码，所有地址都重定位； ② 待装配的机器语言模组，当需要执行时，由连线装入程式把它们和某些运行程式连线起来，转换成能执行的机器语言代码； ③ 汇编语言代码，须经过汇编程式汇编后，成为可执行的机器语言代码。 目标代码生成阶段应考虑直接影响到目标代码速度的三个问题：一是如何生成较短的目标代码；二是如何充分利用计算机中的暂存器，减少目标代码访问存储单元的次数；三是如何充分利用计算机指令系统的特点，以提高目标代码的质量。表格管理
编译过程中源程式的各种信息被保留在种种不同的表格，编译各阶段的工作都涉及到构造、查找、或更新有关的表格。 编译程式的公共辅助部分。对源程式中的各种量进行管理，登记在相应的表格。编译程式处理时通过查表得到所需的信息。出错处理
如果编译过程中发现源程式有错误，编译程式应报告错误的性质和错误的发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程式的其余部分能继续被编译下去，有些编译程式还能自动纠正错误，这些工作由错误处理程式完成。 需要注意的是，一般上编译器只做语法检查和最简单的语义检查，而不检查程式的逻辑。
㈥ 编译原理笔记17：自下而上语法分析（4）LR(0)、SLR(1) 分析表的构造
（移进项目就是指圆点右边是终结符的项目，规约项目指的就是圆点在右部最右端的项目）
LR(0) 文法可以直接通过识别活前缀的 DFA 来构造 LR 分析表
假定 C = {I 0 , I 1 , ... , I n } （aka. LR(0) 项目规范族、DFA 状态集）
首先为文法产生式进行编号，拓广文法的产生式要标记为 0（这里就是后面分析表中 rj 的产生式编号 j 的由来）
然后令每个项目集 I k 的下标 k 作为分析器的状态（行首），包含 S' → .S 的集合下标为分析器的初态（也就是 DFA 的初态，一般都是 0 ）。
下面用一个例子来说明 ACTION、GOTO 子表的构造：
SLR(1) 为解决冲突提出了一个简单的方法：通过识别活前缀的 DFA 和【简单向前看一个终结符】构造 SLR(1) 分析表。
如果我们的识别活前缀的 DFA 中存在移进-规约冲突、规约-规约冲突，都可以尝试使用这个方法来解决冲突。（这里说【尝试】，当然是因为 SLR 也只能解决一部分问题，并不是万能的灵丹妙药。。）
这里，我们拿前面那个 LR(0) 解决不了的文法来举例
该文法不是 LR(0) 文法，但是是 SLR(1) 文法。
观察上图 DFA 中的状态2，想象当我们的自动机正处于这个状态：次栈顶已经规约为 T 了，栈顶也是当前的状态 2 ，而当前剩余输入为 *。
如果这个自动机不会【往前多看一步】的话，那么对处于这个状态的自动机来说，看起来状态 2 中的移进项目和规约项目都是可选的。这就是移进-规约冲突。
想要解决这个冲突，就轮到【往前多看一步】上场了——把当前剩余输入考虑进来，辅助进行项目的选择：
对其他的冲突也使用同样的方法进行判断。
这种冲突性动作的解决办法叫做 SLR(1) 解决办法
准备工作部分，与 LR(0) 分析表的构造差不多：同样使用每个项目集的状态编号作为分析器的状态编号，也就同样用作行下标；同样使用拓广文法产生式作为 0 号产生式。
填表也和 LR(0) 类似，唯一的不同体现在对规约项的处理方法上：如果当前状态有项目 A → α.aβ 和 A → α. ，而次栈顶此时是 α 且读写头读到的是 a，那么当且仅当 a∈FOLLOW(A) 时，我们才会用 A → α 对 α 进行规约。
如果构造出来的表的每个入口都不含多重定义（也就是如上图中表格那样的，每个格子里面最多只有一个动作），那么该表就是该文法的 SLR(1) 表，这个文法就是 SLR(1) 文法。使用 SLR(1) 表的分析器叫做一个 SLR(1) 分析器。
任意的二义文法都不能构造出 SLR(1) 分析表
例：悬空 else
例：
这里的 L 可以理解为左值，R 可以理解为右值
经过计算可以确定其 DFA 如下图所示。
在 状态4 中，由于 "=" 同时存在于 FOLLOW(L) 与 FOLLOW(R) 中，因此该状态内存在移进-规约冲突，故该文法不是 SLR(1) 文法。
这样的非二义文法可以通过增加向前看终结符的个数来解决冲突（比如LL(2)、LR(2)）但这会让问题更加复杂，故一般不采用。而二义文法无论向前看多少个终结符都无法解决二义性。
㈦ 编译原理笔记9：语法分析树、语法树、二义性的消除
语法分析树和语法树不是一种东西 。习惯上，我们把前者叫做“具体语法树”，其能够体现推导的过程；后者叫做“抽象语法树”，其不体现过程，只关心最后的结果。
语法分析树是语言推导过程的图形化表示方法。这种表示方法反映了语言的实质以及语言的推导过程。
定义：对于 CFG G 的句型，分析树被定义为具有下述性质的一棵树：
推导，有最左推导和最右推导，这两种推导方式在推导过程中的分析树可能不同，但因最终得到的句子是相同的，所以最终的分析树是一样的。
分析树能反映句型的推导过程，也能反映句型的结构。然而实际上，我们往往不关心推导的过程，而只关心推导的结果。因此，我们要对 分析树 进行改造，得到 语法树 。语法树中全是终结符，没有非终结符。而且语法树中没有括号
定义：
说白了，语法树这玩意，就一句话： 叶子全是操作数，内部全是操作符 ，树里没有非终结符也不能有括号。
语法树要表达的东西，是操作符（运算）作用于操作数（运算对象）
举俩例子吧：
【例】： -(id+id) 的语法树：
【例】：-id+id 的语法树：
显然，我们从上面这两个语法树中，直接就能观察出来它们的运算顺序。
【例】：句型 if C then s1 else s2
二义性问题：一个句子可能对应多于一棵语法树。
【例】： 设文法 G： E → E+E | E*E | (E) | -E | id
则，句子 id+id*id、id+id+id 可能的分析树有：
在该例中，虽然 id+id+id 的 “+” 的结合性无论左右都不会影响结果。但万一，万一“+”的含义变成了“减法”，那么左结合和右结合就会引起很大的问题了。
我们在这里讲的“二义性”的“义”并非语义——我们现在在学习的内容是“语法分析器”，尚未到需要研究语言背后含义的阶段。
我们现在讲的“二义性”指的是一个句子对应多种分析树。
二义性的体现，是文法对同一句子有不止一棵分析树。这种问题由【句子产生过程中的某些推导有多于一种选择】引起。悬空 else 问题就可以很好地体现这种【超过一种选择】带来的二义性问题，示例如下。
看下面这么个例子。。
（其实，我感觉这个其实比较像是“说话大喘气”带来的理解歧义问题。。。）上面的产生式中并没体现出来该咋算分一块，所以两种完全不同的句子结构都是合法的。
二义性问题是有救的，大概有以下这三种办法：
这些办法的核心，其实都是将优先级和结合性说明白。
核心：把优先级和结合性说明白
既然要说明白，那就不能让一个非终结符可以直接在当次推导中能推出会带来优先级和结合性歧义的东西。（对分析树的一个内部节点，不会有出现在其下面的分支是相同的非终结符的情况。如果有得选，那就有得歧义了。没得选才能确定地一路走到黑）
改写为非二义文法的二义文法大概有下面这几个特点：
改写的关键步骤：
【例】改写下面的二义文法为非二义文法。图右侧是要达成的优先级和结合性
改写的核心其实就两句话：
所以能够得到非终结符与运算的对应关系（因为不同的运算有不同的优先级，我们想要引入多个优先级就要引入多个新的非终结符。这样每个非终结符就可以负责一个优先级的运算符号，也就是说新的非终结符是与运算有关系的了。因此这里搞出来了“对应关系”四个字）如下：
优先级由低到高分别是 +、 、-，而距离开始符号越近，优先级越低。因此在这里的排序也可以+ -顺序。每个符号对应一层的非终结符。根据所需要的结合性，则可确定是左递归还是右递归，以确定新的产生式长什么样子
【例】：规定优先级和结合性，写出改写的非二义文法
我们已经掌握了一种叫做【改写】的工具，能让我们消除二义性。接下来我们就要用这个工具来尝试搞搞悬空 else 问题！
悬空 else 问题出现的原因是 then 数量多于 else，让 else 有多个可以结合的 then。在二义文法中，由于选哪两个 then、else 配对都可以，故会引起出现二义的情况。在这里，我们规定 else 右结合，即与左边最靠近的 then 结合。
为改写此文法，可以将 S 分为完全匹配（MS）和不完全匹配（UMS）两类。在 MS 中体现 then、else 个数相等即匹配且右结合；在UMS 中 then、else 不匹配，体现 else 右结合。
【例】：用改写后的文法写一个条件语句
经过检查，无法再根据文法写出其他分析树，故已经消除了二义性
虽然二义文法会导致二义性，但是其并非一无是处。其有两个显着的优点：
在 Yacc 中，我们可以直接指定优先级、结合性而无需自己重写文法。
left 表示左结合，right 表示右结合。越往下的算符优先级越高。
嗯就这么简单。。。
我们其实可以把语言本身定义成没有优先级和结合性的。。然后所有的优先、结合都交由括号进行控制，哪个先算就加括号。把一个过程的结束用明确的标志标记出来。
比如在 Ada 中：
在 Pascal 中，给表达式加括号：
㈧ 编译原理的数据结构
编译原理一直是计算机学习的必修课.
当然，由编译器的阶段使用的算法与支持这些阶段的数据结构之间的交互是非常强大的。编译器的编写者尽可能有效实施这些方法且不引起复杂性。理想的情况是：与程序大小成线性比例的时间内编译器，换言之就是，在0 （ n ）时间内，n是程序大小的度量（通常是字符数）。本节将讲述一些主要的数据结构，它们是其操作部分阶段所需要的，并用来在阶段中交流信息。 临时文件（temporary file）：计算机过去一直未能在编译器时将整个程序保留在存储器中。这一问题已经通过使用临时文件来保存翻译时中间步骤的结果或通过“匆忙地”编译（也就是只保留源程序早期部分的足够信息用以处理翻译）解决了。存储器的限制现在也只是一个小问题了，现在可以将整个编译单元放在存储器之中，特别是在可以分别编译的语言中时。但是偶尔还是会发现需要在某些运行步骤中生成中间文件。其中典型的是代码生成时需要反填（backpatch）地址。例如，当翻译如下的条件语句时 if x = 0 then ... else ... 在知道else部分代码的位置之前必须由文本跳到else部分：
CMP X,0 JNE NEXT ;;
location of NEXT not yet known < code for then-part > NEXT : < code for else-part >
通常，必须为NEXT的值留出一个空格，一旦知道该值后就会将该空格填上，利用临时文件可以很容易地做到这一点。
如果想利用上面的编译原理开发一套属于自己的编程语言，或者想在一个产品中嵌入编程语言，可以参考zengl开源网开发的zengl编程语言，该编程语言为国人使用C语言开发，里面包含两个部分，一个是编译器，一个是解释执行中间代码的虚拟机。编译器包含了词法扫描，语法分析，中间代码输出等，虚拟机则类似JAVA一样解释执行中间代码。作者将所有的版本都公布出来，好让读者可以由浅入深的做研究，并且为了证明该编程语言的实用性，还结合SDL游戏开发库开发了一款图形界面和命令行界面的21点扑克小游戏 。
zengl编程语言目前适用平台为windows和linux (最开始在Linux下使用gcc开发，后来移植到windows平台)
㈨ ！！编译原理DFA和NFA
DFA或NFA是对计算机程序的行为的抽象模型。你编写的程序其实就对应了一个自动机。简单举例来说，如果a,b可以取值0或1; 程序： if(a==1) b=1; 这个程序对应了一个自动机。
对应的自动机就有状态 (0,0), (0,1), (1,1), (1, 0)
比如你自动机的初始状态是 (1,0)即a=1,b=0时，运行程序的下一个状态就是(1,1)。
画图出来就是 这4个状态作为顶点，并且有下面几条边
(0,0) --> (0,0)（自环）, (1,0)-->(1,1), (1,1)-->(1,1)（自环）, (0,1)-->(0,1)自环
存在的意义就是一种理论模型，也可以认为是一种编程思想。 词法分析系也离不开 if else， 这一系列的if else和条件也就组成自动机。。。
最经典体现自动机思想的算法就是KMP算法，你肯定学过，字符串子串匹配的算法。 回忆这个算法的过程：算法第一步构造的next表（数据结构教材的说法）其实就是根据子串的内容构造了一个自动机！ 算法第二步将原串作为自动机输入，自动机的输出就是匹配到的子串位置或者无匹配。