发布时间 : 星期三 文章编译原理 - 复习重难点更新完毕开始阅读487eb1c128ea81c759f5780b
from成都信息工程大学软件工程学院
第一章
从本质上来说，程序设计语言是按一定规则排列的符号集合，而编译程序就是把这些符号集合变成机器指令的转换器，编译程序又称为编译器。
程序设计语言【高级语言，低级语言（机器语言和汇编语言）】
编译过程：词法分析，语法分析，中间代码生成，优化，目标代码产生。
三元式定义为如下形式：（op, a1, a2)
其中op为操作码或运算符，a1和a2为操作数或运算分量。
编译 : 将高级语言程序翻译成另一种语言的等价程序。 解释：翻译一句执行一句，边翻译边执行，直到程序结束。
与编译的区别：不生成等价的目标代码程序。 优点：解释方式便于程序的调试。（编译方式只需翻译一次，且目标程序的执行速度快）
（1）词法分析
主要任务：从左到右扫描源程序，逐一读入构成源程序的字符流，识别出 其中的一个个单词，识别出的单词称单词符号，也简称符号。 单词是高级语言程序中有实际意义的最小语法单位。 （2）语法分析 任务“组词成句”，根据单词分析出组成源程序的各类语法单位， 并指出其中的语法错误。
语法单位——由源程序的单词构成（如表达式、语句、……乃至整个程序。） 语法单位的构成规则——语法规则。
一个语言的词法规则和语法规则定义了一个程序的形式结构。 语法单位的表示——语法树 （3）语义分析和中间代码生成
任务：分析出语法单位具体的动作意义，进行初步翻译，生成与源程序等价的中间代码程序。
from成都信息工程大学软件工程学院
语义: 定义一个程序所表示的意义,用语义规则描述。
中间代码：指令应结构简单、含义明确，易于实现源程序——中间代码 ——目标代码三者之间的转换。
中间代码常用形式： 逆波兰式、三元式、四元式等。 四元式： （运算符，对象1，对象2，结果）
例：z=x+a%3*y
(1)（ % a 3 t1 ） （2） （ * t1 y t2 ） (3) （3） （ + x t2 t3 ）（4） （ = t3 _ z ） （4） 代码优化
任务： 对中间代码进行等价的加工变换，以便生成更有效更节省时间和空间的目标代码。
例：z=x+a%3*y 的四元式序列： (1)% a 3 t1 ） （2） （ * t1 y t2 ）
(3)（ + x t2 z ）
（5）目标代码生成 任务：将中间代码程序变换成目标代码程序。 2．按“遍”组合方式 “遍”：对源程序或等价的中间语言程序从头到尾扫描，完成规定的 任务，并生成新的中间结果或目标程序，称一“遍”。 编译程序的构造与三个方面有关 :源语言 ，目标语言，编译方法。
第二章 形式语言与自动机理论基础
主要内容：语言和文法、有限自动机、正则表达式。 语言：符号串的集合。
元素—— 符号串——该语言的一个句子。 字母表——符号串中符号的来源。 【例2-1】 Σ={a，b，c，……，z}，x =“laugh”，则 |x|=5 Σ={I，you，he，am，is，are，a，student}， y=“I am a student”，空格不计算长度，则 |y|=4。 空符号串：无任何符号的串，简称空串，用ε表示，|ε|=0 【例2-4】 若 U = { a，b }， V = { c，d }
则 UV = { ac，ad，bc，bd }
闭包： 若指定字母表Σ，则Σ*表示Σ上的所有有穷长的串的集合。
Σ* =Σ0∪Σ1∪Σ2∪……∪Σn∪…… Σ* 称为集合Σ的闭包。
Σ+ =Σ1∪Σ2∪……∪Σn∪…… Σ+ 称为集合Σ的正闭包。
成立的等式：Σ* =Σ0∪Σ+ ， Σ+ =ΣΣ* =Σ*Σ
若符号串 x 是Σ*的元素,则表示为 x∈Σ* ,否则 x Σ* 。 【例2-5】 Σ={0,1} Σ*={ε,0,1,00,10,11,000,001,100,………} 文法的形式定义：
1：终结符用VT 表示、2：非终结符用VN 表示、3：规则 α→β、 4：文法 定义：一个文法是一个四元组G（VN ，VT ，S ， P） VN ： 非终结符集（非空）；VT ： 终结符集（非VN∩VT＝? ；
from成都信息工程大学软件工程学院
S：识别符号或开始符号，S∈VN，且至少在一条规则中作为左部出现； P ： 规则（产生式）的集合。用V表示 VN∪VT ，称G的字母表或词汇表。 【例2-7】 有一文法G（VN ，VT ，S ， P）
其中: VN = { S } VT = { 0，1 } 开始符号是 S P = { S→0S1， S→01 }
{t } m2. 扩展的BNF n 表示法
（1）“{ }” 表示符号串t的多次重复，n为重复的最小次数，m为重复的 最大次数，省略n、m表示t可以重复0到任意多次。 【例2-9】文法规则 S→0S1|01
简化为 S→0(S1|1) 或 S→(0S|0)1 或 S→0(S| ε)1 （3）“[ ]”：[t]表示符号串t可选（即可有可无）。 【例2-11】C语言条件语句的语法图：
文法相关概念：
定义1：如α→β是文法G（VN ，VT ，S ， P）的一条规则， γ、δ∈V * ， 若有符号串 v、w 满足 v =γαδ， w =γβδ 则称v（应用规则α→β）直接产生w ，或称 w 是 v 的直接推导，反过来称 w 直接归约 到 v ，记作 v ? w 。 【例2-13】 对文法G： S→0S1 S →01 有直接推导序列： S ? 0S1? 00S11?000111
定义2：如果存在直接推导序列：v = w0 ? w1? w2 ?……? wn = w 则称v 推导（产生）出w，推导长度为n ，反过来称w 归约到v，记作 v? w。 如果有 v ? w ，或 v = w ，则记作 v ? w。
【例2-14】 S ? 0S1 ? 00S11 ? 000111 S 推导出 “ 000111” ， 推导长度3 “ 000111” 归约到 S， 表示成 S ? 000111
2．句型和句子
定义： 文法G（VN，VT，S ，P），若符号串x可由开始符号S推导出（S ? x），则称 x 是 G 的一个句型，若x仅由终结符组成，则称 x 为G 的一个句子。
3．形式语言
定义：文法描述的语言是该文法的所有句子的集合，记作 L(G)。集合形式表示：
L(G) = { α | S?α ∧ α∈VT* }
【例2-16】文法G： S →0S1 S →01 描述的语言：L(G)= { 0n1n | n≥1 }
4．文法的等价性 定义：若有文法G1、G2，它们描述的语言相同，即 L( G1 ) = L( G2 ) 则称两文法 G1 和 G2 等价。
from成都信息工程大学软件工程学院
【例2-17】有文法 G[A]： A→0R A→01 R→A1 描述的语言 L(G) = { 0n1n
| n≥1 }。定义：若有文法G1、G2，它们描述的语言相同，即 L( G1 ) = L( G2 ) 则称两文法 G1 和 G2 等价。 5. 递归规则和递归文法
递归规则：形如P→α1Pα2的规则称递归规则。 若α1=ε则称左递归规则; 若α2=ε则称右递归规则。
递归文法：含有递归规则的文法称递归文法。
P?α1Pα2的递归称间接递归,含间接递归的文法也是递归文法。
文法分类：
1、0型文法（无限制文法或短语文法）定义2-7 设G=(VN，VT，P，S)，如果它的每个产生式α→β满足α、β∈(VN∪VT)*，且α至少含有一个非终结符，则G是一个0型文法。
结论：0型文法的能力相当于图灵机。 任何0型语言都是递归可枚举的，反之，递归可枚举集也必定是一个0型语言。
2、1型文法 （上下文有关文法）
定义2-8 设G=(VN，VT，P，S)，如果它的每个产生式α→β满足 |β|≥|α|（仅S→ε除外），则G是一个1型文法。 另一种描述：文法的产生式形如 α1Aα2 → α1βα2 其中A∈VN，α、β∈(VN∪VT)*且β≠ε。
【例2-18】1型文法G[S]：
S → xSYZ | xYZ yZ→yz xY→xy ZY→YZ yY→yy zZ→zz
3、2型文法 （上下文无关文法）
定义2-9 设G=(VN，VT，P，S)，如果它的每个产生式α→β中的α是一个非终结符，则G是一个2型文法或上下文无关文法。
【例2-19】 2型文法G[S]：
S→E T→P | T﹡P F→i | (E) E→T | E＋T P→F | F↑P 4、3型文法 （正规文法或正则文法）
定义2-10 设G=(VN，VT，P，S)，如果它的每个产生式均形如A→aB 或 A→a 其中A、B∈VN，a∈VT。 【例2-20】 3型文法G[S] ：
S → aA A → aA A → a S → a A → dA A → d