第2章程序语言的基本知识精选文档.ppt

第2章程序语言的基本知识本讲稿第一页，共七十页第第 2 章章 程序语言的基本知识程序语言的基本知识符号串的集合符号串的集合文法和语言文法和语言分析树和二义性分析树和二义性形式语言概观形式语言概观2023/4/102本讲稿第二页，共七十页2.1 2.1 符号串的集合符号串的集合字母表字母表字母表是符号的非字母表是符号的非空有穷集合，用空有穷集合，用 表示表示n 符号：可以相互区别的记号（元素）n不同的语言有不同的字母表n英语26个英文字母nPascal语言 AZ,az,09,+,-,*,/,:,；,.,(,),2023/4/103本讲稿第三页，共七十页2.1 2.1 符号串的集合符号串的集合符号串符号串符号串是由字母符号串是由字母表中的符号所组表中的符号所组成的有穷序列成的有穷序列n例如：=a,b 则 a,b,aa,ab,aabba都是上的符号串n是任何上的符号串n在语言理论中，符号串又称为在语言理论中，符号串又称为:句子、字句子、字2023/4/104本讲稿第四页，共七十页2.1 2.1 符号串的集合符号串的集合n符号串的长度符号串的长度n符号串中包含符号的个数n符号串 s 的长度记为|s|例，对于字母表a,b,c，aab 是其上的一个符号串，|aab|=3 注意：空符号串，|=02023/4/105本讲稿第五页，共七十页2.1 2.1 符号串的集合符号串的集合n符号串的前缀、后缀、子串符号串的前缀、后缀、子串后缀：后缀：删去符号串 s 头部的零个或多于零个符号得到的符号串前缀：前缀：移走符号串 s 尾部的零个或多于零个符号得到的符号串 2023/4/106本讲稿第六页，共七十页2.1 2.1 符号串的集合符号串的集合n符号串的真前缀、真后缀和真子串符号串的真前缀、真后缀和真子串非空非空n子串：子串：从 s 中删去一个前缀和一个后缀得到的符号串 *对于每个符号串s，s 和两者都是符号串 s 的前缀、后缀和子串2023/4/107本讲稿第七页，共七十页2.1 2.1 符号串的集合符号串的集合n符号串的运算：符号串的运算：n连接：连接：符号串、的连接，是把 的符号写在 的符号之后得到的符号串 n如=ab,=cd 则 =abcd n注：=n方幂：方幂：符号串自身连接 n 次得到的符号串nn 定义为 n 个n1=,2=，注：0=2023/4/108本讲稿第八页，共七十页2.1 2.1 符号串的集合符号串的集合例例:汉语所有符合汉语语法的句子构成的集合 PASCAL语言所有合法的 PASCAL 程序构成的集合n注意：空集 、和 的不同语言语言某个字母表上的某个字母表上的符号串的集合符号串的集合2023/4/109本讲稿第九页，共七十页2.1 2.1 符号串的集合符号串的集合n语言的运算：语言的运算：n语言是符号串的集合，集合的运算有并、交、差等n并运算并运算 等同于集合的并运算2023/4/1010本讲稿第十页，共七十页2.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=2023/4/1011本讲稿第十一页，共七十页2.1 2.1 符号串的集合符号串的集合n*闭包闭包（Kleene 闭包）nL*=L0L1L2L3 n+闭包闭包（正闭包）nL+=L1L2L3nL*=L+2023/4/1012本讲稿第十二页，共七十页2.1 2.1 符号串的集合符号串的集合注意注意:后面通常是考虑字母表的*闭包和+闭包n例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,2023/4/1013本讲稿第十三页，共七十页2.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+2023/4/1014本讲稿第十四页，共七十页2.2 2.2 文法和语言文法和语言n如何来描述一种语言？如何来描述一种语言？n如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示n如果语言是无穷的，找出语言的有穷表示。2023/4/1015本讲稿第十五页，共七十页2.2 2.2 文法和语言文法和语言语言有穷表示的两个途经*文法即是以生成方式描述语言的生成方式生成方式语言中的每个句语言中的每个句子可以用严格定子可以用严格定义的规则来构造义的规则来构造2023/4/1016本讲稿第十六页，共七十页2.2 2.2 文法和语言文法和语言*自动机即是以识别方式描述语言的识别方式识别方式用一个过程，当输入的一任意串属于用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会语言时，该过程经有限次计算后就会停止并回答停止并回答“是是”，若不属于，要么，若不属于，要么能停止并回答能停止并回答“不是不是”，（要么永远，（要么永远运行下去）运行下去）2023/4/1017本讲稿第十七页，共七十页2.2 2.2 文法和语言文法和语言n一个自然语言的例子一个自然语言的例子规则（文法）规则（文法）句子 主语 谓语 （1）主语 冠词 形容词 名词 （2）冠词the 形容词 grey 谓语 动词 直接宾语 （5）动词 助动词 动词原形 （6）助动词will 动词原形 eat 直接宾语 冠词 名词 （9）名词wolf 名词 goat2023/4/1018本讲稿第十八页，共七十页 句子句子 主语主语 谓语谓语 冠词冠词 形容词形容词 名词名词 谓语谓语 the 形容词形容词 名词名词 谓语谓语 the grey 名词名词 谓语谓语 the grey wolf 谓语谓语 the grey wolf 动词动词 直接宾语直接宾语 .the grey wolf will eat the goat句子可根据规则推导（生成）出来：句子可根据规则推导（生成）出来：The grey wolf will eat the goat分析句子分析句子2023/4/1019本讲稿第十九页，共七十页谓语谓语主语主语冠词冠词形容词形容词名词名词动词动词直接宾语直接宾语句子句子The grey wolf will eat the goat2023/4/1020本讲稿第二十页，共七十页2.2 2.2 文法和语言文法和语言文法文法 G GV VT TV VN NS SP P终结符号集非终结符号集开始符号产生式集合n文法的形式定义文法的形式定义2023/4/1021本讲稿第二十一页，共七十页终结符号集终结符号集 V VT T 代表语言中不可再分的基本符号语言中不可再分的基本符号，如汉语中的汉字、PASCAL语言中的基本字,其中的元素一般用小写字母或数字表示（a,b,c,0,1)2.2 2.2 文法和语言文法和语言2023/4/1022本讲稿第二十二页，共七十页非终结符号集非终结符号集 V VN N 代表语法单位语法单位，如汉语中的语句、段落，PASCAL语言中的语句、表达式、子程序等，其中的元素一般用大写字母表示（A,B,C），或者用尖括号括起一个串来表示2.2 2.2 文法和语言文法和语言2023/4/1023本讲稿第二十三页，共七十页开始符号开始符号 S S 是一个特殊的非终结符号，代表最高级的语法单位最高级的语法单位，S 至少要在一条产生式中作为左部出现2.2 2.2 文法和语言文法和语言2023/4/1024本讲稿第二十四页，共七十页产生式集合产生式集合 P P2.2 2.2 文法和语言文法和语言 产生式（重写规则、生成式），是形如或=的（，）有序对，且V+，V*，其中 V=（VTVN）称为产生式的左部，不能为空称为产生式的右部，可以为空 （如：A ）2023/4/1025本讲稿第二十五页，共七十页2.2 2.2 文法和语言文法和语言例1：文法 G=（VT，VN，S，P）VN=S VT=0,1 P=S0S1,S01 n可以只写出产生式，通过产生式可以得到文法的其它部分n左部相同的产生式可以写在一起，如:S 0S1|012023/4/1026本讲稿第二十六页，共七十页2.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=2023/4/1027本讲稿第二十七页，共七十页2.2 2.2 文法和语言文法和语言推推 导导直接推导直接推导直接归约直接归约归归 约约 如果 A 是 G 的一条产生式，则称用代替A为一步直接推导，记为A A A 2023/4/1028本讲稿第二十八页，共七十页2.2 2.2 文法和语言文法和语言n推导推导是用产生式的右部代替左部，归约归约是用产生式的左部代替右部，归约是推导的逆过程直接推导直接推导直接归约直接归约 用A代替为一步直接归约，记为=A A A 2023/4/1029本讲稿第二十九页，共七十页2.2 2.2 文法和语言文法和语言n推导的长度推导的长度n直接推导的次数n ，长度大于等于 1 的推导n ，长度大于等于 0 的推导n推导的例子：S 0S1 00S11 000111，长度为 3 记为：S 000111 S S2023/4/1030本讲稿第三十页，共七十页2.2 2.2 文法和语言文法和语言最左推导最左推导最右推导最右推导对中的最左非终结符进行展开对中的最右非终结符进行展开2023/4/1031本讲稿第三十一页，共七十页2.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*a2023/4/1032本讲稿第三十二页，共七十页2.2 2.2 文法和语言文法和语言最右归约最右归约最左归约最左归约 最左推导的逆过程是最右归约，即对最右边的可归约串进行归约 最右推导的逆过程是最左归约，即对最左边的可归约串进行归约a*aa*a=a*Fa*F=F*FF*F=T*FT*F=T T=E Ea*aa*a=F*aF*a=T*aT*a=T*FT*F=T T=E E*最左归约称为规范归约2023/4/1033本讲稿第三十三页，共七十页2.2 2.2 文法和语言文法和语言句型句型句子句子 只包含终结符号的句型称为句子。句子是一种特殊的句型。从文法的开始符号出发进行零步或多于零步的推导得到的文法符号串（S ）。句型可以既包含终结符号又包含非终结符号。2023/4/1034本讲稿第三十四页，共七十页2.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 a2023/4/1035本讲稿第三十五页，共七十页2.2 2.2 文法和语言文法和语言n语言的形式定义语言的形式定义n文法 G 推导出的所有句子组成的集合，称为语言语言，记为 L（G）nL（G）=|S ，VT*2023/4/1036本讲稿第三十六页，共七十页2.2 2.2 文法和语言文法和语言n例子：nG1：S A A 0A1 A 01 是由一个或多个 0 开头，后跟同样数目的 1 的符号串构成的集合（语言），可记为：L(G)=0 n 1 n|n 1 2023/4/1037本讲稿第三十七页，共七十页2.2 2.2 文法和语言文法和语言nG2：E idE E+EE E*EE （E）产生的是表达式的集合2023/4/1038本讲稿第三十八页，共七十页2.2 2.2 文法和语言文法和语言nG3：E E+T E T T T*F T F F （E）F id产生的也是表达式的集合2023/4/1039本讲稿第三十九页，共七十页2.2 2.2 文法和语言文法和语言n一个文法对应一个语言，但一个语言可能有若干个文法产生它，这若干个文法是等价的，称为 等价文法等价文法n例 G2 与 G32023/4/1040本讲稿第四十页，共七十页2.2 2.2 文法和语言文法和语言n上下文无关文法能够描述现今程序设计语言的上下文无关文法能够描述现今程序设计语言的大部分语法结构大部分语法结构n算术表达式n赋值语句n条件语句等2023/4/1041本讲稿第四十一页，共七十页2.2 2.2 文法和语言文法和语言n表达式文法：G=(+,*,id,(,),E,E,P)P:E idE E+EE E*EE (E)E 表示算术表达式，id 表示程序的“变量”，该文法定义了由变量，+，*，(和)组成的算术表达式的语法结构，即：变量是算术表达式；若 E1 和 E2 是算术表达式，则 E1+E2，E1*E2 和(E1)也是算术表达式。2023/4/1042本讲稿第四十二页，共七十页2.2 2.2 文法和语言文法和语言n描述一种简单赋值语句的产生式：赋值语句赋值语句 id=En描述条件语句的产生式：条件语句条件语句 if条件then语句 if条件then语句else语句2023/4/1043本讲稿第四十三页，共七十页2.3 2.3 分析树和二义性分析树和二义性n分析树分析树是描述上下文无关文法句型推导的一种直观方法，也称为推导树分析树分析树句型推导句型推导对应关系对应关系2023/4/1044本讲稿第四十四页，共七十页2.3 2.3 分析树和二义性分析树和二义性n为句型推导构造分析树n例子：E TnE E+T E T T T*F T F F （E）F a T*F F*F a*FTT*FFaaE a*a2023/4/1045本讲稿第四十五页，共七十页2.3 2.3 分析树和二义性分析树和二义性n分析树的特性：分析树的特性：n根标识为开始符号n内部结点标识为非终结符号n每一内部结点及其子结点对应一条产生式，该结点是产生式的左部，子结点从左至右排列构成产生式的右部n叶结点从左至右排列构成句型TT*FFaaE2023/4/1046本讲稿第四十六页，共七十页2.3 2.3 分析树和二义性分析树和二义性n分析树与句型推导的关系分析树与句型推导的关系n一次推导（不是一个句型）对应一棵分析树n一棵分析树可能对应若干个推导n例如下面的推导对应的也是上面那棵分析树 E T T*F T*a F*a a*aTT*FFaaE2023/4/1047本讲稿第四十七页，共七十页2.3 2.3 分析树和二义性分析树和二义性n说明分析树没有严格反映推导的顺序n但是一棵分析树对应一个最左推导，也只能对应一个最右推导TT*FFaaE2023/4/1048本讲稿第四十八页，共七十页2.3 2.3 分析树和二义性分析树和二义性对应最左推导分析树对应最右推导分析树2023/4/1049本讲稿第四十九页，共七十页2.3 2.3 分析树和二义性分析树和二义性n分析句型：短语、直接短语、句柄分析句型：短语、直接短语、句柄n如果 S A和 A ，则称是关于 A的，句型的一个短语短语（子树的叶子）SA2023/4/1050本讲稿第五十页，共七十页2.3 2.3 分析树和二义性分析树和二义性例：句型 F*a 的短语TT*FFaEF*anE E+T E T T T*F T F F （E）F aFa2023/4/1051本讲稿第五十一页，共七十页2.3 2.3 分析树和二义性分析树和二义性n如果S A和 A ，则称是关于 A的，句型的一个直接短语直接短语（只有父子两代的子树的叶子）SA2023/4/1052本讲稿第五十二页，共七十页2.3 2.3 分析树和二义性分析树和二义性例：句型 F*a 的直接短语TT*FFaEFa2023/4/1053本讲稿第五十三页，共七十页2.3 2.3 分析树和二义性分析树和二义性n最左直接短语称为句柄句柄n最左性体现在分析树和句型中SA2023/4/1054本讲稿第五十四页，共七十页2.3 2.3 分析树和二义性分析树和二义性例：句型 F*a 的句柄TT*FFaEF2023/4/1055本讲稿第五十五页，共七十页2.3 2.3 分析树和二义性分析树和二义性n句型的素短语素短语、最左素短语最左素短语1、是关于 A 的，句型的一个短语2、至少含有一个终结符3、除自身外不含更小的带终结符的短语称是关于 A 的，句型的一个素短语素短语n句型最左边的素短语称为最左素短语最左素短语2023/4/1056本讲稿第五十六页，共七十页例：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 （E）F a2023/4/1057本讲稿第五十七页，共七十页2.3 2.3 分析树和二义性分析树和二义性n句子、文法和语言的二义性句子、文法和语言的二义性n如果一个文法的句子有两棵或两棵以上的分析树，称此句子是二义句子是二义的n最左（右）推导与分析树一一对应，句子二义说明它有两个或以上最左（右）推导2023/4/1058本讲稿第五十八页，共七十页2.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）2023/4/1059本讲稿第五十九页，共七十页2.3 2.3 分析树和二义性分析树和二义性n如果一个文法有一个句子是二义的，此文法称为二二义文法义文法nE id E E+E E E*E E （E）2023/4/1060本讲稿第六十页，共七十页2.3 2.3 分析树和二义性分析树和二义性n如果一个语言的所有文法都是二义的，称此语语言是二义言是二义的的n希望文法是无二义的，因为希望对于每一个句子进行唯一确定的分析2023/4/1061本讲稿第六十一页，共七十页2.4 2.4 形式语言概观形式语言概观n乔姆斯基（乔姆斯基（Chomsky）在）在 1956 年提出形式语言理年提出形式语言理论，他将形式文法分为四类论，他将形式文法分为四类(0,1,2,3)，对应四类，对应四类形式语言形式语言(0,1,2,3)n分类的方法是对文法的产生式进行不同的限制分类的方法是对文法的产生式进行不同的限制2023/4/1062本讲稿第六十二页，共七十页2.4 2.4 形式语言概观形式语言概观n0 型文法|0，即 （）n1 型（上下文有关）文法|（）n2 型（上下文无关）文法 A VN，（VTVN）*（A）n3 型（正规）文法nAa 或 AaB（右线性）nAa 或 ABa（左线性）2023/4/1063本讲稿第六十三页，共七十页2.4 2.4 形式语言概观形式语言概观例：例：1 1 型（上下文有关）文法型（上下文有关）文法 文法文法 G G：SCDSCD AbbA AbbACaCACaCABaaBBaaBCbCBCbCBBbbBBbbBADaDADaDCCBDbDBDbDDDAabDAabDL(G)=ww|wa,bL(G)=ww|wa,b*2023/4/1064本讲稿第六十四页，共七十页2.4 2.4 形式语言概观形式语言概观例：例：2 2 型（上下文无关）文法型（上下文无关）文法 文法文法 G G1 1：SaB|bASaB|bAAa|aS|bAAAa|aS|bAABb|bS|aBBBb|bS|aBB 文法文法 G G2 2：S0A|1B|0S0A|1B|0A0A|1B|0SA0A|1B|0SB1B|1|0B1B|1|02023/4/1065本讲稿第六十五页，共七十页2.4 2.4 形式语言概观形式语言概观例：例：3 3 型（正规）文法型（正规）文法 文法文法 G G：S0A|1B|0S0A|1B|0A0A|1B|0SA0A|1B|0SB1B|1|0B1B|1|02023/4/1066本讲稿第六十六页，共七十页2.4 2.4 形式语言概观形式语言概观n0 型文法产生的语言称为 0 型语言n1 型文法或上下文有关文法产生的语言称为 1 型语言或上下文有关语言n2 型文法或上下文无关文法产生的语言称为 2 型语言或上下文无关语言n3 型文法或正则（正规）文法产生的语言称为 3 型语言正则（正规）语言2023/4/1067本讲稿第六十七页，共七十页2.4 2.4 形式语言概观形式语言概观n四种文法（语言）之间的逐级“包含”关系2 型文法（语言）型文法（语言）1 型文法（语言）型文法（语言）0 型文法（语言）型文法（语言）3 型文法（语言）型文法（语言）2023/4/1068本讲稿第六十八页，共七十页2.4 2.4 形式语言概观形式语言概观n识别各类语言的数学模型（自动机）识别各类语言的数学模型（自动机）n图灵机（0 型语言）n有界图灵机、线性有界自动机（1 型语言）n下推自动机（2 型语言）n有限自动机（3 型语言）2023/4/1069本讲稿第六十九页，共七十页The End!The End!2023/4/1070本讲稿第七十页，共七十页