《编译原理chapter2语言的基本知识》由会员分享，可在线阅读，更多相关《编译原理chapter2语言的基本知识（50页珍藏版）》请在金锄头文库上搜索。
1、1,2,学习本章的目的,构造编译程序的算法是从研究源程序及目标程序产生的，首先找到源语言的形式描述，根据这种描述，构造出相应的分析加工程序。 语言分语法，语义和语用。程序语言语法的形式描述是很好用的，语义的形式描述不那磨好用，但它推动语言理论的发展。,3,2.1.1 字母表 2.1 .2 符号串 一. 符号串的定义 二. 术语 三. 符号串的运算 四. 符号串集合的运算,2.1 符号串,4,字母表是符号的非空有穷集合。任何程序语言都有自己的字母表，例如: 1.计算机语言：由符号“0”和“1”组成的字 母表,=0，1 2. ASCII字符集； 3. Pascal字母表为： = AZ, az, 0
2、9, +, -, *, /, , :, , ; ，.， , (, ), , , , ,2.1.1 字母表,5,一. 符号串的定义 (1) 是上的一个符号串。 (2) 若x是上的符号串，而a是的元素, 则xa是上的符号串。 (3) y是上的符号串,当且仅当它由(1)和 (2)导出。 由字母表中的符号所组成的的任何有穷 序列被称之为该字母表上的符号串,也称作 “字“。,2.1.2 符号串,6,设s是符号串 前缀：移走s的尾部的零个或多于零个符号 后缀：删去s的头部的零个或多于零个符号 子串: 从s中删去一个前缀和一个后缀 子序列: 从s中删去零个或多于零个符号(这些符号不要求是连续的） 逆转（用S
3、R表示）：将S中的符号按相反次序写出而得到的符号串。 长度：是该符号串中的符号的数目。例如|aab|=3,|=0。,二术语,7,：符号串s=banana 前缀：,b,ba,ban,bana,banan,banana 后缀：banana,anana,nana,ana,na,a, 子串: banana,anana,banan,anan, 真前缀，真后缀，真子串: xsx 子序列: baa(这些符号不要求是连续的） 逆转（用SR表示）：ananab 长度：banana=6,例,8,1.连接：设x和y是符号串，它们的连接 xy是把y的符号写在x的符号之后得到的符号串。例如，x=ba,y=nana,xy
4、=banana. 2.方幂：x0= ; x1=x; x2=xx; ;xn=xn-1x; 例如, x=ba, x1= ba, x2=baba, x3=bababa,.,三.符号串的运算,9,设L和M是两个符号串集合，则 1.合并：LMs|sL or sM 2.连接：LM st|sL and tM 3.方幂： L0=， L1L， L2LL, ., LnLn-1L 4. 语言L的Kleene闭包，记作L*， L*Li(i=0) =L0L1L2L3 5语言L的正闭包，记作L+（L+L L*） L+Li(i =1) =L1L2L3L4,四. 符号串集合(语言）的运算,10,如：L=AZ,az D=09
5、1LD=AZ,az ,09 2LD是由所有用一个字母后跟一个数字 组成的符号串所构成的集合。 3L4是由所有的四个字母的符号串构 的集合。 4L（LD)* 是由所有的字母打头的字母和数字组成的符号串所构成的集合. 5D+是由所有的长度大于等于1的数字串所构成的集合.,例,11,2.2 文法和语言的定义,2 . 2 . 1 引子 2 . 2 . 2 文法和语言的定义 一. 文法和语言的定义 二. 推导 三. 语言 四. 最左推导和最右推导 五。短语，直接短语，句柄,12,引子,分析：The grey wolf will eat the goat,谓语,主语,冠词,形容词,名词,动词,直接宾语,助
6、动词,句子,动原,冠词,名词,The grey wolf will eat the goat,13,为了进行机械分析， ：“句子由主语后跟随谓语组成”表示为：,句子 主语 谓语 （1） 主语 冠词 形容词 名词 （2） 冠词the 形容词 grey 谓语 动词 直接宾语 （5） 动词 助动词 动词原形 （6） 助动词will 动词原形 eat 直接宾语 冠词 名词 （9） 名词wolf 名词 goat,语法规则,14,：终结符号集，非终结符号集，语法规则，开始符号。,终结符号集VT=the，grey, wolf,will, eat, goat 非终结符号集VN=句子，主语， 谓语， 冠词， 形
7、容词， 名词 ， 动词 ， 直接宾语 ， 助动词 ，动词原形 语法规则集P=句子 主语谓语， 开始符号S= 句子,句子的语法有四部分,15,句子主语 谓语 冠词 形容词 名词 谓语 the 形容词 名词 谓语 the grey名词 谓语 the grey wolf 谓语 the grey wolf 动词 直接宾语 . the grey wolf will eat the goat,句子根据规则推导出来,16,句子 the grey wolf will eat the goat the grey wolf will eat the wolf the grey goat will eat the
8、wolf the grey goat will eat the grey 合符语法且合符语义的句子仅是： the grey wolf will eat the goat,+ ,句子既要合符语法又要合符语义,17,分析：The grey wolf will eat the goat,句子,主语,谓语,冠词,形容词,名词,动词,直接宾语,助动词,动原,冠词,名词,goat,the,eat,will,The,grey,wolf,句型分析一,18,分析：The grey wolf will eat the goat,句子,主语,谓语,冠词,形容词,名词,动词,直接宾语,助动词,动原,冠词,名词,goa
9、t,the,eat,will,The,grey,wolf,句型分析二,19,一个上下文无关文法 G= （VT，VN S, P ），其中： VT是一个非空有穷终结符号集合； VN是一个非空有穷的非终结符号集合， 且VTVN； S VN ，称为开始符号。 P是一个产生式的非空有穷集合，每个产 生式的形式是A(或A :)，其中 AVN，（VTVN）*。开始符号S至必须在某个产生式的左部出现一次 。 缩写形式： A 1|2,一 文法的定义,20,G=(a,+,*,(,),， ， ，P ) P： * （ ) a E E+T T T T*F F F ( E ) a (2.1),例2.2 算术表达式的文法G
10、:,21,令G=(VT,VN,S,P), 若AP, 且,(VTVN)*,则称A直接推出,表示成 A A直接推出 直接归约到A 如果存在一个直接推导序列： 012 n（n0） 表示成 0 n 0 n 或者0=n或者0 n,+ ,+ ,* ,二. 定义2.3 直接推导和推导的定义,22,例：E E+T T+T F+T a+T a+F a+a,23,设文法 G（VT，VN，S,P）。如果S ,则称是一个句型。仅含终结符号的句型是一个句子。语言 L(G）是由文法G产生的所有句子所组成的集合： L(G)|S 且VT* 例2.3 考虑一个文法 G(a,b,S,S，P）其中P：SaSb ab SaSb aa
11、Sbb a3Sb3 an-1Sbn-1 anbn,* ,+ ,三. 定义2.4：语言的定义,24,设G=(VT=a,b,VN=S,A,B,S,P P由下列产生式组成:SaB|bA Aa|aS|bAA Bb|bS|aBB L(G)=w|wa,b+,且w中有相同个数的a和b。 用归纳法证明下面结论（对w的长度） ： (1)S w,当且仅当w中含有相同个数的a和b。 (2)A w,当且仅当w中a的个数比b的个数多一个。 (3)B w,当且仅当w中b的个数比a的个数多一个。 归纳基础 当|w|=1，Aa, B b, 不能从S导出长度 为1的终极行,则上述结论显然成立。,*,*,*,例2.4,25,设(
12、1),(2)和(3)对于长度不超过k-1的所有w都成立。那么，证明对|w|=k也成立。 对于（1），推导的第一步必是SaB或SbA, 对于第一种情形，必有w=aw1且B w1， |w1|=k-1， 它含的b个数比a多一个，因此，w中a,b的个数相等。推导的第一步是SbA,证明完全类似。反之， |w|=k, w中a,b的个数相等,要证S w。考虑的S推导，推导出的开始符号，或为a或为b。若 SaB,B w1, |w1|=k-1, w1中b的个数比a多一个,w= aw1。若S bA，证明和类SaB类似。 （2）和（3）的证明留给同学们。,*,*,*,归纳步骤：,26,: 对于w和G, wL(G)
13、是否存在S w，如何构造 例如，GE（例2.2）和w=a+a a EE+T T+T F+T a+T a+TF a+F F a+a F a+aa（ 最左） 特点：A (A) ， VT* EE+T E+T F E+ T a E+Fa E+aa T+aa F+aa a+aa 特点：A (A)， VT*（最右）,+ ,四. 最左推导和最右推导,27,令GS是一个文法，如果有 S A 且A 则称是一个关于非终结符号A的，句型的短语。其次如果有 S A 且 A 则称是直接短语。一个句型的最左直接短语称为该句型的句柄。 文法（21）的一个句型 a1*a2+a3 ，尽管 有E a2a3 ，但是 a2a3 并不是该句型 的一个短语,因为不存在 E a1*E。 短语：a1,a2,a3，a1 *a2,a1*a2+a3 直接短语:a1，a2 ,a3 句柄:a1,+ ,* ,* ,+ ,+ ,定义2.5,28,2.3 分析树和二义性,一. 分析树的定义 二. 如何画出分析树 三. 子树 四. 二义性文法的定义 五. 在构造编译程序中如何处理 二义性文法,29,设G=（VT，VN，S，P）,G的一棵分析树满足如下条件： 1. 每一个结点有一个标记，此标记是 VTVN中的符号。 2根的标记是S。 3如果一个结点是内部结点，且有标记A,那么A 必在VN中。 4如果编号为n的结点有标记A,结点n1,n2,
