语言分析基础

1、1第二章第二章 语言分析基础语言分析基础2语言分析基础语言分析基础l 文法和语言概述文法和语言概述l 字母表和符号串字母表和符号串l 文法和语言的形式定义文法和语言的形式定义l 文法的类型文法的类型l 上下文无关文法及其语法树上下文无关文法及其语法树l 句型的分析句型的分析l 有关文法实用中的说明有关文法实用中的说明3形式语言形式语言( (Chomsky) )：通过抽象，对语言进行形式化描述，用一组数：通过抽象，对语言进行形式化描述，用一组数学符号和规则来描述的语言称为形式语言。学符号和规则来描述的语言称为形式语言。 * *的任何子集称作的任何子集称作 上的形式语言。上的形式语言。L（GS）=

2、 | VT*,S +由文法定义语言：由文法定义语言： 2.4 2.4 文法的类型文法的类型文法文法 GS =（VN ， VT ， P ， S） VN ：有穷非空的非终结符号集：有穷非空的非终结符号集 VT ：有穷非空的终结符号集，且：有穷非空的终结符号集，且VNVT= P： 有穷非空产生式或规则的集合有穷非空产生式或规则的集合 S： 开始符号（识别符号）开始符号（识别符号） SVN ， S至少要在至少要在 一条规则中作为左部出现。一条规则中作为左部出现。4 Chomsky Chomsky对文法中的规则施加不同限制对文法中的规则施加不同限制，将文法和语言分为四大类：，将文法和语言分为四大类：0

3、0型文法型文法 0 0型语言或短语结构语言型语言或短语结构语言1 1型文法型文法 1 1型语言或上下文有关语言型语言或上下文有关语言2 2型文法型文法 2 2型语言或上下文无关语言型语言或上下文无关语言3 3型文法型文法 3 3型语言或正则型语言或正则( (正规正规) )语言语言2.4 2.4 文法的类型文法的类型50型语言：型语言：L00型文法称为型文法称为无约束短语结构文法无约束短语结构文法。规则的左部和右。规则的左部和右部都可以是符号串，一个短语可以产生另一个短语。部都可以是符号串，一个短语可以产生另一个短语。 0型文法，型文法，P：:=，其中：，其中：V*且至少含有一个且至少含有一个非

4、终结符，非终结符，V* 。2.4 2.4 文法的类型文法的类型60型文法，型文法，GS: SABS | AB ABBA A0 B1L(GS)=x | x是由是由n个个01或或10组成的二进制数字串，组成的二进制数字串，n1该文法产生的语言为该文法产生的语言为2.4 2.4 文法的类型文法的类型7SACaBSACaBCaaaCCaaaCCBDBCBDBaBBaaBBaCBECBE aDDaaDDaADACADACaEEaaEEaAEAE例：例：0 0型文法型文法GSGS：2.4 2.4 文法的类型文法的类型8 1型文法型文法 ，P：A := ，其中，其中 AVN， V*， V。1型语言：型语言：

5、L1称为称为上下文敏感上下文敏感或或上下文有关文法上下文有关文法。也即只有。也即只有在在 、 这样的上下文中才能把这样的上下文中才能把A改写为改写为。2.4 2.4 文法的类型文法的类型9SaSBESaSBESaBESaBEBEbEBEbEaBab aBab bBbb bBbb bEbebEbeeEeeeEee例：例：1 1型（上下文有关）文法型（上下文有关）文法SS：2.4 2.4 文法的类型文法的类型10 2型文法，型文法，P： A:=，其中其中 A VN ，V*2型语言：型语言：L2 称为称为上下文无关文法上下文无关文法。也即把。也即把A改写为改写为时，不必考虑上下文。时，不必考虑上下文

6、。2.4 2.4 文法的类型文法的类型11例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GSGS：SABSAB ABS | 0 ABS | 0 BSA | 1 BSA | 1 SS2.4 2.4 文法的类型文法的类型12（右线性）（右线性）P： A:=a 或或 A:=aB 其中其中 A、B VN a VT3型语言：型语言：L3，又称正则语言。，又称正则语言。3型文法称为型文法称为正则文法正则文法。它是对。它是对2型文法进行进一步限制。型文法进行进一步限制。左线性左线性 和右线性文法是相互等价的和右线性文法是相互等价的 （左线性）（左线性）P： A:=a 或或 A:=Ba 其中

7、其中 A、B VN a VT 3 3型文法：型文法：2.4 2.4 文法的类型文法的类型13GSGS： S0A | 1B | 0S0A | 1B | 0 A0A | 1B | 0S A0A | 1B | 0S B1B | 1 | 0 B1B | 1 | 0GIGI： IlTIlTIlIlTlTTlTTdTTdTTlTlTdTd例：例：3 3型文法型文法2.4 2.4 文法的类型文法的类型140 0型文法可以产生型文法可以产生L0L0、L1L1、L2L2、L3L3，但，但1 1型文法只型文法只能产生能产生L1L1、L2L2、L3L3，不能产生，不能产生L0L0，以此类推。，以此类推。 L0 L1

8、 L2 L3L0 L1 L2 L32型文法型文法1型文法型文法0型文法型文法3型文法型文法四种文法的关系四种文法的关系2.4 2.4 文法的类型文法的类型152 2型文法型文法（不确定的下推自动机）（不确定的下推自动机）1 1型文法型文法（不确定的界限自动机）（不确定的界限自动机）0 0型文法型文法（图灵机）（图灵机）3 3型文法型文法（有限自动机）（有限自动机）形式语言与自动机形式语言与自动机2.4 2.4 文法的类型文法的类型16(2) SaSBC SaBC CBDB DBDC DCBC aBab bBbb bCbc (1) SACaB CaaaC CBDB CBE aDDa ADAC a

9、EEa AE cCcc (3) SAc SSc Aab AaAb BcB Bc (4) SaS SaA AbA AbB试判断下列产生式集所对应的文法类型和产生的语言类型：试判断下列产生式集所对应的文法类型和产生的语言类型：2.4 2.4 文法的类型文法的类型0型文法型文法1型文法型文法2型文法型文法3型文法型文法17l 自然语言是上下文有关的。自然语言是上下文有关的。l 上下文无关文法有足够的能力描述现今程序设计语上下文无关文法有足够的能力描述现今程序设计语言的语法结构言的语法结构: : 算术表达式算术表达式 语句语句赋值语句赋值语句条件语句条件语句读语句读语句l 基于正则文法讨论词法分析问题

10、，基于上下文无关基于正则文法讨论词法分析问题，基于上下文无关文法讨论语法分析问题。文法讨论语法分析问题。2.4 2.4 文法的类型文法的类型18l 算术表达式的上下文无关文法表示：算术表达式的上下文无关文法表示： 文法文法G=(E, +,G=(E, +,* *,i,(,), P, E,i,(,), P, E P: E i P: E i E E+E E E+E E E E E* *E E E (E) E (E)l 条件语句的上下文无关文法表示：条件语句的上下文无关文法表示： if if then then | | if if then then else else 2.4 2.4 文法的类型文法

11、的类型192.5 2.5 上下文无关文法及其语法树上下文无关文法及其语法树l 规范推导规范推导l 语法树语法树l 文法的二义性文法的二义性20l 最左（最右）推导最左（最右）推导在推导的任何一步在推导的任何一步，其中，其中、是句是句型，都是对型，都是对中的最左（右）非终结符进行中的最左（右）非终结符进行替换。替换。l 规范推导：规范推导：即最右推导。即最右推导。l 规范句型：规范句型：由规范推导所得的句型。由规范推导所得的句型。1.1.规范推导规范推导2.5 2.5 上下文无关文法及其语法树上下文无关文法及其语法树21最左、最右推导示例：最左、最右推导示例：表达式表达式i+ii+i* *i i

12、的生成过程可的生成过程可表示为如下的：表示为如下的：文法文法GEGE如下：如下： EE+E EE+E EE EE* *E E E( E ) E( E ) Ei Ei l 每句子一定都存在规范推导。每句子一定都存在规范推导。l 不是每个句型都一定存在规范推导。不是每个句型都一定存在规范推导。2.5 2.5 上下文无关文法及其语法树上下文无关文法及其语法树最右推导过程：最右推导过程：E=E + EE=E + E =E + E =E + E * * E E =E + E =E + E * * i i =E + i =E + i * * i i =i + i =i + i * * i i 最左推导过程

13、：最左推导过程：E=E + EE=E + E =i + E =i + E =i + E =i + E * * E E = =i + i i + i * * E E =i + i =i + i * * i i例：例：i + i i + i * * E E ？22对文法对文法GS=(VGS=(VT T,V,VN N,S,P) ,S,P) ，满足下列条件的树称为，满足下列条件的树称为GSGS的语法树：的语法树： (1) (1) 结点：终结符或非终结符；结点：终结符或非终结符； (2) (2) 根结点：文法开始符根结点：文法开始符S S； (3) (3) 内部结点内部结点( ( 指非树叶结点指非树叶结

14、点 ) )：非终结符：非终结符 如果某内部结点如果某内部结点A A有有n n个儿子，它的所有子结点从左至右依次个儿子，它的所有子结点从左至右依次 标记为标记为x x1 1、x x2 2、x xn n，则，则AxAx1 1x x2 2xxn n一定是文法一定是文法GSGS的一的一 条产生式。条产生式。2.语法树语法树的结果：从左到右读出叶子的标记而构成。语法树的结果：从左到右读出叶子的标记而构成。2.5 2.5 上下文无关文法及其语法树上下文无关文法及其语法树23iii句子句子 i+ii+i* *i i 的语法树：的语法树：文法文法GEGE： EE+EEE+E EE EE* *E E E( E

15、) E( E ) Ei Ei 2.5 2.5 上下文无关文法及其语法树上下文无关文法及其语法树24 语法树的构造过程：语法树的构造过程：（1 1）从开始符号出发，向下画一个分枝，表示第一个）从开始符号出发，向下画一个分枝，表示第一个 直接推导；直接推导；（2 2）从非终结符号往下画分枝，表示即将进行的直接）从非终结符号往下画分枝，表示即将进行的直接 推导；推导；（3 3）重复步骤（）重复步骤（2 2）直到全部推导都在树上表示出来。）直到全部推导都在树上表示出来。 2.5 2.5 上下文无关文法及其语法树上下文无关文法及其语法树25语法树构造示例语法树构造示例最左推导过程：最左推导过程：E=E

16、+ EE=E + E =i + E =i + E =i + E =i + E * * E E =i + i =i + i * * E E =i + i =i + i * * i i表达式表达式i+ii+i* *i i的语法树生成过程如下：的语法树生成过程如下： 文法文法GEGE如下：如下：EE+E EE+E EEEE* *E E E( E ) E( E ) Ei Ei EiE*Eii从左到右从左到右读出推导树读出推导树叶子叶子标记连接成的标记连接成的文文法符号串法符号串，为为GSGS的的句型句型。也把该推导树称为该。也把该推导树称为该句型句型的的语法树语法树。语法树语法树- -句型推导的直观表

17、示句型推导的直观表示语法树是用来描述句型（句子）语法树是用来描述句型（句子）语法结构的一种辅助工具。语法结构的一种辅助工具。EE2.5 2.5 上下文无关文法及其语法树上下文无关文法及其语法树26文法文法 GS： (1) S aAcBe (2) A b (3) A Ab (4) B dS aAcBe aAbcBe abbcBe abbcde（1 1）（3 3）（2 2）（4 4）bbAdSaceAB2.5 2.5 上下文无关文法及其语法树上下文无关文法及其语法树语法树构造示例语法树构造示例27文法文法 GS：(1) S aAcBe(2) A b(3) A Ab(4) B db bAdSaceA

18、BS aAcBe aAcde aAbcde abbcde（1 1）（4 4）（3 3）（2 2） 语法树只表示推导的结果，不表示推导的过程。 或者：表示了所有可能的推导(二义性文法除外)。2.5 2.5 上下文无关文法及其语法树上下文无关文法及其语法树语法树构造示例语法树构造示例28语法树只表示推导的结果，不表示推导的过程，或者说表示语法树只表示推导的结果，不表示推导的过程，或者说表示了一个句型的种种可能的推导了一个句型的种种可能的推导( (二义性文法除外二义性文法除外) )。【注意】语法树和推导之间的对应关系为：每一棵语法树至【注意】语法树和推导之间的对应关系为：每一棵语法树至少存在一个推导

19、与之对应，每一个推导都存在一棵语法树。少存在一个推导与之对应，每一个推导都存在一棵语法树。 【 问题】问题】 （1 1）一个句型是否只对应唯一的一棵语法树？）一个句型是否只对应唯一的一棵语法树？ （2 2）一个句型是否只有唯一的一个最左（最右）推导？）一个句型是否只有唯一的一个最左（最右）推导？l 语法树和推导语法树和推导2.5 2.5 上下文无关文法及其语法树上下文无关文法及其语法树29l 句子的二义性句子的二义性文法文法GSGS的一个句子的一个句子如果能找到如果能找到两种不同的最左推导两种不同的最左推导( (或或最右推导最右推导) )，或者存在两棵不同的语法树，则称这个句子，或者存在两棵不

20、同的语法树，则称这个句子是二义性的。是二义性的。l文法的二义性文法的二义性一个文法如果包含二义性的句子，则这个文法是二义文法，一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。否则是无二义文法。这里的二义性是指语法结构上的。这里的二义性是指语法结构上的。3.文法二义性2.5 2.5 上下文无关文法及其语法树上下文无关文法及其语法树l 二义语言二义语言- 如果一个语言没有任何无二义的文法来描述，则这个如果一个语言没有任何无二义的文法来描述，则这个 语言是二义的语言是二义的 - - 先天二义性语言。先天二义性语言。L=aibjck | i=j 或 j=k，i、j、k1301 1

21、、文法的二义性和语言的二义性是不同的概念。如、文法的二义性和语言的二义性是不同的概念。如 果一个文法是二义性的，并不能说明其描述的语果一个文法是二义性的，并不能说明其描述的语 言也是二义性的。但如果语言是二义性的，则描言也是二义性的。但如果语言是二义性的，则描 述它的任何文法一定都是二义性的。述它的任何文法一定都是二义性的。2 2、只要不是二义语言，总可以找到无二义的文法来、只要不是二义语言，总可以找到无二义的文法来 描述它。描述它。3 3、要进行确定的语法语义分析，要求文法必须是无、要进行确定的语法语义分析，要求文法必须是无 二义的。二义的。2.5 2.5 上下文无关文法及其语法树上下文无关

22、文法及其语法树31练习：给出练习：给出i+ii+i* *i i的两种推导，并画出语法树。的两种推导，并画出语法树。iii最左推导过程（最左推导过程（2 2）：）：E=E E=E * * E E =E + E =E + E * * E E =i + E =i + E * * E E =i + i =i + i * * E E =i + i =i + i * * i i 最左推导过程最左推导过程(1)(1)：E=E + EE=E + E =i + E =i + E =i + E =i + E * * E E =i + i =i + i * * E E =i + i =i + i * * i i2.

23、5 2.5 上下文无关文法及其语法树上下文无关文法及其语法树文法文法GEGE如下：如下： EE+E EE+E EE EE* *E E E( E ) E( E ) Ei Ei 32l 二义性的不确定性二义性的不确定性二义性会给语法分析带来不确定性。如果一个句子具有二义二义性会给语法分析带来不确定性。如果一个句子具有二义性，那么对这个句子的结构可能有多种性，那么对这个句子的结构可能有多种正确正确的解释。所的解释。所以，二义性一般是有害的。以，二义性一般是有害的。l 文法的二义性是不可判定的文法的二义性是不可判定的即不存在算法，能够在有限步数内确切判定一个文法是否为即不存在算法，能够在有限步数内确切

24、判定一个文法是否为二义文法。二义文法。若要证明是二义性，只要举出一例。若要证明是二义性，只要举出一例。 若能控制文法的二义性，即加入人为的附加条件，则二义文若能控制文法的二义性，即加入人为的附加条件，则二义文法的存在并非坏事。法的存在并非坏事。2.5 2.5 上下文无关文法及其语法树上下文无关文法及其语法树33l 文法二义性消除文法二义性消除 (1) (1) 不改变文法中原有的语法规则，仅加进一些不改变文法中原有的语法规则，仅加进一些 语法的非形式规定。语法的非形式规定。 (2) (2) 构造一个等价的无二义性文法，即把排除二构造一个等价的无二义性文法，即把排除二 义性的规则合并到原有文法中，

25、改写原有的义性的规则合并到原有文法中，改写原有的 文法。文法。2.5 2.5 上下文无关文法及其语法树上下文无关文法及其语法树34文法二义性消除示例文法二义性消除示例【例】对文法【例】对文法GEGE，不改变已，不改变已有的四条规则，仅加进运算符有的四条规则，仅加进运算符的优先顺序和结合规则，即：的优先顺序和结合规则，即： （1 1） * *优先于优先于+ + （2 2） * *、+ +都服从左结合都服从左结合这样，对文法这样，对文法GEGE中的句子中的句子i+ii+i* *i i就只有如右图所示的惟就只有如右图所示的惟一一棵语法树。一一棵语法树。iii2.5 2.5 上下文无关文法及其语法树上

26、下文无关文法及其语法树文法文法GEGE如下：如下： EE+E EE+E EE EE* *E E E( E ) E( E ) Ei Ei 35EETFTFiiTFi*句子句子i+ii+i* *i i的语法树的语法树2.5 2.5 上下文无关文法及其语法树上下文无关文法及其语法树文法二义性消除示例文法二义性消除示例【例】将文法【例】将文法GEGE改写为无改写为无二义性的文法如下：二义性的文法如下： GE: EE+TTGE: EE+TT TT TT* *FFFF F(E)i F(E)i此时，句子此时，句子i+ii+i* *i i就只有如右就只有如右图所示的惟一一棵语法树。图所示的惟一一棵语法树。 36解：解： 存在二义句子存在二义句子 iiiiii。 是二义文法。文法没有规定是二义文法。文法没有规定、 的优先的优先级和结合性。级和结合性。 按惯例规定按惯例规定、 的优先级和结合性，改的优先级和结合性，改写文法为无二义的文法：写文法为无二义的文法：S SA | AS SA | A A AB |