《编译原理第二章》PPT课件.ppt

1、第二章,语法描述,定义：称A直接推出，即 A 仅当A 是一个产生式， 且， (VT VN)* 。 如果1 2 n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n 。 对文法G(E)： E i | E+E | E*E | (E) E (E) (E+E) (i+E) (i+i),即表示从0 出发，经 一步或若干步 或者说 使用若干次规则可推导出 n。,2.3.2 语言的形式定义,如果存在一个直接推导序列：,则我们称这个序列是一个从0至n的长度为n的推导，记为,2推导,0 1 2 n,2.3.2 语言的形式定义,设有文法GE=(E,T,F,i,+,*,(,),P,

2、E),对 i+i*i 有如下直接推导序列:,我们可记为,其中P为：EE+T | T,TT*F | F,F(E) | i,E,E+T,T+T,F+T,i+T,i+T*F,i+F*F,i+i*F,i+i*i,2.3.2 语言的形式定义,3广义推导,我们有：,对上例 EE+T | T TT*F | F F(E) | i,2.3.2 语言的形式定义,区别:直接推导的长度大于等于1，而广义推导的长度大于等于0。,2.3.2 语言的形式定义,4. 句型和句子,设有文法GS（S是文法G的开始符号）,2.3.2 语言的形式定义,例1 设有文法GS：,我们有:,显然，符号串01、0S1、00S11和000111

3、 都是文法GS的句型，而01和000111又是文法GS的句子。,S01 | 0S1,2.3.2 语言的形式定义,例2 设有文法GE：,试证明符号串 (i*i+i) 是文法GE的一个句子。,分析 只要证明符号串 (i*i+i) 对文法 G存在一个推导，就可证明符号串 (i*i+i) 是文法GE的一个句子。,EE+E | E*E | (E) | i,2.3.2 语言的形式定义,EE+E | E*E | (E) | i,E,(E),(E+E),(E*E+E),(i*E+E),(i*i+E),(i*i+i),（2）L(G)是VT* 的子集。即属于VT* 的符 号串 x 不一定属于L(G)。,2.3.2

4、 语言的形式定义,5语言,文法GS产生的所有句子的集合称为文 法G所定义的语言,记为L(GS)：,由语言定义可知：,（1）当文法给定，语言也就确定。,2.3.2 语言的形式定义,例3 设有文法GS ：S01 | 0S1,求该文法所描述的语言是什么？,分析 由识别符号S出发，将推出一些什么样的句子，也就是说，L(GS)将由什么样的一些符号串所组成的集合，找出其中的规律，用式子或自然语言描述出来。,2.3.2 语言的形式定义,我们应用第二个规则n1次，然后再应用第一个规则1次，有：,S,0S1,00S11,0n-1S1n-1,0n1n,可见，此文法定义的语言为,L(GS)= 0n1n | n1,S

5、01 | 0S1,2.3.2 语言的形式定义,例4 设有文法GS：S0S | 1S |,该文法所定义的语言是什么？,由该文法所确定的语言为,L(GS)=, 0, 1, 00, 01, 10, 11, = x | x0,1* ,2.3.2 语言的形式定义,例5 设有文法GA：,该文法所定义的语言是什么？,分析 从文法开始符号A出发可推导出以y开头后面跟一个或多个x结尾的符号串，所以该文法定义的语言为,AyB B xB | x,L(GA)= yxn | n1,2.3.2 语言的形式定义,由此可见，从已知文法确定语言的中心思想是：从文法的开始符号出发，反复连续地使用规则替换、展开非终结符，找出句子的

6、规律，用式子或自然语言描述出来。,2.3.2 语言的形式定义,形式语言理论可以证明如下两点：,(1) 给定一种语言，能确定其文法，但这种文法不是唯一的，即：LG1或G2或,(2) 给定一个文法，就能从结构上唯一确定其语言，即：GL(G)；,文法和语言是密切相关的，文法所定义的任一句型和句子, 都可以根据文法推导出来。,我们提出一个问题：,这种推导过程是否唯一？,同一个句型(句子)可以通过不同的推导序列推导出来，这是因为在推导过程中与所选择非终结符的次序有关。,例如，设有文法GN1,N1N,NND | D,D0 | 1 | 2,N1,N,ND,N2,D2,12,N1,N,ND,DD,1D,12,

7、N1,N,ND,DD,D2,12,句子12有下列三种不同的推导序列:,最左(最右)推导，是指对于一个推导序列中的每一步直接推导 , 都是对 中的最左(最右)非终结符进行替换。,最右推导也称为规范推导，用规范推导推导出的句型称为规范句型。,例 设有文法GS:,请给出句子101001的最右、最左推导。,分析 最右推导是指在推导过程中任何一步 (和是句型)，都是对中的最右非终结符进行替换。,SAB,AA0 | 1B,B0 | S1,S,AB,AS1,AAB1,AA01,A1B01,A1001,1B1001,101001,句子101001的最右推导为:,SAB,AA0 | 1B,B0 | S1,最左推

8、导是指在推导过程中任何一步 (和是句型), 都是对的最左非终结符进行替换。,句子101001的最左推导为：,SAB,AA0 | 1B,B0 | S1,S,AB,1BB,10B,10S1,10AB1,101BB1,1010B1,101001,语法树与二义性,用一张图表示一个句型的推导,称为语法树。 (i*i+i)的语法树,E (E) (E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i),E (E) (E+E) (E+i) (E*E+i) (E*i+i) (i*i+i),一棵语法树是不同推导过程的共性抽象。,G(E)： E i | E+E | E*E | (E) (i*i+i

9、),如果使用最左(右)推导，则一个最左(右)推导与语法树一一对应。 一个句型是否只对应唯一一棵语法树？,定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。即：如果一个文法存在某个句子，它有两个不同的最左（最右）推导， 则说这个文法是二义的 G(E)： E i|E+E|E*E|(E) 是二义文法。 语言的二义性：一个语言是二义性的，如果对它不存在无二义性的文法。 可能存在G和G，一个为二义的，一个为无二义的。但L(G)=L(G) 二义性问题是不可判定问题，即不存在一个算法，它能在有限步骤内，确切地判定一个文法是否是二义的。 可以找到一组无二义文法的充分条件。,二义文法：

10、G(E)： E i|E+E|E*E|(E),表达式 项|表达式+项 项 因子 | 项*因子 因子 (表达式) | i,无二义文法： G(E)：E T | E+T T F | T*F F (E) | i,2020/9/13,2.3.2 语法分析树与二义性,消除二义性：,用一种层次观点看待表达式 按照优先集和结合性,29,2020/9/13,2.3.2 语法分析树与二义性,用一种层次观点看待表达式 i * i + i i * (i + i) i * (i * i + i) i * i * (i + i) + i * i + i 取消二义性的文法 表达式 项 |表达式 + 项 项 因子| 项 * 因

11、子 因子 i |（表达式）,表达式,30,2020/9/13,中国科大,2.3.2 语法分析树与二义性,用一种层次观点看待表达式 i * i + i i * (i + i) i * (i * i + i) i * i * (i + i) + i * i + i 取消二义性的文法 E T | E + T T F | T * F F i |（E）,E,E,31,E T F (E) (E+T) (T+T) (T*F+T) (F*F+T) (i*F+T) (i*i+T) (i*i+F) (i*i+i),考虑句子(i*i+i),描述程序设计语言时，对于上下文无关文法的限制 ： 1 不含PP形式的产生式

12、2 每个非终结符P必须有用处 即：,2.3.3 形式语言鸟瞰,Chomsky于1956年建立形式语言体系，他把文法分成四种类型：0，1，2，3型。 与上下文无关文法一样，它们都由四部分组成，但对产生式的限制有所不同。,0型(短语文法，图灵机)： 产生式形如： 其中： (VT VN)*且至少含有一个非终结符； (VT VN)* 0型文法又叫短语文法，记为PSG。0型文法相应的语言称为0型语言或称递归可枚举集，它的识别系统是图灵（Turing）机。,1型(上下文有关文法，线性界限自动机)： 文法G的每一个产生式，均在0型文法的基础上增加了字符长度上满足的限制，则称文法G为1型文法或上下文有关文法，

13、记为CSG。 1型文法相应的语言称为1型语言或上下文有关语言，它的识别系统是线性界限自动机。,2型(上下文无关文法，非确定下推自动机)： 产生式形如： A 其中：A VN； (VT VN)*。 3型(正规文法，有限自动机)： 产生式形如： A B 或 A 其中： VT*；A，BVN 产生式形如： A B 或 A 其中： VT*；A，BVN,右线性文法,左线性文法,四种类型描述能力比较,0型,1型,2型,3型,L5=anbn|n1 不能由正规文法产生，但可由上下文无关文法产生： G5(S)： S aSb| ab L6=anbncn|n1不能由上下文无关文法产生，但可由上下文有关文法产生： G6(S)： S aSBC| aBC CB BC aB ab bB bb bC bc cC cc,程序设计语言不是上下文无关语言，甚至不是上下文有关语言。 L7=c| (a|b)*不能由上下文无关文法产生，甚至连上下文有关文法也不能产生，只能由0型文法产生。 现今程序设计语言的语言结构，用上下文无关文法描述就足够了。,5. 四类文法的关系与区别 关系： 从0型文法到3型文法逐渐增加限制。13型文法都属于0型文法，2、3型文法均属于1型文法，3型文法属于2型文法。 区别： 0、1型文法的产生式左部存在