《编译原理：文法和语言》由会员分享，可在线阅读，更多相关《编译原理：文法和语言（59页珍藏版）》请在金锄头文库上搜索。
1、第二章 文法和语言42.1 文法的直观表示42.2 符号和符号串42.3 文法和语言的形式定义42.4文法的类型42.5 上下文无关文法及语法树42.6 句型分析42.7 文法的实用限制 1第2章文法和语言【学习目标】 本章是为语言的语法描述寻求工具 掌握对程序设计语言给出精确、无二义 （严谨、易读）的语法描述的手段之一 文法。 对形式语言的理论有一个初步基础 根据文法的特点指导语法分析过程22.1 文法的直观表示文法：阐明语法的一个工具，也可以说是以有穷的集合 刻画无穷的集合的一个工具。 语言：程序设计语言。 一、语言概述4语言是由符合语法的句子组成的集合。 汉语-所有符合汉语语法的句子的全
2、体 英语-所有符合英语语法的句子的全体 程序设计语言-所有该语言的程序的全体 每个句子构成的规律语法4研究语言 每个句子的含义 语义每个句子和使用者的关系语用3形式语言：只考虑语法而不考虑语义的符号语言 。4每种语言具有两个可识别的特性 语言的形式 与该形式相关联的意义4“形式”指语言的所有规则，描述出现什么符号 串4语言可以看成在一个基本符号集上定义的，按 一定规则构成的基本符号串组成的所有集合。4形式语言理论是对符号串集合的表示法、结构 及其特性的研究，是程序设计语言语法分析研 究的基础。44表达语言时，一般无法穷尽语言的所有句子 ，常用规则加以描述 4 例：汉语句子的构成规则：句子=主语
3、谓语主语=代词|名词代词= 我 | 你 | 他名词= 王明 | 大学生 | 工人 | 英语谓语=动词直接宾语动词= 是 | 学习直接宾语=代词|名词二、文法的直观概念5推导：“我是大学生” 是汉语的一个句子 句子 主语 谓语 代词谓语我谓语我动词直接宾语 我是直接宾语我是名词我是大学生 62.2 符号与符号串一、相关概念 程序设计语言是由程序构成的集合，程序是由基 本符号按照一定的规则构成的集合。 1. 符号、字母表和符号串4基本符号：可以相互区别的基本元素，如字母 ，数字，标点符号。4字母表：基本符号的非空有穷集合，常用表 示。例： =0,1， =a, b, c, , x,y, z74符号串
4、：由字母表中的符号构成的任何有穷序 列称为符号串。符号串中的符号是有顺序的。例如 =0,1上的符号串0, 1, 00, 01, 11, 10 注意：表示空符号串,它表示不包含任何 符号串，不是空格符。符号串集合：字母表上若干个符号串组成的集合. 例：字母表=0,1 的符号串集合A=1, 00, 01; 约定：小写字母 a,b,r表示符号.小写字母 s,t,z表示符号串;84符号串s的头（前缀）和尾（后缀） ： 如果s=xy是一符号串，那么x是s的头，y 是s的尾。若x是非空，则y是固有尾；若y 非空，则x是固有头。 前缀：移走符号串s尾部的零个或多个符 号得到的串。 如：设s=abc,那么s的
5、前缀 是，a，ab，abc 后缀：移走符号串s头部的零个或多个符 号得到的串。 如：s =abc的后缀是，c ，bc，abc，s的固有尾是，c，bc。4 94符号串s的子串： 从s中删去任何前缀或后缀得到的串. 如:bc是符号串abc的一个子串.4对符号串s， s和两者都是符号串s的 前缀、后缀和子串。4符号串s的真前缀，真后缀，真子串： 任何非空符号串 x，是s的前缀，后缀 或子串，并且 s x102.符号串的运算(1)符号串相等：符号串x，y，如果两者诸符号依次相等，则 两符号串相等。 (2)符号串的长度：符号串中包含符号的个数。 |abc|=3；| |=0； (3)符号串的连结： x=a
6、bc，y=def 则xy=abcdef；yx=defabc； xy yx x=x =x；11(4)符号串集合的乘积：设A、B为两个符号串集合，其乘积为 AB=xy|x A，yB； 例：A=aa，bb，B=cc，dd，则 AB=aacc，aadd，bbcc，bbdd A=A =A； (5)空集： 不含任何元素的集合称为空集。记为； 对任何集合A：A = A= ; 注意： 12(6)符号串的方幂：x是字母表上的符号串，则x的幂运算为： x0= ; x1= x; x2= xx; xn= xn-1x=x xn-1 (n0) xn表示n个x相连结。 eg：x=ok；则 x0= ; x1= ok; x2=
7、 okok; (7)符号串集合的方幂： A为符号串集合，则A的幂运算为： A0=; A1=A; A2=AA;. An= An-1A=AAn-1;(n0)A=aa，bb，则A0=； A1=aa，bb；A2=AA=aaaa，aabb，bbaa，bbbb;.13(8)符号串集合的闭包和正闭包 集合A的闭包表示为A*（亦称为自反闭包或 星闭包）定义为： A*=A0 A1 A2 A3 =Ak， k0 正闭包表示为A+具体定义为 A+=A1 A2 A3 =Ak， k1 由定义可以看到A*= A0 A+例：=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aa
8、a,aab,143、语言(1)由一组符号所构成的集合。即： 字母表上的 每个语言是*的一个子集。 例如：字母表=a,b， *=,a,b,aa,ab,ba,bb,aaa,aab, 集合ab,aabb,aaabbb,anbn, 或表示 为w|w*且w=anbn,n1为字母表上的 一个语言。 集合a,aa,aaa, 或表示为w|w*， 且w=an，n1 为字母表上的一个语言。 (2) 是一个语言。 (3) 即 是一个语言。152.3 文法和语言的形式定义如何来描述一种语言？ 如果语言是有穷的（只含有有穷多个句子），可以 将句子逐一列出来表示 如果语言是无穷的，找出语言的有穷表示。语言的 有穷表示有两
9、个途径：生成方式 （文法）：语言中的每个句子可以用严 格定义的规则来构造。 识别方式（自动机）：用一个过程，当输入的一 个任意串属于语言时，该过程经有限次计算后就 会停止并回答“是”，若不属于，要么能停止并回 答“不是”，（要么永远继续下去。）16一、规则（重写规则、产生式或生成式）4规则是形如或=的(，)有序对， 其 中 V+， V*中的一个符号 称为规则的左部 称作规则的右部。4例： 4文法可利用规则来描述。17二、文法的定义1、文法G定义为四元组(VN，VT，P，S )其中 VN ：非终结符号；VT：终结符号集；P：规 则集合；VN，VT和P是非空有穷集。 S：开始符或识别符，是一个非终
10、结符，至少 要在一条规则的左部出现。 VN VT = ，V=VN VT ，V称为文法G的字母表例1：文法G = (VN，VT，P，S)， 其中 VN=S，VT=0，1，P=S0S1，S01。18文法G习惯上只将规则写出。 如例1还可以写成：G：S0S1S01或GS：S0S1S01或GS：S0S1 | S0119总结一个文法的几种写法 G=(S,A，a,b，P，S)其中P：SaAb Aab AaAb A G：SaAb Aab AaAb A GS： S aAb Aab AaAb A GS： SaAb Aab |aAb |20三、推导的定义用文法定义语言的中心思想是：从文法的开始符号出发 ，反复使用
11、合适规则，对非终结符施行替换和展开。1、直接推导： 是文法G的产生式，若有v ，w满足：v =，w = , 其中 V*,V*。则称v直接推导到w,或w直接归 约到v记作 vw，2、推导：如果存在直接推导的序列：v=W0 W1 W2 Wn=w,(n0)；称v推导出w(推导长度为n)，或称w归 约到v。 记作v w。 若有v w，或v=w，则记作v w ，(n=0)*21例3：G： S0S1， S010S1 00S1100S11 000S111000S111 00001111 S 0S1 00S11 000S111 00001111 S 00001111S S 00S11 00S11+*2243、
12、规范推导 最左(最右)推导：在推导的任何一步，其 中、是句型，都是对中的最左（右） 非终结符进行替换最右推导被称为规范推导。 例4：GE： EE+T|TTT*F|FF(E)|a EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a（最左推导） EE+T E+T*F E+T*a E+F*a E+a*aT+a*a F+a*a a+a*a （最右推导） 23四、句型、句子和语言的定义1.句型:文法GS，若S x，则称x是G的句型。 2.句子:文法GS，若S x，且xVT*，则称x是 G的句子。句子是句型的特殊，只包含终结符 。 例5：G：S0S1， S01S 0S1 00
13、S11 000S111 00001111G的句型S, 0S1 ,00S11 ,000S111,00001111G的句子000011113.语言:文法G的一切句子的集合, 记为L(G)，* *24例 6 文法GS： （1）SaSBE （2）SaBE （3）EBBE （4）aBab （5）bBbb （6）bEbe （7）eEeeSanBnEn anbnen则 L（G）= anbnen | n1 因为San-1S（BE）n-1 an（BE）n ，继 续推导时，将用规则(3)(7)替换*25S a S BE (SaSBE)a aBEBE (SaBE)aabEBE ( aBab )aabBEE ( EB
14、BE )aabbEE （bBbb)aabbeE （bEbe)aabbee （eEee)G生成的每个串都在L(G)中 L(G)中的每个串确实能被G生成26五、语言和文法4给定一个文法，能从结构上唯一确定其语言4给定一个语言，不能唯一确定其文法，即一 个语言可有多个文法与之对应4已知语言描述，写出文法，应满足： 所描述的语言的任何句子都能由该文法产 生 该文法推导不出不是已知语言的任何句子4已知文法，写出语言描述，应满足： 该文法能推导出的任何句子都包含在所描 述的语言中 描述的语言中不包含该文法推导不出的句 子27六、文法的等价若L（G1）=L（G2），称文法G1和G2是等价的如文法G1A：A0R 与G2S：S0S1 等价A01 S01RA1 作业：P47:1，4，5282.4 文 法 的 类 型一、文法分类通过对产生式施加不同的限制，将文法分为四 类设有文法G=(VN，VT，P，S);40型文法：（短语结构文法）图灵机对任一产生式，都有(VNVT)+，且 至少包含一个非终结符，(VNVT)*41型文法：（上下文有关文法） 对任一产生式，都有|， 仅 仅 S除外。29文法GS是1型文法SaSBC| aBCCB DBDB DCDCBCaBabbBbbbCbccCcc
