第二章 高级语言及其文法 School of Computer Science & Technology

Slides:



Advertisements
Similar presentations
2.8 函数的微分 1 微分的定义 2 微分的几何意义 3 微分公式与微分运算法则 4 微分在近似计算中的应用.
Advertisements

2.5 函数的微分 一、问题的提出 二、微分的定义 三、可微的条件 四、微分的几何意义 五、微分的求法 六、小结.
复习: :对任意的x∈A,都有x∈B。 集合A与集合B间的关系 A(B) A B :存在x0∈A,但x0∈B。 A B A B.
圆的一般方程 (x-a)2 +(y-b)2=r2 x2+y2+Dx+Ey+F=0 Ax2+Bxy+Cy2+Dx+Ey+ F=0.
第五章 二次型. 第五章 二次型 知识点1---二次型及其矩阵表示 二次型的基本概念 1. 线性变换与合同矩阵 2.
第二章 文法和语言 2.1 文法的基本概念 符号和符号串 2.2 句型的分析 文法和语言的形式定义 推导与递归 文法的分类 语法树
第三章 函数逼近 — 最佳平方逼近.
编 译 原 理 指导教师:杨建国 二零一零年三月.
《高等数学》(理学) 常数项级数的概念 袁安锋
§1 线性空间的定义与性质 ★线性空间的定义 ★线性空间的性质 ★线性空间的子空间 线性空间是线性代数的高等部分,是代数学
常用逻辑用语复习课 李娟.
一、原函数与不定积分 二、不定积分的几何意义 三、基本积分公式及积分法则 四、牛顿—莱布尼兹公式 五、小结
2-7、函数的微分 教学要求 教学要点.
初中数学八年级下册 (苏科版) 10.4 探索三角形 相似的条件(2).
编译原理与技术 --文法和分析 2018/9/17 《编译原理与技术》讲义.
EBNF 请用扩展的 BNF 描述 C语言里语句的结构; 请用扩展的 BNF 描述 C++语言里类声明的结构;
第二章 矩阵(matrix) 第8次课.
语法分析在编译程序中的逻辑位置 语 法 分 析 表 处 理 源 程 序 词 法 分 析 语 义 分 析 中 间 代 码 生 成 中 间 代
语言及其文法.
第四章 语法分析.
第二章 高级语言及其语法描述 常用的高级语言 FORTRAN 数值计算 COBOL 事务处理 PASCAL 结构程序设计
管理信息结构SMI.
Part5语法分析 授课:胡静.
元素替换法 ——行列式按行(列)展开(推论)
第2次课 上下文无关文法
第一单元 初识C程序与C程序开发平台搭建 ---观其大略
第3章 文法和语言.
§2 求导法则 2.1 求导数的四则运算法则 下面分三部分加以证明, 并同时给出相应的推论和例题 .
第二章 Java语言基础.
第三章 文法和语言 本章目的为语言的语法描述寻求工具,以便: 对源程序给出精确无二义的语法描述。(严谨、简洁、易读)
《编译原理与技术》 期末复习 计算机科学与技术学院 郑启龙 李 诚 25/12/2018.
第三章 语法分析 自顶向下语法分析思想 语法分析方法的分类: 自顶向下语法分析方法(Top-Down) ,亦称面向目标的分析方法;
语法分析 本章内容 语法分析器:把词法分析生成的词法单元流翻译成语法分析树(parse tree)
第3,4次课 一个简单的语法制导翻译器 2.3~2.5.
第一章 函数与极限.
第2章 高级语言及其语法描述 2.1 程序语言的定义 2.2 高级语言的一般特征 2.3 程序语言的语法描述.
数列.
C语言程序设计 主讲教师:陆幼利.
EBNF与操作语义 请用扩展的 BNF 描述 javascript语言里语句的结构;并用操作语义的方法描述对应的语义规则
学习目标 1、什么是字符集 2、字符集四个级别 3、如何选择字符集.
实数与向量的积.
文法等价变换 文法的等价 对文法G1和G2,若有:L(G1)=L(G2),则称文法G1和G2等价, 记作:G1=G2. 文法等价变换
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
WPT MRC. WPT MRC 由题目引出的几个问题 1.做MRC-WPT的多了,与其他文章的区别是什么? 2.Charging Control的手段是什么? 3.Power Reigon是什么东西?
复习.
自底向上的语法分析 4.5.
第四章 文法和语言 本章目的 为语言的语法描述寻求工具
成绩是怎么算出来的? 16级第一学期半期考试成绩 班级 姓名 语文 数学 英语 政治 历史 地理 物理 化学 生物 总分 1 张三1 115
第4章 Excel电子表格制作软件 4.4 函数(一).
定理21.9(可满足性定理)设A是P(Y)的协调子集,则存在P(Y)的解释域U和项解释,使得赋值函数v(A){1}。
第九节 赋值运算符和赋值表达式.
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
3.16 枚举算法及其程序实现 ——数组的作用.
1.2 子集、补集、全集习题课.
1.设A和B是集合,证明:A=B当且仅当A∩B=A∪B
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
2.2矩阵的代数运算.
上杭二中 曾庆华 上杭二中 曾庆华 上杭二中 曾庆华.
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
第二节 函数的极限 一、函数极限的定义 二、函数极限的性质 三、小结 思考题.
《离散结构》 二元运算性质的判断 西安工程大学计算机科学学院 王爱丽.
§2 方阵的特征值与特征向量.
主讲教师 欧阳丹彤 吉林大学计算机科学与技术学院
基于列存储的RDF数据管理 朱敏
C++语言程序设计 C++语言程序设计 第一章 C++语言概述 第十一组 C++语言程序设计.
第四节 向量的乘积 一、两向量的数量积 二、两向量的向量积.
§4.5 最大公因式的矩阵求法( Ⅱ ).
编译原理实践 6.程序设计语言PL/0.
最小生成树 最优二叉树.
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
Presentation transcript:

第二章 高级语言及其文法 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为一个四元组: G = (V,T,P,S) V:非终结符(Terminal)集 语法变量(成分)——代表某个语言的各种子结构 T:终结符(Variable)集 语言的句子中出现的字符,V∩T =  S:开始符号(Start Symbol),S∈V 代表文法所定义的语言,至少在产生式左侧出现一次 2017/3/22

文法G的形式定义 P:产生式(Product)集合 α→β,被称为产生式(定义式),读作:α定义为β。其中α∈(V∪T)+,且α中至少有V中元素的一个出现。β∈(V∪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产生的语言(续) L(G)={x|S* x and x∈T*} 文法G可以派生出多少个句子? 文法G的作用——语言的有穷描述 以有限的规则描述无限的语言现象 有限: 产生式集合、终结符集合、非终结符集合 无限: 可以导出无穷多个句子(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.4 文法的分类(Chomsky体系) 根据语言结构的复杂程度(形式语言) 涉及文法的复杂程度、分析方法的选择 反映文法描述语言的能力 如果G满足文法定义的要求,则G是0型文法(短语结构文法PSG: Phrase Structure Grammar )。 L(G)为PSL。 2017/3/22

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

2.上下文无关文法(CFG) 如果对于αβ∈P,均有|β|≥|α|,并且α∈V成立,则称G为2型文法 即:上下文无关文法(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 都是3型文法(正规文法 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型语言(除S→ε); ---其识别系统是线性界限自动机 * α∈V : 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

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

BNF范式——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