高级程序设计语言编译原理

第二章高级语言及其语法描述 第二章高级语言及其语法描述 程序设计语言的语法程序设计语言的语义程序设计语言的特点程序设计语言的语法描述 第二章高级语言及其语法描述 任何语言实现的基础是语言的定义 在定义方面 编译程序研制者与一般用户有所不同用户关心语言如何使用开发人员关心文法的定义 他们对哪些构造允许出现更感兴趣 即使一时不能看出某种构造的实际应用 或者判断实现该结构会导致严重的困难 但仍必须严格根据语言的定义实现它 程序语言主要由语法和语义两方面定义 2 1程序语言的定义 第二章高级语言及其语法描述 2 1 1语法 所谓一个语言的语法是指这样的一组规则 用它可以形成和产生一个合适的程序 这些规则一部分称为词法规则 另一部分能称为语法规则 或产生规则 第二章高级语言及其语法描述 几个概念 a 一个语言只是用一个有限字符集作为字母表 b 词法规则是指单词符号的形成规则 单词符号一般包括 各类型的常数 标识符 基本字 算符和界符等 C 语言的语法规则规定了如何从单词符号形成更大的结构 即语法单位或语法范畴 换言之 语法规则是语法单位的形成规则 一般程序语言的语法单位有 表达式 语句 分程序 函数 过程和程序等 第二章高级语言及其语法描述 对于一个语言来说 不仅要给出它的词法 语法规则 而且要定义它的单词符号和语法单位的意义 这就是语义问题 语义是指这样的一组规则 使用它可以定义一个程序的意义 我们采用的方法为 属性文法和基于属性文法的语法制导翻译方法 2 1 2语义 第二章高级语言及其语法描述 程序语言的基本功能是描述数据和对数据的运算 所谓程序 从本质上来说是描述一定数据的处理过程 程序 第二章高级语言及其语法描述 程序设计语言的定义 建立在有限字母集之上的一个符号系统有一定的语法和语义规则语法规则 词法规则和语法规则语义规则 描述语法单位的功能和含义程序设计语言的功能是描述数据和对数据的运算 第二章高级语言及其语法描述 2 2高级语言的一般特性 2 2 1高级语言分类2 2 2程序结构2 2 3数据类型与操作2 2 4语句与控制结构 第二章高级语言及其语法描述 2 2 1高级语言分类 从不同的角度看 对高级程序设计语言有不同的分类方法 如果我们从语言范型分类 当今的大多数程序设计语言可划分为四类 一 强制式语言强制式语言也称过程式语言 其特点是命令驱动 面向语句 一个强制式语言程序由一系列的语句组成 每个浯句的执行引起若干存储单元中的值的改变 这种语言的语法形式通常具有如下形式 语句1 语句2 语句n 许多广为使用的语言 如FORTRAN C Pascal 等等 属于这类语言 第二章高级语言及其语法描述 2 2 1高级语言分类 二 应用式语言与强制式语言不同的是 应用式语言更注重程序所表示的功能 而不是一个语句接一个语句地执行 程序的开发过程是从前面已有的函数出发构造出更复杂的函数 对初始数据集进行操作直至最终的函数可以用于从初始数据计算出最终的结果 这种语言通常的语法形式是 函数n 函数2 函数1 数据 因此 这种语言也称函数式语言 LISP 20世纪50年代末由麻省理工学院为研究人工智能而开发的 和ML 20世纪70年代 由爱丁堡大学开发的一个通用的函数式编程语言 属于这种语言 第二章高级语言及其语法描述 2 2 1高级语言分类 三 基于规则的语言基于规则的语言程序的执行过程是 检查一定的条件 当它满足值 则执行适当的动作 最有代表性的基于规则语言是Prolog 它也称逻辑程序设计语言 因为它的基本允许条件是谓词逻辑表达式 这类语言的语法形式通常为 条件1 动作l条件2 动作2条件n 动作3 第二章高级语言及其语法描述 2 2 1高级语言分类 四 面向对象语言面向对象语言如今已成为最流行 最重要的语言 它主要的特征是支持封装性 继承性和多态性等 把复杂的数据和用于这些数据的操作封装在一起 构成对象 对简单对象进行扩充 继承简单对象的特性 从而设计出复杂的对象 通过对象的构造可以使面向对象程序获得强制式语言的有效性 通过作用于规定数据的函数的构造可以获得应用式语言的灵活性和可靠性 第二章高级语言及其语法描述 2 2 2程序结构 不同程序语言都有各自的程序结构C语言程序可以包含多个函数Pascal支持过程的嵌套定义程序结构的不同 决定了符号表构造方法的不同 第二章高级语言及其语法描述 Pascal是一个允许子程序嵌套定义的语言 programmain procedureP1 procedureP11 begin end begin end procedureP2 begin end begin end 第二章高级语言及其语法描述 程序设计语言支持特定的数据类型与操作 一个数据类型通常包括以下三种要素 a 用于区别这种类型的数据对象的属性b 这种类型的数据对象可以具有的值c 可以作用于这种类型数据对象的操作 2 2 3数据类型与操作 第二章高级语言及其语法描述 一 初等数据类型 基本数据类型 常见的初等数据类型有 a 数值数据b 逻辑数据c 字符数据d 指针类型 不同的数据类型占存储空间不同 表示的数的范围也不相同 第二章高级语言及其语法描述 名字和标识符 标识符 无意义的符号串名字 可以看成是代表一个抽象的存储单元名字的值 名字所代表的单元的内容则认为是此名字的值 名字的属性 一个名字的属性包括类型和作用域 标识符 名字与存储空间的关系 同一标识符可以表示不同的名字 同一名字可以表示不同的存储空间 同一存储空间可以有多个名字 第二章高级语言及其语法描述 二 构造数据类型 a 数组特点 一个数组是由同一类型数据所组成的某种n维矩形结构 每个元素占相同的存储空间下标 沿着每一维的距离称为一个下标 数组元素的命名 数组名 下标确定数组与可变数组 在编译时数组所需的存储空间是否确定数组元素的存储与地址的计算内情向量表 数据类型 数组的维数 下标的变化范围 首地址 设计符号表的构造方法 需要在符号表中存储更多的信息 并需要定义不同的属性文法以便对其语义进行描述 第二章高级语言及其语法描述 b 记录从逻辑上说 记录结构是由已知类型的数据组合起来的一种结构 记录结构是许多程序语言的一类重要的数据结构 第二章高级语言及其语法描述 Pascal语言采用下面形式定义记录 CARD recordNAME array 1 20 ofchar AGE integer MARRIED booleanend 第二章高级语言及其语法描述 多种基本数据类型组成的新的数据类型记录分量的访问 记录名 分量名记录的存放 连续存放记录的长度 每个分量的长度之和记录分量地址的计算 首地址 各分量相对于首地址的偏移 offset 特点 第二章高级语言及其语法描述 如 就CARD而言 NAME AGE MARRIED的相对数OFFSET分别为0 20 24 于是 假定CARD的首地址为a 那么 CARD NAME地址为aCARD AGE地址为a 20CARD MARRIED地址为a 24 第二章高级语言及其语法描述 2 2 4语句与控制结构 表达式数值 关系 逻辑 字符串语句赋值语句控制语句 无条件 条件 循环 过程调用 返回 说明句简单句和复合句 第二章高级语言及其语法描述 一 表达式组成 运算量 亦称操作数 即数据引用或函数调用 和算符组成的 表示形式 前缀式 a bc中缀式 a b c后缀式 abc 第二章高级语言及其语法描述 表达式中的算符 算符的优先级和结合性乘幂 或 一元负 乘 除 加 减 关系符 非 not 或 NOT 与 and或 AND 或 or或 OR 消除文法的二义性 第二章高级语言及其语法描述 算符的代数性质 作用 交换率 结合率和分配率 常常可用来优化目标程序的质量 但是必须注意两点 代数性质引用到什么程度视具体语言的不同而不同 如在ALGOL中把A B C D处理成C D A B 则至少是对ALGOL不够忠实 数学上成立的代数性质在计算机上未必完全成立 如 A B C A B C 在计算机上并不普遍成立 决定了在优化的过程中应采取的优化策略 第二章高级语言及其语法描述 二 语句 从功能上说语句大体可分执行性语句和说明性语句 说明性语句旨在定义不同数据类型的变量或运算 执行性语句旨在描述程序的动作 对不同的语句 编译器的处理方式不同 执行性语句又可分赋值语句 控制语句和输入 输出语句 从形式上说 语句还可分为简单句 复合句和分程序等 根据属性文法的定义进行处理 第二章高级语言及其语法描述 2 3程序语言的语法描述 对于高级程序语言及编译程序而言 语言的语法定义是非常重要的 本节将介绍语法结构的形式描述问题 第二章高级语言及其语法描述 字母表 由若干元素组成的有限非空集合 用 表示 它的每个元素称为一个符号 符号串 由 中的符号所构成的有穷序列 符号串的前缀和后缀及子串 设x是一个符号串 将x的尾 前 部删掉几个字符后形成的符号串 称为x的前 后 缀 从一个符号串中删去他的一个前缀和后缀后所剩下部分称为x的子串 与文法定义相关的几个概念和术语 第二章高级语言及其语法描述 空串 字 不包含符号的序列称为空串 字 记为 用 表示 上的所有符号串的全体 空字也包括在其中 如 若 a b 则 a b aa ab bb aaa 表示不含人何元素的空集 这里要注意 和 的区别 与文法定义相关的几个概念和术语 第二章高级语言及其语法描述 符号串及符号串集合的运算 符号串的连接运算 设x和y是两个符号串 如果将y直接拼接在x之后 称这种操作为符号串的连接 记作 x y符号串的方幂 一个符号串与其自身的n 1的任意连接称为符号串的n次幂 记作 xnxn xn 1 x x xn 1特别地 x0 第二章高级语言及其语法描述 应用举例 第二章高级语言及其语法描述 符号串及符号串集合的运算 字符串集合的和 等价于集合的并运算 设A B是两个符号串的集合 则将集合A B的和记为A B或A B 定义为 A B w w A或w B 符号串集合的连接 的子集U和V中的 连接 积定义为 UV U V 即集合UV中的符号串是由U和V的符号串连接而成的 注意 一般UV VU 但 UV W U VW 第二章高级语言及其语法描述 符号串集合V自身的n次 连接 积记为 Vn VV V Vn 1V VVn 1 n个V 规定V0 V的闭包 令 V V0 V1 V2 称V 是V的闭包 V的正则包 正闭包 正则闭包 记V VV 称V 是V的正则包 即V V1 V2 V3 第二章高级语言及其语法描述 一个例子 有一个字母表 A a b c A0 A1 A2 A3 A A 第二章高级语言及其语法描述 作业 课后练习P353 4 第二章高级语言及其语法描述 文法是描述语言的语法结构的形式规则 即语法规则 所谓上下文无关文法是这样一种文法 它所定义的语法范畴 或语法单位 是完全独立于这种范畴可能出现的环境的 特点 独立性缺点 不能用来描述自然语言 但对于程序语言基本上够用 所以以后凡 文法 一词 若无特殊说明 均指上下文无关文法 2 3 1上下文无关文法 第二章高级语言及其语法描述 引例 例子 对于英文句子 Hegavemeabook 是由如下语法规则产生的 第二章高级语言及其语法描述 由语法规则 推导 出句子的过程 第二章高级语言及其语法描述 推导 过程对应的语法分析树 第二章高级语言及其语法描述 上下文无关文法的定义 一个上下文无关文法G包括四个组成部分 一组终结符号 一组非终结符 一个开始符号 以及一组产生式 形式上定义一个上下文无关文法 是一个四元式 P 第二章高级语言及其语法描述 上下文无关文法的形式定义 形式上定义一个上下文无关文法 是一个四元式 P 其中 是一个非空有限集 它的每一个元素称为终结符号 是一个非空有限集 它的每一个元素称为非终结符号 是一个非终结符号 称为开始符号 P是一个产生式 有限 集合 每个产生式形式是A 其中 A 开始符号S至少必须在某一产生式的左部出现一次 第二章高级语言及其语法描述 上下文无关文法的举例 一个上下文无关文法G Z 是一个四元式 P 其中 a b c Z A B ZP Z AB A aAb B cB c 第二章高级语言及其语法描述 上下文无关文法的定义 所谓终结符号乃是组成语言的基本符号 终结 含义在于是具有独立意义的最小语法单位 即不能再分解了的语法单位 如 He book 如程序语言中的基本字 标识符 常数 算符和界符等 如 a b c 终结符号一般用小写字母表示 第二章高级语言及其语法描述 上下文无关文法 2 所谓非终结符号 也称语法变量 用来代表语法范畴 如 算术表达式 布尔表达式 过程 等 一个非终结符代表一个一定的语法概念 因此非终结符是一个类 或集合 记号 而不是个体记号 非终结符号一般用大写字母表示如 E T F 第二章高级语言及其语法描述 3 开始符号是一个特殊的非终结符号 它代表所定义的语言中我们最感兴趣的语法范畴 上下文无关文法 第二章高级语言及其语法描述 4 产生式 也称为产生规则或简称规则 是定义语法范畴的一种书写规则 一个产生式的形式是A 其中箭头左边的A是一个非终结符 称为产生式的左部符号 箭头右边的 是终结符号或与非终结符号组成的一符号串 称为产生式的右部 或称候选式 上下文无关文法 第二章高级语言及其语法描述 文法简写约定 只写出产生式集合 第一个产生式的左部符号约定为文法的开始符号所有产生式中的大写字母组成文法的非终结符号集 小写字母组成文法的终结符号集 一个上下文无关文法G Z 是一个四元式 P 其中 a b c Z A B ZP Z AB A aAb B cB c G Z Z ABA aAb B cB c 简写 第二章高级语言及其语法描述 产生式实例 变量是一个算术表达式 若E1和E2是算术表达式 E1 E2是算术表达式E1 E2是算术表达式 E1 是算术表达式 E i 第二章高级语言及其语法描述 关于产生式 可能用多个产生式对一个非终结符进行定义E i 定义产生式 可以采用递归的形式直接递归间接递归 第二章高级语言及其语法描述 利用语法规则进行分析的方法 推导 对于当前符号串中的非终结符 用对应的产生式的右部去替换之 构造语法树 文法的开始符号作为根结点 每推导一步 将非终结符作为父结点 对应的产生式的右部作为其孩子结点 第二章高级语言及其语法描述 推导与直接推导 直接推导 仅当A 是一个产生式 有 A 该推导称为直接推导 直接导出 推导的描述形式 任意次推导 至少一次推导 第二章高级语言及其语法描述 句型与句子 假定G是一个文法 S是它的开始符号 如果S 表示从S出发 经0步或若干步可推出 则称 是一个句型 仅含终结符号的句型是一个句子 文法G所产生的句子的全体是一个语言 将它记为L G L G S VT 第二章高级语言及其语法描述 句型与句子 例如 终结符号串 i i i 是文法E E E E E E 的一个句子 因为存在一个从开始符号E至 i i i 的推导 E E E E E E E i E E i i E i i i 而E E E E E 等是文法的句型 第二章高级语言及其语法描述 用文法定义语言的方法 采用推导的方法 从文法的开始符号 利用产生式 对非终结符进行替换 展开 推导出全部句子的集合 第二章高级语言及其语法描述 例2 1考虑一个文法G1 S bAA aA a它定义了一个什么语言呢 解 从开始符号S出发 我们可以推出如下句子 S bA baS bA baA baaS bA baA baa a可以写为 L G1 ban n 1 第二章高级语言及其语法描述 例2 2设有文法G2S P aPbP ba bQaQ ab求语言L G2 解 L G2 ba baba abab ababab 第二章高级语言及其语法描述 例2 3设有文法G3S ABA aA aB bB b求语言L G3 解 L G3 ambn m n 1 第二章高级语言及其语法描述 例2 4构造一个文法G4使L G4 an n 1 解 G4 S aS a 第二章高级语言及其语法描述 例2 5构造一个文法G5使L G5 anb n 1 解 G5 S aS ab 第二章高级语言及其语法描述 例2 6构造一个文法G6使L G6 anbm n 1 m 1 解 G6 S ABA aA aB bB b 第二章高级语言及其语法描述 例2 7构造一个文法G7使L G7 anbn n 0 解 G7 S aSb 第二章高级语言及其语法描述 例2 8 已知语言L anbbn n 1 写出产生L的文法 解 G S S aAbA aAb b如果写成G S S aSb b可不可以 如果写成G S S aSb abb可不可以 第二章高级语言及其语法描述 例2 9 试构造生成语言L anbnci n 0 i 1 的文法解 G Z Z ABA aAb B cB c 第二章高级语言及其语法描述 例2 10 已知语言L x x a b c 且x的排列是对称的 aabcbaa aabbaa 等 写出该语言的文法 解 G Z Z aZa bZb cZc a b c 第二章高级语言及其语法描述 最左 右 推导 最左推导或最右推导 所谓最左推导是指 任何一步 都是对 中的最左非终结符进行替换的 同样 可定义最右推导 对于文法 E E E E E E 关于 i i i 的最左推导 E E E E E E E i E E i i E i i i 第二章高级语言及其语法描述 语法分析树 简称语法树 用来表示推导过程 2 3 2语法分析树与二义性 语法树的构造 语法树的根结点由开始符号所标记 随着推导的展开 当某个非终结符被它的某个候选式所替换时 这个非终结符的相应结点就产生了下一代新结点 每个新结点和其父亲结点间都有一条连线 在一棵语法树生长过程中的任何时刻 所有那些没有后代的端末结点自左至右排列起来就是一个句型 第二章高级语言及其语法描述 语法树示例 例如对于文法E E E E E E 关于 i i i 的推导形成语法树如图 第二章高级语言及其语法描述 语法树的不唯一性 一个句型是否只对应唯一的一棵语法树呢 也就是说它是否只有唯一的一个最左 最右 推导呢 第二章高级语言及其语法描述 语法树的不唯一性 对于文法 E E E E E E 关于 i i i 的最左推导有2个 E E E E i E i E E i i E i i i E E E E E E E i E E i i E i i i 第二章高级语言及其语法描述 E E E E E E 关于 i i i 的语法树 关于 i i i 的语法树也有2棵 第二章高级语言及其语法描述 文法的二义性 二义文法 如果一个文法存在某个句子对应两棵不同的语法树 则称这个文法是二义的 也就是说 若一个文法存在某个句子 它有两个不同的最左 最右 推导 则这个文法是法是二义的 第二章高级语言及其语法描述 文法二义性的几个问题 文法二义不等于语言二义文法的二义性是不可判定的文法的二义性证明 找出一个句子 它有两个不同的最左推导或最右推导文法二义性的消除 给每个产生式定义优先级 第二章高级语言及其语法描述 消除文法二义性示例 一个二义文法E E EE E EE E E i 二义原因分析没有定义运算符优先级和结合性消除方法定义优先级和结合性给每个候选式定义一个优先级引入新的非终结符 建立新的产生式 第二章高级语言及其语法描述 一个二义文法E E EE E EE E E i 一个无二义文法E T E TT F T FF E F i 第二章高级语言及其语法描述 上下文无关文法的几点限制 1 文法中不含任何下面形式的产生式 P P因为这种产生式除了产生二义性外没有任何用处 2 每个非终结符P必须有用处 这一方面意味着 必须存在含P的句型 也就是 从开始符号出发 存在推导S P 另一方面意味着 必须存在终结符串 VT 使得P 也就是 对于P不存在永不终结的回路 第二章高级语言及其语法描述 形式语言分类 乔姆斯基把文法分为四种类型0型1型2型3型0型强于1型 1型强于2型 2型强于3型 这几文法的差别在于对产生式施加不同的限制 第二章高级语言及其语法描述 0型文法 G VT VN S P 是一个0型文法 如果它的每个产生式是这样的结构 VN VT 且至少有一个非终结符 而 VN VT 0型文法也称短语文法0型文法的描述能力相当于图灵机该文法所描述的语言称为0型语言 或者称递归可枚举语言 第二章高级语言及其语法描述 1型文法 特点 产生式的形式为 其中 但S 除外 且S不得出现于任何产生式的右部1型文法又称为上下文有关文法另一种定义形式 A 该文法所描述的语言又称上下文有关语言 第二章高级语言及其语法描述 2型文法 特点 该文法的产生式满足 A A为非终结符 为终结符和非终结符组成的符号串 可以是空串该文法又称为上下文无关文法该文法所描述的语言又称为上下文无关语言 第二章高级语言及其语法描述 3型文法 特点 该文法的产生式满足 A B或A B A为非终结符 为终结符组成的符号串 可以是空串该文法又称为右线性文法 或左线性文法 通称正规文法该文法所描述的语言又称为正规语言 第二章高级语言及其语法描述 四种文法的比较 第二章高级语言及其语法描述 内容回顾 关于文法描述的几个重要概念字母表 字符串 空串 等等字符串的连接 字符串集合的连接 字符串的幂 字符串集合的幂上下文无关文法G VT VN S P 产生式的特点 产生式的形式推导 最左 右 推导 语法树句型与句子文法的二义性形式语言分类 第二章高级语言及其语法描述 作业 1 设有文法G S ABA A0 1BB 0 S1请写出句子101001的最左推导 2 设有文法G S aA aA aS请该文法产生的语言 3 设计一个文法描述语言L a2n b2n n 1 第二章高级语言及其语法描述 例1已知文法G A B C a b c A P 其中产生式P由以下组成 A abcA aBbcBb bBBc CbccbC CbaC aaBaC aa问 此文法是哪种文法 它所描述的语言有何特点 习题 第二章高级语言及其语法描述 解 由于A为开始符 由于A aBbc abBc abCbcc aCbbcc aabbcc语言为 anbncn n 0 第二章高级语言及其语法描述 例2文法G N 为 N D NDD 0 1 2 3 4 5 6 7 8 9G N 的语言是什么 解 N ND NDD NDDDD D D D所以G N 的语言是允许0开头的非负整数 第二章高级语言及其语法描述 例3为只包含数字 加号和减号的表达式 例如9 2 5 3 1 等构造一个文法 解 G S S S D S D DD 0 1 2 3 4 5 6 7 8 9 第二章高级语言及其语法描述 例2文法G N 为 N D NDD 0 1 2 3 4 5 6 7 8 9G N 的语言是什么 解 N ND NDD NDDDD D D D所以G N 的语言是允许0开头的非负整数 第二章高级语言及其语法描述 解 偶数的组成和特点 可以是一位偶数 例如2 4 6 8 可以是多位偶数 首位不能为0 末位只能是0 2 4 6 8 中间为任意G Z F A CNDN NE E E 0 CD 0 AC A BB 1 3 5 7 9A 2 4 6 8 例4试构造文法 该文法可以生成所有不能以0开头的偶数 第二章高级语言及其语法描述 解 奇数的组成和特点 可以是一位奇数 例如1 3 5 7 9 可以是多位奇数 首位不能为0 末位只能是1 3 5 7 9 中间为任意 例5试构造文法 该文法可以生成所有不能以0开头的奇数 G Z F B CNBN NE E E 0