绪论概念&文法与语言
以老师PPT为标准，借鉴部分教材内容，AlvinZH学习笔记。
绪论基本概念
1. 低级语言：字位码、机器语言、汇编语言。与特定的机器有关，功效高，但使用复杂、繁琐、费时、易出错。
高级语言：Fortran、Pascal、C语言等。不依赖具体机器，移植性好，对用户要求低，易使用，易维护等。
2. 把高级程序设计语言翻译成汇编语言后机器语言的工作称为编译，完成翻译工作的软件系统称为编译程序或编译器。
3. 源程序：程序语言处理系统的输入程序，用汇编语言或高级语言编写的程序。编写输入程序的语言称为源语言。
程序语言处理系统的输出程序称为目标程序（目标代码），相应的语言称为目标语言。目标语言可以是机器语言或汇编语言，也可以是介于低级语言和高级语言之间的中间语言。
能对编译得到的中间语言进行解释执行的程序称为解释程序。常见中间语言：四元式、三元式、逆波兰表示。优点：便于做优化处理；便于编译程序的移植。
4. 通常将某种语言程序（源程序）变换为与之等价的语言程序的程序（目标程序）通称为翻译程序或变换程序；汇编程序、编译程序以及各种变换程序的总称。
源语言为汇编语言、目标语言为机器原因的翻译程序称为汇编程序，其翻译过程称为汇编。
5. 编译过程五个基本阶段：词法分析；语法分析；语义分析、生成中间代码；代码优化；生成目标程序。
编译程序的七个逻辑部分：语法分析程序；词法分析程序；语义分析、生成中间代码；代码优化；生成目标程序；符号表管理；错误处理。
6. 遍：对源程序或源程序的中间形式从头到尾扫描一遍，并作有关的加工处理，生成新的与源程序的中间形式或目标程序。一遍扫描的编译程序以语法分析程序为核心。分遍将编译程序前端和后端分开，为编译程序的移植创造条件；主要缺点是增加了不少的重复性工作。
7. 前端和后端
前端：通常将与源程序有关的编译部分称为前端。包括词法分析、语法分析、语义分析、中间代码生成、代码优化-------分析部分。特点：与源语言有关。
后端：与目标机有关的部分称为后端。目标程序生成（与目标机有关的优化）-------综合部分。特点：与目标机有关。
文法与语言
1. 符号串知识
- 符号串集合幂运算： \(A^0={ε}\), \(A^1=A\), \(A^2=AA\), ...
- 符号串集合闭包运算。正闭包： \(A^+=A^1∪A^2∪A^3∪...\)。闭包： \(A^*=A^0∪A^+\)。
2. 文法：文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为"文法"（或称为"语法"）。
文法定义四元组：\(G=(Vn，Vt，P，Z)\)。\(V_n\)为非终结符号集，\(V_t\)为终结符号集，二者统称字汇表（V)；P为产生式（规则）集合；Z为开始符号（识别符号）。
3. 推导：\(==>\)。一步或多步推导：\(=+=>\)。零步或多步推导：\(=*=>\)。规范推导：\(=|=>\)。
最右推导：若符号串中有两个以上的非终结符，先推右边的。最左推导类似定义。最右推导也称规范推导，由规范推导的句型称为规范句型。
规约是推导的逆过程。最左规约与最右推导互逆，最左规约也称规范规约。对句型中最左简单短语（句柄）进行的规约称为规范规约。
语法树中，语法成分在形式语言中又称为“非终结符”，单词符号在形式语言中又称为“终结符号”。
4. 语言形式定义：
- 句型：Z => x，且x ∈ V。直观理解，语法树从左至右的一个序列。
- 句子：Z =+> x，且x ∈ Vt*。直观理解，语法树从左至右终结符序列，是句型的一个特例。
- 语言：由文法G[Z]产生的所有句子的集合，记为L(G[Z])。
文法与语言的关系：多对一。
5. 递归规则：左递归、右递归、自嵌入递归。递归文法的优点：可用有穷条规则，定义无穷语言。
左递归文法不能用自顶向下的方法来进行语法分析，会造成死循环。
6. 句型的短语、简单短语和句柄
已知文法G[Z]，\(w::=xuy ∈V^+\) 为该文法的句型。
- 短语：\(Z =*> xUy\)，且U =+> u, 则u是句型w相对于非终结符U的短语。直观理解，短语是句型中的某个非终结符所能推出的符号串。
- 简单短语：Z =*> xUy，且U => u。
- 句柄：最左的简单短语。
利用句型对应的语法树，某子树的末端结点按自左向右顺序为句型中的符号串，该符号串为该句型的相对于该子树根的短语。
7. 二义性文法----不可判定
- 文法所定义的某个句子存在两棵不同的语法树。
- 文法中存在某个句子，它有两个不同的规范（最右）推导。
- 文法中存在某个句子，它有两个不同的规范（最左）规约，即在规约中某些规范句型的句柄不唯一。
8. 文法实用限制
- 有害规则：U => U。引起二义性。
- 多余规则：推导过程中始终用不到或者一旦使用无法推出任何终结符号串。
8. 文法的其他表示
- 扩充的BNF表示
- 语法图
9. 文法和语言分类：0型，1型，2型，3型。区别在于对产生式施加不同的限制。
- 0型：规则中存在 \(u::=v\)，其中u∈V+且至少包含一个Vn，v∈V*。短语结构文法，左部为至少包含一个Vn的符号串，右部为符号串（可为空）。由图灵机接受。
- 1型：规则中存在 \(xUy ::= xuy\)，其中U∈Vn，x、y、u∈V*。上下文敏感（上下文有关）文法，只有在上下文x...y中才可重写。由一种线性界限的图灵机接受。
- 2型：规则中存在 \(U ::= u\)，其中U∈Vn，u∈V*。上下文无关文法，与BNF表示等价。由下推自动机接受。
- 3型：规则中存在 \(U ::= t\) 或 \(U ::= Wt\)（左线性）【\(T::>tW\)（右线性）】 ，U、W∈Vn，t∈Vt。正则文法。由有穷自动机接受。（左线性和右线性不能同时出现）
- L0>L1>L2>L3，即4类文法从0型到3型是逐渐增加限制的。
四种文法类型的关系及判断方法
四种文法区别在于规定产生式的左边和右边的字符的组成规则不同。明确四种文法从0型到3型，其规则和约定越来越多，限制条件也越来越多，所以，我们判断时可以从最复杂的3型进行判断，3->2->1->0依次向下判断。
快速判断3型文法
- 左边必须只有一个字符，且必须是非终结符（∈Vn）。（与2型文法的第一点相同）
- 右边最多只能有两个字符，且当有两个字符时必须有一个为终结符而另一个为非终结符。当右边只有一个字符时，此字符必须为终结符。
- 左线性和右线性不能同时出现。对于所有右边有两个字符的产生式，终结符和非终结符的相对位置一定要固定，要么全为 非终结符+终结符，要么全为 终结符+非终结符。
3型文法实在2型文法的基础上满足：A→α|αB（右线性）或A→α|Bα（左线性）。
快速判断2型文法
- 左边必须有且仅有一个非终结符。
- 右边含有若干个终结符和非终结符（只要是有限的就行，没有个数限制）。 （与1型文法的第二点相同）
2型文法是在1型文法的基础上，再满足：每一个α→β中都有α是非终结符（条件1）。
快速判断1型文法
- 左边可以含有一个、两个或两个以上的字符，但其中必须至少有一个非终结符。
- 右边含有若干个终结符和非终结符（只要是有限的就行，没有个数限制）。
1型文法是在0型文法的基础上满足：每一个α→β,都有|β|>=|α|。有一特例：α→ε也满足1型文法。
快速判断0型文法
不用判断，只要能描述出来，都属于0型文法。
参考链接：http://www.360doc.com/content/17/0626/11/37475013_666625064.shtml
- 邵老师课堂PDF
- 《编译原理级编译程序构造》