《ch3-new文法和语言》由会员分享，可在线阅读，更多相关《ch3-new文法和语言（79页珍藏版）》请在金锄头文库上搜索。
1、1,第三章 文法和语言,一个程序设计语言是一个记号系统，它的完整定义包括两个方面： 语法是指一组规则，应用这组规则可以形成和产生一个合适的程序。通常用上下文无关文法作为描述语法的工具. 语义：程序设计语言的语义分为两种： 1）静态语义是一系列限定规则，并确定哪些合乎语法的程序是合适的； 2）动态语义（运行语义或执行语义）表明程序要做什么，要计算什么.,主要内容： 文法和语言、上下文无关文法、句型分析等,2, 3.1 文法的直观概念,文法的直观认识： 如何给出语言的有穷表示？ 语言是由句子组成的，因此，可以用一些规则说明或定义句子的组成结构。,例如：我是大学生 := :=| :=我|你|他 :=
2、王明|大学生|工人|英语 := :=是|学习 :=,这些规则成为判别句子结构合法与否的依据.这些规则看成是一种元语言，这样的语言描述称为文法.,3,应用规则推导句子： = = =我 =我 =我是 =我是 =我是大学生,“=”的含义是使用一条规则代替=左边的某个符号并产生=右端的符号串.,应用这些规则可以产生很多句子.这样，使用文法作为工具，不仅定义了句子的结构，而且通过有穷的规则描述出语言的全部句子.,4,字母表是元素的非空有穷集合,字母表中至少包含一个元素。 字母表中的元素，可以是字母、数字或其他符号。,3.2 符号和符号串 一.字母表 alphabet,【例如】 = a,b,c 是字母表，
3、由a,b,c三个元素组成。,【例如】 = 0,1 是字母表，由0,1两个元素组成。,不同的语言有不同的字母表。,英文的字母表是26个字母、数字和标点符号的集合； C语言的字母表是字母、数字和若干专用符号组成。,任何语言的字母表指出了该语言中允许出现的一切符号。,5,二.符号（字符）symbol,字母表中的元素称为符号，或称为字符。,【例如】 = a,b,c a,b,c是字母表中的符号。,【例如】 = 0,1 0,1是字母表中的符号。,6,三.符号串（字）string,符号的有穷序列称为字符串。,【例如】设有字母表 = a,b,c， 则有符号串 a,b,ab,ba,cba,abc, (a,b,a
4、b,ba,cba,abc等都是字母表上的符号串),符号串总是建立在某个特定字母表上的且只能由字母表上的有穷多个符号组成。,符号串中符号的顺序是很重要的， 如 ab 和 ba 是字母表上的两个不同的符号串。,不包含任何符号的符号串，称为空符号串，用(epsilon)表示，即空符号串由 0 个符号组成，其长度|=0,7,符号串的头尾：如果zxy是一符号串，那么x是z的头，y是z的尾。 如果x是非空的，那么y是固有尾；如果y是非空的，那么x是固有头。 符号串集合：若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。,四.符号串的运算相关概念,例如: zabc，那么z的头是,
5、a, ab, abc. Z的尾是, c, bc, abc.,8,四.符号串的运算 1.符号串的连接 connection,设 x 和 y 是符号串，则串 xy 称为它们的连接。即 xy 是将 y 符号串写在 x 符号串之后得到的符号串。,【例如】设 x abc，y = 10a， 则 xy abc10a 则 yx 10aabc,特别，对任意一符号串 x 有： x x x,9,2.符号串的幂运算 power,设 x 是符号串，则 x 的幂运算定义为： x0 x1 x x2 xx xn xxx = xxn-1 (n0),n,【例如】设 x = abc,则 x0 x1 abc x2 abcabc ,1
6、0,3.集合的乘积 product,设 A 和 B 是符号串的集合，则 A 和 B 的乘积定义为： AB = xy | x A, y B 即集合 AB 中的符号串是由 A 和 B 的符号串连接而成的。,【例如】设 A = a,b,B = c,d 则 AB ac,ad,bc,bd,因为对任意一符号串 x 有： x x x 所以，对任意集合 A，有 A = A = A,11,空集 empty set, 表示不含任何元素的空集 , = ,注意： 是符号串，不是集合，表示由空符号串 所组成的集合，但这样的集合不是空集， 即不包含空串。 (不属于),对任意集合 A，有 A = A = ,12,4.集合的
7、幂运算,设 A 是符号串的集合，则集合 A 的幂运算定义为： A0 A1 A A2 AA An AAA = AAn-1 (n0),n,【例如】设 A = a,b,则 A0 A1 a,b A2 AA = aa,ab,ba,bb A3 AAA = A2A = aaa,aab,aba,abb,baa,bab,bba,bbb ,13,5.集合A的正闭包A+与闭包A*,设 A 是符号串的集合， 则集合 A 的正闭包A+和闭包A*分别定义为： A+ A1 U A2 U A3 U U An U A* A0 U A1 U A2 U A3 U U An U = U A+,【例如】设 A = a,b,则 A+ a
8、,b,aa,ab,ba,bb,aaa,aab, A* ,a,b,aa,ab,ba,bb,aaa,aab,正闭包：Positive closure 闭包 ：Star closure（星闭包）,14,【例如】设 A = a,则 A+ a,aa,aaa, = an | n=1 A* , a,aa,aaa, = an | n=0,A* = A0 A1 A2 A3 ，称 A* 是 A 的闭包。 A+ = AA* ，称 A+ 是A的正则闭包。,*表示上的所有符号串的全体,15,3.3 文法和语言的形式定义,1、规则,规则，也称重写规则、产生式或生成式，是形如或 =的( ，)有序对，其中是字母表V的正闭包V
9、+中的一个符号，是V*中的一个符号。 称为规则的左部， 称作规则的右部。 或 := 表示“定义为”或“生成”，意思是左部符号用右部符号串定义或左部符号生成右部符号串。,16,2 、文法定义,文法G定义为四元组(VN，VT，P，S )其中 VN:非终结符号(或语法实体，或变量)集； VT:终结符号集； P: 规则的集合； VN，VT和P是 非空有穷集。 S:称作识别符号或开始符号的一个非终结符，它至少要在一条产生式中作为左部出现。 VN和VT不含公共的元素，即VN VT = 用V表示VN VT ，称为文法G的字母表或字汇表 规则，也称重写规则、产生式或生成式，是形如或 =的( ，)有序对，其中是
10、字母表V的正闭包V+中的一个符号，是V*中的一个符号。 称为规则的左部， 称作规则的右部。,17,例 文法G=（VN，VT，P，S） VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号,例 文法G=（VN，VT，P，S） VN =标识符，字母，数字 VT =a,b,c,x,y,z,0,1,9 P= a z 0 9 S=,19,文法的写法 元符号: = | 习惯 大写字母表示非终结符 小写字母表示终结符,(1) G：SaAb Aab AaAb A,(2) GS： Aab AaAb A SaSb (3) GS:Aab |aAb | SaSb,20,推导的定义,直接推导“”
11、 是文法G的产生式，若有v,w满足：v=,w= , 其中V*,V* 则称v直接推导到w,记作 v w 也称w直接归约到v 例：G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1,21,推导,. ( . ) . . ( ) VAR;BEGIN READ()END. VAR A;BEGIN READ( ) END. ( A) VAR A;BEGIN READ( ) END. VAR A;BEGIN READ( A) END. ( A),22,若存在v =w0 w1 . wn=w,(n0) 则记为v w，称作v推导出w，或w归约到v
12、 若有v w 或 v=w， 则记为v w,推导的定义,23,例：G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 00S11 000S111 00001111 S 00001111 S S 00S11 00S11,24,句型、句子的定义,句型 有文法G，若S =* x，则称x是文法G的句型。 句子 有文法G，若S =* x，且xVT*，则称x是文法G的句子。 例：G： S0S1， S01 S 0S1 00S11 000S111 00001111 G的句型S,0S1 ,00S11 ,000S111,00001111 G的句子0
13、0001111, 01,25,句型、句子,例：GE： EE+T|T TT*F|F F(E)|a EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a 句子：用符号a，+，*，(和)构成的算术表达式,26,(文法生成的)语言的定义,由文法G生成的语言记为L(G),它是文法G的一切句子的集合: L(G)=x|S =* x，其中S为文法的开始符号，且x VT* 例：G： S0S1， S01 L(G)=0n1n|n1,例 文法GS： （1）SaSBE （2）SaBE （3）EBBE （4）aBab （5）bBbb （6）bEbe （7）eEee L（G）= anbnen |
14、 n1 G生成的每个串都在L(G)中 L(G)中的每个串确实能被G生成,根据1式进行n-1次得到 an-1 S（BE）n-1 由2式an(BE)n 由3式得到anBnEn 由4式得anbBn-1En 由5式n-1次得到anbnEn 由6式1次，7式n-1次得到anbnen,28,文法的等价,若L（G1）=L（G2），则称文法G1和G2是等价的。 如文法G1A：ADB 与G2S：S0S1 等价 ADE S01 EAB D0 B1,29,【例】设计一个表示所有标识符的文法,分析：标识符的定义是字母或以字母开头的字母数字串，其结构如下：,用 I 表示标识符，L 代表字母，D 代表数字，则定义标识符的文法为： G =（VN，VT，P，S） 其中： VN = I,L,D VT = a,b,x,y,z,0,1,2,9 P = IL | IL |ID L a | b | | x | y | z D 0 | 1 | |9 S = I,30,【例】用文法定义一个含+、*的算术表达式。,变量是表达式； 若 E1 和 E2 是算术表达式，则 E1+E2，E1*E2，(E) 也是算术表达式。,算术表达式的文法为： G =（VN，VT，P，S） 其中： VN = E VT = i,+,*,(,) P = E i | E+E
