编译原理

一、编译过程
编译程序完成从源程序到目标程序的翻译工作，是一个复杂的过程。而在大半个学期的学习下，我发现必须熟记编译过程，它能够让每个阶段的任务目的明确也有助于学习过程中更好地理解编译原理。

编译程序结构图.png

阶段：
词法分析：对源程序的字符串流进行扫描和分解，识别并输出一个个单词符号及其属性（token）
语法分析：把源程序的单词序列组成语法短语（表示成语法树）
语义分析：完成对某些语义的分析，主要包括声明和类型检查
中间代码生成：中间代码是不依赖于机器但是又便于生成依赖于机器的目标代码的一种结构简单、含义明确的记号系统
代码优化：对代码进行等价变换，使得结果相同但运行速度加快或者占用空间减小
目标代码生成

二、文法和语言
刚开始一直没搞懂文法和语言的作用，不明白这两个概念的引进对于编译过程有什么意义以及到后面引进语言后他们之间的关系，而这些都是后面程序编译的基础。

为什么引入文法
语言是由无穷的句子构成的，为表达无穷的句子引入有穷的规则（文法）。即文法是以有穷的集合刻画无穷的集合的一个工具。

先理清几个定义：

文法是以有穷的集合刻画无穷的集合的一个工具。
语言是由句子组成的集合，是由一组符号所构成的集合。

语言研究的三个方面：
    1. 语法 -- 表示构成语言句子的各个记号之间 的组合规律
    2. 语义 -- 表示各个记号的特定含义。(各个记号和记号所表示的对象之间的关系)
    3. 语用 --表示在各个记号所出现的行为中， 它们的来源、使用和影响。

* 由文法G生成的语言记为L(G)，它是文法G的一切句子的集合:
    L(G)={x|S =>* x，其中S为文法的开 始符号，且x ∈VT*} *

三、词法分析
正则表达式
自动机

四、语法分析
通常把语法分析分为两大类：自上向下分析和自下而上分析。

语法分析有几个要点：语法树、二义性、句柄。具体操作碰上了LL和LR分析。LL分析法比较简单，主要思想就是可以向前读入一个(常用的LL(1))词素来决定选择哪个语法推导规则。这种分析法可以手动实现但限制较多，比如说要让两个并列的规则FIRST集不相交。LR语法比LL普适，但分析过程要建立状态转移手写略费事，一般用工具生成如yacc。LR中优化了状态数后有LALR分析法，是最常用的一种分析法。语法分析理论比较繁琐，工程中具体分析法也难实现，初学理解了基本的几种语法分析理论后，选择实现最简单的LL即可。

LR分析法的引进

解决冲突，能根据当前分析栈中的符号串和向右顺序查看输入串的k个符号就可唯一地确定句柄。比起自上而下的LL(k)分析方法和自底向上的优先分析方法对文法的限制少得多。

LR分析器结构

LR分析器工作过程示意图.png

LR分析器由三个部分组成：
(1) 总控程序，也可称驱动程序。对所有的LR分析器总控程序都是相同的。
(2) 分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示
(3) 分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。

分析过程

1、ACTION表规定了栈顶状态为S时遇到输入符号a应执行的动作：
动作主要有四种：移进、归约、接受、报错。
2、DOTO表是转向表：
GOTO[S，X]：若XVT，表示在当前状态下，读入a应转向什么状态；若XVN，表示当前栈顶句柄归约成X后，应转向什么状态。

LR0分析过程.jpeg

分析器的动作就是由栈顶状态和当前输入符号所决定。

LR分析表

LR分析器的核心就在LR分析表。LR分析表的构建是由已构造出的LR(0)项目集规范族来进行构造的。
1、LR(0)分析表构造基本概念
活前缀：在规范归约的句型中，不含有句柄以后任何符号的前缀称为活前缀。
归态活前缀：活前缀的尾部正好是句柄之尾，这时可以进行归约。归约之后又会成为另一句型的活前缀。
非归态活前缀：句柄尚未形成，需要继续移进若干符号之后才能形成句柄。
2、LR分析表的生成

• LR(0)项目：在文法G中每个产生式的右部适当位置添加一个圆点构成项目。
• 构造识别活前缀的NFA：把文法的所有产生式的项目都列出，并使每个项目都作为NFA的一个状态。
  根据圆点所在的位置和圆点后是终结符还是非终结符把项目分为：移进项目、待约项目、归约项目、接受项目。
• LR(0)项目集规范族的构造：构成识别一个文法活前缀的DFA项目集的全体称为这个文法的LR(0)项目集规范族。
• LR(0)分析表的构造：利用DFA的项目集和状态转换函数构造它的LR(0)分析表.

概括来说，LR分析表的构建就是由已构造出的LR(0)项目集规范族来进行构造的。
好的，听上去很复杂（事实上，刚看书时简直一头雾水0.0），那么，一步步弄清楚。
首先，项目集：项目集是项目的集合，那么，项目是什么，前面提到过这个概念。在代码里，可以简单地理解成“用.分割“（分割产生的项目在真正的语法分析时对应不同的操作，比如规约还是移位）。
后面重点是项目集规范族的构造。

编译原理学了一个学期感觉自己还是什么都不会，或许是太菜了吧（其实就是没写代码！！！！！！）总之，over～