程序语言的基本知识

1、2022-3-211编编 译译 原原 理理杭州电子科技大学杭州电子科技大学2022-3-212第第 2 章章 程序语言的基本知识程序语言的基本知识符号串的集合符号串的集合文法和语言文法和语言分析树和二义性分析树和二义性形式语言概观形式语言概观2022-3-2132.1 2.1 符号串的集合符号串的集合字母表字母表字母表是符号的字母表是符号的非空有穷集合，非空有穷集合，用用 表示表示n 符号：可以相互区别的记号（元素）n不同的语言有不同的字母表n英语26个英文字母nPascal语言 AZ, az, 09, +, -, *, /, , :, , , ；, . , , (, ), , , , 202

2、2-3-2142.1 2.1 符号串的集合符号串的集合符号串符号串符号串是由字母符号串是由字母表中的符号所组表中的符号所组成的有穷序列成的有穷序列n例如： = a , b 则 a, b, aa, ab, aabba都是上的符号串n是任何上的符号串n在语言理论中，符号串又称为在语言理论中，符号串又称为: 句子、字句子、字2022-3-2152.1 2.1 符号串的集合符号串的集合n符号串的长度符号串的长度n符号串中包含符号的个数n符号串 s 的长度记为 |s|例，对于字母表a,b,c，aab 是其上的一个符号串，| aab | = 3 注意：空符号串， | |=02022-3-2162.1 2.

3、1 符号串的集合符号串的集合n符号串的前缀、后缀、子串符号串的前缀、后缀、子串后缀：后缀：删去符号串 s 头部的零个或多于零个符号得到的符号串前缀：前缀：移走符号串 s 尾部的零个或多于零个符号得到的符号串 2022-3-2172.1 2.1 符号串的集合符号串的集合n符号串的真前缀、真后缀和真子串符号串的真前缀、真后缀和真子串非空非空n子串：子串：从 s 中删去一个前缀和一个后缀得到的符号串 * 对于每个符号串s， s 和两者都是符号串 s 的前缀、后缀和子串2022-3-2182.1 2.1 符号串的集合符号串的集合n符号串的运算：符号串的运算：n连接：连接：符号串、的连接，是把 的符号写

4、在 的符号之后得到的符号串 n如 = ab, = cd 则 = abcd n注： = = n方幂：方幂：符号串自身连接 n 次得到的符号串nn 定义为 n 个n1 =, 2 =，注：0 =2022-3-2192.1 2.1 符号串的集合符号串的集合例例: : 汉语所有符合汉语语法的句子构成的集合 PASCAL语言所有合法的 PASCAL 程序构成的集合n注意：空集 、 和 的不同语言语言某个字母表上的某个字母表上的符号串的集合符号串的集合2022-3-21102.1 2.1 符号串的集合符号串的集合n语言的运算：语言的运算：n语言是符号串的集合，集合的运算有并、交、差等n并运算并运算 等同于集

5、合的并运算2022-3-21112.1 2.1 符号串的集合符号串的集合n连接连接n两个符号串集合 L 和 M 的乘积定义为： LM = st | s L 且 t M 例如：集合 A =ab,cde B =0,1 则 AB = ab1,ab0,cde0,cde1 n L = L = L nL L L = Ln L0 = 2022-3-21122.1 2.1 符号串的集合符号串的集合n* 闭包闭包（Kleene 闭包）nL* = L0L1L2L3 n+闭包闭包（正闭包）nL+ = L1L2L3nL* = L+ 2022-3-21132.1 2.1 符号串的集合符号串的集合注意注意: 后面通常是考

6、虑字母表的 * 闭包和 + 闭包n例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,2022-3-21142.1 2.1 符号串的集合符号串的集合n综合性的例子综合性的例子：P10 例2.1 L = A , B , C , , Z , a , b , c , , z D = 0 , 1 , , 9 n把 L 和 D 两个字母表看作长度为 1 的符号串集合，即语言1. L D 2. LD 3. L4 4. L* 5. L(L D)* 6. D+2022-3-21152.2 2.2 文法和语言文法和语言n如何来描述一种语言？如

7、何来描述一种语言？n如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示n如果语言是无穷的，找出语言的有穷表示。2022-3-21162.2 2.2 文法和语言文法和语言语言有穷表示的两个途经* 文法即是以生成方式描述语言的生成方式生成方式语言中的每个句语言中的每个句子可以用严格定子可以用严格定义的规则来构造义的规则来构造2022-3-21172.2 2.2 文法和语言文法和语言* 自动机即是以识别方式描述语言的识别方式识别方式用一个过程，当输入的一任意串用一个过程，当输入的一任意串属于语言时，该过程经有限次计属于语言时，该过程经有限次计算后就会停止并回答算后就会停止并回答“是是”

8、，若，若不属于，要么能停止并回答不属于，要么能停止并回答“不不是是”，（要么永远运行下去），（要么永远运行下去）2022-3-21182.2 2.2 文法和语言文法和语言n一个自然语言的例子一个自然语言的例子规则（文法）规则（文法） 句子 主语 谓语 （1） 主语 冠词 形容词 名词 （2） 冠词the 形容词 grey 谓语 动词 直接宾语 （5） 动词 助动词 动词原形 （6） 助动词will 动词原形 eat 直接宾语 冠词 名词 （9） 名词wolf 名词 goat2022-3-2119 句子句子 主语主语 谓语谓语 冠词冠词 形容词形容词 名词名词 谓语谓语 the 形容词形容词 名

9、词名词 谓语谓语 the grey 名词名词 谓语谓语 the grey wolf 谓语谓语 the grey wolf 动词动词 直接宾语直接宾语 . the grey wolf will eat the goat句子可根据规则推导（生成）出来：句子可根据规则推导（生成）出来：The grey wolf will eat the goat分析句子分析句子2022-3-2120谓语谓语主语主语冠词冠词形容词形容词名词名词动词动词直接宾语直接宾语句子句子The grey wolf will eat the goat2022-3-21212.2 2.2 文法和语言文法和语言文法文法 G GV VT

10、 TV VN NS SP P终结符号集终结符号集非终结符号集非终结符号集开始符号开始符号产生式集合产生式集合n文法的形式定义文法的形式定义2022-3-2122终结符号集终结符号集 V VT T 代表语言中不可再分的基本语言中不可再分的基本符号符号，如汉语中的汉字、PASCAL语言中的基本字,其中的元素一般用小写字母或数字表示（a,b,c,0,1) 2.2 2.2 文法和语言文法和语言2022-3-2123非终结符号集非终结符号集 V VN N 代表语法单位语法单位，如汉语中的语句、段落，PASCAL语言中的语句、表达式、子程序等，其中的元素一般用大写字母表示（A,B,C），或者用尖括号括起一

11、个串来表示2.2 2.2 文法和语言文法和语言2022-3-2124开始符号开始符号 S S 是一个特殊的非终结符号，代表最高级的语法单最高级的语法单位位，S 至少要在一条产生式中作为左部出现2.2 2.2 文法和语言文法和语言2022-3-2125产生式集合产生式集合 P P2.2 2.2 文法和语言文法和语言 产生式（重写规则、生成式），是形产生式（重写规则、生成式），是形如如或或=的（的（，）有序对，）有序对，且且VV+ +，VV* *，其中，其中 V=V=（V VT TVVN N）称为产生式的左部，不能为空称为产生式的左部，不能为空称为产生式的右部，可以为空称为产生式的右部，可以为空

12、（如：（如：A A ）2022-3-21262.2 2.2 文法和语言文法和语言例1：文法 G = （VT，VN，S，P） VN = S VT = 0, 1 P = S0S1, S01 n可以只写出产生式，通过产生式可以得到文法的其它部分n左部相同的产生式可以写在一起，如:S 0S1 | 012022-3-21272.2 2.2 文法和语言文法和语言例2：文法 G = （VT，VN，S，P）VN = ，VT = a,b,c,x,y,z,0,1,9P = a, z 0, 9 S = 2022-3-21282.2 2.2 文法和语言文法和语言推推 导导直接推导直接推导直接归约直接归约归归 约约 如

13、果 A 是 G 的一条产生式，则称用代替A为一步直接直接推导推导，记为A A A 2022-3-21292.2 2.2 文法和语言文法和语言n推导推导是用产生式的右部代替左部，归约归约是用产生式的左部代替右部，归约是推导的逆过程直接推导直接推导直接归约直接归约 用A代替为一步直接归约直接归约，记为=A A A 2022-3-21302.2 2.2 文法和语言文法和语言n推导的长度推导的长度n直接推导的次数n ，长度大于等于 1 的推导n ，长度大于等于 0 的推导n推导的例子： S 0S1 00S11 000111，长度为 3 记为：S 000111 S S2022-3-21312.2 2.2

14、 文法和语言文法和语言最左推导最左推导最右推导最右推导对对中的最中的最左左非终结符进行展开非终结符进行展开对对中的最中的最右右非终结符进行展开非终结符进行展开lmrm2022-3-21322.2 2.2 文法和语言文法和语言n例子：表达式文法 E E + T E T T T * F T F F （E） F a最左推导：E T T*F F*F a*F a*a* 最右推导又称为规范推导最右推导：E T T*F T*a F*a a*almlmlmlmlmrmrmrmrmrm2022-3-21332.2 2.2 文法和语言文法和语言最右归约最右归约最左归约最左归约 最左推导的逆过程是最右归约，最左推导

15、的逆过程是最右归约，即对最右边的即对最右边的可归约串可归约串进行归约进行归约 最右推导的逆过程是最左归约，最右推导的逆过程是最左归约，即对最左边的即对最左边的可归约串可归约串进行归约进行归约a a* *a a = = a a* *F F = = F F* *F F = = T T* *F F = = T T = = E Ea a* *a a = = F F* *a a = = T T* *a a = = T T* *F F = =T T = = E E* 最左归约称为规范归约2022-3-21342.2 2.2 文法和语言文法和语言句型句型句子句子 只包含终结符号的句型称为句子。句子是一种特殊

16、的句型。 从文法的开始符号出发进行零步或多于零步的推导得到的文法符号串（S ）。句型可以既包含终结符号又包含非终结符号。2022-3-21352.2 2.2 文法和语言文法和语言n例：在推导E T T*F F*F a*F a*a 中，句型有： E 、T、T*F 、F*F 、a*F 、a*a句子是： a*anE E + T E T T T * F T F F （E） F a2022-3-21362.2 2.2 文法和语言文法和语言n语言的形式定义语言的形式定义n文法 G 推导出的所有句子组成的集合，称为语言语言，记为 L（G）nL（G）=| S ， VT* 2022-3-21372.2 2.2

17、文法和语言文法和语言n例子：nG1： S A A 0A1 A 01 是由一个或多个 0 开头，后跟同样数目的 1 的符号串构成的集合（语言），可记为：L ( G ) = 0 n 1 n | n 1 2022-3-21382.2 2.2 文法和语言文法和语言nG2： E idE E + EE E * EE （E）产生的是表达式的集合2022-3-21392.2 2.2 文法和语言文法和语言nG3： E E + T E T T T * F T F F （E） F id产生的也是表达式的集合2022-3-21402.2 2.2 文法和语言文法和语言n一个文法对应一个语言，但一个语言可能有若干个文法产

18、生它，这若干个文法是等价的，称为 等价文法等价文法n例 G2 与 G32022-3-21412.2 2.2 文法和语言文法和语言n上下文无关文法能够描述现今程序设计语上下文无关文法能够描述现今程序设计语言的大部分语法结构言的大部分语法结构n算术表达式n赋值语句n条件语句等2022-3-21422.2 2.2 文法和语言文法和语言n表达式文法：G = ( +,*,id,(,), E, E, P ) P:E idE E+EE E*EE (E)E 表示算术表达式， id 表示程序的“变量”，该文法定义了由变量，+，*，( 和 ) 组成的算术表达式的语法结构，即： 变量是算术表达式；若 E1 和 E2

19、 是算术表达式，则 E1+ E2，E1*E2 和 (E1) 也是算术表达式。2022-3-21432.2 2.2 文法和语言文法和语言n描述一种简单赋值语句的产生式： 赋值语句赋值语句 id = En描述条件语句的产生式： 条件语句条件语句 if条件then语句 if条件then语句else语句2022-3-21442.3 2.3 分析树和二义性分析树和二义性n分析树分析树是描述上下文无关文法句型推导的一种直观方法，也称为推导树分析树分析树句型推导句型推导对应关系对应关系2022-3-21452.3 2.3 分析树和二义性分析树和二义性n为句型推导构造分析树n例子：E TnE E + T E

20、T T T * F T F F （E） F a T*F F*F a*FTT*FFaaE a*a2022-3-21462.3 2.3 分析树和二义性分析树和二义性n分析树的特性：分析树的特性：n根标识为开始符号n内部结点标识为非终结符号n每一内部结点及其子结点对应一条产生式，该结点是产生式的左部，子结点从左至右排列构成产生式的右部n叶结点从左至右排列构成句型TT*FFaaE2022-3-21472.3 2.3 分析树和二义性分析树和二义性n分析树与句型推导的关系分析树与句型推导的关系n一次推导（不是一个句型）对应一棵分析树n一棵分析树可能对应若干个推导n例如下面的推导对应的也是上面那棵分析树 E

21、 T T*F T*a F*a a*aTT*FFaaE2022-3-21482.3 2.3 分析树和二义性分析树和二义性n说明分析树没有严格反映推导的顺序n但是一棵分析树对应一个最左推导，也只能对应一个最右推导TT*FFaaE2022-3-21492.3 2.3 分析树和二义性分析树和二义性对应最左推导分析树分析树对应最右推导分析树分析树2022-3-21502.3 2.3 分析树和二义性分析树和二义性n分析句型：短语、直接短语、句柄分析句型：短语、直接短语、句柄n如果 S A和 A ，则称是关于 A的，句型的一个短语短语（子树的叶子）SA2022-3-21512.3 2.3 分析树和二义性分析

22、树和二义性例：句型 F * a 的短语TT*FFaEF*anE E + T E T T T * F T F F （E） F aFa2022-3-21522.3 2.3 分析树和二义性分析树和二义性n如果S A和 A ，则称是关于 A的，句型的一个直接短语直接短语（只有父子两代的子树的叶子）SA2022-3-21532.3 2.3 分析树和二义性分析树和二义性例：句型 F*a 的直接短语TT*FFaEFa2022-3-21542.3 2.3 分析树和二义性分析树和二义性n最左直接短语称为句柄句柄n最左性体现在分析树和句型中SA2022-3-21552.3 2.3 分析树和二义性分析树和二义性例：

23、句型 F*a 的句柄TT*FFaEF2022-3-21562.3 2.3 分析树和二义性分析树和二义性n句型的素短语素短语、最左素短语最左素短语1、是关于 A 的，句型的一个短语2、至少含有一个终结符3、除自身外不含更小的带终结符的短语称是关于 A 的，句型的一个素短语素短语n句型最左边的素短语称为最左素短语最左素短语2022-3-2157例：EE+TE+TFTT*Fan句型：T + T * F + an短语： T+T*F+a、 T+T*F、T*F、T（左边）、an直接短语：T、 T*F、an句柄：Tn素短语：T*F、an最左素短语： T*FnE E + T E T T T * F T F F

24、 （E） F a2022-3-21582.3 2.3 分析树和二义性分析树和二义性n句子、文法和语言的二义性句子、文法和语言的二义性n如果一个文法的句子有两棵或两棵以上的分析树，称此句子是二义句子是二义的n最左（右）推导与分析树一一对应，句子二义说明它有两个或以上最左（右）推导2022-3-21592.3 2.3 分析树和二义性分析树和二义性nE E+E id+E id+E*E id+id*E id+id*idnE E*E E+E*E id+E*E id+id*E id+id*idEE+Eid*EEididEE*Eid+EEidid例：nE id E E + E E E * E E （E）20

25、22-3-21602.3 2.3 分析树和二义性分析树和二义性n如果一个文法有一个句子是二义的，此文法称为二义文法二义文法nE id E E + E E E * E E （E）2022-3-21612.3 2.3 分析树和二义性分析树和二义性n如果一个语言的所有文法都是二义的，称此语言是二义语言是二义的的n希望文法是无二义的，因为希望对于每一个句子进行唯一确定的分析2022-3-21622.4 2.4 形式语言概观形式语言概观n乔姆斯基（乔姆斯基（Chomsky）在）在 1956 年提出形式语言年提出形式语言理论，他将形式文法分为四类理论，他将形式文法分为四类 ( 0 , 1 , 2 , 3 )，对应四类形式语言对应四类形式语言 ( 0 , 1 , 2 , 3 )n分类的方法是对文法的产生式进行不同的限制分类的方法是对文法的产生式进行不同的限制2022-3-21632.4 2.4 形式语言概观形式语言概观n0 型文法 | | 0，即 （ ）n1 型（上下文有关）文法 | | | | （ ）n2 型（上下文无关）文法 A VN， （VTVN）* （ A ）n3 型（正规）文法nAa 或 AaB（右线性）nAa 或 ABa（左线性）2022-3-21642.4 2.4