第2章 语言分析基础(3).ppt

1、1,第二章 语言分析基础,2,语言分析基础,文法和语言概述 字母表和符号串 文法和语言的形式定义 文法的类型 上下文无关文法及其语法树 句型的分析 有关文法实用中的说明,3,形式语言(Chomsky)：通过抽象，对语言进行形式化描述，用一组数学符号和规则来描述的语言称为形式语言。 *的任何子集称作上的形式语言。,2.4 文法的类型,文法 GS =（VN ， VT ， P ， S） VN ：有穷非空的非终结符号集 VT ：有穷非空的终结符号集，且VNVT= P： 有穷非空产生式或规则的集合 S： 开始符号（识别符号） SVN ， S至少要在 一条规则中作为左部出现。,4,Chomsky对文法中的

2、规则施加不同限制，将文法和语言分为四大类： 0型文法 0型语言或短语结构语言 1型文法 1型语言或上下文有关语言 2型文法 2型语言或上下文无关语言 3型文法 3型语言或正则(正规)语言,2.4 文法的类型,5,0型语言：L0,0型文法称为无约束短语结构文法。规则的左部和右部都可以是符号串，一个短语可以产生另一个短语。,0型文法，P：:=，其中：V*且至少含有一个非终结符，V* 。,2.4 文法的类型,6,0型文法，GS: SABS | AB ABBA A0 B1,L(GS)=x | x是由n个01或10组成的二进制数字串，n1,2.4 文法的类型,7,SACaB CaaaC CBDB aBB

3、a CBE aDDa ADAC aEEa AE,例：0型文法GS：,2.4 文法的类型,8,1型文法 ，P：A := ，其中 AVN， V*， V。,1型语言：L1,称为上下文敏感或上下文有关文法。也即只有在 、 这样的上下文中才能把A改写为。,2.4 文法的类型,9,SaSBE SaBE BEbE aBab bBbb bEbe eEee,例：1型（上下文有关）文法S：,2.4 文法的类型,10,2型文法，P： A:=，其中 A VN ，V*,2型语言：L2,称为上下文无关文法。也即把A改写为时，不必考虑上下文。,2.4 文法的类型,11,例：2型（上下文无关）文法 文法GS：SAB ABS

4、| 0 BSA | 1 S,2.4 文法的类型,12,（右线性）P： A:=a 或 A:=aB 其中 A、B VN a VT,3型语言：L3，又称正则语言。,3型文法称为正则文法。它是对2型文法进行进一步限制。 左线性 和右线性文法是相互等价的,（左线性）P： A:=a 或 A:=Ba 其中 A、B VN a VT,3型文法：,2.4 文法的类型,13,GS： S0A | 1B | 0 A0A | 1B | 0S B1B | 1 | 0,GI： IlT Il TlT TdT Tl Td,例：3型文法,2.4 文法的类型,14,2型文法,1型文法,0型文法,3型文法,四种文法的关系,2.4 文法

5、的类型,15,形式语言与自动机,2.4 文法的类型,16,(2) SaSBC SaBC CBDB DBDC DCBC aBab bBbb bCbc,(1) SACaB CaaaC CBDB CBE aDDa ADAC aEEa AE cCcc,(3) SAc SSc Aab AaAb BcB Bc,(4) SaS SaA AbA AbB,试判断下列产生式集所对应的文法类型和产生的语言类型：,2.4 文法的类型,0型文法,1型文法,2型文法,3型文法,17,自然语言是上下文有关的。 上下文无关文法有足够的能力描述现今程序设计语言的语法结构: 算术表达式 语句 赋值语句 条件语句 读语句 基于正则

6、文法讨论词法分析问题，基于上下文无关文法讨论语法分析问题。,2.4 文法的类型,18,算术表达式的上下文无关文法表示： 文法G=(E, +,*,i,(,), P, E P: E i E E+E E E*E E (E) 条件语句的上下文无关文法表示： if then | if then else ,2.4 文法的类型,19,2.5 上下文无关文法及其语法树,规范推导 语法树 文法的二义性,20,最左（最右）推导 在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换。 规范推导：即最右推导。 规范句型：由规范推导所得的句型。,1.规范推导,2.5 上下文无关文法及其语法树,21,最

7、左、最右推导示例：,表达式i+i*i的生成过程可表示为如下的：,文法GE如下： EE+E EE*E E( E ) Ei,每句子一定都存在规范推导。 不是每个句型都一定存在规范推导。,2.5 上下文无关文法及其语法树,最右推导过程：E=E + E =E + E * E =E + E * i =E + i * i =i + i * i,最左推导过程：E=E + E =i + E =i + E * E =i + i * E =i + i * i,例：i + i * E ？,22,对文法GS=(VT,VN,S,P) ，满足下列条件的树称为GS的语法树： (1) 结点：终结符或非终结符； (2) 根结点

8、：文法开始符S； (3) 内部结点( 指非树叶结点 )：非终结符 如果某内部结点A有n个儿子，它的所有子结点从左至右依次 标记为x1、x2、xn，则Ax1x2xn一定是文法GS的一 条产生式。,2.语法树,语法树的结果：从左到右读出叶子的标记而构成。,2.5 上下文无关文法及其语法树,23,句子 i+i*i 的语法树：,文法GE： EE+E EE*E E( E ) Ei,2.5 上下文无关文法及其语法树,24,语法树的构造过程： （1）从开始符号出发，向下画一个分枝，表示第一个 直接推导； （2）从非终结符号往下画分枝，表示即将进行的直接 推导； （3）重复步骤（2）直到全部推导都在树上表示出

9、来。,2.5 上下文无关文法及其语法树,25,语法树构造示例,最左推导过程：E=E + E =i + E =i + E * E =i + i * E =i + i * i,表达式i+i*i的语法树生成过程如下：,文法GE如下： EE+E EE*E E( E ) Ei,i,E,*,E,从左到右读出推导树叶子标记连接成的文法符号串，为GS的句型。也把该推导树称为该句型的语法树。,语法树-句型推导的直观表示,语法树是用来描述句型（句子）语法结构的一种辅助工具。,E,E,2.5 上下文无关文法及其语法树,26,文法 GS： (1) S aAcBe (2) A b (3) A Ab (4) B d,S,

10、（1）,（3）,（2）,（4）,S,2.5 上下文无关文法及其语法树,语法树构造示例,27,文法 GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,S,S,（1）,（4）,（3）,（2）,语法树只表示推导的结果，不表示推导的过程。 或者：表示了所有可能的推导(二义性文法除外)。,2.5 上下文无关文法及其语法树,语法树构造示例,28,语法树只表示推导的结果，不表示推导的过程，或者说表示 了一个句型的种种可能的推导(二义性文法除外)。 【注意】语法树和推导之间的对应关系为：每一棵语法树至 少存在一个推导与之对应，每一个推导都存在一棵语法树。 【 问题】 （1）一个句型是否

11、只对应唯一的一棵语法树？ （2）一个句型是否只有唯一的一个最左（最右）推导？,语法树和推导,2.5 上下文无关文法及其语法树,29,句子的二义性 文法GS的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。,文法的二义性 一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。,这里的二义性是指语法结构上的。,3.文法二义性,2.5 上下文无关文法及其语法树,二义语言 如果一个语言没有任何无二义的文法来描述，则这个 语言是二义的 - 先天二义性语言。,L=aibjck | i=j 或 j=k，i、j、k1,30,1、文法的二义性

12、和语言的二义性是不同的概念。如 果一个文法是二义性的，并不能说明其描述的语 言也是二义性的。但如果语言是二义性的，则描 述它的任何文法一定都是二义性的。 2、只要不是二义语言，总可以找到无二义的文法来 描述它。 3、要进行确定的语法语义分析，要求文法必须是无 二义的。,2.5 上下文无关文法及其语法树,31,练习：给出i+i*i的两种推导，并画出语法树。,最左推导过程（2）：E=E * E =E + E * E =i + E * E =i + i * E =i + i * i,最左推导过程(1)：E=E + E =i + E =i + E * E =i + i * E =i + i * i,2

13、.5 上下文无关文法及其语法树,文法GE如下： EE+E EE*E E( E ) Ei,32,二义性的不确定性 二义性会给语法分析带来不确定性。如果一个句子具有二义性，那么对这个句子的结构可能有多种正确的解释。所以，二义性一般是有害的。 文法的二义性是不可判定的 即不存在算法，能够在有限步数内确切判定一个文法是否为二义文法。 若要证明是二义性，只要举出一例。 若能控制文法的二义性，即加入人为的附加条件，则二义文法的存在并非坏事。,2.5 上下文无关文法及其语法树,33,文法二义性消除 (1) 不改变文法中原有的语法规则，仅加进一些 语法的非形式规定。 (2) 构造一个等价的无二义性文法，即把排

14、除二 义性的规则合并到原有文法中，改写原有的 文法。,2.5 上下文无关文法及其语法树,34,文法二义性消除示例,【例】对文法GE，不改变已 有的四条规则，仅加进运算符 的优先顺序和结合规则，即： （1） *优先于+ （2） *、+都服从左结合 这样，对文法GE中的句子 i+i*i就只有如右图所示的惟 一一棵语法树。,2.5 上下文无关文法及其语法树,文法GE如下： EE+E EE*E E( E ) Ei,35,句子i+i*i的语法树,2.5 上下文无关文法及其语法树,文法二义性消除示例,【例】将文法GE改写为无 二义性的文法如下： GE: EE+TT TT*FF F(E)i 此时，句子i+i

15、*i就只有如右 图所示的惟一一棵语法树。,36,解： 存在二义句子 iii。 是二义文法。文法没有规定、 的优先级和结合性。 按惯例规定、 的优先级和结合性，改写文法为无二义的文法：S SA | A A AB | B B S | (S) | i,判断文法：SSS | SS | S | i 是否二 义文法？如果是，为它写一个等价的无二义文法。,课堂练习,37,证明文法：SSaS|为二义文法，并将其改 写为无二义的文法。,证明： 存在句子aa对应两棵语法树 该文法是二义文法。,该文法产生的语言是若干个a(可以是0个) 构成的符号串的集合。 可以改写为无二义的文法:SaS|,课堂练习,38,考虑以下的两个语言，给出其