1、编译原理引论编译原理引论授课：胡静授课：胡静2022-11-29编译原理2第一章第一章 概论概论编译的基本概念编译的基本概念编译过程和编译程序的构造编译过程和编译程序的构造2022-11-29编译原理3基本概念基本概念2022-11-29编译原理4基本概念基本概念2022-11-29编译原理5源程序的编译和运行源程序的编译和运行2022-11-29编译原理6源程序的解释运行源程序的解释运行2022-11-29编译原理7源程序的编译源程序的编译-解释运行解释运行2022-11-29编译原理8编译器和解释器编译器和解释器编译器和解释器的比较编译器和解释器的比较相同点（执行相同的任务）相同点（执行相
2、同的任务）:检查输入程序并确定这个程序是否一个有效程序检查输入程序并确定这个程序是否一个有效程序建立一个内部模型来刻画输入程序的结构和含义建立一个内部模型来刻画输入程序的结构和含义决定在执行期间值的存放位置决定在执行期间值的存放位置不同点（执行的行为不同）：不同点（执行的行为不同）：编译器以一个可执行程序的描述作为输入，以另一个编译器以一个可执行程序的描述作为输入，以另一个等价的可执行程序的描述作为输出。等价的可执行程序的描述作为输出。解释器以一个可执行程序的描述作为输入，以执行这解释器以一个可执行程序的描述作为输入，以执行这一可执行程序描述的结果作为输出。一可执行程序描述的结果作为输出。20
3、22-11-29编译原理9什么是编译器什么是编译器什么是编译程序什么是编译程序预处理器预处理器编译器编译器汇编器汇编器装配连接编辑装配连接编辑骨架程序骨架程序 源程序源程序 目标汇编程序目标汇编程序 可重定位机器代码可重定位机器代码 绝对机器码绝对机器码可重定位目标文件库可重定位目标文件库2022-11-29编译原理10编译器的应用模型（逻辑结构）编译器的应用模型（逻辑结构）出出错错处处理理语法分析程序语法分析程序语义分析程序语义分析程序目标代码生成程序目标代码生成程序词法分析程序词法分析程序中间代码生成程序中间代码生成程序代码优化程序代码优化程序表表格格管管理理编译的前端编译的前端（Fron
4、t End）分析部分分析部分与源语言有关与源语言有关编译的后端编译的后端（Back End）综合部分综合部分与目标语言有关与目标语言有关2022-11-29编译原理112022-11-29编译原理122022-11-29编译原理13遍（遍（PASS）遍：对源程序（包括源程序的中间表示形式）从头到尾扫描遍：对源程序（包括源程序的中间表示形式）从头到尾扫描一次并作有关的加工处理，生成新的源程序中间形式或目标一次并作有关的加工处理，生成新的源程序中间形式或目标程序，通常称之为一遍。上一遍的结果是下一遍的输入，最程序，通常称之为一遍。上一遍的结果是下一遍的输入，最后一遍生成目标程序。后一遍生成目标程序
5、。遍与基本阶段的区别：遍与基本阶段的区别：五个基本阶段是将源程序翻译成目标程序在逻辑上要完成的工五个基本阶段是将源程序翻译成目标程序在逻辑上要完成的工作作遍是指完成上述五个基本阶段的工作要经过几次扫描处理遍是指完成上述五个基本阶段的工作要经过几次扫描处理2022-11-29编译原理14内容提要内容提要预备知识预备知识形式语言基础形式语言基础程序语言的定义（语法定义、语义定义）程序语言的定义（语法定义、语义定义）高级语言的一般特性（程序结构、数据类型和操高级语言的一般特性（程序结构、数据类型和操作、语句与控制结构）作、语句与控制结构）程序语言的文法程序语言的文法文法的类型文法的类型上下文无关文法
6、及其语法树上下文无关文法及其语法树有关文法实用中的一些说明有关文法实用中的一些说明预备知识预备知识更多的概念和一些约定更多的概念和一些约定A,B,C,用来表示用来表示非终结符非终结符a,b,c,表示表示终结符终结符,X,Y,Z 可以用来表示可以用来表示终结符或者非终结符终结符或者非终结符,w,x,y,z 表示表示终结符号串终结符号串,表示由表示由终结符或非终结符构成的符号串终结符或非终结符构成的符号串在产生式在产生式A中，中，A 是产生式的左边是产生式的左边(lefthand side,LHS)是产生式的右边是产生式的右边(righthand side,RHS)A1|n 表示产生式表示产生式
7、A 1,A n符号串和符号串集合的运算符号串和符号串集合的运算符号串和符号串集合的运算符号串和符号串集合的运算将字符看做符号，则单词就是符号串，将字符看做符号，则单词就是符号串，单词集合就是符号串的集合单词集合就是符号串的集合将单词看做符号，则句子就是符号串，将单词看做符号，则句子就是符号串，而所有句子的集合（语言）就是符号串而所有句子的集合（语言）就是符号串的集合的集合高级语言的一般特征高级语言的一般特征 高级语言的程序结构高级语言的程序结构 程序程序子程序子程序或或分程分程序序语句语句表达式表达式数据数据引用引用算符算符函数函数调用调用文法的直观概念文法的直观概念关于文法的定义关于文法的定
8、义定义定义3.1文法文法G定义为四元组（定义为四元组（VN,VT,P,S）。）。其中其中VN为非终结符号（或语法实体，或变量）集；为非终结符号（或语法实体，或变量）集；VT为终结符为终结符号集；号集；P为产生式（也称规则）的集合；为产生式（也称规则）的集合；VN,VT和和P是非空有穷是非空有穷集。集。S称做识别符号或开始符号，是一个非终结符（称做识别符号或开始符号，是一个非终结符（S VN），至少要在一条规则中作为左部出现。），至少要在一条规则中作为左部出现。VN和和VT不含公共元素，即不含公共元素，即VNVT=。通常。通常V表示表示VNVT，V称为文法称为文法G的字母表或字汇表。的字母表或字
9、汇表。例例3.1 文法文法G=（VN，VT，P，S）VN=S,VT=0,1 P=S0S1,S01 S为开始符号为开始符号文法可以简写，只需要指出开始符号和产生式即可。文法可以简写，只需要指出开始符号和产生式即可。关于文法的定义（续）关于文法的定义（续）定义定义3.2如如是文法是文法G=(VN,VT,P,S)的规则的规则(或说是或说是P中第一中第一个产生式个产生式)，和和是是V*中的任意符号串，若有符号串中的任意符号串，若有符号串v，w满足：满足：v=，w=，则说，则说v（应用规则（应用规则）直接产生直接产生w，或说，或说w是是v的直接推导。的直接推导。（v=w）例：例：GS：S0S1，S01
10、S 0S1 00S11 000S111 00001111G关于文法的定义（续）关于文法的定义（续）定义定义3.3如果存在直接推导的序列：如果存在直接推导的序列：v=w0=w1=w2=wn=w，(n0)，则称，则称v推导出（产推导出（产生）生）w（推导长度为（推导长度为n）。记做）。记做v=+w。定义定义3.4若有若有v=+w，或，或v=w，则记做，则记做v=*w。规范推导（最右推导）规范推导（最右推导）最左推导：若规则右端符号串中有两个以上的非终结最左推导：若规则右端符号串中有两个以上的非终结符时，先推导左边的。符时，先推导左边的。最右推导：若规则右端符号串中有两个以上的非终结最右推导：若规则
11、右端符号串中有两个以上的非终结符时，先推导右边的。符时，先推导右边的。关于文法的定义（续）关于文法的定义（续）定义定义3.5设设GS是一文法，如果符号串是一文法，如果符号串x是从识别符号推导出来的，即有是从识别符号推导出来的，即有S=*x，则称，则称x是文法是文法GS的句型。若的句型。若x只由终结符号组成，则称只由终结符号组成，则称x为为GS的句子。的句子。定义定义3.6文法文法G所产生的语言定义为集合所产生的语言定义为集合x|S=*x，其中，其中S为文法的开始为文法的开始符号，且符号，且xVT*。可用。可用L(G)表示该集合。表示该集合。例：例：G：S0S1，S01S 0S1 00S11 0
12、00S111 00001111L(G)=0n1n|n1关于文法的定义（续）关于文法的定义（续）定义定义3.7若若L(G1)=L(G2)，则称文法，则称文法G1和和G2是等价的。是等价的。例例1：如文法：如文法G1A：A0R 与与G2S：S0S1 等价等价 A01 S01 RA1例例2：G1E:E i 与与 G2E：E T|E+T等价等价 E E+E T F|T*F E E*E F （E）|i E (E)文法的类型文法的类型 Chomsky将文法分为四种类型：将文法分为四种类型：0型文法：对任一产生式型文法：对任一产生式，都有，都有(VNVT)+，(VNVT)*1型文法：对任一产生式型文法：对任
13、一产生式，都有，都有|，仅仅仅仅 S除外除外2型文法：对任一产生式型文法：对任一产生式，都有，都有VN，(VNVT)*3型文法：任一产生式型文法：任一产生式的形式都为的形式都为AaB或或Aa，其中其中AVN，BVN，aVT。上述叫做右线性文法，。上述叫做右线性文法，另有左线性文法，二者等价。另有左线性文法，二者等价。文法的类型举例文法的类型举例1型（上下文有关）文法型（上下文有关）文法 文法文法GS：SCDAbbA CaCABaaB CbCBBbbBADaD CBDbD DAabDL(G)=ww|wa,b*文法的类型举例文法的类型举例2型（上下文无关）文法型（上下文无关）文法 文法文法GS：S
14、aB|bAAa|aS|bAABb|bS|aBB 文法文法GS：S0A|1B|0A0A|1B|0SB1B|1|0文法的类型举例文法的类型举例定义标识符的定义标识符的3型（正规）文法型（正规）文法 文法文法GI：I lTI lT lTT dTT lT d文法和语言文法和语言0型文法型文法0型文法（短语文法）的能力相当于图灵机，可以表征任何递型文法（短语文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何归可枚举集，而且任何0型语言都是递归可枚举的型语言都是递归可枚举的1型文法（上下文有关文法）型文法（上下文有关文法）产生式的形式为产生式的形式为1A212，即只有，即只有A出现在出现在1和和
15、2的上下文的上下文中时，才允许中时，才允许取代取代A。其识别系统是线性界限自动机。其识别系统是线性界限自动机。2型文法（上下文无关文法）型文法（上下文无关文法）产生式的形式为产生式的形式为A，取代取代A时与时与A的上下文无关。其识别系的上下文无关。其识别系统是不确定的下推自动机。统是不确定的下推自动机。3型文法（正则文法）型文法（正则文法）产生的语言是有穷自动机（产生的语言是有穷自动机（FA）所接受的集合）所接受的集合上下文无关文法上下文无关文法上下文无关文法有足够的能力描述现今程序设计语言的语法结构上下文无关文法有足够的能力描述现今程序设计语言的语法结构算术表达式算术表达式语句语句赋值语句赋
16、值语句条件语句条件语句读语句读语句文法文法G=(E,+,*,I,(,),P,E ifthen P:E i|ifthenelse E E+EE E*EE (E)上下文无关文法的语法树用于描述上下文无关文法的用于描述上下文无关文法的句型推导句型推导的直观方法的直观方法 例:GS:SaASASbAASSSaAba S a A S S b A b a句型句型aabbaa的语法树（推导树）的语法树（推导树）叶子结点：树中没有子孙的结点。叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记，所得的句型为推导树的结从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。
17、果。也把该推导树称为该句型的语法树。a aa a上下文无关文法的语法树推导过程中施用产生式的顺序 例例:GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa文法的二义性最左（最右）推导：在推导的任何一步最左（最右）推导：在推导的任何一步，其中，其中、是句型，都是对是句型，都是对中的最左（右）非终结符进行中的最左（右）非终结符进行替换替换最右推导被称为规范推导。最右推导被称为规范推导。由规范推导所得的句型称为规范句型由
18、规范推导所得的句型称为规范句型文法的二义性文法的二义性例：GE:E iE E+EE E*EE (E)E E E+E E+E E E*E i E i i i i i E E E E*E E i E+E i E+E i i i i句型句型 i*i+i 的两个不同的最左推导：的两个不同的最左推导：推导推导1：E E+E E*E+E i*E+E i*i+E i*i+i推导推导2：E E*E i*E i*E+E i*i+E i*i+i文法的二义性文法的二义性若一个文法存在某个句子对应两棵不同的语法树，若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是则称这个文法是二义二义的。或者，若一个文法存在
19、某的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文个句子有两个不同的最左（右）推导，则称这个文法是法是二义二义的。的。部分二义文法可以改造为无二义文法部分二义文法可以改造为无二义文法GE:E i GE：E T|E+T E E+E T F|T*F E E*E F （E）|i E (E)规定优先顺序（规定优先顺序（T）和结合律（左递归）和结合律（左递归）第一部分习题第一部分习题 1.1何谓源程序、目标程序、翻译程序、编译程序和解释程何谓源程序、目标程序、翻译程序、编译程序和解释程序序?它们之间可能有何种关系它们之间可能有何种关系?1.2一个典型的编译系统通常由哪些部分组成一个
20、典型的编译系统通常由哪些部分组成?各部分的主要各部分的主要功能是什么功能是什么?1.3选择一种你所熟悉的程序设计语言，试列出此语言中的全选择一种你所熟悉的程序设计语言，试列出此语言中的全部关键字，并通过上机使用该语言以判明这些关键字是否为部关键字，并通过上机使用该语言以判明这些关键字是否为保留字。保留字。1.4选取一种你所熟悉的语言，试对它进行分析，以找出此语选取一种你所熟悉的语言，试对它进行分析，以找出此语言中的括号以及逗号有多少种不同的用途。言中的括号以及逗号有多少种不同的用途。2022-11-29编译原理46第二部分习题第二部分习题2.1设有字母表设有字母表A1=a,b,z，A2=0,1
21、,9，试回，试回答下列问题：答下列问题：(1)字母表字母表A1上长度为上长度为2的符号串有多少个的符号串有多少个?(2)集合集合A1A2含有多少个元素含有多少个元素?(3)列出集合列出集合A1(A1A2)*中的全部长度不大于中的全部长度不大于3的符的符号串。号串。2022-11-29编译原理472.2试分别构造产生下列语言的文法。试分别构造产生下列语言的文法。(1)anbn|n0；(2)anbmcp|n,m,p0；(3)an#bn|n0cn#dn|n0；(4)w#wr#|w0,1*，wr是将是将w的符号按逆序排列所的符号按逆序排列所得的符号串得的符号串；(5)任何不是以任何不是以0开始的所有奇
22、整数所组成的集合；开始的所有奇整数所组成的集合；(6)所有由偶数个所有由偶数个0和偶数个和偶数个1所组成的符号串的集所组成的符号串的集合。合。2022-11-29编译原理482.3试描述由下列文法所产生的语言的特点试描述由下列文法所产生的语言的特点(文法的文法的开始符号均为开始符号均为S)。(1)S10S0SaAAbAAa(2)SSSS1A0A1A0A(3)SbAdcAAGSG Aa(4)SaSSSa 2022-11-29编译原理492.4 考察文法考察文法G=(VN,VT,P,S)，其中：，其中：VN=S,A,B,C,D,E,F,G VT=a,P=SABC,CBC,CA,BAGE,BGGBF
23、,AGAD,DBBD,DEAE,FBBF,FEEa,AA 此文发属于什么文法此文发属于什么文法2022-11-29编译原理502.5设已给文法设已给文法G程序：程序：程序程序分程序分程序|复合语句复合语句 分程序分程序无标号分程序无标号分程序|标号：分程序标号：分程序 复合语句复合语句无标号复合语句无标号复合语句|标号：复合语句标号：复合语句 无标号分程序无标号分程序分程序首部；复合尾部分程序首部；复合尾部 无标号复合语句无标号复合语句begin复合尾部复合尾部 分程序首部分程序首部begin说明说明|分程序首部；说明分程序首部；说明 复合尾部复合尾部语句语句end|语句；复合尾部语句；复合尾
24、部 说明说明d 语句语句s 标号标号L(1)给出句子给出句子 L:L:begin d;d;s;s end 的最左推导和最右推导。的最左推导和最右推导。(2)画出上述句子的语法树。画出上述句子的语法树。2022-11-29编译原理512.6设已给文法设已给文法GS：SaAcB SBdSBaScABcABABaBAaBc Aa Bb 试检验下列符号串中哪些是试检验下列符号串中哪些是GS中的句子，给出这些句子的中的句子，给出这些句子的最左推导、最右推导和相应的语法树。最左推导、最右推导和相应的语法树。(1)aacb(2)aabacbadcd(3)aacbccb(4)aacabcbcccaacdca(5)aacabcbcccaacbca2022-11-29编译原理522.7试证明：试证明：文法文法 SABSDCAaAAa BbBcBbcCcCCc DaDbDab 为二义性文法。为二义性文法。2022-11-29编译原理532022-11-29编译原理54
