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

第2章程序语言的基本知识第1页，此课件共70页哦第第 2 章章 程序语言的基本知识程序语言的基本知识符号串的集合符号串的集合文法和语言文法和语言分析树和二义性分析树和二义性形式语言概观形式语言概观2023/4/162第2页，此课件共70页哦2.1 2.1 符号串的集合符号串的集合字母表字母表字母表是符号的字母表是符号的非空有穷集合，非空有穷集合，用用 表示表示n 符号：可以相互区别的记号（元素）n不同的语言有不同的字母表n英语26个英文字母nPascal语言 AZ,az,09,+,-,*,/,:,；,.,(,),2023/4/163第3页，此课件共70页哦2.1 2.1 符号串的集合符号串的集合符号串符号串符号串是由字母表符号串是由字母表中的符号所组成的中的符号所组成的有穷序列有穷序列n例如：=a,b 则 a,b,aa,ab,aabba都是上的符号串n是任何上的符号串n在语言理论中，符号串又称为在语言理论中，符号串又称为:句子、字句子、字2023/4/164第4页，此课件共70页哦2.1 2.1 符号串的集合符号串的集合n符号串的长度符号串的长度n符号串中包含符号的个数n符号串 s 的长度记为|s|例，对于字母表a,b,c，aab 是其上的一个符号串，|aab|=3 注意：空符号串，|=02023/4/165第5页，此课件共70页哦2.1 2.1 符号串的集合符号串的集合n符号串的前缀、后缀、子串符号串的前缀、后缀、子串后缀：后缀：删去符号串 s 头部的零个或多于零个符号得到的符号串前缀：前缀：移走符号串 s 尾部的零个或多于零个符号得到的符号串 2023/4/166第6页，此课件共70页哦2.1 2.1 符号串的集合符号串的集合n符号串的真前缀、真后缀和真子串符号串的真前缀、真后缀和真子串非空非空n子串：子串：从 s 中删去一个前缀和一个后缀得到的符号串 *对于每个符号串s，s 和两者都是符号串 s 的前缀、后缀和子串2023/4/167第7页，此课件共70页哦2.1 2.1 符号串的集合符号串的集合n符号串的运算：符号串的运算：n连接：连接：符号串、的连接，是把 的符号写在 的符号之后得到的符号串 n如=ab,=cd 则 =abcd n注：=n方幂：方幂：符号串自身连接 n 次得到的符号串nn 定义为 n 个n1=,2=，注：0=2023/4/168第8页，此课件共70页哦2.1 2.1 符号串的集合符号串的集合例例:汉语所有符合汉语语法的句子构成的集合 PASCAL语言所有合法的 PASCAL 程序构成的集合n注意：空集 、和 的不同语言语言某个字母表上的符某个字母表上的符号串的集合号串的集合2023/4/169第9页，此课件共70页哦2.1 2.1 符号串的集合符号串的集合n语言的运算：语言的运算：n语言是符号串的集合，集合的运算有并、交、差等n并运算并运算 等同于集合的并运算2023/4/1610第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=2023/4/1611第11页，此课件共70页哦2.1 2.1 符号串的集合符号串的集合n*闭包闭包（Kleene 闭包）nL*=L0L1L2L3 n+闭包闭包（正闭包）nL+=L1L2L3nL*=L+2023/4/1612第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,2023/4/1613第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+2023/4/1614第14页，此课件共70页哦2.2 2.2 文法和语言文法和语言n如何来描述一种语言？如何来描述一种语言？n如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示n如果语言是无穷的，找出语言的有穷表示。2023/4/1615第15页，此课件共70页哦2.2 2.2 文法和语言文法和语言语言有穷表示的两个途经*文法即是以生成方式描述语言的生成方式生成方式语言中的每个句子语言中的每个句子可以用严格定义的可以用严格定义的规则来构造规则来构造2023/4/1616第16页，此课件共70页哦2.2 2.2 文法和语言文法和语言*自动机即是以识别方式描述语言的识别方式识别方式用一个过程，当输入的一任意串属于语用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止言时，该过程经有限次计算后就会停止并回答并回答“是是”，若不属于，要么能停，若不属于，要么能停止并回答止并回答“不是不是”，（要么永远运行，（要么永远运行下去）下去）2023/4/1617第17页，此课件共70页哦2.2 2.2 文法和语言文法和语言n一个自然语言的例子一个自然语言的例子规则（文法）规则（文法）句子 主语 谓语 （1）主语 冠词 形容词 名词 （2）冠词the 形容词 grey 谓语 动词 直接宾语 （5）动词 助动词 动词原形 （6）助动词will 动词原形 eat 直接宾语 冠词 名词 （9）名词wolf 名词 goat2023/4/1618第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分析句子分析句子2023/4/1619第19页，此课件共70页哦谓语谓语主语主语冠词冠词形容词形容词名词名词动词动词直接宾语直接宾语句子句子The grey wolf will eat the goat2023/4/1620第20页，此课件共70页哦2.2 2.2 文法和语言文法和语言文法文法 G GV VT TV VN NS SP P终结符号集非终结符号集开始符号产生式集合n文法的形式定义文法的形式定义2023/4/1621第21页，此课件共70页哦终结符号集终结符号集 V VT T 代表语言中不可再分的基本符号语言中不可再分的基本符号，如汉语中的汉字、PASCAL语言中的基本字,其中的元素一般用小写字母或数字表示（a,b,c,0,1)2.2 2.2 文法和语言文法和语言2023/4/1622第22页，此课件共70页哦非终结符号集非终结符号集 V VN N 代表语法单位语法单位，如汉语中的语句、段落，PASCAL语言中的语句、表达式、子程序等，其中的元素一般用大写字母表示（A,B,C），或者用尖括号括起一个串来表示2.2 2.2 文法和语言文法和语言2023/4/1623第23页，此课件共70页哦开始符号开始符号 S S 是一个特殊的非终结符号，代表最高级的语法单位最高级的语法单位，S 至少要在一条产生式中作为左部出现2.2 2.2 文法和语言文法和语言2023/4/1624第24页，此课件共70页哦产生式集合产生式集合 P P2.2 2.2 文法和语言文法和语言 产生式（重写规则、生成式），是形如或=的（，）有序对，且V+，V*，其中 V=（VTVN）称为产生式的左部，不能为空称为产生式的右部，可以为空 （如：A ）2023/4/1625第25页，此课件共70页哦2.2 2.2 文法和语言文法和语言例1：文法 G=（VT，VN，S，P）VN=S VT=0,1 P=S0S1,S01 n可以只写出产生式，通过产生式可以得到文法的其它部分n左部相同的产生式可以写在一起，如:S 0S1|012023/4/1626第26页，此课件共70页哦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/1627第27页，此课件共70页哦2.2 2.2 文法和语言文法和语言推推 导导直接推导直接推导直接归约直接归约归归 约约 如果 A 是 G 的一条产生式，则称用代替A为一步直接推导，记为A A A 2023/4/1628第28页，此课件共70页哦2.2 2.2 文法和语言文法和语言n推导推导是用产生式的右部代替左部，归约归约是用产生式的左部代替右部，归约是推导的逆过程直接推导直接推导直接归约直接归约 用A代替为一步直接归约，记为=A A A 2023/4/1629第29页，此课件共70页哦2.2 2.2 文法和语言文法和语言n推导的长度推导的长度n直接推导的次数n ，长度大于等于 1 的推导n ，长度大于等于 0 的推导n推导的例子：S 0S1 00S11 000111，长度为 3 记为：S 000111 S S2023/4/1630第30页，此课件共70页哦2.2 2.2 文法和语言文法和语言最左推导最左推导最右推导最右推导对中的最左非终结符进行展开对中的最右非终结符进行展开2023/4/1631第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*最右推导又称为规范推导最右推导：E T T*F T*a F*a a*a2023/4/1632第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*最左归约称为规范归约2023/4/1633第33页，此课件共70页哦2.2 2.2 文法和语言文法和语言句型句型句子句子 只包含终结符号的句型称为句子。句子是一种特殊的句型。从文法的开始符号出发进行零步或多于零步的推导得到的文法符号串（S ）。句型可以既包含终结符号又包含非终结符号。2023/4/1634第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 a2023/4/1635第35页，此课件共70页哦2.2 2.2 文法和语言文法和语言n语言的形式定义语言的形式定义n文法 G 推导出的所有句子组成的集合，称为语言语言，记为 L（G）nL（G）=|S ，VT*2023/4/1636第36页，此课件共70页哦2.2 2.2 文法和语言文法和语言n例子：nG1：S A A 0A1 A 01 是由一个或多个 0 开头，后跟同样数目的 1 的符号串构成的集合（语言），可记为：L(G)=0 n 1 n|n 1 2023/4/1637第37页，此课件共70页哦2.2 2.2 文法和语言文法和语言nG2：E idE E+EE E*EE （E）产生的是表达式的集合2023/4/1638第38页，此课件共70页哦2.2 2.2 文法和语言文法和语言nG3：E E+T E T T T*F T F F （E）F id产生的也是表达式的集合2023/4/1639第39页，此课件共70页哦2.2 2.2 文法和语言文法和语言n一个文法对应一个语言，但一个语言可能有若干个文法产生它，这若干个文法是等价的，称为 等价文法等价文法n例 G2 与 G32023/4/1640第40页，此课件共70页哦2.2 2.2 文法和语言文法和语言n上下文无关文法能够描述现今程序设计语言的上下文无关文法能够描述现今程序设计语言的大部分语法结构大部分语法结构n算术表达式n赋值语句n条件语句等2023/4/1641第41页，此课件共70页哦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/1642第42页，此课件共70页哦2.2 2.2 文法和语言文法和语言n描述一种简单赋值语句的产生式：赋值语句赋值语句 id=En描述条件语句的产生式：条件语句条件语句 if条件then语句 if条件then语句else语句2023/4/1643第43页，此课件共70页哦2.3 2.3 分析树和二义性分析树和二义性n分析树分析树是描述上下文无关文法句型推导的一种直观方法，也称为推导树分析树分析树句型推导句型推导对应关系对应关系2023/4/1644第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*a2023/4/1645第45页，此课件共70页哦2.3 2.3 分析树和二义性分析树和二义性n分析树的特性：分析树的特性：n根标识为开始符号n内部结点标识为非终结符号n每一内部结点及其子结点对应一条产生式，该结点是产生式的左部，子结点从左至右排列构成产生式的右部n叶结点从左至右排列构成句型TT*FFaaE2023/4/1646第46页，此课件共70页哦2.3 2.3 分析树和二义性分析树和二义性n分析树与句型推导的关系分析树与句型推导的关系n一次推导（不是一个句型）对应一棵分析树n一棵分析树可能对应若干个推导n例如下面的推导对应的也是上面那棵分析树 E T T*F T*a F*a a*aTT*FFaaE2023/4/1647第47页，此课件共70页哦2.3 2.3 分析树和二义性分析树和二义性n说明分析树没有严格反映推导的顺序n但是一棵分析树对应一个最左推导，也只能对应一个最右推导TT*FFaaE2023/4/1648第48页，此课件共70页哦2.3 2.3 分析树和二义性分析树和二义性对应最左推导分析树对应最右推导分析树2023/4/1649第49页，此课件共70页哦2.3 2.3 分析树和二义性分析树和二义性n分析句型：短语、直接短语、句柄分析句型：短语、直接短语、句柄n如果 S A和 A ，则称是关于 A的，句型的一个短语短语（子树的叶子）SA2023/4/1650第50页，此课件共70页哦2.3 2.3 分析树和二义性分析树和二义性例：句型 F*a 的短语TT*FFaEF*anE E+T E T T T*F T F F （E）F aFa2023/4/1651第51页，此课件共70页哦2.3 2.3 分析树和二义性分析树和二义性n如果S A和 A ，则称是关于 A的，句型的一个直接短语直接短语（只有父子两代的子树的叶子）SA2023/4/1652第52页，此课件共70页哦2.3 2.3 分析树和二义性分析树和二义性例：句型 F*a 的直接短语TT*FFaEFa2023/4/1653第53页，此课件共70页哦2.3 2.3 分析树和二义性分析树和二义性n最左直接短语称为句柄句柄n最左性体现在分析树和句型中SA2023/4/1654第54页，此课件共70页哦2.3 2.3 分析树和二义性分析树和二义性例：句型 F*a 的句柄TT*FFaEF2023/4/1655第55页，此课件共70页哦2.3 2.3 分析树和二义性分析树和二义性n句型的素短语素短语、最左素短语最左素短语1、是关于 A 的，句型的一个短语2、至少含有一个终结符3、除自身外不含更小的带终结符的短语称是关于 A 的，句型的一个素短语素短语n句型最左边的素短语称为最左素短语最左素短语2023/4/1656第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 a2023/4/1657第57页，此课件共70页哦2.3 2.3 分析树和二义性分析树和二义性n句子、文法和语言的二义性句子、文法和语言的二义性n如果一个文法的句子有两棵或两棵以上的分析树，称此句子是二义句子是二义的n最左（右）推导与分析树一一对应，句子二义说明它有两个或以上最左（右）推导2023/4/1658第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）2023/4/1659第59页，此课件共70页哦2.3 2.3 分析树和二义性分析树和二义性n如果一个文法有一个句子是二义的，此文法称为二义文法二义文法nE id E E+E E E*E E （E）2023/4/1660第60页，此课件共70页哦2.3 2.3 分析树和二义性分析树和二义性n如果一个语言的所有文法都是二义的，称此语语言是二义言是二义的的n希望文法是无二义的，因为希望对于每一个句子进行唯一确定的分析2023/4/1661第61页，此课件共70页哦2.4 2.4 形式语言概观形式语言概观n乔姆斯基（乔姆斯基（Chomsky）在）在 1956 年提出形式语言理论，年提出形式语言理论，他将形式文法分为四类他将形式文法分为四类(0,1,2,3)，对应四类形式，对应四类形式语言语言(0,1,2,3)n分类的方法是对文法的产生式进行不同的限制分类的方法是对文法的产生式进行不同的限制2023/4/1662第62页，此课件共70页哦2.4 2.4 形式语言概观形式语言概观n0 型文法|0，即 （）n1 型（上下文有关）文法|（）n2 型（上下文无关）文法 A VN，（VTVN）*（A）n3 型（正规）文法nAa 或 AaB（右线性）nAa 或 ABa（左线性）2023/4/1663第63页，此课件共70页哦2.4 2.4 形式语言概观形式语言概观例：例：1 1 型（上下文有关）文法型（上下文有关）文法 文法文法 G G：SCDSCD AbbA AbbACaCACaCABaaBBaaBCbCBCbCBBbbBBbbBADaDADaDCCBDbDBDbDDDAabDAabDL(G)=ww|wa,bL(G)=ww|wa,b*2023/4/1664第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|0SB1B|1|0B1B|1|02023/4/1665第65页，此课件共70页哦2.4 2.4 形式语言概观形式语言概观例：例：3 3 型（正规）文法型（正规）文法 文法文法 G G：S0A|1B|0S0A|1B|0A0A|1B|0SA0A|1B|0SB1B|1|0B1B|1|02023/4/1666第66页，此课件共70页哦2.4 2.4 形式语言概观形式语言概观n0 型文法产生的语言称为 0 型语言n1 型文法或上下文有关文法产生的语言称为 1 型语言或上下文有关语言n2 型文法或上下文无关文法产生的语言称为 2 型语言或上下文无关语言n3 型文法或正则（正规）文法产生的语言称为 3 型语言正则（正规）语言2023/4/1667第67页，此课件共70页哦2.4 2.4 形式语言概观形式语言概观n四种文法（语言）之间的逐级“包含”关系2 型文法（语言）型文法（语言）1 型文法（语言）型文法（语言）0 型文法（语言）型文法（语言）3 型文法（语言）型文法（语言）2023/4/1668第68页，此课件共70页哦2.4 2.4 形式语言概观形式语言概观n识别各类语言的数学模型（自动机）识别各类语言的数学模型（自动机）n图灵机（0 型语言）n有界图灵机、线性有界自动机（1 型语言）n下推自动机（2 型语言）n有限自动机（3 型语言）2023/4/1669第69页，此课件共70页哦The End!The End!2023/4/1670第70页，此课件共70页哦