《0文法和语言的基本知识()》由会员分享，可在线阅读，更多相关《0文法和语言的基本知识()（79页珍藏版）》请在金锄头文库上搜索。
1、第二章 文法和语言的基本知识形式语言理论是编译的重要理论 基础。本章主要介绍编译理论中用到 的有关形式语言理论的最基本概念， 重点介绍如何采用形式化的方法描述 程序设计语言。第二章 文法和语言的基本知识q字母表和符号串 q文法和语言的形式定义q短语、直接短语和句柄q语法树和文法的二义性q文法和语言的分类2.0 概 述对程序设计语言的描述是从语法 、语义和语用三个因素来考虑。语法是对语言结构的定义。语用则是从使用的角度去描述 语言。语义是描述了语言的含义。2.0 概 述 例如 赋值语句s2*3.1416*r*(r+h)的非形式化的描述为： 语法：赋值语句由一个变量，后随一个赋 值号“”，再在其后
2、面跟一个表达式构 成。 语义：首先计算语句右部表达式的值，然 后把所得结果送给左部变量中。 语用：赋值语句可用来计算和保存表达式 的值。2.0 概 述这种非形式化的描述,不够清晰 和准确,为了精确定义和描述程序设 计语言,需采用形式化的方法。所谓 形式化的方法,是用一整套带有严格 规定的符号体系来描述问题的方法。形式语言理论是编译的重要理论 基础。重点介绍如何采用形式化的方 法描述程序设计语 言。 2.1 字母表和符号串元素的非空有穷集合。 例如，= a, b, c 1. 字母表根据字母表的定义，是字母表， 它由a、b、c三个元素组成。程序设计语言的字母表=x | x ASCII字符是一个字母
3、表，由0、1两个元素 组成。注意:例如， =0, 1(2) 字母表中的元素, 可以是字母、 数字或其他符号。(1) 字母表中至少包含一个元素。2.1 字母表和符号串字母表中的元素称为符号或称为 字符。 例如，前述例子中2. 符号（字符）a、b、c 是字母表中的符号； 0、1 是字母表中的符号。2.1 字母表和符号串例如，设有字母表= a, b, c 符号的有穷序列称为符号串。符号串总是建立在某个特定字 母表上的且只由字母表上的有穷多 个符号组成。则有符号串 a，b，ab，ba， cba， abc 3. 符号串（字）2.1 字母表和符号串说明: 不包含任何符号的符号串, 称为空符 号串，用表示。
4、符号串中符号的顺序是很重要的。ab和ba是字母表上的 两个不同的符号串。空符号串由0个符号组 成，其长度|=02.1 字母表和符号串2.2 符号串的运算设x和y是符号串，则串xy称为它们 的连结。则XYabc10a，YX10aabc 注意：对任意一个符号串x，1. 符号串的连结例如，设Xabc，Y10a我们有 xxx2.2 符号串的运算 2. 符号串集合的乘积设A和B是符号串的集合, 则A和B 的乘积定义为：集合的乘积是满足于 xA, yB 的所有符号串 xy 所构成的集合。AB=xy | xA, yBA=A=A2.2 符号串的运算 例如：设A= a, b , B= c, d 则AB= ac,
5、 ad, bc, bd 由于对任意的符号串x，总有 x=x=x 所以, 对任意集合A, 我们有:2.2 符号串的运算特别指出的是， 是符号串, 不是 集合，而表示由空符号串 所组 成的集合, 但这样的集合不是空集合 = 。2.2 符号串的运算3. 符号串的幂运算设x是符号串, 则x的幂运算定义为： x0= x1= xx2= xxx3= xxxxn= xx x=x xn- 1(n0) n注意：x0 12.2 符号串的运算例如, 设 xabc 则 x0= x1=abc x2=xx=abcabc2.2 符号串的运算4. 符号串集合的幂运算设A是符号串的集合，则集合A的 幂运算定义为： A0= A1=
6、A A2=AAAn= AA A=AAn-1(n0) n2.2 符号串的运算 例如，设A= a, b ，则 A0= A1=A= a, b A2=AA= aa, ab, ba, bb A3=AAA=A2A = aaa, aab, aba, abb, baa, bab, bba, bbb 2.2 符号串的运算5. 集合A的正闭包A与闭包A*设A是符号串的集合，则A的正闭 包A和A的闭包A*的定义为:A+=A1A2 An A*= A0 A1A2 An =A+2.2 符号串的运算可见,集合A的正闭包表示A上元素a,b 构成的所有符号串的集合,集合A的闭包比 集合A的正闭包多含一个空符号串。例如，设A=
7、a, b , 则：A+= a, b, aa, ab, ba, bb, aaa, aab, A*=, a, b, aa, ab, ba, bb, aaa, aab, 即：闭包为集合中元素的任意组合2.3 文法和语言的形式定义每个形式语言都是某个字母表上按 某种规则构成的所有符号串的集合。 反之，任何一个字母表上符号串的集 合均可定义为一个形式语言。形式语言序列的集合称为形式语言。2.3 文法和语言的形式定义下面用A表示+ ，用式子A0表示 符号串0A或A生 成符号串0，符号 “”读作“生成”或“ 由组成”。则集 合A可表示成： A0 A1 AA0 AA1+=123 = 0, 1, 00, 10,
8、 11, 01, 000, 100, 2.3.1 文法的形式定义 规则是一个符号与一个符号串的 有序对（A,），通常写作： A（或A ) 1. 规则 也称产生式规则的作用是告诉我们如何用规 则中的符号串生成语言中的序列。2.3.1 文法的形式定义 例如，前述例中一组规则 描述的语言序列只可能是由0和1 组成的符号串。A0 A1 AA0 AA12.3.1 文法的形式定义 规则中出现的符号分为两类，一 类是终结符号，另一类是非终结符号 。非终结符号是出现在规则左部能 派生出符号或符号串的那些符号，即 每个非终结符号表示一定符号串的集 合，用大写字母表示或用尖括号把非 终结符号括起来。例如，上例中的
9、A。2.3.1 文法的形式定义 终结符号是不属于非终结符号 的那些符号, 它是组成语言的基本符 号，是一个语言的不可再分的基本符 号，通常用小写字母表示。例如，上例中的0和1。 2.3.1 文法的形式定义 规则的非空有穷集合，通常表示 成四元组VN是规则中非终结符号的集合。VT是规则中终结符号的集合。P 是文法规则的集合。 2. 文法G=VN,VT, P, S 2.3.1 文法的形式定义 S 是一个非终结符号，称为文法 的开始符号或文法的识别符号，它至 少要在一条规则中作为左部出现。由 它开始，识别出我们所定义的语言。 由文法定义可知，文法是对语言 结构的定义和描述，文法四大要素中 关键是规则
10、的集合。 2.3.1 文法的形式定义将它们缩写为：A1 | 2 | | nA1 A2An其中每个i有时也称为是A的一个候选式。为了书写方便，对于若干个左 部相同的规则，如2.3.1 文法的形式定义我们约定： 第一条规则的左部是识别符号。 对文法G不用四元式显示表示，仅只将规则写出。 2.3.1 文法的形式定义G=(VN，VT，P，S )VN=AVT=0，1P: A 0 | 1 | A0 | A1S=A前例中描述+的文法是:2.3.2 推导和归约推导：从文法开始符号开始，从文法开始符号开始， 通过产生式的通过产生式的右部取代左部右部取代左部的过程，的过程， 最终产生句子。最终产生句子。规约规约：
11、从给定源语言的句子开：从给定源语言的句子开 始，通过产生式的始，通过产生式的左部取代右部左部取代右部的过的过 程，最终到达开始符号。程，最终到达开始符号。 2.3.2 推导和归约最左推导，每次使用一个规则以其右部取每次使用一个规则以其右部取 代符号串的代符号串的最左非终结符最左非终结符最右推导也称为规范推导，最左规约又称 为规范规约。最右推导，每次使用一个规则以其右部取每次使用一个规则以其右部取 代符号串的代符号串的最右非终结符非终结符注：推导和规约的每一步只能用一 个产生式进行替换。2.3.2 规范推导和规范归约例 设有文法GS: 请给出句子101001的最右、最左推导。 分析 最右推导是指
12、在推导过程中 任何一步 (和是句型)，都是对 中的最右非终结符进行替换。SAB AA0 | 1B B0 | S12.3.2 规范推导和规范归约SABAS1AAB1AA01A1B01 A10011B1001101001句子101001的最右推导为: SAB AA0 | 1B B0 | S12.3.2 推导和归约最左推导是指在推导过程中任何 一步 (和是句型), 都是对的最 左非终结符进行替换。句子101001的最左推导为： SAB AA0 | 1B B0 | S1SAB1BB10B10S110AB1 101BB11010B11010012.3.2 语言的形式定义 (1) 形式上的区别，推导用“”
13、表 示，规则用“”表示 。 (2) 对文法G中任何规则A， 我们有A，即推导的依据是规则 。 注意推导和规则的区别：即表示从0 出发，经 一步或若干步 或者说 使用若干次规则可推导出 n。 2.3.2 语言的形式定义 如果存在一个推导序列： 则我们称这个序列是一个从0至n 的长度为n的推导，记为 0 1 2 n+0 n2.3.2 语言的形式定义 例如 设有文法GE=(E,T,F,i,+,*,(,),P,E)对 i+i*i 有如下推导序列: 我们可记为 其中P为：EE+T | T TT*F | F F(E) | iEE+TT+TF+Ti+Ti+T*F i+F*Fi+i*Fi+i*iEi+i*i+
14、2.3.2 语言的形式定义 广义推导 我们有：0n表示从0出发，经0步或若干步， 可推导出n。*也就是说0n意味着0n或者0=n 。*+EE*Ei+i*i*对上例 EE+T | TTT*F | FF(E) | i2.3.2 语言的形式定义 4. 句型和句子 设有文法GS（S是文法G的开始符号）如果S x, x (VNVT)* 则称符号串x为文法GS的句型。*如果S x, x VT* 则称符号串x为文法GS的句子。*2.3.2 语言的形式定义 例1 设有文法GS： 我们有 : 显然，符号串01、0S1、00S11和 000111 都是文法GS的句型，而01和 000111又是文法GS的句子。 S
15、01 | 0S1 S 01*S 0S1*S 00S11*S 000111*2.3.2 语言的形式定义 例2 设有文法GE： 试证明符号串 (i*i+i) 是文法GE的一 个句子。 分析 只要证明符号串 (i*i+i) 对文法 G 存在一个推导，就可证明符号串 (i*i+i) 是文法GE的一个句子。 EE+E | E*E | (E) | i2.3.2 语言的形式定义 EE+E | E*E | (E) | iE(E)(E+E )(E*E+E)(i*E+E)(i*i+E) (i*i+i)即有 E(i*i+i), 所以符号串(i+i*i)是文法GE的一个句子。 *（2）L(G)是VT* 的子集。即属于VT* 的符 号串 x 不一定属于L(G)。2.3.2 语言的形式定义 5语言 文法GS产生的所有句子的集合称为文法G所定义的语言,记为L(GS)： 由语言定义可知： （1）一旦文法给定，语言
