《第02章_文法和语言的基本知识(1)精选文档.ppt》由会员分享，可在线阅读，更多相关《第02章_文法和语言的基本知识(1)精选文档.ppt（80页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第02章_文法和语言的基本知识(1)本讲稿第一页，共八十页第二章第二章 文法和语言的基本知识文法和语言的基本知识q字母表和符号串字母表和符号串q文法和语言的形式定义文法和语言的形式定义q短语、直接短语和句柄短语、直接短语和句柄q语法树和文法的二义性语法树和文法的二义性q文法和语言的分类文法和语言的分类本讲稿第二页，共八十页2.0 概概 述述 对程序设计语言的描述是从语法、语义和语用三个因素来考虑。语法是对语言结构的定义。语用则是从使用的角度去描述语言。语义是描述了语言的含义。本讲稿第三页，共八十页2.0 概概 述述例如例如 赋值语句赋值语句s s2*3.1416*r*(r+h)2*3.1416
2、*r*(r+h)的的 非形式化的描述为：非形式化的描述为：语法：赋值语句由一个变量，后随一个赋 值号“”，再在其后面跟一个表达式构成。语义：首先计算语句右部表达式的值，然后把所得结果送给左部变量中。语用：赋值语句可用来计算和保存表达式的值。本讲稿第四页，共八十页2.0 概 述 这种非形式化的描述,不够清晰和准确,为了精确定义和描述程序设计语言,需采用形式化的方法。所谓形式化的方法,是用一整套带有严格规定的符号体系来描述问题的方法。形式语言理论是编译的重要理论基础。重点介绍如何采用形式化的方法描述程序设计语言。本讲稿第五页，共八十页2.1 字母表和符号串元素的非空有穷集合。例如，=a,b,c 1
3、.字母表 根据字母表的定义，是字母表，它由a、b、c三个元素组成。程序设计语言的字母表 =x|x ASCII字符本讲稿第六页，共八十页 是一个字母表，由0、1两个元素组成。注意:例如，=0,1 (2)字母表中的元素,可以是字母、数字或其他符号。(1)字母表中至少包含一个元素。2.1 字母表和符号串本讲稿第七页，共八十页 字母表中的元素称为符号或称为字符。例如，前述例子中2.符号（字符）a、b、c 是字母表中的符号；0、1 是字母表中的符号。2.1 字母表和符号串本讲稿第八页，共八十页 例如，设有字母表=a,b,c 符号的有穷序列称为符号串。符号串总是建立在某个特定字母表上的且只由字母表上的有穷
4、多个符号组成。则有符号串 a，b，ab，ba，cba，abc 3.符号串（字）2.1 字母表和符号串本讲稿第九页，共八十页说明说明:不包含任何符号的符号串,称为空符号串，用表示。符号串中符号的顺序是很重要的。ab和ba是字母表上的两个不同的符号串。空符号串由0个符号组成，其长度|=0|=02.1 字母表和符号串本讲稿第十页，共八十页2.2 符号串的运算符号串的运算 设x和y是符号串，则串xy称为它们的连结。则XYabc10a，YX10aabc注意：对任意一个符号串x，1.符号串的符号串的连结连结例如，设Xabc，Y10a我们有 xxx本讲稿第十一页，共八十页2.2 符号串的运算符号串的运算2.
5、符号串集合的符号串集合的乘积乘积 设A和B是符号串的集合,则A和B的乘积定义为：集合的乘积是满足于 xA,yB的所有符号串 xy 所构成的集合。AB=xy|xA,yB本讲稿第十二页，共八十页A=A=A2.2 符号串的运算符号串的运算例如：设A=aa,b,B=c,d 则AB=aac,aad,bc,bd 由于对任意的符号串x，总有x=x=x所以,对任意集合A,我们有:本讲稿第十三页，共八十页2.2 符号串的运算符号串的运算 特别指出的是，是符号串,不是集合，而表示由空符号串 所组成的集合,但这样的集合不是空集合=。本讲稿第十四页，共八十页2.2 符号串的运算符号串的运算 3.符号串的幂运算符号串的
6、幂运算 设x是符号串,则x的幂运算定义为：x0=x1=x x2=xx x3=xxx xn=xx x=x xn-1(n0)n注意：x0 1本讲稿第十五页，共八十页2.2 符号串的运算符号串的运算例如,设 xabc 则x0=x1=abcx2=xx=abcabc 本讲稿第十六页，共八十页2.2 符号串的运算符号串的运算 4.符号串符号串集合的幂运算集合的幂运算 设A是符号串的集合，则集合A的幂运算定义为：A0=A1=AA2=AA An=AA A=AAn-1(n0)n本讲稿第十七页，共八十页2.2 符号串的运算符号串的运算例如，设A=a,b，则A0=A1=A=a,b A2=AA=aa,ab,ba,bb
7、 A3=AAA=A2A=aaa,aab,aba,abb,baa,bab,bba,bbb 本讲稿第十八页，共八十页2.2 符号串的运算符号串的运算5.集合集合A的正闭包的正闭包A与闭包与闭包A*设A是符号串的集合，则A的正闭包A和A的闭包A*的定义为:A+=A1A2 An A*=A0 A1A2 An=A+本讲稿第十九页，共八十页2.2 符号串的运算符号串的运算 可见,集合A的正闭包表示A上元素a,b构成的所有符号串的集合,集合A的闭包比集合A的正闭包多含一个空符号串。例如，设A=a,b,则：A+=a,b,aa,ab,ba,bb,aaa,aab,A*=,a,b,aa,ab,ba,bb,aaa,aa
8、b,即：闭包为集合中元素的任意组合本讲稿第二十页，共八十页2.3 2.3 文法和语言的形式定义文法和语言的形式定义 每个形式语言都是某个字母表上按某种规则构成的所有符号串的集合。反之，任何一个字母表上符号串的集合均可定义为一个形式语言。形式语言形式语言序列的集合称为形式语言。本讲稿第二十一页，共八十页2.3 2.3 文法和语言的形式定义文法和语言的形式定义 下面用A表示+，用式子A0表示符号串0A或A生成符号串0，符号“”读作“生成”或“由组成”。则集合A可表示成：A0A1AA0AA1+=123=0,1,00,10,11,01,000,100,本讲稿第二十二页，共八十页2.3.1 2.3.1
9、文法的形式定义文法的形式定义 规则是一个符号与一个符号串的有序对（A,），通常写作：A（或A)1.1.规则规则 也称产生式也称产生式 规则的作用是告诉我们如何用规则中的符号串生成语言中的序列。本讲稿第二十三页，共八十页2.3.1 2.3.1 文法的形式定义文法的形式定义 例如，前述例中一组规则 描述的语言序列只可能是由0和1组成的符号串。A0A1AA0AA1本讲稿第二十四页，共八十页2.3.1 2.3.1 文法的形式定义文法的形式定义 规则中出现的符号分为两类，一类是终结符号，另一类是非终结符号。非终结符号是出现在规则左部能派生出符号或符号串的那些符号，即每个非终结符号表示一定符号串的集合，用
10、大写字母表示或用尖括号把非终结符号括起来。例如，上例中的A。本讲稿第二十五页，共八十页2.3.1 2.3.1 文法的形式定义文法的形式定义 终结符号是不属于非终结符号的那些符号,它是组成语言的基本符号，是一个语言的不可再分的基本符号，通常用小写字母表示。例如，上例中的0和1。本讲稿第二十六页，共八十页2.3.1 2.3.1 文法的形式定义文法的形式定义 规则的非空有穷集合，通常表示成四元组VN是规则中非终结符号的集合。VT是规则中终结符号的集合。P 是文法规则的集合。2.文法文法G=VN,VT,P,S 本讲稿第二十七页，共八十页2.3.1 2.3.1 文法的形式定义文法的形式定义 S 是一个非
11、终结符号，称为文法的开始符号或文法的识别符号，它至少要在一条规则中作为左部出现。由它开始，识别出我们所定义的语言。由文法定义可知，文法是对语言结构的定义和描述，文法四大要素中关键是规则的集合。本讲稿第二十八页，共八十页2.3.1 2.3.1 文法的形式定义文法的形式定义将它们缩写为：A1|2|nA1A2An 其中每个i有时也称为是A的一个候选式。为了书写方便，对于若干个左部相同的规则，如本讲稿第二十九页，共八十页2.3.1 2.3.1 文法的形式定义文法的形式定义我们约定：第一条规则的左部是识别符号。对文法G不用四元式显示表示，仅 只将规则写出。本讲稿第三十页，共八十页2.3.1 2.3.1
12、文法的形式定义文法的形式定义 G=(VN，VT，P，S)VN=AVT=0，1P:A 0|1|A0|A1S=A前例中描述+的文法是:本讲稿第三十一页，共八十页2.3.1 2.3.1 文法的形式定义文法的形式定义求其VN、VTS AA B|if A then A else AB C|B+C|+CC D|C*D|*DD x|(A)|-D设文法G产生式为:本讲稿第三十二页，共八十页2.3.2.3.2 2 推导和归约推导和归约 推导：从文法开始符号开始，通过产生式的右部取代左部的过程，最终产生句子。规约：从给定源语言的句子开始，通过产生式的左部取代右部的过程，最终到达开始符号。由终结符组成的字符串本讲稿
13、第三十三页，共八十页2.3.2.3.2 2 推导和归约推导和归约 最左推导，每次使用一个规则以其右部取代符号串的最左非终结符 最右推导也称为规范推导，最左规约又称为规范规约。最右推导，每次使用一个规则以其右部取代符号串的最右非终结符 注：推导和规约的每一步只能用一个产生式进行替换。本讲稿第三十四页，共八十页2.3.2.3.2 2 规范推导和规范归约规范推导和规范归约 例 设有文法GS:请给出句子101001的最右、最左推导。分析 最右推导是指在推导过程中任何一步(和是句型)，都是对中的最右非终结符进行替换。SABAA0|1BB0|S1本讲稿第三十五页，共八十页2.3.2.3.2 2 规范推导和
14、规范归约规范推导和规范归约SABAS1AAB1AA01 A1B01A1001 1B1001101001句子101001的最右推导为:SABAA0|1BB0|S1本讲稿第三十六页，共八十页2.3.2.3.2 2 推导和归约推导和归约 最左推导是指在推导过程中任何一步(和是句型),都是对的最左非终结符进行替换。句子101001的最左推导为：SABAA0|1BB0|S1SAB1BB10B 10S110AB1101BB1 1010B1101001本讲稿第三十七页，共八十页2.3.2 2.3.2 语言的形式定义语言的形式定义 (1)形式上的区别，推导用“”表示，规则用“”表示。(2)对文法G中任何规则A
15、，我们有A，即推导的依据是规则。注意推导和规则的区别：本讲稿第三十八页，共八十页 即表示从0 出发，经一步或若干步 或者说 使用若干次规则可推导出 n。2.3.2 2.3.2 语言的形式定义语言的形式定义 如果存在一个推导序列：则我们称这个序列是一个从0至n的长度为n的推导，记为 0 1 2 n+0 n本讲稿第三十九页，共八十页2.3.2 2.3.2 语言的形式定义语言的形式定义 例如 设有文法GE=(E,T,F,i,+,*,(,),P,E)对 i+i*i 有如下推导序列:我们可记为 其中P为：EE+T|TTT*F|FF(E)|iEE+T T+T F+Ti+T i+T*Fi+F*Fi+i*Fi
16、+i*iEi+i*i+本讲稿第四十页，共八十页2.3.2 2.3.2 语言的形式定义语言的形式定义 广义推导 我们有：0n表示从0出发，经0步或若干步，可推导出n。*也就是说0n意味着0n或者0=n。*+EE*Ei+i*i*对上例 EE+T|T TT*F|F F(E)|i本讲稿第四十一页，共八十页2.3.2 2.3.2 语言的形式定义语言的形式定义 4.句型和句子 设有文法GS（S是文法G的开始符号）如果S x,x(VNVT)*则称符号串x 为文法GS的句型。*如果S x,x VT*则称符号串x为文法 GS的句子。*本讲稿第四十二页，共八十页2.3.2 2.3.2 语言的形式定义语言的形式定义
17、 例1 设有文法GS：我们有:显然，符号串01、0S1、00S11和000111 都是文法GS的句型，而01和000111又是文法GS的句子。S01|0S1S 01*S 0S1*S 00S11*S 000111*本讲稿第四十三页，共八十页2.3.2 2.3.2 语言的形式定义语言的形式定义 例2 设有文法GE：试证明符号串(i*i+i)是文法GE的一个句子。分析 只要证明符号串(i*i+i)对文法 G存在一个推导，就可证明符号串(i*i+i)是文法GE的一个句子。EE+E|E*E|(E)|i本讲稿第四十四页，共八十页2.3.2 2.3.2 语言的形式定义语言的形式定义 EE+E|E*E|(E)
18、|iE(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)即有 E(i*i+i),所以符号串(i+i*i)是文法 GE的一个句子。*本讲稿第四十五页，共八十页（2）L(G)是VT*的子集。即属于VT*的符 号串 x 不一定属于L(G)。2.3.2 2.3.2 语言的形式定义语言的形式定义 5语言 文法GS产生的所有句子的集合称为文 法G所定义的语言,记为L(GS)：由语言定义可知：（1）一旦文法给定，语言也就确定。L(GS)=x|Sx且xVT*本讲稿第四十六页，共八十页2.3.2 2.3.2 语言的形式定义语言的形式定义 例3 设有文法GS：S01|0S1求该文法所描述的语
19、言是什么？分析 由识别符号S出发，将推出一些什么样的句子，也就是说，L(GS)是由什么样的一些符号串所组成的集合，找出其中的规律，用式子或自然语言描述出来。由文法推出语言本讲稿第四十七页，共八十页2.3.2 2.3.2 语言的形式定义语言的形式定义 我们应用第二个规则n1次，然后再应用第一个规则1次，有：S0S100S110n-1S1n-10n1n即S0n1n*可见，此文法定义的语言为L(GS)=0n1n|n1S01|0S1本讲稿第四十八页，共八十页2.3.2 2.3.2 语言的形式定义语言的形式定义 例4 设有文法GS：S0S|1S|该文法所定义的语言是什么？由该文法所确定的语言为 L(GS
20、)=,0,1,00,01,10,11,=x|x0,1*本讲稿第四十九页，共八十页2.3.2 2.3.2 语言的形式定义语言的形式定义 例5 设有文法GA：该文法所定义的语言是什么？分析 从文法开始符号A出发可推导出以y开头后面跟一个或多个x结尾的符号串，所以该文法定义的语言为AyBB xB|xL(GA)=yxn|n1本讲稿第五十页，共八十页2.3.2 2.3.2 语言的形式定义语言的形式定义 该文法所定义的语言是什么？例6 文法G:(S,A,B,a,b,c,P,S)P:SAB AaA|BbBc|bcL(G)=anbmcm,n=0,m=1本讲稿第五十一页，共八十页2.3.2 2.3.2 语言的形
21、式定义语言的形式定义 该文法所定义的语言是什么？例7 文法G:(S,A,B,a,b,c,P,S)P:SaSAB SabB BAAB bAbb bBbc cBccL(G)=anbncn,n1本讲稿第五十二页，共八十页2.3.2 2.3.2 语言的形式定义语言的形式定义 由此可见，从已知文法确定语言的中心思想是：从文法的开始符号出发，反复连续地使用规则替换、展开非终结符，找出句子的规律，用式子或自然语言描述出来。本讲稿第五十三页，共八十页2.3.2.3.3 3 文法的形式定义文法的形式定义 例1 设字母表=a,b，试设计一个文法，描述语言 L=a2n,b2n|n1 分析 设计一个文法来描述一个语言
22、,关键是设计一组规则生成语言中的符号串。因此，为设计该语言文法，必须分析这个语言是由怎样一些符号串组成的，即首先分析语言中串的结构特征：由语言构造文法本讲稿第五十四页，共八十页2.3.2.3.3 3 文法的形式定义文法的形式定义当n1 L=aa,bb L=aa,bb,aaaa,bbbb,aaaaaa,bbbbbb,即语言L是由偶数个a，偶数个b这样的符号串组成的集合。L=a2n,b2n|n1当n2 L=aaaa,bbbb当n3 L=aaaaaa,bbbbbb本讲稿第五十五页，共八十页2.3.2.3.3 3 文法的形式定义文法的形式定义因此，定义语言L的文法 G=(VN，VT，P，S)其中：VN
23、=A,B,DVT=a,bP=Aaa S=ABaa Dbb|bbD|bb|bbD注意:VTaa,bb|aaB|aaB本讲稿第五十六页，共八十页2.3.2.3.3 3 文法的形式定义文法的形式定义 提出问题:描述该语言的文法是否唯一呢？显然，G不同于G。由此可见，对于一个给定的语言，描述该语言的文法是不唯一的。P:AB|DBaa|aBaDbb|bDb本讲稿第五十七页，共八十页 若G和G是两个不同的文法，如果它们描述的语言相同，那么，称G和G 为等价文法。2.3.2.3.3 3 文法的形式定义文法的形式定义本讲稿第五十八页，共八十页描述该语言的文法是否G？2.3.2.3.3 3 文法的形式定义文法的
24、形式定义 对此例，我们提出下面这样一个问题：G=(A,a,b,P,A)P=Aaa|bb|Aaa|Abb 本讲稿第五十九页，共八十页 对于文法G来说，它所产生的有些符号串，如aabb，bbaa，不属于语言L，即设计的文法超出了所定义语言的范围。2.3.2.3.3 3 文法的形式定义文法的形式定义P=Aaa|bb|Aaa|Abb 本讲稿第六十页，共八十页2.3.2.3.3 3 文法的形式定义文法的形式定义 例2 试设计一个表示所有标识符的文法 分析 题意是用文法定义标识符，必须确定P中规则。为了设计出一组规则，首先应搞清楚集合中串的结构特首先应搞清楚集合中串的结构特征征。本讲稿第六十一页，共八十页
25、2.3.2.3.3 3 文法的形式定义文法的形式定义 用I代表标识符；L代表字母；D代表数字;则定义标识符的文法为：字母 字母或数字串标识符的结构可用下图表示:本讲稿第六十二页，共八十页2.3.2.3.3 3 文法的形式定义文法的形式定义 G=(VN，VT，P，S)其中：VN=I,L,DVT=a,b,c,x,y,z,0,1,2,9P=IL S=ILa|b|c|x|y|zD0|1|2|3|9|I L|I D本讲稿第六十三页，共八十页2.3.2.3.3 3 文法的形式定义文法的形式定义 若将定义标识符的文法设计成：其中 VN，VT，S 同上 G=(VN，VT，P，S)P=IL|I DLa|b|c|
26、x|y|zD0|1|2|3|9 本讲稿第六十四页，共八十页2.3.2.3.3 3 文法的形式定义文法的形式定义 该文法不能定义ab，abc 仅由字母串组成的标识符，缩小了所定义语言的范围。P=IL|I DLa|b|c|x|y|zD0|1|2|3|9 本讲稿第六十五页，共八十页2.3.2.3.3 3 文法的形式定义文法的形式定义 用I代表标识符；L代表字母；D代表数字；T代表字母数字串；则定义标识符的文法还可写为：字母 字母或数字串本讲稿第六十六页，共八十页2.3.2.3.3 3 文法的形式定义文法的形式定义P:IL|LT TL|D|LT|DT La|b|c|x|y|z D0|1|2|3|9 字
27、母 字母或数字串本讲稿第六十七页，共八十页2.3.2.3.3 3 文法的形式定义文法的形式定义 例3 用文法定义一个含、*的算术表达式，定义用下述自然语言描述：变量是一个表达式；若 E1和 E2是算术表达式,则 E1E2、E1*E2、(E1)也是算术表达式。本讲稿第六十八页，共八十页2.3.2.3.3 3 文法的形式定义文法的形式定义 分析 算术表达式的定义用自然语言描述，这是对算术表达式的非形式定义，题意用文法来定义算术表达式，即是用形式化的方法定义表达式。定义算术表达式的文法为：G=(E,i,+,*,(,),P,E)其中P为：Ei|E+E|E*E|(E)本讲稿第六十九页，共八十页2.3.2
28、.3.3 3 文法的形式定义文法的形式定义P为：Ei|E+E|E*E|(E)i,i+i,i*i,i+i*i,(i+i),注意：是符号串的集合本讲稿第七十页，共八十页2.3.2.3.3 3 文法的形式定义文法的形式定义 例4 设字母表=a,b ,试设计一个文法，描述语言 L=abna|n0 分析 该语言中串的结构特征是 当n1 L=aba L=aa,aba,abba,当n2 L=abba 当n0 L=aa (b0=)本讲稿第七十一页，共八十页2.3.2.3.3 3 文法的形式定义文法的形式定义所以定义语言的文法为：G=(A,B,a,b,P,A)P=AaBa BBb|L=aa,aba,abba,本
29、讲稿第七十二页，共八十页2.3.2.3.3 3 文法的形式定义文法的形式定义 例5 设字母表=(,),试设计一个文法描述语言 L=(n )n|n0分析 该语言中串的结构特征是 当n=0 L=注:(0 )0=当n=1 L=()当n=2 L=()L=,(),(),(),本讲稿第七十三页，共八十页2.3.2.3.3 3 文法的形式定义文法的形式定义P:S|(S)所以定义语言的文法为：L=(n )n|n0本讲稿第七十四页，共八十页2.3.4 2.3.4 递归规则与文法的递归性递归规则与文法的递归性递归规则 如果文法中有规则 AA 称为规则左递归。如果文法中有规则 A A 称为规则右递归。如果文法中有规
30、则 A A 称为规则递归。本讲稿第七十五页，共八十页2.3.4 2.3.4 递归规则与文法的递归性递归规则与文法的递归性文法的递归性若文法中有推导AA 称文法左递归。+若文法中有推导A A称文法右递归。+若文法中有推导A A 称文法递归。+本讲稿第七十六页，共八十页2.3.4 2.3.4 递归规则与文法的递归性递归规则与文法的递归性例1 文法中有如下规则：这三条规则都不是递归规则，但有 在文法中使用递归规则，使得我们能用有限的规则去定义无穷集合的语言。UVxVUy|zUVx Uyx,则该文法是左递归的。本讲稿第七十七页，共八十页2.3.4 2.3.4 递归规则与文法的递归性递归规则与文法的递归
31、性 例2 考虑文法GA：由于该文法无递归性，由它所描述的语言是有穷的。该文法描述的语言为:AaB|bBBa|bL(GA)=aa,ab,ba,bb 本讲稿第七十八页，共八十页 2.3.4 2.3.4 递归规则与文法的递归性递归规则与文法的递归性例3 考虑文法GN1 该文法有直接左递归规则 NND,则称该文法为左递归文法或说文法左递归，其定义的语言为0,1,2+。N1NNND|DD0|1|2本讲稿第七十九页，共八十页 2.3.4 2.3.4 递归规则与文法的递归性递归规则与文法的递归性 也就是说，当一个语言是无穷集合时，则定义该语言的文法一定是递归的。若不用递归规则，则 NND 需要用 ND|DD|DDD|即无穷多条规则来定义由数字0,1,2 组成的所有无符号整数。本讲稿第八十页，共八十页