您好、欢迎来到现金彩票网!
当前位置:2019欢乐棋牌 > 指称语义 >

编译原理Chapt2

发布时间:2019-07-02 07:47 来源:未知 编辑:admin

  编译原理Chapt2_理学_高等教育_教育专区。国防科技大学的编译原理课件 非常好

  第二章 高级语言及其语法描述 数值计算 事务处理 结构程序设计 大型程序、 大型程序、嵌入式实时系统 逻辑程序设计 算法语言 系统程序设计 Internet程序设计 Internet程序设计 常用的高级语言 FORTRAN COBOL PASCAL ADA PROLOG ALGOL C/C++ Java 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 与机器语言或汇编语言比较, 与机器语言或汇编语言比较,高级语言 的优点: 的优点: 较接近于数学语言和工程语言,比较直观、 较接近于数学语言和工程语言,比较直观、 自然和易于理解; 自然和易于理解; 便于验证其正确性,易于改错; 便于验证其正确性,易于改错; 编写效率高; 编写效率高; 易于移植. 易于移植. 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 2.1 程序语言的定义 程序语言由两方面定义: 程序语言由两方面定义: 语法 语义 语用 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 一. 语法 程序本质上是一定字符集上的字符串。 程序本质上是一定字符集上的字符串。 语法:一组规则,用它可以形成和产生一 语法:一组规则, 合式(well-formed)的程序。 的程序。 个合式 的程序 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 语 法 单词符号是语言中具有独立意义的最基本结构。 单词符号是语言中具有独立意义的最基本结构。 一般包括:常数、标识符、基本字、算符、 一般包括:常数、标识符、基本字、算符、界 符等。 符等。 描述工具: 描述工具:有限自动机 词法规则:单词符号的形成规则。 词法规则:单词符号的形成规则。 语法规则:语法单位的形成规则。 语法规则:语法单位的形成规则。 语法单位通常包括:表达式、语句、分程序、 语法单位通常包括:表达式、语句、分程序、 过程、函数、程序等; 过程、函数、程序等; 描述工具: 描述工具:上下文无关文法 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 E→i E→E+E E→E*E E→(E) 语法规则和词法规则定义了程序的的形 式结构。 式结构。定义语法单位的意义属于语义 问题。 问题。 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 二. 语义 语义:一组规则, 语义:一组规则,用它可以定义一个程 序的意义。 序的意义。 描述方法: 描述方法: 自然语言描述:隐藏错误、二义性和不完整 自然语言描述:隐藏错误、 性 形式描述: 形式描述: 操作语义(PL/1) 操作语义(PL/1) 指称语义(ADA) 指称语义(ADA) 代数语义(PASCAL) 代数语义(PASCAL) 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 三.程序语言的基本功能和层次结构 程序语言的基本功能: 程序语言的基本功能:描述数据和对数据 的运算。 的运算。 所谓程序, 所谓程序,本质上说是描述一定数据的处 理过程。 理过程。 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 程序的层次结构 程序 子程序或分程序、过程、 子程序或分程序、过程、函数 语句 表达式 数据引用 算符 函数调用 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 程序语言每个组成成分的逻辑和实现意义 抽象的逻辑的意义 数学意义 计算机实现的意义 具体实现 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 2.2 高级语言的一般特性 高级语言的分类 强制式语言(Imperative Languge)也称过程式语 强制式语言(Imperative Languge)也称过程式语 命令驱动, 言:命令驱动,面向语句 FORTRAN、 FORTRAN、C、Pascal,Ada Pascal, 应用式语言( Language): ):注重程 应用式语言(Applicative Language):注重程 序所表示的功能, 序所表示的功能,而不是一个语句接一个语句地执 行 LISP、 LISP、ML 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 2.2 高级语言的一般特性 2.2.1 高级语言的分类 基于规则的语言(RuleLanguage): ):检查 基于规则的语言(Rule-based Language):检查 一定的条件,当它满足值, 一定的条件,当它满足值,则执行适当的动作 Prolog 面向对象语言(Object-Oriented Language): 面向对象语言(ObjectLanguage): 封装性、继承性和 封装性、继承性和多态性 Smalltalk,C++, Smalltalk,C++,Java 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 2.2 高级语言的一般特性 2.2.2 程序结构 FORTRAN 一个程序由一个主程序段和若干辅程序段组成。 一个程序由一个主程序段和若干辅程序段组成。 辅程序段可以是子程序、函数段或数据块。 辅程序段可以是子程序、函数段或数据块。 每个程序段有一系列的说明语句和执行语句组成。 每个程序段有一系列的说明语句和执行语句组成。 各段可以独立编译。 各段可以独立编译。 模块结构, 模块结构,没有嵌套和递归 各程序段中的名字相互独立, 各程序段中的名字相互独立,同一个标识符在不 同的程序段中代表不同的名字。 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 主程序 PROGRAM … … end 辅程序1 辅程序1 SUBROUTINE … … end 辅程序2 辅程序2 FUNCTION … … end 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 PASCAL PASCAL程序本身可以看成是一个操作系 程序本身可以看成是一个操作系 统所调用的过程,过程可以嵌套和递归。 统所调用的过程,过程可以嵌套和递归。 一个PASCAL过程: 过程: 一个 过程 过程头; 过程头; 说明段(由一系列的说明语句组成); 说明段(由一系列的说明语句组成); begin 执行体(由一系列的执行语句组成); 执行体(由一系列的执行语句组成); end 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 作用域: 作用域:一个名字能被使用的区域范围 称作这个名字的作用域。 称作这个名字的作用域。 允许同一个标识符在不同的过程中代表 不同的名字。 不同的名字。 名字作用域规则-- 最近嵌套原则 -- 名字作用域规则--最近嵌套原则 一个在子程序B1中说明的名字 只在 一个在子程序 中说明的名字X只在 中 中说明的名字 只在B1中 有效(局部于B1); 有效(局部于 ); 如果B2是 的一个内层子程序且 的一个内层子程序且B2中对 如果 是B1的一个内层子程序且 中对 标识符X没有新的说明 则原来的名字X在 没有新的说明, 标识符 没有新的说明,则原来的名字 在 B2中仍然有效。如果 对X重新作了说明, 中仍然有效。 重新作了说明, 中仍然有效 如果B2对 重新作了说明 那么, 对 的任何引用都是指重新说明 那么,B2对X的任何引用都是指重新说明 过的这个X。 过的这个 。 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 A(real) A(integer) B(real) B(bool) program main var A, B : real; … procedure P1 var B:boolean; … begin … end procedure P2 var A:integer; … begin … end begin … 国防科技大学计算机系602教研室 国防科技大学计算机系 教研室 end PASCAL提供了丰富的数据类型和运算 提供了丰富的数据类型和运算 方式, 方式,它允许用户动态地申请和退还存 贮空间。 贮空间。 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 ADA 程序包(package): 把数据和操作代码封装在 : 程序包 一起,支持数据抽象。 一起,支持数据抽象。 一个程序包分为两部分: 一个程序包分为两部分: 可见的规范说明部分, 可见的规范说明部分,它定义了程序包外面可以访 问的对象。 问的对象。 程序包体,它实际定义程序包的实现细节。 程序包体,它实际定义程序包的实现细节。 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 package STACKS is type ELEM is private; type STACK is limited private; procedure push (S: in out STACK; E: in ELEM); procedure pop (S: in out STACK; E: out ELEM); … end STACK; package body STACKS is procedure push(S: in out STACK; E: in ELEM); begin ……实现细节 实现细节 end push; procedure pop (S: in out STACK; E: out ELEM); begin ……实现细节 实现细节 end pop; 国防科技大学计算机系602教研室 国防科技大学计算机系 教研室 end; JAVA Java是一种面向对象的高级语言 是一种面向对象的高级语言 类(Class) ) 继承(Inheritance) 继承 多态性(Polymorphism)和动态绑定 和动态绑定(Dynamic 多态性 和动态绑定 binding) 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 class Car{ int color_number; int door_number; int speed; … push_break ( ) { … } add_oil ( ) { … } } class Trash_Car extends car { double amount; fill_trash ( ) { … } } 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 2.2.3 数据类型与操作 一个数据类型通常包括以下三种要素: 一个数据类型通常包括以下三种要素: 用于区别这种类型数据对象的属性 这种类型的数据对象可以具有的值 可以作用于这种类型的数据对象的操作 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 2.2.3 数据类型与操作 一.初等数据类型 数值类型:整型、实型、复数、双精度, 数值类型:整型、实型、复数、双精度, 运算: 运算:+,-,*,/等 逻辑类型:布尔运算: 逻辑类型:布尔运算:∨,∧,┑ 字符类型: 字符类型:符号处理 指针类型 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 标识符与名字 标识符:以字母开头的, 标识符:以字母开头的,由字母数字组成 的字符串。 的字符串。 标识符与名字两者有本质区别 两者有本质区别: 标识符与名字两者有本质区别: 标识符是语法概念 标识符是语法概念 名字有确切的意义和属性 名字有确切的意义和属性 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 Jordan ? 标识符! ? 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 ? 标识符与名字 名字: 名字: 值:单元中的内容 属性: 属性:类型和作用域 名字的性质的说明方式: 名字的性质的说明方式: 由说明语句来明确规定的 隐含说明: I,J,K,…N 隐含说明:FORTRAN 以I,J,K, N为首的名字 代表整型,否则为实型。 代表整型,否则为实型。 动态确定:走到哪里,是什么,算什么 动态确定:走到哪里,是什么, 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 二 数据结构 逻辑上, 逻辑上,数组是由同一类型数据所组成 的某种n维矩形结构,沿着每一维的距离, 的某种n维矩形结构,沿着每一维的距离, 称为下标 下标。 称为下标。 数组可变与不可变: 数组可变与不可变:编译时能否确定其存贮 空间的大小。 空间的大小。 访问: 访问:给出数组名和下标值 存放方式: 按行存放, 存放方式: 按行存放,按列存放 1 数组 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 数组元素地址计算 数组A[10,20]的A[1,1]为 数组A[10,20]的A[1,1]为a,各维下标 A[10,20] 按行存放,那么A[i j]地址为 A[i, 地址为: 为1,按行存放,那么A[i,j]地址为: a+(i-1)*20+(ja+(i-1)*20+(j-1) 数组元素地址计算公式 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 设A为 d1 × d2 ×L×dn 的n维数组,各维下限 均为 li ,各维上限均为 ui , di = ui ? li +1 ,按行存放,则数组元素 A(i1,i1,L,in ) 的 地址D为: D = a + (i1 ?1 d2 Ldn + (i2 ?1 d3 Ldn ) ) +L+ (in?1 ?1 dn + (in ?1 ) ) = CO NSPART +VARPART 其中: CONSPART = a ? C C = d2 Ldn + d3 Ldn +L+ dn +1 VARPART = i1d2 Ldn + i2d3 Ldn +L+ in?1dn + in = (L((i1d2 + i2 )d3 + i3 )Lin?1)dn + in 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 内情向量 把数组的有关信息记录在一个“ 把数组的有关信息记录在一个“内情向 每个数组的内情向量必须包括: 量”中,每个数组的内情向量必须包括: 维数,各维的上、下限,首地址, 维数,各维的上、下限,首地址,以及 数组(元素)的类型。 数组(元素)的类型。 l1 l2 … ln n type u1 u2 … un C a 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 d1 d2 … dn 2 记录 逻辑上说, 逻辑上说,记录结构由已知类型的数据组 合在一起的一种结构。 合在一起的一种结构。 record { char NAME[20]; integer AGE; bool MARRIED; } CARD[1000] 访问: 访问:复合名存储: 存储:连续存放 域的地址计算: 域的地址计算:相对于记录结构起点的相 对数OFFSET OFFSET。 对数OFFSET。 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 字符串、表格、 3 字符串、表格、栈 字符串:符号处理、 字符串:符号处理、公式处理 表格: 表格:本质上是一种记录结构 线性表:一组顺序化的记录结构 线性表: 栈:一种线性表,后进先出,POP, PUSH 一种线性表,后进先出, 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 三 抽象数据类型 数据对象的一个集合; 数据对象的一个集合; 作用于这些数据对象的抽象运算的集合; 作用于这些数据对象的抽象运算的集合; 这种类型对象的封装, 这种类型对象的封装,即,除了使用类型中所定义 的运算外,用户不能对这些对象进行操作。 的运算外,用户不能对这些对象进行操作。 一个抽象数据类型包括: 一个抽象数据类型包括: 程序设计语言对抽象数据类型的支持 Ada语言通过程序包( package)提供了数据封装 语言通过程序包( 语言通过程序包 ) 的支持 Smalltalk、C++和Java语言则通过类(Class)对 语言则通过类( 、 和 语言则通过类 ) 抽象数据类型提供支持。 抽象数据类型提供支持。 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 2.2.4 语句与控制结构 一.表达式 表达式由运算量(也称操作数, 表达式由运算量(也称操作数,即数据引用或 函数调用)和算符(操作符)组成。 函数调用)和算符(操作符)组成。 形式:中缀、前缀、 形式:中缀、前缀、后缀 X*Y -A P↑ 表达式形成规则 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 算符的优先次序 一般的规定 PASCAL:左结合 PASCAL:左结合A+B+C=(A+B)+C FORTRAN:对于满足左、 FORTRAN:对于满足左、右结合的算符可任 取一种, A+B+C就可以处理成(A+B)+C, 就可以处理成(A+B)+C 取一种,如A+B+C就可以处理成(A+B)+C,也 可以处理成A+(B+C) A+(B+C)。 可以处理成A+(B+C)。 注意两点: 注意两点: 代数性质能引用到什么程度视具体的语言不 同而不同; 同而不同; 在数学上成立的代数性质在计算机上未必完 全成立。 全成立。 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 二.语句 赋值语句: 赋值语句: A := B 名字左值:该名字代表的那个单元(地址) 名字左值:该名字代表的那个单元(地址)称 为该名字的左值。 所代表的存贮单元的地址) 为该名字的左值。(所代表的存贮单元的地址) 右值:一个名字的值称为该名字的右值。 右值:一个名字的值称为该名字的右值。(所 代表的存贮单元的内容) 代表的存贮单元的内容) 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 控制语句: 控制语句: 无条件转移语句 goto L 条件语句 if B then S if B then S1 else S2 循环语句 while B do S repeat S until B for i:=E1 step E2 until E3 do S 过程调用语句 call P(X1, X2, ... ,Xn) 返回语句 return (E) 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 说明语句: 说明语句:定义各种不同数据类型的变量 或运算,定义名字的性质。 或运算,定义名字的性质。 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 简单句和复合句 简单句: 简单句:不包含其他语句成分的基本句 复合句: 复合句:句中有句的语句 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 复习: 复习:程序语言的定义 程序语言由两方面定义: 程序语言由两方面定义: 语法:一组规则, 语法:一组规则,用它可以形成和产生一个合 式(well-formed)的程序 的程序 词法规则:单词符号的形成规则。 词法规则:单词符号的形成规则。 常数、标识符、基本字、算符、界符等。 常数、标识符、基本字、算符、界符等。 有限自动机 语法规则:语法单位的形成规则。 语法规则:语法单位的形成规则。 表达式、语句、分程序、过程、函数、程序等; 表达式、语句、分程序、过程、函数、程序等; 上下文无关文法 语义:一组规则, 语义:一组规则,用它可以定义一个程序的意 义 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 复习: 复习:程序语言的基本功能和层次结构 程序语言的基本功能:描述数据和对数据的运算。 程序语言的基本功能:描述数据和对数据的运算。 所谓程序,本质上说是描述一定数据的处理过程。 所谓程序,本质上说是描述一定数据的处理过程。 程序 子程序或分程序、过程、 子程序或分程序、过程、函数 语句 表达式 数据引用 算符 教研室 函数调用 国防科技大学计算机系602教研室 国防科技大学计算机系 复习: 复习:高级语言的一般特性 高级语言的分类 程序结构 数据类型与操作 初等数据类型 数据结构 抽象数据类型 语句与控制结构 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 2.3 程序语言的语法描述 几个概念: 几个概念: 考虑一个有穷 字母表∑ 考虑一个有穷 字母表∑ 字符集 其中每一个元素称为一个字符 其中每一个元素称为一个字符 上的字 也叫字符串 是指由∑ 字符串) ∑上的字(也叫字符串) 是指由∑中的字符所构 成的一个有穷序列 不包含任何字符的序列称为空字 记为ε 空字, 不包含任何字符的序列称为空字,记为ε 表示∑上的所有字的全体,包含空字ε 用∑*表示∑上的所有字的全体,包含空字ε 例如: 设 ∑={a, b},则 例如: ={a, b}, ∑*={ε,a,b,aa,ab,ba,bb,aaa,...} ={ε,a,b,aa,ab,ba,bb,aaa,...} 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 ∑*的子集 和V的连接(积)定义为 的子集U和 的连接( UV={ αβ α∈U & β∈V } 设: U={ a, aa } V= { b, bb } 那么: 那么: UV= { ab, abb, aab, aabb} 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 ∑*的子集 和V的连接(积)定义为 的子集U和 的连接( UV={ αβ α∈U & β∈V } V自身的 n次积记为 自身的 次积记为 Vn=VV…V 规定V ε , 规定 0={ε},令 V*=V0∪V1∪V2∪V3∪… 称V*是V的闭包 的闭包; 记 V+=VV* ,称V+是V的正规闭包。 的正规闭包。 的正规闭包 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 设: U={ a, aa } 那么: 那么: U* = { ε , a, aa, aaa, aaaa, …} U+ = { a, aa, aaa, aaaa, …} 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 2.3.1 上下文无关文法 文法: 描述语言的语法结构的形式规则 文法: He gave me a book. 主语谓语间接宾语直接宾语 谓语间接宾语直接宾语 句子 → 主语谓语间接宾语直接宾语 句子 主语 代词 主语 → 代词 谓语 动词 谓语 → 动词 间接宾语 代词 间接宾语 → 代词 直接宾语 → 冠词 名词 直接宾语 冠词 名词 名词 代词 代词 → He 代词 代词 → me 名词 名词 → book 冠词 冠词 → a 动词 → gave 动词 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 句子 → 主语 谓语 间接宾语 直接宾语 句子 主语谓语 间接宾语直接宾语 句子 主语 谓语间接宾语 直接宾语 主语 → 代词 主语 代词 主语 代词 谓语 → 动词 谓语 动词 谓语 动词 间接宾语 → 代词 间接宾语 代词 间接宾语 代词 直接宾语 → 冠词 名词 直接宾语 冠词 名词 直接宾语 冠词 名词 代词 → He 代词 代词 代词 → me 代词 代词 句子 句子 句子 名词 → book 名词 名词 主语谓语 间接宾语直接宾语 ?主语 谓语 间接宾语 直接宾语 主语 谓语间接宾语 直接宾语 冠词 → a 冠词 冠词 代词谓语 间接宾语直接宾语 ?代词 谓语 间接宾语 直接宾语 代词 谓语间接宾语 直接宾语 动词 → gave 动词 动词 谓语间接宾语 直接宾语 ?He 谓语 间接宾语 直接宾语 谓语 间接宾语直接宾语 动词间接宾语 直接宾语 ?He 动词 间接宾语 直接宾语 动词 间接宾语直接宾语 间接宾语直接宾语 ?He gave 间接宾语 直接宾语 间接宾语 直接宾语 代词直接宾语 ?He gave 代词 直接宾语 代词 直接宾语 直接宾语 ?He gave me 直接宾语 直接宾语 ?He gave me 冠词 名词 冠词名词 冠词 名词 名词 ?He gave me a 名词 名词 国防科技大学计算机系602教研室 国防科技大学计算机系 教研室 ?He gave me a book 上下文无关文法的定义: 上下文无关文法的定义: 一个上下文无关文法G 一个上下文无关文法G是一个四元式 P), G=(VT,VN,S,P),其中 终结符集合(非空) VT:终结符集合(非空) 非终结符集合(非空) VN:非终结符集合(非空),且VT ∩ VN=? S:文法的开始符号,S∈VN 文法的开始符号, P:产生式集合(有限),每个产生式形式为 产生式集合(有限) P→α, P∈VN, α ∈ (VT ∪ VN)* →α, 开始符S 开始符S至少必须在某个产生式的左部出现 一次。 一次。 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 例,定义只含+,*的算术表达式的文法 定义只含 , 的算术表达式的文法 G={i,+,*,(,)},{E},E, P, 其 , ,,, , , , , 由下列产生式组成: 中,P由下列产生式组成: 由下列产生式组成 E→i E → E+E E → E*E E → (E) 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 几点规定: 几点规定: 定义只含+, 的算术表达式的文法 例,定义只含 ,*的算术表达式的文法 表示, “ → ”也可以用“::=表示, , G={i,+,*,(,)},{E},E, P, 其中, , 也可以用“ , 表示 这种表示称为巴 ,,, , , 其中, 科斯范式(BNF) 科斯范式 P由下列产生式组成: 由下列产生式组成: 由下列产生式组成 P i E → → α1 P → α2 可缩写为 P → α1α2…αn α …α E → E+E … E →→ α P E*En E → ,“”读成“或”,称为 的一个候选式。 其中, 读成“ 称为P的一个候选式 的一个候选式。 其中 (E) 读成 表示一个文法时,通常只给出开始符号和产生式, 表示一个文法时,通常只给出开始符号和产生式, 如上例,可表示为: 如上例,可表示为: G(E): E → i E+E E*E (E) : 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 定义: αγβ, 定义:称α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) ? ? 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 通常, 表示: 出发, 通常,用 α1 ?αn 表示:从α1出发,经过 一步或若干步,可以推出αn。 一步或若干步,可以推出α 表示: 出发,经过0 用 α1 ?αn 表示:从α1出发,经过0步或 若干步,可以推出α 若干步,可以推出αn。 所以 : α ?β 即 α = β 或 * * + α ?β + 定义:假定G是一个文法, 是它的开始符号。 定义:假定G是一个文法,S 是它的开始符号。 * 称是一个句型 句型。 如果 ,则α称是一个句型。仅含终结符 S? α 号的句型是一个句子 文法G 句子。 号的句型是一个句子。文法G所产生的句子的全 体是一个语言 语言, L(G)。 体是一个语言,将它记为 L(G)。 L(G) = { S ? , α ∈V *} α α T 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 + 例: (i*i+i)是文法 是文法 G(E): E → i E+E E*E (E) : 的一个句子。 的一个句子。 证明: 证明: E ? (E) ? (E+E)? (E*E+E)? (i*E+E)? ? ? ? (i*i+E) ? (i*i+i) E,(E),(E*E+E),…,(i*i+i)是句型。 是句型。 , , , , 是句型 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 例:文法G1(A): 文法 : A → cAb G1(A)的语言 的语言? 的语言 L(G1)={c,cb,cbb,…} , , , 开头, 以c开头,后继若干个 开头 后继若干个b 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 例:文法G2(S): 文法 : S → AB A → aAa B → bBb G2(S)的语言 的语言? 的语言 L(G2)={ambnm,n0} , 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 的文法。 例:给出产生语言为{anbnn≥1}的文法。 给出产生语言为 ≥ 的文法 G3(S): : S → aSb S → ab 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 例:给出产生语言为{ambn1≤n≤m≤2n}的 给出产生语言为 ≤ ≤ ≤ 的 文法。 文法。 G4(S): : S → aSb aaSb S → ab aab 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 从一个句型到另一个句型的推导往往不唯 一。 E+E?i+E?i+i E+E?E+i?i+i ? ? ? ? 最左推导:任何一步α ? β都是对α中的最 都是对α 最左推导:任何一步α 左非终结符进行替换。 左非终结符进行替换。 最右推导:任何一步α 都是对α 最右推导:任何一步α ? β都是对α中的最 右非终结符进行替换。 右非终结符进行替换。 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 2.3.2 语法树与二义性 用一张图表示一个句型的推导,称为语法树。 用一张图表示一个句型的推导,称为语法树。 : (i*i+i)的语法树 (i*i+i)的语法树 G(E): E → i E+E E*E (E) (i*i+i) E ?(E) ?(E+E) ?(E*E+E) ?(i*E+E) ?(i*i+E) ?(i*i+i) 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 E ?(E) ?(E+E) ?(E+i) ?(E*E+i) ?(E*i+i) ?(i*i+i) ? 一棵语法树是不同推导过程的共性抽象。 一棵语法树是不同推导过程的共性抽象。 如果使用最左( 如果使用最左(右)推导,则一个最左(右) 推导,则一个最左( 推导与语法树一一对应。 推导与语法树一一对应。 一个句型是否只对应唯一一棵语法树? 一个句型是否只对应唯一一棵语法树? E ( E E i E + E i ) E ( E i E * E i 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 ) E +E i * E i 定义: 定义:如果一个文法存在某个句子对应两 文法是二义的。 颗不同的语法树,则说这个文法是二义的 颗不同的语法树,则说这个文法是二义的。 G(E): E → iE+EE*E(E) 是二义文法。 是二义文法。 : 语言的二义性:一个语言是二义性的 语言是二义性的, 语言的二义性:一个语言是二义性的,如 果对它不存在无二义性的文法。 果对它不存在无二义性的文法。 可能存在G和 ,一个为二义的, 可能存在 和G’,一个为二义的,一个为无二 义的。 义的。但L(G)=L(G’) 二义性问题是不可判定问题, 二义性问题是不可判定问题,即不存在一 个算法,它能在有限步骤内, 个算法,它能在有限步骤内,确切地判定 一个文法是否是二义的。 一个文法是否是二义的。 可以找到一组无二义文法的充分条件。 可以找到一组无二义文法的充分条件。 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 二义文法: 二义文法: G(E): E → iE+EE*E(E) : 无二义文法: 无二义文法: G(E):E → T E+T : T → F T*F F → (E) i 表达式+项 表达式 →项表达式 项 表达式 项 → 因子 项*因子 因子 表达式) 因子 → (表达式 i 表达式 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 考虑句子(i*i+i) 考虑句子 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) E T E ( E T T F * F i E + T F i ) 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 i 描述程序设计语言时, 描述程序设计语言时,对于上下文无关文 法的限制 : 1 不含P→P形式的产生式 不含P 每个非终结符P 2 每个非终结符P必须有用处 即: S ?αPβ * * P?r r ∈V * T 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 2.3.3 形式语言鸟瞰 Chomsky于1956年建立形式语言体系, 于 年建立形式语言体系, 年建立形式语言体系 他把文法分成四种类型: , , , 他把文法分成四种类型:0,1,2,3 型。 与上下文无关文法一样, 与上下文无关文法一样,它们都由四部 分组成,但对产生式的限制有所不同。 分组成,但对产生式的限制有所不同。 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 ? 0型(短语文法,图灵机 : 型 短语文法 图灵机): 短语文法, 产生式形如: 产生式形如: α → β 其中: 其中:α∈ (VT ∪ VN)*且至少含有一个非终结 符;β∈ (VT ∪ VN)* 产生式形如: 产生式形如: α → β 其中: α 其中:α ≤ β,仅 S→ε 例外。 β, →ε 例外。 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 ? 1型(上下文有关文法,线性界限自动机 : 型 上下文有关文法 线性界限自动机): 上下文有关文法, ?2型(上下文无关文法,非确定下推自动机 : 型 上下文无关文法 非确定下推自动机): 上下文无关文法, 产生式形如: 产生式形如: A → β 其中: ∈ 其中:A∈ VN;β∈ (VT ∪ VN)*。 ?3型(正规文法,有限自动机 : 型 正规文法 有限自动机): 正规文法, 产生式形如: A → αB 或 A → α 右线性文法 产生式形如: 其中: 其中: α∈ VT*;A,B∈VN , ∈ 产生式形如: 产生式形如: A → Bα 或 A → α 左线性文法 α 其中: 其中: α∈ VT*;A,B∈VN , ∈ 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 四种类型描述能力比较 0型 1型 2型 3型 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 L5={anbnn≥1} 不能由正规文法产生,但 ≥ 不能由正规文法产生, 可由上下文无关文法产生: 可由上下文无关文法产生: G5(S): : S → aSb ab L6={anbncnn≥1}不能由上下文无关文法产 ≥ 不能由上下文无关文法产 可由上下文有关文法产生: 生,但可由上下文有关文法产生: G6(S): S → aSBC aBC : CB → BC aB → ab bB → bb bC → bc cC → cc 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 程序设计语言不是上下文无关语言, 程序设计语言不是上下文无关语言,甚至 不是上下文有关语言。 不是上下文有关语言。 L7={αcα α∈ α α α∈(ab)*}不能由上下文无关文 不能由上下文无关文 法产生, 法产生,甚至连上下文有关文法也不能产 只能由0型文法产生。 生,只能由0型文法产生。 标识符引用 过程调用过程中, 实参数地对应性( (如 过程调用过程中,形-实参数地对应性(如 个数,顺序和类型一致性) 个数,顺序和类型一致性) 现今程序设计语言的语言结构, 现今程序设计语言的语言结构,用上下文 无关文法描述就足够了。 无关文法描述就足够了。 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系 作业 P36-6,7,8,9,10,11 国防科技大学计算机系602教研室 教研室 国防科技大学计算机系

http://acetechpng.com/zhichenyuyi/158.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有