第2章文法和语言.ppt

《第2章文法和语言.ppt》由会员分享，可在线阅读，更多相关《第2章文法和语言.ppt（80页珍藏版）》请在三一办公上搜索。

1、第二章 文法和语言的基本知识,形式语言的理论是编译的重要理论基础。有关形式语言的概念包括：字母表和符号串文法和语言的形式定义短语、直接短语和句柄语法树和文法的二义性文法和语言的分类,第二章 文法和语言的基本知识,2.1 概述2.2 字母表和符号串2.3 法和语言的形式定义2.4 短语、直接短语和句柄2.5 语法树与文法的二义性2.6 文法和语言的分类2.7 自上而下的分析方法2.8 有关文法实用中的一些说明,2.1 概述,语言是一个记号系统汉语-符合汉语语法的句子的全体英语-符合英语语法的句子的全体程序设计语言-该语言的程序的全体,2.1 概述,对程序设计语言非形式化的描述：语法：定义每个程序

2、构成的规则 语义：定义每个程序的意义 语用：每个程序(语句)的用途例s=2*3.1416*r*(h+r)的非形式化的描述：语法赋值语句有一个变量、一个赋值号后跟表达式构成语义计算=右部的值，送入左部变量语用赋值语句用来计算和保存表达式的值,2.1 概述,非形式化描述不清晰 不准确形式化描述用一整套带有严格规定的符号体系来描述问题的方法用形式语言描述各种程序设计语言,程序设计语言包括:语法和语义语法(syntax)定义:是一组规则，用它可以形成和产生一个合适的程序描述工具:文法作用:定义什么样的符号序列是合法的，与符号的含义无关。,形式语言的基本形式,例:“我是大学生”是汉语的一个句子,用EBN

3、F来表示汉语句子的构成规则：句子=主语谓语主语=代词名词代词=我你他名词=王明大学生工人英语谓语=动词直接宾语动词=是学习直接宾语=代词名词,例如:句子“我是大学生”的推导过程如下：句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生,2.2 字母表和符号串,1、字母表和符号定义:元素的非空有穷集合例：=01=ab,c元素也称为符号，字母表也称符号集。程序语言的字母表由字母数字和若干专用符号组成。,2、符号串,定义:由字母表中的符号组成的任何有穷序列例：字母表=01上的符号串：0,00,10等=ab,c上的符号串：a,ab,aaca等,2、符号串,在符号串中，符

4、号是有顺序的，顺序不同,代表不同的符号串，如ab和ba不同不含任何符号的符号串称为空串，用表示注意:并不等于空集合 符号串长度:符号串中含有符号的个数如:|abc|=3|=0,3、符号串的运算,符号串的连接：设x、y是符号串,它们的连接是把y的符号写在 x的符号之后得到的符号串xy例如 x=ST，y=abu，则 xy=STabu x=x=？符号串的方幂：把符号串a自身连接n次得到的符号串an=aaaa a1 a2 a0 a1=a a2=aa a0=,4、符号串集合,定义:若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。符号串集合的乘积：符号串集合A和B的乘积定义为:AB

5、=xy|xA且yB，即AB是由A中的串x和B中的串y连接而成的串xy组成的集合。若集合A=ab,cde B=0,1 则 AB=ab0,ab1,cde0,cde1显然 A=A=？,4、符号串集合,符号串集合的方幂:设A是符号串的集合，则称Ai为符号串集A的方幂，其中i是非负整数。具体定义如下:A0=A1=A,A2=A AAk=AA.A(k个)=AAk-1=Ak-1 A,例：A=0,1,5、集合的闭包,闭包集合A的闭包A*(正闭包A+)定义如下：A+=A1 A2 A3 An A*=A0 A1 A2 A3 An 例：设有字母表=0,1+=12=0,1,00,01,10,11,000,即+表示上0 1

6、构成的所有符号串的集合。*=012=,0,1,00,01,10,11,000,字母表上的一个语言是上符合某种规则的一些符号串的集合，是*的一个子集。例如：=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,1.集合ab,aabb,aaabbb,anbn,或w|w*且w=anbn,n1为字母表上的一个语言。集合a,aa,aaa,或w|w*且w=an,n1为字母表上的一个语言。是一个语言。即 是一个语言。,5、集合的闭包,重点回顾,解释程序(interpreter)与编译程序编译程序是将源程序翻译成目标程序后再执行该目标程序解释程序则是逐条读出源程序中的语句并解释执行，即在解释程序的执行

7、过程中并不产生目标程序。编译的基本过程,重点回顾,字母表和符号符号串符号串的运算符号串的连接符号串的方幂符号串集合符号串集合的乘积符号串集合的方幂集合的闭包,2.3 文法和语言的形式定义,1形式语言的定义2.文法的定义3文法的简化表示法4推导与归约5句型、句子、语言的定义6规范推导和规范归约7文法的递归性,1形式语言的定义,序列的集合称为形式语言（字母表上按某种规则构成的所有符号串的集合）形式语言的描述:枚举法当语言为有穷集合时 文法当语言为无穷集合时,1形式语言的定义,例：=a,b L1=a,b,ab；L2=aa,bb,aabb L3=a,b,aa,ab,ba,bb,aab,aba,abb,

8、baa=+无穷集不宜用枚举法来描述自然语言描述（由a、b构成的所有符号串）非形式化描述 文法描述：形式化描述 A-a A-b A-Aa A-Ab,2文法的定义,产生式（规则）产生式是一个有序对(,)，通常写作（或:=）。读作：定义为。称为产生式的左部，称为产生式的右部。产生式又叫做定义式或者语法规则。一组规则定义了一个语言的语法结构机器识别（语法正确与否）的要求,2文法的定义,例：A0 A1 AA 0 AA 1描述的语言L=0,1,00,01,10,11,100,111,001,000,011=+,非终结符号：出现在规则左部能派生出符号或符号串的那些，即每个非终结符号表示一定符号串的集合，一般

9、用大写字母表示。终结符号：不属于非终结符号的那些符号，他是组成语言的基本符号，是一个语言的不可再分的基本符号，通常用小写字母表示。,文法定义:文法G(Grammar)定义为四元组（VN，VT，P，S）VN(Nonterminal)：非终结符集。VT(Terminal)：终结符集。是语言的句子中出现的字符。所以，有VNVT=P(Production)：产生式（规则）集合S：SVN，开始符号或识别符号,2文法的定义,说明:V=VNVT，V称为文法G的词汇表P中产生式形如：,其中V+且至少含一个非终结符，V*VNVT=S是一个非终结符，且至少要在一条产生式的左部出现,2文法的定义,例1：文法G=(V

10、N,VT,P,S)其中：VN=S，VT=0，1，P=S0S1,S01开始符为S例2：文法G=(VN,VT,P,S)VN=标识符，字母，数字，VT=a,b,c,x,y,z,0,1,9，P=，a,z，0,9，S=,2文法的定义,2文法的定义,例3：以下四元组都是文法。(A，0，1，A01，A0A1，A1A0，A)。(A，0，1，A0，A0A，A)。(A，B，0，1，A01，A0A1，A1A0，BAB，B0，A)。(A，B，0，1，A0，A1，A0A，A1A，A)。(S，a，b，S00S，S11S，S00，S11，S)。,3文法的简化表示法,简化表示法:通常不用将文法的四元组表示出来，只写出产生式约

11、定：第一条产生式的左部是开始符号或用GS表示S是开始符号用大写字母（或用尖括号括起来）表示非终结符用小写字母表示终结符左部相同的产生式A,A可以记为A|，其中“|”是“或”的意思，,分别称为侯选式,例2可以化简为：文法GS：SA|SA|SDAa|b|zD0|1|9,字母,标识符,数字,3文法的简化表示法,例2：文法G=(VN,VT,P,S)VN=标识符，字母，数字，VT=a,b,c,x,y,z,0,1,9，P=，a,z，0,9，S=,4.推导(Derivation)与归约(Reduction),直接推导和直接归约：Aa是文法G的产生式，若有v，w满足：v=xAy,w=xay,则称v直接推导出w

12、,也称w直接归约到v,记作 v w直接推导就是用产生式的右部替换产生式的左部的过程（仅使用一次规则）直接归约就是用产生式的左部替换产生式的右部的过程,例 文法G：S0S1，S01 有直接推导：S 0S1（S0S1）0S1 00S11（S0S1）00S11 000S111（S0S1）000S111 00001111（S01）,4.推导(Derivation)与归约(Reduction),推导和归约若存在直接推导序列0 1 2.n 则称0推导出n，或n归约到0,记为 0=+n若有0=+n，或0=n，则记作0=*n,4.推导(Derivation)与归约(Reduction),例 文法G：S0S1，

13、S01 S 0S1 00S11 000111 S=+000111S=*S,4.推导(Derivation)与归约(Reduction),4.推导(Derivation)与归约(Reduction),例 文法GE：EE+T|T TT*F|F F(E)|i,对i+i*i的直接推导序列,E E+T,T+T,F+T,i+T,i+T*F,i+F*F,i+i*Fi+i*i,5句型、句子、语言的定义,句型和句子设有文法GS，若符号串是从开始符推导出来的,即 S=*，(VNVT)*则称是文法G的句型。若仅由终结符组成,即 S=+，且 VT*，则称是文法G的句子。例 文法GS：S0S1，S01因为S 0S1 0

14、0S11 000S111 00001111所以S,0S1,00S11,000S111,00001111都是G的句型00001111是G的句子,5句型、句子、语言的定义,句型和句子例 文法GE：EE+T|T TT*F|F F(E)|ii+T*F(i*i+i),5句型、句子、语言的定义,语言的定义由文法G生成的语言记为L(G),它是文法G的一切句子的集合,即 L(G)=x|S=+x，且 xVT*例 文法G：S0S1，S01S0S1 00S11 03S13 0n-1S1n-1 0n1nL(G)=0n1n|n1,文法和语言的关系：文法G生成的每个串都在L(G)中L(G)中的每个串确实能被G生成根据语言

15、，可以设计一组规则生成语言中的所以句子而得到该语言相应的文法；但描述该语言的文法不唯一。根据文法，可以通过推导得到该文法相应的语言；从已知文法确定语言的方法：从文法的开始符号出发，反复连续的使用规则，对非终结符施行替换和展开，找出句子规律。,5句型、句子、语言的定义,例：GE：EE+T|TTTF|FF(E)|iEE+T T+T F+T i+T i+TF i+FF i+iF i+ii(i+i);i*i*i;(i*i+i)自然语言描述：一切能用符号i，+，(，)构成的算术表达式,5句型、句子、语言的定义,小结：给定一个文法，就能从结构上唯一的确定其语言，即GL(G)给定一种语言，能确定其文法，但这

16、种文法不是唯一的，即LG1、G2等,5句型、句子、语言的定义,6规范推导和规范归约,同一个句型（句子）可有不同的推导序列如果在推导的任何一步，其中、是句型，都是对中的最左（最右）非终结符进行替换,则称这种推导为最左(最右)推导最右推导被称为规范推导由规范推导所得的句型称为规范句型规范推导的逆过程，称为最左规约，也称为规范规约。,6规范推导和规范归约,例：设有文法GS:S-ABA-A0|1BB-0|S1请给出句子101001的规范推导和规范规约,S,AB,AS1,AAB1,AA01,A1B01,A1001,1B1001,101001,归约符号表示：,7文法的递归性,所谓递归规则是指规则的左部和右

17、部具有相同非终结符的规则A-A规则左递归 A-A规则右递归 A-A规则递归文法递归性：A+A；A+A；A+A递归规则的使用，可用有限的规则刻画无穷的语言。,7文法的递归性,含有递归规则的文法，一定是递归的。不含递归规则的文法也可能是递归的。例：U-Vx V-Uy|zU Vx Uyx 规则不递归 文法左递归例：A-aB|bB B-a|b 是否递归？描述的语言是什么？aa,ab,ba,bb文法无递归性，描述的有穷语言若描述无穷语言，文法一定递归。程序设计语言是无穷集合，描述他们的文法一定递归。,2.4 短语、直接短语和句柄,短语：设S是文法的开始符，是句型(即有S*），如果满足条件：S*A;A+则

18、称是相对于非终结符A的句型的一个短语。直接短语（简单短语）：如果满足条件：S*A;A 则称是句型的一个直接短语。每个直接短语都是某规则的右部。句柄：一个句型可能有多个直接短语，其中最左的直接短语称之为句柄。短语是相对于某个句型的（即句型的一部分）,2.4 短语、直接短语和句柄,例题：文法GN1:N1N NND|D D0|1|2 分析句型ND的短语对文法，首先建立该句型的推导过程：N1=N=ND,2.4 短语、直接短语和句柄,N1=N=ND 从推导过程中，有 N1*N1 N1+ND 句型本身是（相对于S的）句型ND的短语 N1+N，但不存在N1+N1D的推导 N不是该句型的一个短语所以句型ND的

19、短语是自身,短语：设S是文法的开始符，是句型(即有S*），如果满足条件：S*A;A+则称是相对于非终结符A的句型的一个短语。,例题：文法GT:TT*F|F F FP|P P(T)|i 分析句型T*P(T*F)的短语、直接短语和句柄,2.4 短语、直接短语和句柄,2.5 语法树与文法的二义性,1.语法树(推导树Parse Tree)作用:直观地描述上下文无关文法的句型推导过程。给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树,2.5 语法树与文法的二义性,1.语法树(推导树Parse Tree)构造方法：已知G=(VN,VT,P,S)每个节点都有一个标记，此标记为V=

20、VNVT 中的一个符号树根节点是文法的开始符S含分支节点的节点一定属于Vn对规则AA1A2A3.AK是文法的一条规则，则节点A有K个分支节点，其分支节点分别为A1，A2，A3.AK,1.语法树(推导树Parse Tree),例：文法G：EE+T|TTTF|F F（E）|i句型T+TF的推导过程与语法树,E=E+T,E=E+T,=E+TF,=T+TF,=T+T,=T+TF,从语法树中看不出句型中的符号被替代的顺序,从左到右读出叶子结点得到的符号串，为文法的句型。也把该语法树称为该句型的语法树。,例：文法G：E-E+T|E-T|TT-T*F|T/F|FF-(E)|i句型(T+i)*i-F最左（右）

21、推导,1.语法树(推导树Parse Tree),2.5 语法树与文法的二义性,2.子树与简单子树语法树的子树是由某一节点连同所有分支组成的部分语法树的简单子树是指只有单层（深度为1）分支的子树。,3.子树与短语的关系,短语子树的末端节点形成的符号串是相对于子树根的短语直接短语简单子树的末端节点形成的符号串是相对于简单子树根的直接短语句柄最左简单子树的末端节点形成的符号串,文法GT:TT*F|FF FP|PP(T)|i 分析句型T*P(T*F)的短语、直接短语和句柄句型T*P(T*F)的语法树：,T,五棵子树对应五个短语,两层子树(简单子树)的末端结点构成直接短语 两棵两层子树对应两个直接短语：

22、P,T*F位于最左边的两层子树的末端结点构成句柄：P,3.子树与短语的关系,P,T*P(T*F),P(T*F),T*F,(T*F),重点回顾,产生式（规则）非终结符号终结符号文法G(Grammar)定义为四元组（VN，VT，P，S）VN(Nonterminal)：非终结符集。VT(Terminal)：终结符集。是语言的句子中出现的字符。所以，有VNVT=P(Production)：产生式（规则）集合S：SVN，开始符号或识别符号,重点回顾,推导与归约直接推导、直接归约推导和归约规范推导、规范归约句型、句子、语言的定义语法树子树与简单子树,重点回顾,子树与短语的关系短语子树的末端节点形成的符号串

23、是相对于子树根的短语直接短语简单子树的末端节点形成的符号串是相对于简单子树根的直接短语句柄最左简单子树的末端节点形成的符号串,短语与语法树文法G：EE+T|TTTF|F F（E）|i文法GE的句型TF+i语法树：,五棵子树对应三个短语,两层子树(简单子树)的末端结点构成直接短语 两棵两层子树对应两个直接短语：TF，i位于最左边的两层子树的末端结点构成句柄：TF,3.子树与短语的关系,T F，i，T F+i,E=E+T,E=E+T,句型的左右推导应构造出同一棵语法树,4.文法的二义性(Ambiguity),文法G：EE+T|TTTF|F F（E）|i,=E+TF,=T+TF,=T+T,=T+TF

24、,文法G：EE+E|EE|（E）|i句子 ii+i 对应的语法树,两个不同的最左推导：推导1：E E+E EE+E iE+E ii+E ii+i推导2：E EE iE iE+E ii+E ii+i,4.文法的二义性(Ambiguity),定义:如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的。二义性文法存在某个句子,它有两个不同的最左（右）推导对于一个程序设计语言来说，希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。,文法G1：EE+E|EE|（E）|i,文法G2：ET|E+TTF|TFF(E)|i,4.文法的二义性(Ambiguity),2.6 文法和语言的分

25、类,通过对产生式施加不同的限制，乔姆斯基（Chomsky）将文法和语言分为四种类型（0、1、2、3型）。0型文法(无限制文法)：对任一产生式，都有(VNVT)*且至少含有一个非终结符，(VNVT)*0型文法描述的是0型语言（无限制语言）,2.6 文法和语言的分类,例：GS:S-0AB1B-0B-SA|01A1-SB1A0-S0B,2.6 文法和语言的分类,1型文法(上下文有关)：文法G中每一条规则的形式为A u，都有、(VNVT)*,AVN，u(VNVT)+。称G是1型文法。它表示当A的上文为且下文为时可把A替换成，因此称1型文法为上下文有关文法。|A|?|u|1型文法描述的是1型语言（上下文

26、有关语言）,例 文法GS：SaSBE SaBEaBab bBbb bEbe eEee,2.6 文法和语言的分类,2.6 文法和语言的分类,2型文法(上下文无关文法)：它是1型文法的特例，对任一产生式，都有VN，(VN VT)*，则称G是2型文法。2型文法描述的是2型语言（上下文无关语言）,例 文法GS：SAB ABS|0BSA|12型文法产生式的一般形式是:A，它表示不管A的上下文如何都可把A替换成，因此被称为上下文无关文法。通常程序设计语言的文法，可用2型文法来描述，因此我们重点研究2型文法。,2.6 文法和语言的分类,2.6 文法和语言的分类,3型文法(正规文法)：它是2型文法的特例，任一

27、产生式的形式都为 AaB或Aa；（ABa或Aa）其中A，BVN，aVT。3型文法描述的是3型语言（正规语言）。在程序设计语言中，3型文法通常用来描述单词的结构。,2.6 文法和语言的分类,四种文法之间的逐级“包含”关系,2.7 自上而下的分析方法,定义:从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。语法树的构造：将文法的开始符号作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。,例 文法G：S cAd A ab|a识别输入串w=cabd是否为该文法的句子,S,推导过程：,=cabd,S,=cAd,2.7 自上而下的分析方法,自上而下方法的主

28、要问题对输入串cabd自上而下构造语法树的另一过程,不成功，不成功的原因是选错产生式Aa,自上而下分析的主要问题是选择产生式:假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？,S,2.7 自上而下的分析方法,2.7 自上而下的分析方法,自下而上的分析方法:从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。语法树的构造：从输入符号串开始，以它作为语法树的末端结点符号串，自底向上的构造语法树,例 文法G：S cAd A ab|a识别输入串w=cabd是否为该文法的句子,归约过程：,用“|-”表示归约，下划线部分为被归约符号,cabd,|-

29、cAd,|-S,自下而上的分析方法,自下而上分析的主要问题对输入串cabd的两种归约过程（1）cabd|-cAd|-S 归约到开始符（2）cabd|-cAbd 不能归约到开始符在自下而上的分析方法中，每一步都是从当前串中选择一个子串加以归约，该子串暂称“可归约串”。如何确定“可归约串”是自下而上分析的主要问题。,自下而上的分析方法,2.8有关文法实用中的一些说明,有关文法的实用限制：有害规则和多余规则有害规则：AA,无用且引起文法的二义多余规则：所有句子的推导都用不到的规则，表现形式：不可到达：不在任何句型中出现的非终结符的规则不可终止：不可推出终结符号串的非终结符的规则,例：文法GS：（1）SBe（2）BCe（3）BAf（4）AAe（5）Ae（6）CCf（7）Df 多余规则为：（7）不可到达（6）不可终止（2）也是多余的,2.8有关文法实用中的一些说明,