《编译原理-复习重难点》由会员分享，可在线阅读，更多相关《编译原理-复习重难点（30页珍藏版）》请在金锄头文库上搜索。
1、from成都信息工程大学软件工程学院第一章从本质上来说，程序设计语言是按一定规则排列的符号集合，而编译程序就是把这些符号集合变成机器指令的转换器，编译程序又称为编译器。程序设计语言【高级语言，低级语言（机器语言和汇编语言）】编译过程：词法分析，语法分析，中间代码生成，优化，目标代码产生。三元式定义为如下形式：（op, a1, a2)其中op为操作码或运算符，a1和a2为操作数或运算分量。编译 : 将高级语言程序翻译成另一种语言的等价程序。解释：翻译一句执行一句，边翻译边执行，直到程序结束。 与编译的区别：不生成等价的目标代码程序。 优点：解释方式便于程序的调试。（编译方式只需翻译一次，且目标程
2、序的执行速度快） （1） 词法分析主要任务：从左到右扫描源程序，逐一读入构成源程序的字符流，识别出 其中的一个个单词，识别出的单词称单词符号，也简称符号。单词是高级语言程序中有实际意义的最小语法单位。（2） 语法分析任务“组词成句”，根据单词分析出组成源程序的各类语法单位， 并指出其中的语法错误。语法单位由源程序的单词构成（如表达式、语句、乃至整个程序。）语法单位的构成规则语法规则。一个语言的词法规则和语法规则定义了一个程序的形式结构。语法单位的表示语法树 （3） 语义分析和中间代码生成任务：分析出语法单位具体的动作意义，进行初步翻译，生成与源程序等价的中间代码程序。语义: 定义一个程序所表示
3、的意义,用语义规则描述。 中间代码：指令应结构简单、含义明确，易于实现源程序中间代码 目标代码三者之间的转换。中间代码常用形式： 逆波兰式、三元式、四元式等。四元式： （运算符，对象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 ） （
4、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”，空格不计算长度，则
5、|y|=4。空符号串：无任何符号的串，简称空串，用表示，|=0【例2-4】 若 U = a，b ， V = c，d 则 UV = ac，ad，bc，bd 闭包： 若指定字母表，则*表示上的所有有穷长的串的集合。* =012n * 称为集合的闭包。 + =12n + 称为集合的正闭包。成立的等式：* =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
6、 ，S ， P） VN ： 非终结符集（非空）；VT ： 终结符集（非VNVT ； S：识别符号或开始符号，SVN，且至少在一条规则中作为左部出现； P ： 规则（产生式）的集合。用V表示 VNVT ，称G的字母表或词汇表。 【例2-7】 有一文法G（VN ，VT ，S ， P） 其中: VN = S VT = 0，1 开始符号是 S P = S0S1， S01 2. 扩展的BNF 表示法 （1）“ ” 表示符号串t的多次重复，n为重复的最小次数，m为重复的最大次数，省略n、m表示t可以重复0到任意多次。 【例2-9】文法规则 S0S1|01 简化为 S0(S1|1) 或 S(0S|0)1 或
7、 S0(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： S0S1 S 01 有直接推导序列： S 0S1 00S11000111 定义2：如果存在直接推导序列：v = w0 w1 w2 wn = w 则称v 推导（产生）出w，推导长度为n ，反过来称w 归约到v，记作 v w。
8、 如果有 v w ，或 v = w ，则记作 v w。【例2-14】 S 0S1 00S11 000111 S 推导出 “ 000111” ， 推导长度3 “ 000111” 归约到 S， 表示成 S 0001112句型和句子定义： 文法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 | n1 4文
9、法的等价性 定义：若有文法G1、G2，它们描述的语言相同，即 L( G1 ) = L( G2 ) 则称两文法 G1 和 G2 等价。 【例2-17】有文法 GA： A0R A01 RA1 描述的语言 L(G) = 0n1n | n1 。定义：若有文法G1、G2，它们描述的语言相同，即 L( G1 ) = L( G2 ) 则称两文法 G1 和 G2 等价。 5. 递归规则和递归文法递归规则：形如P1P2的规则称递归规则。 若1=则称左递归规则;若2=则称右递归规则。递归文法：含有递归规则的文法称递归文法。 P1P2的递归称间接递归,含间接递归的文法也是递归文法。 文法分类：1、0型文法（无限制文
10、法或短语文法）定义2-7 设G=(VN，VT，P，S)，如果它的每个产生式满足、(VNVT)*，且至少含有一个非终结符，则G是一个0型文法。结论：0型文法的能力相当于图灵机。 任何0型语言都是递归可枚举的，反之，递归可枚举集也必定是一个0型语言。2、1型文法 （上下文有关文法）定义2-8 设G=(VN，VT，P，S)，如果它的每个产生式满足 |（仅S除外），则G是一个1型文法。 另一种描述：文法的产生式形如 1A2 12 其中AVN，、(VNVT)*且。 【例2-18】1型文法GS：S xSYZ | xYZ yZyzxYxy ZYYZyYyy zZzz3、2型文法 （上下文无关文法）定义2-9
11、 设G=(VN，VT，P，S)，如果它的每个产生式中的是一个非终结符，则G是一个2型文法或上下文无关文法。【例2-19】 2型文法GS： SE TP | TP Fi | (E) ET | ET PF | FP 4、3型文法 （正规文法或正则文法）定义2-10 设G=(VN，VT，P，S)，如果它的每个产生式均形如AaB 或 Aa 其中A、BVN，aVT。 【例2-20】 3型文法GS ： S aA A aA A a S a A dA A d 消除空产生式定理：对任一文法G1，可构造文法G2，使得L(G1)=L(G2)，且G2中无空产生式。证明：根据G1，构造G2的方法如下： (1) 令b=A | Ae(2) b=bA | A +a, ab+。(3) 从G1中删除所有空产生式。(4) 从G1中删除只能导出空串的非终极符。(5) 对于文法中任意产生式AX1X2Xi-1XiXi+1Xn a.若XiVT，不做动作；b.若XiVN-b，不做动作；c.若Xib，补充规则A X1X2Xi-1Xi+1Xn；例： AaB
