第2章程序语言的基本知识优秀PPT.ppt

《第2章程序语言的基本知识优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第2章程序语言的基本知识优秀PPT.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章程序语言的基本知识现在学习的是第1页，共70页第第 2 章章 程序语言的基本知识程序语言的基本知识符号串的集合符号串的集合文法和语言文法和语言分析树和二义性分析树和二义性形式语言概观形式语言概观2022/12/52现在学习的是第2页，共70页2.1 2.1 符号串的集合符号串的集合字母表字母表字母表是符号的非字母表是符号的非空有穷集合，用空有穷集合，用 表示表示n 符号：可以相互区别的记号（元素）n不同的语言有不同的字母表n英语26个英文字母nPascal语言 AZ,az,09,+,-,*,/,:,；,.,(,),2022/12/53现在学习的是第3页，共70页2.1 2.1 符号串的集

2、合符号串的集合符号串符号串符号串是由字母表符号串是由字母表中的符号所组成的中的符号所组成的有穷序列有穷序列n例如：=a,b 则 a,b,aa,ab,aabba都是上的符号串n是任何上的符号串n在语言理论中，符号串又称为在语言理论中，符号串又称为:句子、字句子、字2022/12/54现在学习的是第4页，共70页2.1 2.1 符号串的集合符号串的集合n符号串的长度符号串的长度n符号串中包含符号的个数n符号串 s 的长度记为|s|例，对于字母表a,b,c，aab 是其上的一个符号串，|aab|=3 注意：空符号串，|=02022/12/55现在学习的是第5页，共70页2.1 2.1 符号串的集合符

3、号串的集合n符号串的前缀、后缀、子串符号串的前缀、后缀、子串后缀：后缀：删去符号串 s 头部的零个或多于零个符号得到的符号串前缀：前缀：移走符号串 s 尾部的零个或多于零个符号得到的符号串 2022/12/56现在学习的是第6页，共70页2.1 2.1 符号串的集合符号串的集合n符号串的真前缀、真后缀和真子串符号串的真前缀、真后缀和真子串非空非空n子串：子串：从 s 中删去一个前缀和一个后缀得到的符号串 *对于每个符号串s，s 和两者都是符号串 s 的前缀、后缀和子串2022/12/57现在学习的是第7页，共70页2.1 2.1 符号串的集合符号串的集合n符号串的运算：符号串的运算：n连接：连

4、接：符号串、的连接，是把 的符号写在 的符号之后得到的符号串 n如=ab,=cd 则 =abcd n注：=n方幂：方幂：符号串自身连接 n 次得到的符号串nn 定义为 n 个n1=,2=，注：0=2022/12/58现在学习的是第8页，共70页2.1 2.1 符号串的集合符号串的集合例例:汉语所有符合汉语语法的句子构成的集合 PASCAL语言所有合法的 PASCAL 程序构成的集合n注意：空集 、和 的不同语言语言某个字母表上的某个字母表上的符号串的集合符号串的集合2022/12/59现在学习的是第9页，共70页2.1 2.1 符号串的集合符号串的集合n语言的运算：语言的运算：n语言是符号串的

5、集合，集合的运算有并、交、差等n并运算并运算 等同于集合的并运算2022/12/510现在学习的是第10页，共70页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=2022/12/511现在学习的是第11页，共70页2.1 2.1 符号串的集合符号串的集合n*闭包闭包（Kleene 闭包）nL*=L0L1L2L3 n+闭包闭包（正闭包）nL+=L1L2L3nL*=L+2022/12/51

6、2现在学习的是第12页，共70页2.1 2.1 符号串的集合符号串的集合注意注意:后面通常是考虑字母表的*闭包和+闭包n例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,2022/12/513现在学习的是第13页，共70页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+2022/12/514现在学习的是第14

7、页，共70页2.2 2.2 文法和语言文法和语言n如何来描述一种语言？如何来描述一种语言？n如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示n如果语言是无穷的，找出语言的有穷表示。2022/12/515现在学习的是第15页，共70页2.2 2.2 文法和语言文法和语言语言有穷表示的两个途经*文法即是以生成方式描述语言的生成方式生成方式语言中的每个句语言中的每个句子可以用严格定子可以用严格定义的规则来构造义的规则来构造2022/12/516现在学习的是第16页，共70页2.2 2.2 文法和语言文法和语言*自动机即是以识别方式描述语言的识别方式识别方式用一个过程，当输入的一任意串

8、属于用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会语言时，该过程经有限次计算后就会停止并回答停止并回答“是是”，若不属于，要么，若不属于，要么能停止并回答能停止并回答“不是不是”，（要么永，（要么永远运行下去）远运行下去）2022/12/517现在学习的是第17页，共70页2.2 2.2 文法和语言文法和语言n一个自然语言的例子一个自然语言的例子规则（文法）规则（文法）句子 主语 谓语 （1）主语 冠词 形容词 名词 （2）冠词the 形容词 grey 谓语 动词 直接宾语 （5）动词 助动词 动词原形 （6）助动词will 动词原形 eat 直接宾语 冠词 名词 （9）名词

9、wolf 名词 goat2022/12/518现在学习的是第18页，共70页 句子句子 主语主语 谓语谓语 冠词冠词 形容词形容词 名词名词 谓语谓语 the 形容词形容词 名词名词 谓语谓语 the grey 名词名词 谓语谓语 the grey wolf 谓语谓语 the grey wolf 动词动词 直接宾语直接宾语 .the grey wolf will eat the goat句子可根据规则推导（生成）出来：句子可根据规则推导（生成）出来：The grey wolf will eat the goat分析句子分析句子2022/12/519现在学习的是第19页，共70页谓语谓语主语主语

10、冠词冠词形容词形容词名词名词动词动词直接宾语直接宾语句子句子The grey wolf will eat the goat2022/12/520现在学习的是第20页，共70页2.2 2.2 文法和语言文法和语言文法文法 G GV VT TV VN NS SP P终结符号集非终结符号集开始符号产生式集合n文法的形式定义文法的形式定义2022/12/521现在学习的是第21页，共70页终结符号集终结符号集 V VT T 代表语言中不可再分的基本符号语言中不可再分的基本符号，如汉语中的汉字、PASCAL语言中的基本字,其中的元素一般用小写字母或数字表示（a,b,c,0,1)2.2 2.2 文法和语言

11、文法和语言2022/12/522现在学习的是第22页，共70页非终结符号集非终结符号集 V VN N 代表语法单位语法单位，如汉语中的语句、段落，PASCAL语言中的语句、表达式、子程序等，其中的元素一般用大写字母表示（A,B,C），或者用尖括号括起一个串来表示2.2 2.2 文法和语言文法和语言2022/12/523现在学习的是第23页，共70页开始符号开始符号 S S 是一个特殊的非终结符号，代表最高级的语法单位最高级的语法单位，S 至少要在一条产生式中作为左部出现2.2 2.2 文法和语言文法和语言2022/12/524现在学习的是第24页，共70页产生式集合产生式集合 P P2.2 2

12、.2 文法和语言文法和语言 产生式（重写规则、生成式），是形如或=的（，）有序对，且V+，V*，其中 V=（VTVN）称为产生式的左部，不能为空称为产生式的右部，可以为空 （如：A ）2022/12/525现在学习的是第25页，共70页2.2 2.2 文法和语言文法和语言例1：文法 G=（VT，VN，S，P）VN=S VT=0,1 P=S0S1,S01 n可以只写出产生式，通过产生式可以得到文法的其它部分n左部相同的产生式可以写在一起，如:S 0S1|012022/12/526现在学习的是第26页，共70页2.2 2.2 文法和语言文法和语言例2：文法 G=（VT，VN，S，P）VN=，VT=

13、a,b,c,x,y,z,0,1,9P=a,z 0,9 S=2022/12/527现在学习的是第27页，共70页2.2 2.2 文法和语言文法和语言推推 导导直接推导直接推导直接归约直接归约归归 约约 如果 A 是 G 的一条产生式，则称用代替A为一步直接推导，记为A A A 2022/12/528现在学习的是第28页，共70页2.2 2.2 文法和语言文法和语言n推导推导是用产生式的右部代替左部，归约归约是用产生式的左部代替右部，归约是推导的逆过程直接推导直接推导直接归约直接归约 用A代替为一步直接归约，记为=A A A 2022/12/529现在学习的是第29页，共70页2.2 2.2 文法

14、和语言文法和语言n推导的长度推导的长度n直接推导的次数n ，长度大于等于 1 的推导n ，长度大于等于 0 的推导n推导的例子：S 0S1 00S11 000111，长度为 3 记为：S 000111 S S2022/12/530现在学习的是第30页，共70页2.2 2.2 文法和语言文法和语言最左推导最左推导最右推导最右推导对中的最左非终结符进行展开对中的最右非终结符进行展开2022/12/531现在学习的是第31页，共70页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*最右推

15、导又称为规范推导最右推导：E T T*F T*a F*a a*a2022/12/532现在学习的是第32页，共70页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*最左归约称为规范归约2022/12/533现在学习的是第33页，共70页2.2 2.2 文法和语言文法和语言句型句型句子句子 只包含终结符号的句型称为句子。句

16、子是一种特殊的句型。从文法的开始符号出发进行零步或多于零步的推导得到的文法符号串（S ）。句型可以既包含终结符号又包含非终结符号。2022/12/534现在学习的是第34页，共70页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 a2022/12/535现在学习的是第35页，共70页2.2 2.2 文法和语言文法和语言n语言的形式定义语言的形式定义n文法 G 推导出的所有句子组成的集合，称为语言语言，记为 L（G）nL（G）=|S ，V

17、T*2022/12/536现在学习的是第36页，共70页2.2 2.2 文法和语言文法和语言n例子：nG1：S A A 0A1 A 01 是由一个或多个 0 开头，后跟同样数目的 1 的符号串构成的集合（语言），可记为：L(G)=0 n 1 n|n 1 2022/12/537现在学习的是第37页，共70页2.2 2.2 文法和语言文法和语言nG2：E idE E+EE E*EE （E）产生的是表达式的集合2022/12/538现在学习的是第38页，共70页2.2 2.2 文法和语言文法和语言nG3：E E+T E T T T*F T F F （E）F id产生的也是表达式的集合2022/12/

18、539现在学习的是第39页，共70页2.2 2.2 文法和语言文法和语言n一个文法对应一个语言，但一个语言可能有若干个文法产生它，这若干个文法是等价的，称为 等价文法等价文法n例 G2 与 G32022/12/540现在学习的是第40页，共70页2.2 2.2 文法和语言文法和语言n上下文无关文法能够描述现今程序设计语言的大上下文无关文法能够描述现今程序设计语言的大部分语法结构部分语法结构n算术表达式n赋值语句n条件语句等2022/12/541现在学习的是第41页，共70页2.2 2.2 文法和语言文法和语言n表达式文法：G=(+,*,id,(,),E,E,P)P:E idE E+EE E*E

19、E (E)E 表示算术表达式，id 表示程序的“变量”，该文法定义了由变量，+，*，(和)组成的算术表达式的语法结构，即：变量是算术表达式；若 E1 和 E2 是算术表达式，则 E1+E2，E1*E2 和(E1)也是算术表达式。2022/12/542现在学习的是第42页，共70页2.2 2.2 文法和语言文法和语言n描述一种简单赋值语句的产生式：赋值语句赋值语句 id=En描述条件语句的产生式：条件语句条件语句 if条件then语句 if条件then语句else语句2022/12/543现在学习的是第43页，共70页2.3 2.3 分析树和二义性分析树和二义性n分析树分析树是描述上下文无关文法

20、句型推导的一种直观方法，也称为推导树分析树分析树句型推导句型推导对应关系对应关系2022/12/544现在学习的是第44页，共70页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*a2022/12/545现在学习的是第45页，共70页2.3 2.3 分析树和二义性分析树和二义性n分析树的特性：分析树的特性：n根标识为开始符号n内部结点标识为非终结符号n每一内部结点及其子结点对应一条产生式，该结点是产生式的左部，子结点从左至右排列构成产生式的右部n叶结点从左至右

21、排列构成句型TT*FFaaE2022/12/546现在学习的是第46页，共70页2.3 2.3 分析树和二义性分析树和二义性n分析树与句型推导的关系分析树与句型推导的关系n一次推导（不是一个句型）对应一棵分析树n一棵分析树可能对应若干个推导n例如下面的推导对应的也是上面那棵分析树 E T T*F T*a F*a a*aTT*FFaaE2022/12/547现在学习的是第47页，共70页2.3 2.3 分析树和二义性分析树和二义性n说明分析树没有严格反映推导的顺序n但是一棵分析树对应一个最左推导，也只能对应一个最右推导TT*FFaaE2022/12/548现在学习的是第48页，共70页2.3 2

22、.3 分析树和二义性分析树和二义性对应最左推导分析树对应最右推导分析树2022/12/549现在学习的是第49页，共70页2.3 2.3 分析树和二义性分析树和二义性n分析句型：短语、直接短语、句柄分析句型：短语、直接短语、句柄n如果 S A和 A ，则称是关于 A的，句型的一个短语短语（子树的叶子）SA2022/12/550现在学习的是第50页，共70页2.3 2.3 分析树和二义性分析树和二义性例：句型 F*a 的短语TT*FFaEF*anE E+T E T T T*F T F F （E）F aFa2022/12/551现在学习的是第51页，共70页2.3 2.3 分析树和二义性分析树和二

23、义性n如果S A和 A ，则称是关于 A的，句型的一个直接短语直接短语（只有父子两代的子树的叶子）SA2022/12/552现在学习的是第52页，共70页2.3 2.3 分析树和二义性分析树和二义性例：句型 F*a 的直接短语TT*FFaEFa2022/12/553现在学习的是第53页，共70页2.3 2.3 分析树和二义性分析树和二义性n最左直接短语称为句柄句柄n最左性体现在分析树和句型中SA2022/12/554现在学习的是第54页，共70页2.3 2.3 分析树和二义性分析树和二义性例：句型 F*a 的句柄TT*FFaEF2022/12/555现在学习的是第55页，共70页2.3 2.3

24、 分析树和二义性分析树和二义性n句型的素短语素短语、最左素短语最左素短语1、是关于 A 的，句型的一个短语2、至少含有一个终结符3、除自身外不含更小的带终结符的短语称是关于 A 的，句型的一个素短语素短语n句型最左边的素短语称为最左素短语最左素短语2022/12/556现在学习的是第56页，共70页例：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 a2022/12/557现在学习的是第57页，共70页2.

25、3 2.3 分析树和二义性分析树和二义性n句子、文法和语言的二义性句子、文法和语言的二义性n如果一个文法的句子有两棵或两棵以上的分析树，称此句子是二义句子是二义的n最左（右）推导与分析树一一对应，句子二义说明它有两个或以上最左（右）推导2022/12/558现在学习的是第58页，共70页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）2022/12/559现

26、在学习的是第59页，共70页2.3 2.3 分析树和二义性分析树和二义性n如果一个文法有一个句子是二义的，此文法称为二二义文法义文法nE id E E+E E E*E E （E）2022/12/560现在学习的是第60页，共70页2.3 2.3 分析树和二义性分析树和二义性n如果一个语言的所有文法都是二义的，称此语言语言是二义是二义的的n希望文法是无二义的，因为希望对于每一个句子进行唯一确定的分析2022/12/561现在学习的是第61页，共70页2.4 2.4 形式语言概观形式语言概观n乔姆斯基（乔姆斯基（Chomsky）在）在 1956 年提出形式语言理论，年提出形式语言理论，他将形式文法

27、分为四类他将形式文法分为四类(0,1,2,3)，对应四类形，对应四类形式语言式语言(0,1,2,3)n分类的方法是对文法的产生式进行不同的限制分类的方法是对文法的产生式进行不同的限制2022/12/562现在学习的是第62页，共70页2.4 2.4 形式语言概观形式语言概观n0 型文法|0，即 （）n1 型（上下文有关）文法|（）n2 型（上下文无关）文法 A VN，（VTVN）*（A）n3 型（正规）文法nAa 或 AaB（右线性）nAa 或 ABa（左线性）2022/12/563现在学习的是第63页，共70页2.4 2.4 形式语言概观形式语言概观例：例：1 1 型（上下文有关）文法型（上

28、下文有关）文法 文法文法 G G：SCDSCD AbbA AbbACaCACaCABaaBBaaBCbCBCbCBBbbBBbbBADaDADaDCCBDbDBDbDDDAabDAabDL(G)=ww|wa,bL(G)=ww|wa,b*2022/12/564现在学习的是第64页，共70页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|0S

29、B1B|1|0B1B|1|02022/12/565现在学习的是第65页，共70页2.4 2.4 形式语言概观形式语言概观例：例：3 3 型（正规）文法型（正规）文法 文法文法 G G：S0A|1B|0S0A|1B|0A0A|1B|0SA0A|1B|0SB1B|1|0B1B|1|02022/12/566现在学习的是第66页，共70页2.4 2.4 形式语言概观形式语言概观n0 型文法产生的语言称为 0 型语言n1 型文法或上下文有关文法产生的语言称为 1 型语言或上下文有关语言n2 型文法或上下文无关文法产生的语言称为 2 型语言或上下文无关语言n3 型文法或正则（正规）文法产生的语言称为 3

30、型语言正则（正规）语言2022/12/567现在学习的是第67页，共70页2.4 2.4 形式语言概观形式语言概观n四种文法（语言）之间的逐级“包含”关系2 型文法（语言）型文法（语言）1 型文法（语言）型文法（语言）0 型文法（语言）型文法（语言）3 型文法（语言）型文法（语言）2022/12/568现在学习的是第68页，共70页2.4 2.4 形式语言概观形式语言概观n识别各类语言的数学模型（自动机）识别各类语言的数学模型（自动机）n图灵机（0 型语言）n有界图灵机、线性有界自动机（1 型语言）n下推自动机（2 型语言）n有限自动机（3 型语言）2022/12/569现在学习的是第69页，共70页The End!The End!2022/12/570现在学习的是第70页，共70页