第二章 高级语言及其文法 School of Computer Science & Technology Harbin Institute of Technology 第二章 高级语言及其文法 重点：文法的定义与分类，CFG的语法树及二义性、程序设计语言的定义。 难点：程序设计语言的语义定义。

第2章 高级语言及其文法 2.1 语言概述 2.2 基本定义 2.3 文法的定义 2.4 文法的分类 2.5 CFG的语法树 第2章 高级语言及其文法 2.1 语言概述 2.2 基本定义 2.3 文法的定义 2.4 文法的分类 2.5 CFG的语法树 2.6 CFG的二义性 2.7 本章小结 2017/3/22

2.1 语言概述 语言是一定的群体用来进行 信息交流的工具。 什么是语言？ 2017/3/22

2.1 语言概述 信息交流的基础是什么？ 按照共同约定的生成规则和理解规则去生成“句子”和理解“句子” 例： “今节日上课始开译第一编” “今日开始上第一节编译课” 2017/3/22

2.1 语言概述 语言的特征 自然语言(Natural Language) 是人与人的通讯工具 语义(semantics):环境、背景知识、语气、二义性——难以形式化 计算机语言(Computer Language) 计算机系统间、人机间通讯工具 严格的语法(Grammar)、语义(semantics) ——易于形式化：严格 2017/3/22

2.1 语言概述 语言的描述方法——现状 自然语言：自然、方便-非形式化 数学语言（符号）：严格、准确-形式化 形式化描述 高度的抽象，严格的理论基础和方便的计算机表示。 2017/3/22

2.1 语言概述 语言——形式化的内容提取 语言(Language)：满足一定条件的句子集合 句子(Sentence)：满足一定规则的单词序列 单词(Token)：满足一定规则的字符(Character)串 语言是字和组合字的规则 例（自然语言：第译始二天课今开编上节） 今天开始上第二节编译课 2017/3/22

2.1 语言概述 语言是字及其组合规则的统一体 2017/3/22

2.1 语言概述 程序设计语言——形式化的内容提取 例：变量:=表达式 程序设计语言(Programming Language)：组成程序的所有语句的集合。 程序(Program)：满足语法规则的语句序列。 语句(Sentence) ：满足语法规则的单词序列。 单词(Token) ：满足词法规则的字符串。 例：变量:=表达式 if 条件表达式 then 语句 while 条件表达式 do 语句 call 过程名(参数表) 2017/3/22

2.1 语言概述 描述形式——文法 语法——语句 语句的组成规则 描述方法：BNF范式、语法(描述)图 词法——单词 单词的组成规则 2017/3/22

形式语言与自动机理论的产生与作用 语言学家Chomsky最初从产生语言的角度研究语言。 1956年，通过抽象，他将语言形式地定义为是由一个字母表中的字母组成的一些串的集合。可以在字母表上按照一定的规则定义一个文法（Grammar），该文法所能产生的所有句子组成的集合就是该文法产生的语言。 2017/3/22

形式语言与自动机理论的产生与作用 克林（Kleene）在1951年到1956年间，从识别语言的角度研究语言，给出了语言的另一种描述。 克林是在研究神经细胞中，建立了自动机，他用这种自动机来识别语言：对于按照一定的规则构造的任一个自动机，该自动机就定义了一个语言，这个语言由该自动机所能识别的所有句子组成。 2017/3/22

形式语言与自动机理论的产生与作用 1959年，Chomsky通过深入研究，将他本人的研究成果与克林的研究成果结合了起来，不仅确定了文法和自动机分别从生成和识别的角度去表达语言，而且证明了文法与自动机的等价性。 2017/3/22

形式语言与自动机理论的产生与作用 20世纪50年代，人们用巴科斯范式（Backus Nour Form 或 Backus Normal Form，简记为BNF）成功地对高级语言ALGOL-60进行了描述。实际上，巴科斯范式就是上下文无关文法（Context Free Grammar）的一种表示形式。这一成功，使得形式语言在20世纪60年代得到了大力的发展。 2017/3/22

形式语言与自动机理论的产生与作用 形式语言与自动机理论除了在计算机科学领域中的直接应用外，更在计算学科人才的计算思维的培养中占有极其重要的地位 计算思维能力的培养，主要是由基础理论系列课程实现的，该系列主要由从数学分析开始到形式语言结束的一些数学和抽象程度比较高的内容的课程组成。 它们构成的是一个梯级训练系统。在此系统中，连续数学、离散数学、计算模型等三部分内容要按阶段分开，三个阶段对应与本学科的学生在大学学习期间的思维方式和能力的变化与提高过程的三个步骤。 2017/3/22

2.2 基本定义 定义2.1 字母表（Alphabet）∑是一个非空有穷集合，字母表中的元素称为该字母表的一个字母（Letter），也叫字符（Character） 例 以下是不同的字母表： ⑴ {a，b，c，d} ⑵ {a，b，c，……，z} ⑶ {0，1} (4) ASCII字母表 2017/3/22

2.2 基本定义 定义2.2 设∑1、∑2是两个字母表，∑1与∑2 的乘积(Product)定义为∑1∑2={ab|a∈∑1，b∈∑2} 例:∑1={0,1}, ∑2={a,b}, ∑1∑2 ={0a,0b,1a,1b} 定义2.3 设∑是一个字母表，∑的n次幂(Power)递归地定义为： ⑴ ∑0={ε} ⑵ ∑n=∑n-1∑ n≥1 例： ∑13 ={000,001,010,011,100,101,110,111} 2017/3/22

2.2 基本定义 定义2.4 设∑是一个字母表，∑的正闭包 (Positive Closure)定义为： ∑+=∑∪∑2∪∑3∪∑4∪…… ∑的克林闭包(Kleene Closure)为： ∑*=∑0∪∑+ =∑0∪∑∪∑2∪∑3∪…… 2017/3/22

2.2 基本定义 例 {0,1}+ = {0，1，00，01，11，000，001，010，011，100，……} {a，b，c，d}+ = {a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，……，aaa，aab，aac，aad，aba，abb，abc……} 2017/3/22

2.2 基本定义 例 {0,1}* = {ε，0，1，00，01，11，000，001，010，011，100，…} {a，b，c，d}* = {ε，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，…，aaa，aab，aac，aad，aba，abb，abc，…} 2017/3/22

2.2 基本定义 定义2.5 设∑是一个字母表，x  ∑*，x称为字母表∑上的一个句子（sentence），ε叫做∑上的一个空句子。 定义2.6 设∑是一个字母表，对任意的x，y∈∑*，a∈∑，句子xay中的a叫做a在该句子中的一个出现(occurrence)。 定义2.7 设∑是一个字母表，x∈∑*，句子x中字符出现的总个数叫做该字符串的长度(length)，记作|x|。 2017/3/22

2.2 基本定义 定义2.8 设∑是一个字母表，x，y∈∑*，x，y的并置(concatenation)是这样一个串，该串是由串x直接连接串y所组成的。记作xy。并置又叫做连结。 对于n≥0，串x的n次幂(power)定义为： ⑴ x0=ε； ⑵ xn=xn-1x。 2017/3/22

2.2 基本定义 定义2.9 设∑是一个字母表，对x，y，z∈∑*，如果x=yz，则称y是x的前缀(prefix)，如果z≠ε，则称y是x的真前缀(proper prefix)；z是x的后缀(suffix)，如果y≠ε，则称z是x的真后缀(proper suffix)。 字母表∑={a，b}上的句子abaabb的前缀、后缀、真前缀和真后缀如下： 前缀：ε，a，ab，aba，abaa，abaab，abaabb 真前缀：ε，a，ab，aba，abaa，abaab 后缀：ε，b，bb，abb，aabb，baabb，abaabb 真后缀：ε，b，bb，abb，aabb，baabb 2017/3/22

2.2 基本定义 定义2.10 设∑是一个字母表，对x，y，z，w，v∈∑*，如果x=yz，w=yv，则称y是x和w的公共前缀(common prefix)。如果x和w的任何公共前缀都是y的前缀，则称y是x和w的最大公共前缀(maximal common prefix)。如果x=zy，w=vy，则称y是x和w的公共后缀(common suffix )。如果x和w的任何公共后缀都是y的后缀，则称y是x和w的最大公共后缀(maximal common suffix )。 2017/3/22

2.2 基本定义 定义2.11设∑是一个字母表，对w，x，y，z∈∑*，如果w=xyz，则称y是w的子串(substring)。 定义2.12 设∑是一个字母表，对t，u，v，w，x，y，z∈∑*，如果t=uyv，w=xyz，则称y是t和w的公共子串(common substring)。如果y1，y2，……，yn是t和w的公共子串，且|yj|=max{|y1|，|y2|，……，|yn|}，则称yj是t和w的最大公共子串(maximal common substring)。 2017/3/22

2.2 基本定义 定义2.13 设∑是一个字母表，L  ∑*，L称为字母表∑上的一个语言（Language），x∈L，x叫做L的一个句子。 例：字母表{0，1}上的语言 {0，1} {00，11} {0，1，00，11} {0，1，00，11，01，10} {00，11}* {01，10}* 2017/3/22

2.2 基本定义 2.14 设∑1，∑2是字母表，L1∑1*，L2∑2*，语言L1与L2的乘积(product)是字母表∑1∪∑2上的一个语言，该语言定义为： L1L2={xy|x∈L1，y∈L2} 2017/3/22

2.2 基本定义 定义2.15 设∑是一个字母表，L∑*，L的n次幂(power)是一个语言，该语言定义为： ⑴ 当n=0是，Ln={ε}； ⑵ 当n≥1时，Ln= Ln-1L。 L的正闭包(positive closure)L+是一个语言，该语言定义为： L+=L∪L2∪L3∪L4∪…… L的克林闭包(Kleene closure)L*是一个语言，该语言定义为： L*= L0∪L∪L2∪L3∪L4∪…… 2017/3/22

如何实现语言结构的 形式化描述？ 2.3 文法的定义 考虑赋值语句的形式： 左部量 = 右部表达式 a = a+a b = m[3]+b m[1] = a+m[2] 考虑赋值语句的形式： 左部量 = 右部表达式 2017/3/22

句子的组成规则 问题：如何用符号来描述？即如何形式化？ <赋值语句><左部量>=<右部表达式> <左部量><简单变量> <左部量> <下标变量> <简单变量>a <简单变量>b <简单变量> c <下标变量>m[1] <下标变量>m[2] <下标变量>m[3] <右部表达式><简单变量><运算符><简单变量> <右部表达式><简单变量><运算符><下标变量> <右部表达式><下标变量><运算符><简单变量> <右部表达式><下标变量><运算符><下标变量> <运算符> + <运算符> - 问题：如何用符号来描述？即如何形式化？ 2017/3/22

定义句子的规则的语法组成 ——终结符号集，非终结符号集，语法规则，开始符号 非终结符号集V = {<赋值语句>，<左部量>，<右部表达式>，<简单变量>，<下标变量>，<运算符>} 终结符号集T = {a , b, c, m[1], m[2], m[3], +, -} 语法规则集P = {<赋值语句><左部量>=<右部表达式> ，……} 开始符号S = 赋值语句 2017/3/22

文法G的形式定义 定义2.16 文法G为一个四元组: Ｇ = (Ｖ，T，Ｐ，Ｓ) Ｖ：非终结符(Terminal)集 语法变量（成分）——代表某个语言的各种子结构 T：终结符(Variable)集 语言的句子中出现的字符，Ｖ∩T =  Ｓ：开始符号(Start Symbol)，S∈Ｖ 代表文法所定义的语言，至少在产生式左侧出现一次 2017/3/22

文法G的形式定义 Ｐ：产生式(Product)集合 α→β，被称为产生式（定义式），读作：α定义为β。其中α∈(Ｖ∪T)+，且α中至少有Ｖ中元素的一个出现。β∈(Ｖ∪T)*。α称为产生式α→β的左部(Left Part)，β称为产生式α→β的右部(Right Part)。 产生式定义各个语法成分的结构（组成规则） 2017/3/22

例2.9 赋值语句的文法 V={<赋值语句>，<左部量>，<右部表达式>，<简单变量>， <下标变量>，<运算符>} T={a，b，c，m[1]，m[2]，m[3]，+，-} P={<赋值语句><左部量>=<右部表达式>， <左部量><简单变量>, <左部量> <下标变量>, <简单变量>a, <简单变量>b, <简单变量> c, <下标变量>m[1], <下标变量>m[2]， <下标变量>m[3], <右部表达式><简单变量> <运算符><简单变量>, <右部表达式><简单变量><运算符> <下标变量>, <右部表达式><下标变量><运算符><简单变量>， <右部表达式><下标变量><运算符><下标变量>， <运算符> +，<运算符> -} S=<赋值语句> 2017/3/22

例2.9 赋值语句的文法（续） 符号化之后： G=({A，B，E，C，D，P}，{a，b，c，m[1]，m[2]，m[3]，+，-}，P，A)， 其中，P={AB=E，BC，BD，Ca，Cb，C c，Dm[1]，Dm[2]，Dm[3]，ECOC，ECOD，EDOC，EDOD，O +，O -} 2017/3/22

产生式的简写 对一组有相同左部的产生式 α→β1，α→β2…，α→βn 可以简单地记为： α→β1|β2|…|βn 读作：α定义为或者β1，或者β2，…，或者βn。并且称它们为α产生式。β1，β2，…，βn称为候选式(Candidate)。 对一个文法，只列出该文法的所有产生式，且所列的第一个产生式的左部是该文法的开始符号。 问题：有了定义句子的规则，如何判定某一句子是否属于某语言？ 2017/3/22

句子的派生(推导)-从产生语言的角度 赋值语句  左部量 = 右部表达式  简单变量 = 右部表达式  a = 右部表达式  a = 简单变量<运算符><简单变量>  a = a <运算符><简单变量>  a = a + <简单变量>  a = a + a 37

句子的归约 ---从识别语言的角度 a = a + a  a = a + <简单变量> 句子的归约 ---从识别语言的角度 a = a + a  a = a + <简单变量>  a = a <运算符><简单变量>  a = 简单变量<运算符><简单变量>  a = 右部表达式  简单变量 = 右部表达式  左部量 = 右部表达式  赋值语句 派生与识别均根据规则 38

基于产生式的变换--推导或归约 定义2.17 设G=(V，T，P，S)是一个文法，如果αβ∈P，γ，δ∈(V∪T)*，则称γαδ在G中直接推导出γβδ，记作： γαδ γβδ 读作：γαδ在文法G中直接推导出γβδ。在不特别强调推导的直接性时，“直接推导”可以简称为推导(derivation)，有时我们也称推导为派生。 与之相对应，也可以称γβδ在文法G中直接归约成γαδ。在不特别强调归约的直接性时，“直接归约”可以简称为归约(reduction)。由于这里实际是将γβδ中的β变成了α，而γ和δ都没有变化，所以又称将β归约成α。 2017/3/22

(多步)推导 α0α1α2 …αn 记为 α0 αn (恰用n步) α0 αn （至少一步） α0 αn （若干步:零步或多步） 2017/3/22

文法G产生的语言 设G=(V，T，P，S)是一个文法，对于A∈V，令 L(A)={x | A x & x∈T*} 不难看出，L(A)就是语法变量A所代表的集合。 定义2.19 设有文法G=(V，T，P，S)，则称 L(G)={w | S w & w∈T* } 为文法G产生的语言(language)。w∈L(G)，w称为G产生的一个句子(sentence)。 显然，对于任意一个文法G，G产生的语言L(G)就是该文法的开始符号S所对应的集合L(S)。 2017/3/22

文法G产生的语言(续) Ｌ(Ｇ)＝{x｜Ｓ* x and x∈T*} 文法Ｇ可以派生出多少个句子？ 文法Ｇ的作用——语言的有穷描述 以有限的规则描述无限的语言现象 有限： 产生式集合、终结符集合、非终结符集合 无限： 可以导出无穷多个句子（L也可是有穷） 2017/3/22

推导/归约举例 A  B=E 有产生式AB=E，所以可以将A换成B=E  C=E 有产生式BC，所以可以将B=E中的B换成C BC| D Ca | b | c Dm[1] | m[2]| m[3] ECOC | COD | DOC | DOD O + | - 推导/归约举例 A  B=E 有产生式AB=E，所以可以将A换成B=E  C=E 有产生式BC，所以可以将B=E中的B换成C  a=E 有产生式Ca，所以可以将C=E中的C换成a  a=COD 有产生式ECOD，所以可以将a=E中的E换成COD  a=bOD 有产生式Cb，所以可以将a=COD中的C换成b  a=b+D 有产生式O+，所以可以将a=bOD的O换成+  a=b+m[1] 有产生式Dm[1]，所以可以将a=b+D的D换成m[1] 2017/3/22

句型与句子 定义2.20 设文法G=(V，T，P，S)，对于α∈(V∪T)*，如果S α，则称α是G产生的一个句型(sentential form)，简称为句型 对于任意文法G=(V，T，P，S)，G产生的句子和句型的区别在于句子满足w∈T*，而句型满足α∈(V∪T)* 44

句型与句子 句子w是从S开始，在G中可以推导出来的终结符号行，它不含语法变量； 句子一定是句型；但句型不一定是句子 45

2.４ 文法的分类(Chomsky体系) 根据语言结构的复杂程度（形式语言） 涉及文法的复杂程度、分析方法的选择 反映文法描述语言的能力 如果G满足文法定义的要求，则Ｇ是０型文法（短语结构文法PSG: Phrase Structure Grammar ）。 L(G)为PSL。 2017/3/22

1. 上下文有关文法(CSG) 如果对于αβ∈P，均有|β|≥|α|成立(Ｓ→ε除外)，则称Ｇ为１型文法 即：上下文有关文法（CSG——Context Sensitive Grammar） L(G)为1型/上下文有关/敏感语言(CSL) 2017/3/22

2.上下文无关文法(CFG) 如果对于αβ∈P，均有|β|≥|α|，并且α∈V成立，则称G为２型文法 即：上下文无关文法(CFG: Context Free Grammar) L(G)为2型/上下文无关语言（CFL） CFG能描述程序设计语言的多数语法成分 2017/3/22

例 标识符的文法 S→a|b|c|d S→aT|bT|cT|dT S→L|LT T→a|b|c|d|0|1|2|3|4|5 例 标识符的文法 S→a|b|c|d S→aT|bT|cT|dT T→a|b|c|d|0|1|2|3|4|5 T→aT|bT|cT|dT|0T N→1T|2T|3T|4T|5T S→L|LT T→L|N|TL|TN L→a|b|c|d N→0|1|2|3|4|5 2017/3/22

3. 正规文法(RG) 设A、B∈V，a∈T或为 右线性(Right Linear)文法：A→aB或A→a 左线性(Left Linear)文法：A→Ba或A→a 都是３型文法(正规文法 Regular Grammar -RG) L(G)为3型/正规集/正则集/正则语言（RL） 能描述程序设计语言的多数单词 左、右线性文法不可混用 2017/3/22

例 非CFL的文法 L={anbncn|n>0}的文法 SaBC|aSBC CBBC aBab bBbb bCbc cCcc “可以证明”不存在CFG G ,使L(G)=L 2017/3/22

非上下文无关的语言结构 程序设计语言的有些语言结构不能用上下文无关文法描述 例2.9 L1={wcw|w∈{a,b}+} aabcaab就是L1的一个句子 这个语言是检查程序中标识符的声明应先于引用的抽象 52

非上下文无关的语言结构 例2.10 L2={anbmcndm|n,m≥0} 它是检查过程声明的形参个数和过程引用的参数个数是否一致问题的抽象  例2.10 L2={anbmcndm|n,m≥0} 它是检查过程声明的形参个数和过程引用的参数个数是否一致问题的抽象 53

Chomsky体系——总结 * A→aB或A→a: G是右线性文法，L(G)是3型语言 G = (V，T，P，S)是一个文法,α→β ∈ P * G是0型文法，L(G)是0型语言； ---其能力相当于图灵机 * |α|≤|β|:G是1型文法，L(G)是1型语言(除Ｓ→ε); ---其识别系统是线性界限自动机 * α∈Ｖ : G是2型文法，L(G)是2型语言; ---其识别系统是不确定的下推自动机 * A→aB或A→a: G是右线性文法，L(G)是3型语言 A→Ba或A→a : G是左线性文法，L(G)是3型语言 ---其识别系统是有穷自动机 2017/3/22

文法的类型 四种文法之间的逐级“包含”关系如下： 四种文法之间的关系是将产生式作进一步限制而定义的。 0型文法 1型文法 2型文法 3型文法 2017/3/22

ＢＮＦ范式——Backus-Naur Form Backus-Normal Form α→β表示为α∷＝β 非终结符用“<”和“>”括起来 终结符：基本符号集 其他 β(α1|α2…|αn)≡βα1|βα2…|βαn [α] ≡ α| ε …… 2017/3/22

ＢＮＦ范式——Backus-Naur Form Backus-Normal Form 例 简单算术表达式(只写产生式) <算术表达式>∷＝<简单表达式>+<简单表达式> <简单表达式>∷＝<简单表达式>*<简单表达式> <简单表达式>∷＝(<简单表达式>) <简单表达式>∷＝id 即：<算术表达式>∷＝<简单表达式>+<简单表达式>|<简单表达式>*<简单表达式>|(<简单表达式>)|id 哪些是终结符？哪些是变量？ 2017/3/22

2.5 CFG的语法树 Parse Tree 用树的形式表示句型的生成 每个推导对应一个中间结点及其儿子——一个二级子树-直接短语 树根： 开始符号 中间结点： 非终结符 叶结点： 终结符或者非终结符 每个推导对应一个中间结点及其儿子——一个二级子树-直接短语 又称为分析树(parse tree)、推导树(derivation tree)、派生树(derivation tree) 2017/3/22

例 句子结构的表示 (文法E→E+E|E*E|(E)|id ） EE+Eid+Eid+E*Eid+id*Eid+id*id E E→E+E E E + E * E→E*E E→id id id E→id E→id 一棵树！ id 2017/3/22

短语(Phrase) 定义2.27 设有CFG G=(V，T，P，S)，α，γ，β∈(V∪T)*，S γAβ，A α，则称α是句型γαβ的相对于变量A的短语(phrase)； 如果此时有Aα，则称α是句型γαβ的相对于变量A的直接短语(immediate phrase) 在无意义冲突时，简称为句型γαβ的直接短语。直接短语也叫做简单短语(simple phrase)。 定义2.28 设有CFG G=(V，T，P，S)，G的句型的最左直接短语叫做句柄(handle)。 2017/3/22

例：(直接)短语 (E+T)+T E→E+T|T (T+T)+T T→T*F|F (F+T)+T F→(E)|id (id+T)+T (a+T*F)+T (a+F*F)+T (a+b*F)+T (a+b*c)+T (a+b*c)+F (a+b*c)+d E→E+T|T T→T*F|F F→(E)|id EE+T T+T F+T (E)+T (E+T)+T 2017/3/22

句柄(Handle)：最左直接短语 (T+T)+T T→T* F|F (F+T)+T E→E+T|T (id+T)+T (a+T*F)+T (a+F*F)+T (a+b*F)+T (a+b*c)+T (a+b*c)+F (a+b*c)+d T→T* F|F E→E+T|T F→( E )| id EE+T T+T F+T (E)+T (E+T)+T 2017/3/22

用子树解释短语，直接短语，句柄 短语：一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。 直接短语：仅有父子两代的一棵子树，它的 所有叶子自左至右排列起来所形成的符号串。 句柄：一个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。 例如，对表达式文法G[E]和句子a1+a2*a3，挑选出推导过程中产生的句型中的短语，直接短语，句柄 2017/3/22

E 短语 E+T E+T E T+T T,T+T T E + F+T F,F+T  a1+T a1, a1+T T * F T  a1+T*F a1, T*F, a1+T*F  a1+F * F a1, F,F*F, a1+F*F F a3 F  a1+a2 *F a1, a2,a1+ a2 *F, a2 *F a1+a2 *a3 a1, a2, a3, a2 * a3 a1+ a2 *a3 a2 a1 2017/3/22

例 短语与分析树 (文法E→E+E|E*E|(E)|id ） 一棵子树的叶子！ 2017/3/22

id+id*id的不同推导E→E+E|E*E|(E)|id  E+id*E  id+id*E  id+id*id E  E+E  id+E  id+E*E  id+id*E  id+id*id E  E+E  E+E*E  E+E*id  E+id*id  id+id*id 不做限制 句型 (sentential Form) （归约） E * id+id*id 施于最左变量 左句型(left-~) （最右归约） E5 id+id*id 施于最右变量 右句型/规范句型 (canonical ~) (最左/规范归约) E + id+id*id 2017/3/22

最左推导与最右推导 最左推导(Left-most Derivation) 每次推导都施加在句型的最左边的语法变量上。——与最右归约对应 最右推导(Right-most Derivation) 每次推导都施加在句型的最右边的语法变量上。——与最左归约（规范规约）对应的规范(Canonical)句型 2017/3/22

2.6 CFG的二义性 对同一句子存在两棵语法分析树 在理论上不可判定 E * id + E + id * 2017/3/22

文法的二义性 1. 描述一个句子的文法不是唯一的； 2. 对于一个句子的分析应是唯一的。 考虑表达式下面的文法 G[E],其产生式如下： 1. 描述一个句子的文法不是唯一的； 2. 对于一个句子的分析应是唯一的。 考虑表达式下面的文法 G[E],其产生式如下： EE+EE*E (E)  a 对于句子a+a*a, 有如下两个最左推导： EE+E a+E a+E*E a+a*E a+a*a E E*E E+E*E a+E*E a+a*E a+a*a 2017/3/22

E E E + E E * E E + E E * E a a a a a a EE+E a+E a+E*E a+a*E a+a*a E E*EE+E*E a+E*Ea+a*E a+a*a E E 最左推导 E + E E * E E + E E * E a a a a a a 2017/3/22

E E E + E E * E E + E E * E a a a a a a E+E*a E+a*a a+a*a E E*EE*a E+E*aE+a*a a+a*a E E 最右推导 E + E E * E E + E E * E a a a a a a 2017/3/22

二义性（ambiquity)的定义 如果一个文法的句子存在两棵分析树,那么,该句子是二义性的。如果一个文法包含二义性的句子,则称这个文法是二义性的; 否则，该文法是无二义性的。几点说明： 1 . 一般来说，程序语言存在无二义性文法， 对于表达式来说，文法（2 .1）是二义性的。对于条件语句，经常使用二义性文法描述它： S if expr then S  if expr then S else S  other 二义性的句子: if e1 then if e2 then s1 else s2 2017/3/22

描述if语句的无二义性文法的产生式 下面是 Smatched_s  unmatched_s matched_s if expr then matched_s else matched_s other unmatched_s if expr then S  if expr then matched_s else unmatched_s 它显然比较复杂，因此： 2. 在能驾驭的情况下，使用二义性文法。 2017/3/22

3. 对于任意一个上下文无关文法，不存在一个算法，判定它是无二义性的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的。 4. 存在先天二义性语言。例如， aibicji, j1 aibjcji, j1 存在一个二义性的句子akbkck。 2017/3/22

分析树与(抽象)语法树不同 (语法)分析树 E + id (抽象)语法树 + id 2017/3/22

2.7 本章小结 语言及其描述 文法的基本概念 Chomsky体系 CFG的语法树 文法的二义性 语言的固有二义性 2017/3/22