编译原理第2章文法和语言.ppt

《编译原理第2章文法和语言.ppt》由会员分享，可在线阅读，更多相关《编译原理第2章文法和语言.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、o基本概念基本概念 字母表、符号、符号串、闭包等字母表、符号、符号串、闭包等o文法的定义文法的定义o文法的分类文法的分类Chromsky Chromsky 对文法的分类对文法的分类o文法和语言文法和语言推导、归约、句型、句子、语言推导、归约、句型、句子、语言o语法分析树和二义性语法分析树和二义性第二章第二章 文法和语言文法和语言2.1 2.1 文法和语言的定义文法和语言的定义例句：例句：int i=0;int i=0;包含字母包含字母i,n,t,=,0,;,i,n,t,=,0,;,所有字母形成字母表；所有字母形成字母表；符号串，如符号串，如intint定义定义2.1 2.1 字母表字母表：字母

2、表：字母表是符号元素的非空有限集合。是符号元素的非空有限集合。定义定义2.2 2.2 符号符号（字符）：字母表中的元素。（字符）：字母表中的元素。定义定义2.3 2.3 符号串符号串（字符串）：字母表中的符号所组成的任何（字符串）：字母表中的符号所组成的任何有穷有穷序列。序列。如字母表如字母表=a,b=a,b，则，则a,ba,b是字母表是字母表中的元素，中的元素，a,b,aa,ab,a,b,aa,ab,都是符号串。都是符号串。空符号串空符号串：不含任何符号的符号串，用：不含任何符号的符号串，用 表示。表示。字母表，符号，符号串字母表，符号，符号串2.1 2.1 文法和语言的定义文法和语言的定义

3、o定义定义2.4 2.4 符号串符号串x x和和y y的的连接连接：指：指x x和和y y的符号按的符号按先后先后顺序排列顺序排列在一起组成的新的符号串，用在一起组成的新的符号串，用xyxy表示。表示。例：若例：若=a,b,x=ab,y=ba,=a,b,x=ab,y=ba,则则xy=abba,yx=baabxy=abba,yx=baab。注意：（注意：（1 1）xyyxxyyx；（2 2）x=x=xx=x=x。o定义定义2.5 2.5 符号串的长度符号串的长度：指符号串中符号的个数。：指符号串中符号的个数。例：例：|ab|=2,|aabb|=4,|=0|ab|=2,|aabb|=4,|=0。字

4、符串连接、字符串长度字符串连接、字符串长度2.1 2.1 文法和语言的定义文法和语言的定义o定义定义2.6 符号串的符号串的前缀前缀和和后缀后缀：分别指符号串的左部和右部任意字：分别指符号串的左部和右部任意字符串。符串。例：例：ab的前缀有的前缀有、a、ab；后缀有；后缀有、b、ab。o定义定义2.7 符号串集合的符号串集合的乘积乘积：设：设A、B是字母表是字母表上的符号串集合，则上的符号串集合，则定义定义A与与B的乘积：的乘积：AB=xy|x A，y B。o例：设例：设=a，b，c，d，令，令A=aa,bb，B=cc,dd,则则AB=aacc,aadd,bbcc,bbdd,BA=ccaa,c

5、cbb,ddaa,ddbb。显然。显然ABBA定义定义空集合空集合：=，有，有A=A=A。前缀、后缀、乘积前缀、后缀、乘积2.1 2.1 文法和语言的定义文法和语言的定义o定义定义2.8 符号串的符号串的方幂方幂：设：设x是符号串，则：是符号串，则：x0=,x1=x,x2=xx,xn=xx(n个个)o定义定义2.9 符号串集合符号串集合A的的方幂方幂：A0=,A1=A,A2=AA,An=AA(n个个A)oA的的正闭包正闭包：A+=A1A2oA的的闭包闭包：A*=A0A1A2o显然：显然：A*=A0A+,A+=AA*o问题问题：A=0,1,则则A+表示的集合意义？表示的集合意义？方幂、正闭包、闭

6、包方幂、正闭包、闭包2.1 2.1 文法和语言的定义文法和语言的定义o什么是文法什么是文法n文法是定义或描述语法结构的一组形式规则，是规则的非空有穷集合文法是定义或描述语法结构的一组形式规则，是规则的非空有穷集合n规则又称为重写规则，产生式或生成式，每个产生式为规则又称为重写规则，产生式或生成式，每个产生式为 或或 :=:=，是某字母表是某字母表A A的正闭包的正闭包A A+的一个符号称为规则的左部；的一个符号称为规则的左部；是是A A*中的一中的一个符号，称为规则的右部。个符号，称为规则的右部。n 与与 的区别？的区别？文法文法2.1 2.1 文法和语言的定义文法和语言的定义o什么是文法什么

7、是文法n文法是定义或描述语法结构一组形式规则，是规则的非空又穷集合文法是定义或描述语法结构一组形式规则，是规则的非空又穷集合n规则又称为重写规则，产生式或生成式，每个产生式为规则又称为重写规则，产生式或生成式，每个产生式为 或或 :=:=，是某字母表是某字母表A A的正闭包的正闭包A A+的一个符号称为规则的左部；的一个符号称为规则的左部；是是A A*中中的一个符号，称为规则的右部。的一个符号，称为规则的右部。n 与与 的区别？的区别？例句：例句：He gave me a book.He gave me a book.英语中的基本语法规则：英语中的基本语法规则：|He He|me|me boo

8、k book gave gave a|an|the a|an|the例句：例句：He gave me a book.He gave me a book.根据上述语法规则对例句进行分析，可推出该例句。根据上述语法规则对例句进行分析，可推出该例句。=He He =He He =He gave He gave =He gave He gave =He gave me He gave me =He gave me He gave me =He gave me a He gave me a =He gave me a book =He gave me a book文法文法2.1 2.1 文法和语言的定义

9、文法和语言的定义int i=0;int i=0;i=i+1;i=i+1;+|=+=(a|z|A|Z|_)(a|z|A|Z|_|0|9)(a|z|A|Z|_)(a|z|A|Z|_|0|9)int|char|int|char|文法包含的要素：文法包含的要素：终极字符集：终极字符集：如如int iint i非终非终极极字符集：字符集：如如 、产生式：产生式：如如 +开始符号：开始符号：文法文法2.1 2.1 文法和语言的定义文法和语言的定义o定义定义2.10 文法文法是一个四元组：是一个四元组：GS=(VN,VT,P,S),其中：其中：VN：非终极符集合（变量集）；：非终极符集合（变量集）；VT：终

10、极符集合；：终极符集合；P：产生式集合，每个产生式为：产生式集合，每个产生式为或或:=，设，设V=VN VT，则，则 V*VNV*，V*；S：开始符号。：开始符号。注意：注意：p VN,VT,P三个集合均为非空有穷集合三个集合均为非空有穷集合p VN VT=p V=VN VT表示文法表示文法G的字母表或词汇表的字母表或词汇表o例例2.1 G=(N,0,1,N0N,N1N,N0,N1,N)，其中：，其中：VN=N;VT=0,1;P=N0N,N1N,N0,N1;S=N。文法文法2.1 2.1 文法和语言的定义文法和语言的定义o规则规则1：a表示表示a的的0次或多次重复出现，即次或多次重复出现，即a

11、表示表示或或a或或aa或或aaa或或aa；am表示表示a的的m到到n次出现。次出现。o规则规则2：a=a01o规则规则3：AxW1y|xW2y|xWny可表示成可表示成Ax(W1|W2|Wn)yn文法产生式的其它表示法：文法产生式的其它表示法：文法文法2.1 2.1 文法和语言的定义文法和语言的定义o定义定义2.11 符号串的符号串的推导推导与与归约归约：已给文法：已给文法G=VN,VT,P,S，V=VN VT，令，令x,y,V*，且，且 P，则，则xy能能直接推导直接推导出出xy，或者或者xy 直接规约直接规约到到xy，记作，记作xyxy。“”读作直接推导读作直接推导例例2.1 G=(N,0

12、,1,N0N,N1N,N0,N1,N)中，存中，存在如下推导：在如下推导：N0 N1 N0N00 N0N01 N1N11N111文法文法2.1 2.1 文法和语言的定义文法和语言的定义 若若若若 1 1,2 2,3 3,n n V*,V*,且有直接推导的序列且有直接推导的序列且有直接推导的序列且有直接推导的序列 1 1 2 2,2 2 3 3,n-1n-1 n n,则称则称则称则称 1 1可可可可推推推推导导导导出出出出 n n，或，或，或，或 n n 规约规约规约规约到到到到 1 1 ，记作，记作，记作，记作 1 1 n n+若若若若 1 1 n n,或或或或 1 1=n n，则记为，则记为

13、，则记为，则记为 1 1 n n+*归约是推导的逆过程，若存在归约是推导的逆过程，若存在归约是推导的逆过程，若存在归约是推导的逆过程，若存在 1 1 n n，则认为，则认为，则认为，则认为 n n能能能能归约归约为为为为 1 1例例2.2 G=(N,0,1,N0N,N1N,N0,N1,N)中：中：有有有有N N0N0N0000，所以，所以，所以，所以 N N 00 00+文法文法2.1 2.1 文法和语言的定义文法和语言的定义oN.Chomsky在在1956年描述形式语言时给出了四类文法的定义。年描述形式语言时给出了四类文法的定义。o0型型文文法法（短短语语文文法法）：要要求求每每个个产产生生

14、式式,有有 V*VNV*，V*,即即 中至少含有一个非终结符中至少含有一个非终结符。o1型文法型文法(上下文有关文法上下文有关文法)：如果对：如果对0型文法施加以下的限制，就得到型文法施加以下的限制，就得到1型型文法：文法：对除对除S外的任何产生式外的任何产生式，要求，要求1|即规则左部符号个数不超过右部符号个数，即规则左部符号个数不超过右部符号个数，S除外除外如：如：A是是1型文法的一个产生式，型文法的一个产生式，和和非空，则只有在非空，则只有在和和这这样一个上下文中样一个上下文中A才能替换为才能替换为。文法分类文法分类注意：注意：如果规则左部有如果规则左部有终结符终结符，则该文法一定属于，

15、则该文法一定属于0或或1型文法。型文法。0、1型文法的型文法的区别区别：规则左、右部的长度：规则左、右部的长度 如果文法中所有规则左部符号串长度均如果文法中所有规则左部符号串长度均小于或等于小于或等于右部符号右部符号串长度，则称为串长度，则称为1型文法，否则为型文法，否则为0型文法。型文法。2.1 2.1 文法和语言的定义文法和语言的定义o2型文法型文法(上下文无关文法上下文无关文法)：如果对：如果对1型文法施加以下的限制，就得到型文法施加以下的限制，就得到2型文法：型文法：G的任何产生式为的任何产生式为A,A VN,(VN VT)*这种文法意味着，每一规则左部只有一个非终结符，无需考虑该非终

16、结符这种文法意味着，每一规则左部只有一个非终结符，无需考虑该非终结符在上下文中的出现情况。在上下文中的出现情况。o3型文法型文法(正则文法正则文法)：如果对如果对2型文法施加以下的限制，就得到型文法施加以下的限制，就得到3型文法：型文法：G的任何产生式为的任何产生式为AB|,或者或者AB|,其中其中 A,B VN,VT3型文法称为型文法称为右线性文法或左线性文法右线性文法或左线性文法；3型文法等价于正规式，所以又称型文法等价于正规式，所以又称正规文法。正规文法。文法分类文法分类总结：总结：2、3型文法规则左部仅为非终结符，若规则型文法规则左部仅为非终结符，若规则右部形式仅为右部形式仅为AB|,

17、或者或者AB|（A,B VN,VT）则为）则为3型文法，否则为型文法，否则为2型文法型文法四种四种类型描述能力比型描述能力比较0型1型2型3型2.1 2.1 文法和语言的定义文法和语言的定义o定义定义2.12 文法文法G=VN,VT,P,S：GG所产生的所产生的所产生的所产生的语言语言，记作，记作，记作，记作L(G)=|L(G)=|V VT T*,*,且且且且S S。*若字符串若字符串若字符串若字符串 是从识别符推导出来的，即是从识别符推导出来的，即是从识别符推导出来的，即是从识别符推导出来的，即S S,则称则称则称则称 为为为为GG的的的的句型句型；若若若若 仅由终结符号组成，即仅由终结符号

18、组成，即仅由终结符号组成，即仅由终结符号组成，即S S，V VT T*,*,则称则称则称则称 为为为为GG的的的的句子；句子；*要求：要求：（1）能根据文法分析其所产生的语言；）能根据文法分析其所产生的语言；（2）能根据语言构造其文法。）能根据语言构造其文法。语言语言*2.1 2.1 文法和语言的定义文法和语言的定义o文法文法 G=VN,VT,P,S，其中：，其中：VN=，；VT=0,1,2,3,4,5,6,7,8,9；P:|0|1|2|3|4|5|6|7|8|9S=写出其对应的语言。写出其对应的语言。分析分析：S=；由由，可得数字串为，可得数字串为09的任意数字；的任意数字；每次用每次用推导

19、，末尾就增加一个推导，末尾就增加一个09的数字，的数字，直到使用直到使用推导为止。推导为止。结论结论：L(G)表示十进制非负整数。表示十进制非负整数。根据文法抽象语言根据文法抽象语言2.1 2.1 文法和语言的定义文法和语言的定义当语言包含的句子无限时，如何构造文法？当语言包含的句子无限时，如何构造文法？2.1 2.1 文法和语言的定义文法和语言的定义例例2.3 构造文法构造文法G，使其描述的语言为，使其描述的语言为正奇数正奇数集合。集合。令令G=VN,VT,P,VT=0,1,2,3,4,5,6,7,8,9P:1|3|5|7|9|0|2|4|6|8VN=,分析分析：正奇数要求，要么是一位奇数数

20、字，要么是以奇数数字结尾的十进制：正奇数要求，要么是一位奇数数字，要么是以奇数数字结尾的十进制数字。数字。根据语言构造文法根据语言构造文法2.1 2.1 文法和语言的定义文法和语言的定义例：构造语言的文法例：构造语言的文法 L(G)=anbn|n0o可能的句子：可能的句子：ooaboaabboaaabbboa bababS SaSbGS=(S,a,b,S|aSb,S)|aSb,S)根据语言构造文法根据语言构造文法2.1 2.1 文法和语言的定义文法和语言的定义o若若=,则则A是是左递归产生式左递归产生式；o若若,=,则则A是是右递归产生式右递归产生式；o若文法若文法G中至少有一个递归产生式，则

21、称中至少有一个递归产生式，则称G是是递归文法递归文法。定义定义定义定义2.13 2.13 文法文法文法文法G=VG=VNN,V,VT T,P,S,P,S，若，若，若，若A A P P且且且且 AA成立，则称成立，则称成立，则称成立，则称A A 是是是是递归递归的；的；的；的；*递归文法递归文法2.1 2.1 文法和语言的定义文法和语言的定义o若推导过程中，总是最先替换最右若推导过程中，总是最先替换最右(左左)的非终结符，则称为的非终结符，则称为最右最右(左左)推导推导o若归约过程中，总是最先归约最右若归约过程中，总是最先归约最右(左左)的非终结符，则称为的非终结符，则称为最右最右(左左)归约归

22、约 若若若若 1 1,2 2,3 3,n n V*,V*,且且且且 1 1 2 2,2 2 3 3,n-1n-1 n n,则则则则 1 1可推导出可推导出可推导出可推导出 n n，记，记，记，记作作作作 1 1 n n+若若若若 1 1 n n或者或者或者或者 1 1=n n，则记为，则记为，则记为，则记为 1 1 n n+*归约是推导的逆过程，若存在归约是推导的逆过程，若存在归约是推导的逆过程，若存在归约是推导的逆过程，若存在 1 1 n n，则认为，则认为，则认为，则认为 n n能能能能归约归约为为为为 1 1推导、规约推导、规约2.1 2.1 文法和语言的定义文法和语言的定义定义定义2.

23、14 句型的最右推导称为句型的最右推导称为规范推导规范推导，其逆过程最左规约称为，其逆过程最左规约称为规范归约规范归约。例如：例如：例如：例如：GG的产生式：的产生式：的产生式：的产生式：E EE+E|E*E|(E)|iE+E|E*E|(E)|i，其中，其中，其中，其中V VT T=+,*,(,),i=+,*,(,),ii*i+i的规范推导的规范推导：E EE*EE*EE*E+EE*E+EE*E+iE*E+iE*i+iE*i+ii*i+ii*i+i规范推导是规范规约的逆过程规范推导是规范规约的逆过程规范推导是规范规约的逆过程规范推导是规范规约的逆过程规范推导、规范规约规范推导、规范规约2.1

24、2.1 文法和语言的定义文法和语言的定义语法树（推导树）语法树（推导树）语法树是一种语法树是一种描述上下文无关文法句型推导描述上下文无关文法句型推导的直观方法，定义为：的直观方法，定义为：给定文法给定文法GS,对于对于G的任何句型都能构造与之关联的语法树，这棵树满足以下的任何句型都能构造与之关联的语法树，这棵树满足以下4个条个条件件:(1)每个每个节点节点都有一个都有一个标记标记，此标记是，此标记是V的一个符号的一个符号(2)根的标记是根的标记是S，即文法的，即文法的标识符号标识符号(3)若一个节点若一个节点n至少有一个它自己除外的子孙至少有一个它自己除外的子孙,并且有标记并且有标记A,则则A

25、肯定在肯定在VN中中(4)若节点若节点n的直接子孙从左到右的次序是节点的直接子孙从左到右的次序是节点n1,n2,nk,其节点分别为其节点分别为A1,A2,Ak,那么那么A A1A2Ak一定是一定是GS中的一条规则。中的一条规则。构造过程：构造过程：（1）从）从识别符号识别符号开始，向下画一个分支，表示第一个直接推导开始，向下画一个分支，表示第一个直接推导（2）再从非终结符号往下画分支，表示即将进行的直接推导，如此进行下去，）再从非终结符号往下画分支，表示即将进行的直接推导，如此进行下去，直到全部推导都在树上表示出来，即可得到语法树直到全部推导都在树上表示出来，即可得到语法树2.1 2.1 文法

26、和语言的定义文法和语言的定义语法树（推导树）语法树（推导树）已知已知G1S:S A|S-A,A a|b|c已知已知G2S:S A|A-S,A a|b|cSS-A句子句子a-b-c的推导过程的推导过程(规范推导规范推导)：SS-AS-AS-cS-cS-A-cS-A-cS-b-c S-b-c A-b-c A-b-c a-b-ca-b-ccS-AbAa句子句子a-b-c的推导过程的推导过程(规范推导规范推导)：SA-SA-SA-S-AA-S-AA-S-cA-S-cA-A-c A-A-c A-A-b-c b-c a-b-ca-b-cSA-SA-SabAa2.1 2.1 文法和语言的定义文法和语言的定义

27、o例例2.2中：中：,|,0|1|2|3|4|5|6|7|8|9有：有：1因此因此1是句型是句型1相对于相对于的短语，而且是直接短语。的短语，而且是直接短语。定义定义定义定义2.15 2.15 文法文法文法文法G=VG=VNN,V,VT T,P,S,P,S，若有，若有，若有，若有S SxAyxAyxyxy，则，则，则，则 称为称为称为称为xy相对于相对于A的的短语短语；若有；若有；若有；若有S SxAyxAyxyxy，则，则，则，则 称为称为称为称为xy相对于相对于A的直接短语的直接短语。*+*句型的最左直接短语称为此句型的句型的最左直接短语称为此句型的句型的最左直接短语称为此句型的句型的最左

28、直接短语称为此句型的句柄句柄。不是不是不是不是 的短语，因为要求：的短语，因为要求：的短语，因为要求：的短语，因为要求：，后面一项不成立。，后面一项不成立。，后面一项不成立。，后面一项不成立。*+短语、直接短语、句柄短语、直接短语、句柄2.1 2.1 文法和语言的定义文法和语言的定义1、有没有简单的方法判定一个句型的所有短语、直接短语、句柄？、有没有简单的方法判定一个句型的所有短语、直接短语、句柄？根据语法树寻找短语、直接短语、句柄根据语法树寻找短语、直接短语、句柄规则：规则：（1）语法树）语法树子树子树的的末端末端节点符号串节点符号串就是语法树所就是语法树所描述句型的描述句型的短语短语（相对

29、于（相对于子数的根）子数的根）（2）简单子树（只有父）简单子树（只有父子两代）的末端节点符号子两代）的末端节点符号串就是串就是直接短语直接短语（3）最左简单子树最左简单子树的末的末端节点符号串就是端节点符号串就是句柄句柄GE:E E+T|T,T T*F|F,F i|(E).句型：句型：F*F*(T+T*i)推导过程：推导过程：ET T T*F T*F T*(E)T*(E)T*(E+T)T*(E+T)T*(E+T*F)T*(E+T*F)T*(E+T*i)T*(E+T*i)T*(T+T*i)T*(T+T*i)T*F*(T+T*i)T*F*(T+T*i)F*F(T+T*i)F*F(T+T*i)ETT

30、*FT*FF(E)+TTT*FiE所有短语：所有短语：F(相对于相对于T)F*F(相对于相对于T)T(相对于相对于E)i(相对于相对于F)T*i(相对于相对于T)(T+T*i)相对于相对于FF*F(T+T*i)相对于相对于T,E直接短语：直接短语：F(相对于相对于T)T(相对于相对于E)i(相对于相对于F)句型的句柄：句型的句柄：F2.2 2.2 句型的语法树和文法的二义性句型的语法树和文法的二义性o若一个文法存在某个句型对应两棵不同的语法树，则称此文法是若一个文法存在某个句型对应两棵不同的语法树，则称此文法是二义性文法二义性文法。o例例2 G=(E,+,*,i,(,),P,E),其中其中P为

31、：为：EE+E|E*E|(E)|i,则则E*E+i对应的语法树：对应的语法树：EE*EE+EiEE+EE*Ei文法的二义性文法的二义性2.2 2.2 句型的语法树和文法的二义性句型的语法树和文法的二义性o定理定理2.2 若文法是非二义的，则此文法的规范句型的若文法是非二义的，则此文法的规范句型的句柄句柄是是唯一唯一的。的。非二义文法的句型对应一棵唯一的语法树，而语法树最左二层子树的叶结非二义文法的句型对应一棵唯一的语法树，而语法树最左二层子树的叶结点所组成的符号串是句柄，因此它的句柄是唯一的。点所组成的符号串是句柄，因此它的句柄是唯一的。2.2 2.2 句型的语法树和文法的二义性句型的语法树和

32、文法的二义性o文法文法G=(E,T,F,+,*,i,(,),P,E),其中其中P为：为：EE+T|T TT*F|F F(E)|i句子句子i+i*i的的规范推导规范推导为：为：EE+TEE+TE+T*FT*FE+T*iiE+i*iiT+i*iTF+i*iFi+i*iiFE+F*i2.2 2.2 句型的语法树和文法的二义性句型的语法树和文法的二义性o文法文法G=(E,T,F,+,*,i,(,),P,E),其中其中P为：为：EE+T|T TT*F|F F(E)|i句子句子i+i*i的的规范归约规范归约为：为：EEE+TE+T*FTE+F*iFE+i*iTT+i*iEF+i*iTi+i*i+*iiF何

33、时能够规约？利用哪个产生何时能够规约？利用哪个产生式进行规约？式进行规约？根据读入字符及现有句型，判断是否为根据读入字符及现有句型，判断是否为句柄，如为句柄，则进行规约。句柄，如为句柄，则进行规约。EE+TT*FiiTFiFE+T*iFi2.2 2.2 句型的语法树和文法的二义性句型的语法树和文法的二义性o规范归约算法：规范归约算法：符号栈符号栈Sk：存放句型的前缀，初始值为存放句型的前缀，初始值为”#”;输入缓冲区输入缓冲区R：存放要识别的串，初始值为存放要识别的串，初始值为”i+i*i#”;单元单元a：从从R左侧读入符号并归约，直到读到结束符左侧读入符号并归约，直到读到结束符”#”。o算法

34、：算法：S1：置初值：置初值a=“”;k=1;s1=“#”;S2：从：从R中读入下一个符号到中读入下一个符号到a；S3：若：若sk的内容的内容=“#E”且且a=“#”，则归约成功，结束；否则转，则归约成功，结束；否则转S4；S4：sk栈顶部分为当前句型的句柄，转栈顶部分为当前句型的句柄，转S5；否则转；否则转S6；S5：sk栈顶部分用一个产生式左部代替；栈顶部分用一个产生式左部代替；S6：a中符号移进中符号移进sk，转，转S2；S7：End。2.2 2.2 句型的语法树和文法的二义性句型的语法树和文法的二义性n文法文法G=(E,T,F,+,*,i,(,),P,E),其中其中P为：为：EE+T|

35、T TT*F|F F(E)|i 句子句子i+i*i的的规范归约规范归约为：为：2.3 2.3 小结小结(1)文法文法(2)句型、句子、语言，文法和语言的构造句型、句子、语言，文法和语言的构造(3)递归文法递归文法(4)规范推导和规范规约规范推导和规范规约(5)短语、直接短语、句柄短语、直接短语、句柄(6)文法的文法的Chomsky分类分类(7)文法产生式的其它表示法文法产生式的其它表示法2.3 2.3 小结小结(1)语法树语法树(2)文法的二义性的判定文法的二义性的判定(3)规范归约算法规范归约算法句型句型短语短语句柄句柄某个句型是否存在两种推导某个句型是否存在两种推导某个句型是否存在两棵语法树某个句型是否存在两棵语法树