资源描述：
《编译原理-复习重难点.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、from成都信息工程大学软件工程学院第一章从本质上来说，程序设计语言是按一定规则排列的符号集合，而编译程序就是把这些符号集合变成机器指令的转换器，编译程序又称为编译器。程序设计语言【高级语言，低级语言（机器语言和汇编语言）】编译过程：词法分析，语法分析，中间代码生成，优化，目标代码产生。三元式定义为如下形式：（op,a1,a2)其中op为操作码或运算符，a1和a2为操作数或运算分量。编译:将高级语言程序翻译成另一种语言的等价程序。解释：翻译一句执行一句，边翻译边执行，直到程序结束。与编译的区别：不生成等价的目标代码程序。优点：解释方式便于程序的调
2、试。（编译方式只需翻译一次，且目标程序的执行速度快）（1）词法分析主要任务：从左到右扫描源程序，逐一读入构成源程序的字符流，识别出其中的一个个单词，识别出的单词称单词符号，也简称符号。单词是高级语言程序中有实际意义的最小语法单位。（2）语法分析任务“组词成句”，根据单词分析出组成源程序的各类语法单位，并指出其中的语法错误。语法单位——由源程序的单词构成（如表达式、语句、……乃至整个程序。）语法单位的构成规则——语法规则。一个语言的词法规则和语法规则定义了一个程序的形式结构。语法单位的表示——语法树（3）语义分析和中间代码生成任务：分析出语法单位具
3、体的动作意义，进行初步翻译，生成与源程序等价的中间代码程序。from成都信息工程大学软件工程学院语义:定义一个程序所表示的意义,用语义规则描述。中间代码：指令应结构简单、含义明确，易于实现源程序——中间代码——目标代码三者之间的转换。中间代码常用形式：逆波兰式、三元式、四元式等。四元式：（运算符，对象1，对象2，结果）例：z=x+a%3*y(1)（%a3t1）（2）（*t1yt2）(3)（3）（+xt2t3）（4）（=t3_z）（1）代码优化任务：对中间代码进行等价的加工变换，以便生成更有效更节省时间和空间的目标代码。例：z=x+a%3*y的四元
4、式序列：(1)%a3t1）（2）（*t1yt2）(3)（+xt2z）（5）目标代码生成任务：将中间代码程序变换成目标代码程序。2．按“遍”组合方式“遍”：对源程序或等价的中间语言程序从头到尾扫描，完成规定的任务，并生成新的中间结果或目标程序，称一“遍”。编译程序的构造与三个方面有关:源语言，目标语言，编译方法。第二章形式语言与自动机理论基础主要内容：语言和文法、有限自动机、正则表达式。语言：符号串的集合。元素——符号串——该语言的一个句子。字母表——符号串中符号的来源。【例2-1】Σ={a，b，c，……，z}，x=“laugh”，则
5、x
6、=5Σ=
7、{I，you，he，am，is，are，a，student}，y=“Iamastudent”，空格不计算长度，则
8、y
9、=4。空符号串：无任何符号的串，简称空串，用ε表示，
10、ε
11、=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-
12、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}开始符号是SP={S
13、→0S1，S→01}2.扩展的BNF表示法（1）“{}”表示符号串t的多次重复，n为重复的最小次数，m为重复的最大次数，省略n、m表示t可以重复0到任意多次。【例2-9】文法规则S→0S1
14、01简化为S→0(S1
15、1)或S→(0S
16、0)1或S→0(S
17、ε)1（3）“[]”：[t]表示符号串t可选（即可有可无）。【例2-11】C语言条件语句的语法图：文法相关概念：定义1：如α→β是文法G（VN，VT，S，P）的一条规则，γ、δ∈V*，若有符号串v、w满足v=γαδ，w=γβδ则称v（应用规则α→β）直接产生w，或称w是v的直接推导，反过来称w直接归
18、约到v，记作v⇒w。【例2-13】对文法G：S→0S1S→01有直接推导序列：S⇒0S1⇒00S11⇒定义2：如果存在直接推导序列：v=
