《天津大学编译原理讲义 - Part2高级语言及其语法描述.》由会员分享，可在线阅读，更多相关《天津大学编译原理讲义 - Part2高级语言及其语法描述.（38页珍藏版）》请在金锄头文库上搜索。
1、Part2 高级语言及其语法描述 授课：胡静 内容提要 预备知识形式语言基础 程序语言的定义（语法定义、语义定义） 高级语言的一般特性（程序结构、数据类型和操作、 语句与控制结构） 程序语言的文法 文法的类型 上下文无关文法及其语法树 有关文法实用中的一些说明 预备知识 更多的概念和一些约定 A, B, C, 用来表示非终结符 a, b, c, 表示终结符 , X, Y, Z 可以用来表示终结符或者非终结符 , w, x, y, z 表示终结符号串 , , , , 表示由终结符或非终结符构成的符号串 在产生式A中， A 是产生式的左边(lefthand side,LHS) 是产生式的右边( r
2、ighthand side, RHS) A1|n 表示产生式 A 1 , A n 符号串和符号串集合的运算 符号串和符号串集合的运算 将字符看做符号，则单词就是符号串，单 词集合就是符号串的集合 将单词看做符号，则句子就是符号串，而 所有句子的集合（语言）就是符号串的集 合 程序语言的定义 程序语言的语法定义 所谓一个语言的语法是指这样一组规则，用它可以形 成和产生一个合式的程序。这些规则一部分称为词法 规则则，另一部分称为语法规则（或产生规则） 词法规则：词法规则规定了字母表中哪样的字符串是一 个单词符号，是单词符号的形成规则 语法规则：语言的语法规则规定了如何从单词符号形成 更大的结构（即
3、语法单位），换言之，语法规则是语法 单位的形成规则 程序语言的定义 程序语言的语义定义 所谓一个语言的语义是指这样的一组规则，使用它可 以定义一个程序的意义。这些规则称为语义。 我们将要介绍的是目前大多数编译程序普遍采用的一 种方法，即基于属性文法的语法制导翻译方法，虽然 还不是形式系统，但是比较接近形式化的。 高级语言的一般特征 高级语言的程序结构 程序 子程序或分程序 语句 表达式 数据 引用 算符函数 调用 数据类型和操作 数据类型的要素： 用于区别这种类型的数据对象的属性； 这种类型的数据对象可以具有的值； 可以作用于这种类型的数据对象的操作； 数据类型分类： 初等数据类型：数值数据、
4、逻辑数据、字符数据、指 针类型 数据结构：数组、记录、字符串、表格、栈、队列和 抽象数据类型（Ada通过程序包package提供，其余通 过类class提供） 语句与控制结构 表达式：一个表达式是由运算量（操作数，即数据引 用或函数调用）和算符组成的。 语句：不同程序语言含有不同形式和功能的各种语句 执行语句：描述程序的动作，分为赋值语句、控制语 句、输入/输出语句； 说明性语句：定义各种不同数据类型的变量或运算 从形式上分，语句可以分为简单句、复合句和分程序 等。 文法的直观概念 关于文法的定义 定义3.1 文法G定义为四元组（VN, VT, P, S）。 其中VN为非终结符号（或语法实体，
5、或变量）集；VT为终结符 号集；P为产生式（也称规则）的集合；VN, VT和P是非空有穷集 。S称做识别符号或开始符号，是一个非终结符（S VN），至 少要在一条规则中作为左部出现。 VN和VT不含公共元素，即VNVT=。通常V表示VNVT，V称 为文法G的字母表或字汇表。 例3.1 文法G=（VN，VT，P，S） VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号 文法可以简写，只需要指出开始符号和产生式即可。 关于文法的定义（续） 定义3.2 如是文法G=(VN, VT, P, S)的规则(或说是P中第一 个产生式)，和是V*中的任意符号串，若有符号串v ，w满足
6、：v=，w=，则说v（应用规则）直 接产生w，或说w是v的直接推导。 （v=w） 例：GS： S0S1， S01 S 0S1 00S11 000S111 00001111 G 关于文法的定义（续） 定义3.3 如果存在直接推导的序列：v=w0=w1=w2=wn=w ，(n0)，则称v推导出（产生）w（推导长度为n）。 记做v=+w。 定义3.4 若有v=+w，或v=w，则记做v=*w。 规范推导（最右推导） 最左推导：若规则右端符号串中有两个以上的非终结 符时，先推导左边的。 最右推导：若规则右端符号串中有两个以上的非终结 符时，先推导右边的。 关于文法的定义（续） 定义3.5 设GS是一文法
7、，如果符号串x是从识别符号推导出来的，即有 S=*x，则称x是文法GS的句型。若x只由终结符号组成，则称x 为GS的句子。 定义3.6 文法G所产生的语言定义为集合x | S=*x，其中S为文法的开始 符号，且xVT *。可用L(G)表示该集合。 例：G： S0S1， S01 S 0S1 00S11 000S111 00001111 L(G) = 0n1n | n1 关于文法的定义（续） 定义3.7 若L(G1) = L(G2)，则称文法G1和G2是等价的。 例1：如文法G1A：A0R 与G2S： S0S1 等价 A01 S01 RA1 例2：G1E: E i 与 G2E：E T|E+T等价
8、E E+E T F|T*F E E*E F （E）|i E (E) 文法的类型 Chomsky将文法分为四种类型： 0型文法：对任一产生式，都有(VNVT)+， (VNVT)* 1型文法：对任一产生式，都有|， 仅仅 除外 2型文法：对任一产生式，都有VN ， (VNVT)* 3型文法：任一产生式的形式都为AaB或Aa， 其中AVN ，BVN ，aVT。上述叫做右线性文法， 另有左线性文法，二者等价。 文法的类型举例 1型（上下文有关）文法 文法GS： SCDAbbA CaCABaaB CbCBBbbB ADaD C BDbD D AabD L(G)=ww|wa,b* 文法的类型举例 2型（上
9、下文无关）文法 文法GS：SaB|bA Aa|aS|bAA Bb|bS|aBB 文法GS：S0A|1B|0 A0A|1B|0S B1B|1|0 文法的类型举例 定义标识符的3型（正规）文法 文法GI：I lT I l T lT T dT T l T d 文法和语言 0型文法 0型文法（短语文法）的能力相当于图灵机，可以表征任何递归 可枚举集，而且任何0型语言都是递归可枚举的 1型文法（上下文有关文法） 产生式的形式为1A212，即只有A出现在1和2的上下文 中时，才允许取代A。其识别系统是线性界限自动机。 2型文法（上下文无关文法） 产生式的形式为A，取代A时与A的上下文无关。其识别系 统是不
10、确定的下推自动机。 3型文法（正则文法） 产生的语言是有穷自动机（FA）所接受的集合 上下文无关文法 上下文无关文法有足够的能力描述现今程序设计语言的语法结构 算术表达式 语句 赋值语句 条件语句 读语句 文法G=(E, +,*,I,(,), P, E ifthen P:E i | ifthenelse E E+E E E*E E (E) 上下文无关文法的语法树 用于描述上下文无关文法的句型推导的直观方法 例: GS: SaAS ASbA ASS Sa Aba S a A S S b A b a 句型aabbaa的语法树（推导树） 叶子结点：树中没有子孙的结点。 从左到右读出推导树的叶子标记，
11、所得的句型为推导树的结 果。也把该推导树称为该句型的语法树。 a a 上下文无关文法的语法树 推导过程中施用产生式的顺序 例: GS: SaAS ASbA ASS Sa Aba S a A S S b A a a b a SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa 文法的二义性 最左（最右）推导：在推导的任何一步，其中 、是句型，都是对中的最左（右）非终结符进行替 换 最右推导被称为规范推导。 由规范推导所得的句型称为规范句型 文法的二义性 例：GE: E i E E+E E E*E
12、 E (E) E E + E E * E i i i E E * E i E + E i i 句型 i*i+i 的两个不同的最左推导： 推导1：E E+E E*E+E i*E+E i*i+E i*i+i 推导2：E E*E i*E i*E+E i*i+E i*i+i 文法的二义性 若一个文法存在某个句子对应两棵不同的语法树，则 称这个文法是二义的。或者，若一个文法存在某个句 子有两个不同的最左（右）推导，则称这个文法是二 义的。 部分二义文法可以改造为无二义文法 GE: E i GE：E T|E+T E E+E T F|T*F E E*E F （E）|i E (E) 规定优先顺序（T）和结合律（左递归） Thanks for your time!Thanks for your time! Questions & AnswersQuestions & Answers
