《编译原理2.1文法和语言概要》由会员分享，可在线阅读，更多相关《编译原理2.1文法和语言概要（60页珍藏版）》请在金锄头文库上搜索。
1、2.1 文法和语言,0 概述 1 形式语言基础 2 文法的直观理解 3 文法和语言的定义 4 文法的类型 5 语法树与二义性 6 句型的分析,0 概述,显然，用高级语言编程比用低级语言来得方便，但要解决两个问题： 1.计算机怎样懂得高级语言程序，这就需要一个翻译程序实现从源程序到目标程序的转换。 2.用什么方法来精确定义高级语言，即怎样精确描述高级语言。 要构造一个编译程序，应深刻理解被编译的源语言的结构（即词法和语法）及其含义（即语义），同时要弄清源语言的语法规则和语义规则是采用什么理论或什么方法来描述的。,当我们表述一种语言时，无非是要说明这种语言的句子，如果语言只含有穷多个句子，则只需列
2、出句子的有穷集就行了，但对于含有无穷句子的语言来讲，就存在着如何给出它的有穷表示的问题。 以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语。,任何语言均可看作一个集合。这个集合中的每个元素都是在一定符号集（字母表）上的一个符号串。 对于自然语言来说，它们是定义在某个字母表上的句子的集合。 对于程序语言来说，它们也是定义在某个字母表上的句子的集合。 这里的句子，就是一个源程序。 通常，源程序是由关键字、标识符、常数、运算符以及一些界限符组成。 这些语法成分统称为单词或单词符
3、号。 单词符号是语言中具有独立意义的最基本单位。语言的单词符号是由词法规则所确定的，即词法规则规定了单词符号的形成规则。,语言概述,语言是由句子组成的集合，或说是由一组符号串所构成的集合。 汉语所有符合汉语语法的句子的全体 英语所有符合英语语法的句子的全体 程序设计语言所有该语言的源程序的全体,研究程序设计语言 每个程序构成的规律 每个程序的含义 每个程序和使用者的关系,语法 表示构成语言句子的各个记号之间的组合规律。 语义 表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系） 语用 表示在各个记号所出现的行为中，它们的来源、使用和影响。,如果不考虑语义和语用，即只从语法这一侧面来
4、看语言，这种意义下的语言称作形式语言。 形式语言抽象地定义为一个数学系统。 “形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。 形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。,一、 形式语言基础,基本概念: 一、字母表和符号串 1.字母表：符号的非空有限集合 例：=a，b，c 2.符号：字母表中的元素 例： a，b，c 3.符号串：符号的有穷序列 例：a, aa, ac, abc， 特别地,空符号串：无任何符号的符号串(),符号串的形式定义 有字母表，定义： （1）是上的符号串； （2）若x是上的符号串，且a ，则ax或xa是上
5、的符号串； （3）y是上的符号串，当且仅当y可由（1）和（2）产生。,4.符号串集合：由符号串构成的集合。,重要约定： 小写字母 s, t, u, , z 表示符号串 大写字母 A, B, C, , Z 表示符号串集合,二.符号串的运算 1.符号串相等：设 x 、y 是字母表 上的两个符号串，若 x 与 y 的诸符号依次相等，则该两符号串相等，记为 x = y 例：x=ab, y=ba, x=y?,2.符号串长度：设 x 是字母表上的符号串，符号串中包含 符号的个数称为符号串 x 的长度，用 x 表示 例: (1). | abc | = ? (2). | | = ? (3). | a x |
6、= | x a | = | x | + 1 ( a ),3. 符号串的连结：设 x 与 y 是字母表 上的两个符号串， 把 y 的所有符号相继写在 x 的符号之后所得到的符号串 称为x 与 y 的连结，用 x y 表示 注意: | x y | = | x | + | y | x = x = x x y y x ( 一般说来 ),. 若 x = abcd , 则 = ?,4 .符号串的逆：设 x 是字母表 上的符号串，其逆为符号串 x 的倒置，记为 。,(2). = ,5.符号串的前缀、后缀和子串：设 x、y、z 是字母表 上的 符号串，则称 x 为符号串 x y 的前缀，y 是符号 串 x y
7、 的 后缀， x、y 、 z 、xy 、yz 是符号串 x y z 的子串 例: abcd前缀、后缀、子串是什么？,6.符号串集合的乘积：设A、B为两个符号串集合，其乘积为 AB=xy|xA,y B 例: (1). 若 A = ab, cd , B = ef, gh ，AB？ (2). x = x = x A = A = A,7.空集：不含任何元素的集合，记为 注意: (1). A = A = (2). ,8.符号串的幂：设 x 是字母表 上的符号串，则 x 的幂运算 为x 0 = x 1=x x 2=xx x n=x n-1x (xx n-1) 例: 若 x = ab 则: x 0 = ?,
8、 x 1 = ?, x 2 = ?, , x n = ?,9.符号串集合的幂：设 A 是符号串集合，则符号串 A 的幂运 算为： A0= A1=A A2=AA An=A n-1A (AA n-1) 例: 若 A = ab, cd ,则: A 0 = ?, A 1 = ?, A 2 = ?, ,注意: A*=A0A+ A+=AA*=A*A 若 A = a, b 则: A*= , a, b, aa, ab, ba, bb, aaa, A+= a, b, aa, ab, ba, bb, aaa, ,10.符号串集合的闭包运算：设A是符号串集合，定义 A = A1 A2 A3 An 称为集合A的正闭包
9、。 A* = A0 A1 A2 A3 An = A0 A 称为集合A的闭包。,为什么对符号、符号串、符号串集合以及它们的运算感兴趣？ 若A为某语言的基本字符集 Aa,b,z,0,1,9, +,_/, ( , ), = B为单词集 B =begin, end, if, then,else,for, +,_/, ( , ), 则B A* 。 语言的句子是定义在B上的符号串。 若令C为句子集合，则C B * , 程序 C,二、文法的直观理解,1.什么是文法： 文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称为“语法”）。,例：有一句子：“我是大学生” 。这是一个在语
10、法、语义上都正确定句子，该句子的结构（称为语法结构）是由它的语法决定的 。在本例中它为“主谓结构”。,如何定义句子的合法性？ 有穷语言 无穷语言,2.语法规则： 我们通过建立一组规则（产生式），来描述句子 的语法结构。规定用“”或“:=”表示“由组成”。, | 你|我|他 王民|大学生|工人|英语 是|学习 |,由产生式推导句子：, 这种推导一直进行下去，直到所有带的符号都由终结符号替代为止。,有了一组产生式之后，可以按照一定的方式用它们去推导或产生句子。 推导方法：从一个初始的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条产生式去进行推导。, | 你|我|他 王民|大学生
11、|工人|英语 是|学习 |,推导方法：从一个初始的符号 开始推导，即用相应产生式的 右部来替代产生式的左部，每 次仅用一条产生式去进行推导。,例：给定一组语法规则，考察一个句子：“我是大学生”的推导过程。,1文法的定义,三 文法和语言的形式定义,定义1: 文法是产生式的有穷集合,通常定义为四元组: G=（VN，VT，P，S） VN ：非终结符号集 VT ：终结符号集 P：产生式或规则的集合 S：开始符号（识别符号） SVN,VVNVT 称为文法的符号集,产生式：U : x U VN, xV*,其中: 产生式：产生式是一个有序对(U, x), 通常写为: U : x 或U x； | U| = 1
12、 |x| 0 非终结符号：出现在产生式的左部,且能推出符号或符号串的 那些符号。其全体构成非终结符号集，记为VN 。 终结符号：不出现在产生式的左部,且不能推出符号或符号串 的那些符号。其全体构成终结符号集，记为VT 。,P = ； ； ； 0； 1； 9； S = ；,例：无符号整数的文法： G=（VN，VT，P，Z） VN, VT = 0,1,2,3,9,几点说明：,产生式左边符号构成集合VN，且 S VN,文法的BNF表示,例 文法G=（VN，VT，P，S），其中 VN = S ， VT = 0, 1 ， P= S 0S1, S 01 思考：S？,例 文法G=（VN，VT，P，S），其中
13、 VN =标识符，字母，数字 ，S= VT =a,b,c,x,y,z,0,1,9 P a z 0 9 思考：S？,2 推导与归约,定义2： 直接推导：文法G：vx Uy，wxuy, 其中x、y V* ，UVN, u V*, 若U uP，则v w，即x Uy xuy 。 若xy，有U u，则U u,换句话说，x和y是符号串，若使用一次产生式可以从x变换出y，则称x直接推导出y(或者说y是x的直接推导），记为x y。,当符号串已没有非终结符号时，推导就必须终止。,例如：GN： N ND | D D 0| 1| 2| 3| 4| 5| 6| 7| 8| 9, N 109,定义3： +推导：x和y是符
14、号串，若使用若干次产生式可以从x变换出y，则称x推导出y(或者说y是x的推导），记为 x y。,例：,则有：,* N 109,则有：,* N N,直观意义：规范推导最右推导,定义5： 最右推导：若符号串中有两个以上的非终结符时，对推导的每一步坚持把中的最右非终结符进行替换，称为最右推导。 最左推导：若符号串中有两个以上的非终结符时，对推导的每一步坚持把中的最左非终结符进行替换，称为最左推导。,定义6： 推导的逆过程称之为归约。,例：x y,可称为x直接推导出y，也可称为y直接归约出x。, x y ,可称为x推导出y，也可称为y归约出x。,3 语言的形式定义,文法GS所产生的 所有句子的集合,即
15、：句型是由文法开始符号推导出来的 由终结符和非终结符组成的符号串。,即：句子是由文法开始符号推导出来的 由终结符组成的符号串。,例：abna|n1,构造其文法 G1Z： ZaBa, Bb|bB G2Z： ZaBa, Bb|Bb,定义8: G和G是两个不同的文法，若 L(G) = L(G) , 则G和G为等价文法。,编译感兴趣的问题是:,给定x, G, 求x L(G) ?,x,算法1,算法2,x L(G) ?,G,y,n,出错处理,停机,4 递归文法,1.递归产生式：产生式右部有与左部相同的符号 对于 U xUy 若x=,即U Uy，左递归； 若y=,即U xU，右递归；,4. 递归文法的优点：可用有穷条产生式，定义无穷语言,!,3. 左递归文法的
