第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) 定义: 是一组规则，用它可以形成和产生一个合适的程序 描述工具:文法 作用: 定义什么样的符号序列是合法的，与符号的含义无关。,形式语言

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

4、号串： 0,00,10等 =ab,c上的符号串： a,ab,aaca等,2、符号串,在符号串中，符号是有顺序的，顺序不同,代表不同的符号串，如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、符号

5、串集合,定义: 若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。 符号串集合的乘积：符号串集合A和B的乘积定义为: AB =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 A Ak = AAA (k个)=AAk-1=Ak-1 A,例：A=0,1,5、集合的闭包,闭

6、包 集合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构成的所有符号串的集合。 *=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

7、为字母表上的一个语言。 是一个语言。 即 是一个语言。,5、集合的闭包,重点回顾,解释程序(interpreter)与编译程序 编译程序是将源程序翻译成目标程序后再执行该目标程序 解释程序则是逐条读出源程序中的语句并解释执行，即在解释程序的执行过程中并不产生目标程序。 编译的基本过程,重点回顾,字母表和符号 符号串 符号串的运算 符号串的连接 符号串的方幂 符号串集合 符号串集合的乘积 符号串集合的方幂 集合的闭包,2.3 文法和语言的形式定义,1形式语言的定义 2. 文法的定义 3文法的简化表示法 4推导与归约 5句型、句子、语言的定义 6规范推导和规范归约 7文法的递归性,1形式语言的定义

8、,序列的集合称为形式语言（字母表上按某种规则构成的所有符号串的集合） 形式语言的描述: 枚举法当语言为有穷集合时 文法当语言为无穷集合时,1形式语言的定义,例： =a,b L1=a,b,ab； L2=aa,bb,aabb L3=a,b,aa,ab,ba,bb,aab,aba,abb,baa=+ 无穷集不宜用枚举法来描述 自然语言描述（由a、b构成的所有符号串）非形式化描述 文法描述：形式化描述 A-a A-b A-Aa A-Ab,2文法的定义,产生式（规则） 产生式是一个有序对(,)，通常写作 （或:= ）。 读作： 定义为。称为产生式的左部，称为产生式的右部。产生式又叫做定义式或者语法规则。

9、 一组规则定义了一个语言的语法结构 机器识别（语法正确与否）的要求,2文法的定义,例： A0 A1 AA 0 AA 1 描述的语言L=0,1,00,01,10,11,100,111,001,000,011=+,非终结符号：出现在规则左部能派生出符号或符号串的那些，即每个非终结符号表示一定符号串的集合，一般用大写字母表示。 终结符号：不属于非终结符号的那些符号，他是组成语言的基本符号，是一个语言的不可再分的基本符号，通常用小写字母表示。,文法定义: 文法G(Grammar)定义为四元组（VN，VT，P，S） VN (Nonterminal)：非终结符集。 VT (Terminal)：终结符集。是

10、语言的句子中出现的字符。所以，有VNVT = P (Production)：产生式（规则）集合 S： SVN，开始符号或识别符号,2文法的定义,说明: V=VNVT，V称为文法G的词汇表 P中产生式形如：,其中V+且至少含一个非终结符，V* VNVT= S是一个非终结符，且至少要在一条产生式的左部出现,2文法的定义,例1：文法G=(VN,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文法

11、的定义,例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文法的简化表示法,简化表示法: 通常不用将文法的四元组表示出来，只写出产生式 约定： 第一条产生式的左部是开始符号 或用GS表示S是开始符号 用大写字母（或用尖括号括起来）表示非终结符 用小写字母表示终结符 左部相同的产生式A,A可以记为A|， 其中“|”是“或”的意思，,分别称为侯选式,例2

12、可以化简为： 文法GS： SA|SA|SD Aa|b|z D0|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,也称w直接归约到v, 记作 v w 直接推导就是用产生式的右部替换产生式的左部的过程（仅使用一次规则） 直接归约就是用产生式的左部替换产生式的右部的过程,

13、例 文法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， S01 S 0S1 00S11 000111 S =+ 000111 S =

14、* 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 00S11 000S111 00001

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

16、言，可以设计一组规则生成语言中的所以句子而得到该语言相应的文法；但描述该语言的文法不唯一。 根据文法，可以通过推导得到该文法相应的语言； 从已知文法确定语言的方法：从文法的开始符号出发，反复连续的使用规则，对非终结符施行替换和展开，找出句子规律。,5句型、句子、语言的定义,例：GE：EE+T|T TTF|F F(E)|i E E+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) 给定一种语

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

18、的递归性,所谓递归规则是指规则的左部和右部具有相同非终结符的规则 A-A规则左递归 A-A规则右递归 A-A规则递归 文法递归性：A +A； A + A ； A + A 递归规则的使用，可用有限的规则刻画无穷的语言。,7文法的递归性,含有递归规则的文法，一定是递归的。不含递归规则的文法也可能是递归的。 例：U-Vx V-Uy|z U Vx Uyx 规则不递归 文法左递归 例：A-aB|bB B-a|b 是否递归？描述的语言是什么？ aa,ab,ba,bb文法无递归性，描述的有穷语言 若描述无穷语言，文法一定递归。 程序设计语言是无穷集合，描述他们的文法一定递归。,2.4 短语、直接短语和句柄,

19、短语：设S是文法的开始符，是句型(即有S *），如果满足条件： S * A ; A + 则称是相对于非终结符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 +

20、ND 句型本身是（相对于S的）句型ND的短语 N1 + N，但不存在N1 + N1D的推导 N不是该句型的一个短语 所以句型ND的短语是自身,短语：设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的任何句型都能构造与之关联的语

21、法树,2.5 语法树与文法的二义性,1.语法树(推导树Parse Tree) 构造方法：已知G=(VN,VT,P,S) 每个节点都有一个标记，此标记为V=VNVT 中的一个符号 树根节点是文法的开始符S 含分支节点的节点一定属于Vn 对规则AA1A2A3AK是文法的一条规则，则节点A有K个分支节点，其分支节点分别为A1，A2，A3AK,1.语法树(推导树Parse Tree),例：文法G：EE+T|T TTF|F F（E）|i 句型T+TF的推导过程与语法树,E=E+T,E=E+T,=E+TF,=T+TF,=T+T,=T+TF,从语法树中看不出句型中的符号被替代的顺序,从左到右读出叶子结点得到

22、的符号串，为文法的句型。也把该语法树称为该句型的语法树。,例：文法G： E-E+T|E-T|T T-T*F|T/F|F F-(E)|i 句型(T+i)*i-F 最左（右）推导,1.语法树(推导树Parse Tree),2.5 语法树与文法的二义性,2.子树与简单子树 语法树的子树是由某一节点连同所有分支组成的部分 语法树的简单子树是指只有单层（深度为1）分支的子树。,3.子树与短语的关系,短语子树的末端节点形成的符号串是相对于子树根的短语 直接短语简单子树的末端节点形成的符号串是相对于简单子树根的直接短语 句柄最左简单子树的末端节点形成的符号串,文法GT: TT*F|F F FP|P P(T)

23、|i 分析句型T*P (T*F)的短语、直接短语和句柄 句型T*P (T*F)的语法树：,T,五棵子树对应五个短语,两层子树(简单子树)的末端结点构成直接短语 两棵两层子树对应两个直接短语： 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 (Producti

24、on)：产生式（规则）集合 S： SVN，开始符号或识别符号,重点回顾,推导与归约 直接推导、直接归约 推导和归约 规范推导、规范归约 句型、句子、语言的定义 语法树 子树与简单子树,重点回顾,子树与短语的关系 短语子树的末端节点形成的符号串是相对于子树根的短语 直接短语简单子树的末端节点形成的符号串是相对于简单子树根的直接短语 句柄最左简单子树的末端节点形成的符号串,短语与语法树 文法G：EE+T|T TTF|F F（E）|i 文法GE的句型TF+i语法树：,五棵子树对应三个短语,两层子树(简单子树)的末端结点构成直接短语 两棵两层子树对应两个直接短语： TF，i 位于最左边的两层子树的末端

25、结点构成句柄： TF,3.子树与短语的关系,T F，i，T F+i,E=E+T,E=E+T,句型的左右推导应构造出同一棵语法树,4.文法的二义性(Ambiguity),文法G：EE+T|T TTF|F F（E）|i,=E+TF,=T+TF,=T+T,=T+TF,文法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),定义:如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的。二义性文法存在某个句子

26、,它有两个不同的最左（右）推导 对于一个程序设计语言来说，希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。,文法G1： E E+E | EE |（E） | i,文法G2： ET|E+T TF|TF F(E)| i,4.文法的二义性(Ambiguity),2.6 文法和语言的分类,通过对产生式施加不同的限制，乔姆斯基（Chomsky）将文法和语言分为四种类型（0、1、2、3型）。 0型文法(无限制文法)： 对任一产生式，都有(VNVT)*且至少含有一个非终结符， (VNVT)* 0型文法描述的是0型语言（无限制语言）,2.6 文法和语言的分类,例：GS: S-0AB 1B-0 B-

27、SA|01 A1-SB1 A0-S0B,2.6 文法和语言的分类,1型文法(上下文有关)： 文法G中每一条规则的形式为A u，都有、(VNVT)*,AVN ， u(VNVT)+。称G是1型文法。 它表示当A的上文为且下文为时可把A替换成，因此称1型文法为上下文有关文法。 |A|?| u | 1型文法描述的是1型语言（上下文有关语言）,例 文法GS： SaSBE SaBE aBab bBbb bEbe eEee,2.6 文法和语言的分类,2.6 文法和语言的分类,2型文法(上下文无关文法)： 它是1型文法的特例，对任一产生式，都有VN ， (VN VT)*，则称G是2型文法。 2型文法描述的是2

28、型语言（上下文无关语言）,例 文法GS： SAB ABS|0 BSA|1 2型文法产生式的一般形式是: A，它表示不管A的上下文如何都可把A替换成，因此被称为上下文无关文法。 通常程序设计语言的文法，可用2型文法来描述，因此我们重点研究2型文法。,2.6 文法和语言的分类,2.6 文法和语言的分类,3型文法(正规文法)： 它是2型文法的特例，任一产生式的形式都为 AaB或Aa；（ABa或Aa）其中A ，BVN ，aVT。 3型文法描述的是3型语言（正规语言）。 在程序设计语言中，3型文法通常用来描述单词的结构。,2.6 文法和语言的分类,四种文法之间的逐级“包含”关系,2.7 自上而下的分析方

29、法,定义: 从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。 语法树的构造：将文法的开始符号作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。,例 文法G：S cAd A ab| a 识别输入串w=cabd是否为该文法的句子,S,推导过程：,=cabd,S,=cAd,2.7 自上而下的分析方法,自上而下方法的主要问题 对输入串cabd自上而下构造语法树的另一过程,不成功，不成功的原因是选错产生式Aa,自上而下分析的主要问题是选择产生式 : 假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？,S

30、,2.7 自上而下的分析方法,2.7 自上而下的分析方法,自下而上的分析方法: 从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。 语法树的构造：从输入符号串开始，以它作为语法树的末端结点符号串，自底向上的构造语法树,例 文法G：S cAd A ab | a 识别输入串w=cabd是否为该文法的句子,归约过程：,用“|-”表示归约，下划线部分为被归约符号,cabd,|-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有关文法实用中的一些说明,