前后文无关文法和语言 讲稿.ppt

《前后文无关文法和语言 讲稿.ppt》由会员分享，可在线阅读，更多相关《前后文无关文法和语言 讲稿.ppt（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、前后文无关文法和语言 第一页，讲稿共六十七页哦重点和难点重点和难点重点：重点：本章中涉及的概念和术语的理解本章中涉及的概念和术语的理解文法和语言的形式定义文法和语言的形式定义难点：难点：短语和句柄的识别短语和句柄的识别二义性文法的判定二义性文法的判定第二页，讲稿共六十七页哦2.1 语言及其表示方法语言及其表示方法规定一种语言首先要规定它各种构造成分的形式，规定一种语言首先要规定它各种构造成分的形式，词汇、句子等的构造规则及表示法。词汇、句子等的构造规则及表示法。编译原理则应建立有关语言的数学化（形式化）模型，编译原理则应建立有关语言的数学化（形式化）模型，以便对程序语言进行研究。以便对程序语言

2、进行研究。第三页，讲稿共六十七页哦定义定义1：相当大的地区内公众所懂得并使用的相当大的地区内公众所懂得并使用的“话话”，以及组，以及组成这些成这些“话话”的方法的统一体。的方法的统一体。缺点：不够形式化和精确化缺点：不够形式化和精确化定义定义2：某一个字母表上的符号串的（句子）的集合。某一个字母表上的符号串的（句子）的集合。缺点：缺乏语言句子的结构性组成描述，缺点：缺乏语言句子的结构性组成描述，缺乏判断任一缺乏判断任一符号串是否为合法句子判断机制。符号串是否为合法句子判断机制。因此，如果能刻画一个语言句子，就定义了该语言。因此，如果能刻画一个语言句子，就定义了该语言。1 1、语言、语言、语言、

3、语言第四页，讲稿共六十七页哦1956年，年，chomsky建立建立文法文法的数学模型，对形的数学模型，对形式化语言和自动机理论的研究取得较大的成果。式化语言和自动机理论的研究取得较大的成果。1960年。年。P.Nuaur和和J.Boukas首先用首先用BNF成功成功对对ALGOL语言的文法进行了描述，虽然对语义形语言的文法进行了描述，虽然对语义形式化描述不理想，但在程序设计语言的语法描述式化描述不理想，但在程序设计语言的语法描述上有足够的能力。上有足够的能力。至此，程序语言就有了形式化表述。至此，程序语言就有了形式化表述。第五页，讲稿共六十七页哦枚举枚举（句子有限）（句子有限）例：例：L=We

4、 are learning computer science,it is interesting数学表示数学表示(句子无限句子无限)例例:1,1/2,1/3,1/n1/n|n N 制定有限条规则，用来产生所需描述语言中的句子全部，制定有限条规则，用来产生所需描述语言中的句子全部，这些规则即这些规则即文法。文法。建立一种算法能对于任给的符号串，判别是否为给定语言的建立一种算法能对于任给的符号串，判别是否为给定语言的合法句子合法句子自动机理论自动机理论自动机理论自动机理论。2 2、表示方法、表示方法、表示方法、表示方法第六页，讲稿共六十七页哦 语言可以看成在一个语言可以看成在一个基本符号集基本符号

5、集上定义的，上定义的，上定义的，上定义的，按按按按一定规则一定规则一定规则一定规则构成的一切基本符号串组成的集构成的一切基本符号串组成的集合。合。第七页，讲稿共六十七页哦2.2 文法的定义文法的定义1 1、例：、例：、例：、例：“我是大学生我是大学生”是汉语的一个句子。是汉语的一个句子。句子句子=主语谓语主语谓语主语主语=代词名词代词名词代词代词=我我你你他他名词名词=王明王明大学生大学生工人工人英语英语谓语谓语=动词直接宾语动词直接宾语动词动词=是是学习学习直接宾语直接宾语=代词名词代词名词 返回第八页，讲稿共六十七页哦=左端的规则由左端的规则由=右端的符号串代替：右端的符号串代替：句子句子

6、 主语主语谓语谓语 代词代词谓语谓语 我我谓语谓语 我我动词动词直接宾语直接宾语 我是我是直接宾语直接宾语 我是我是名词名词 我是大学生我是大学生 按照如下方式用它们导出句子：按照如下方式用它们导出句子：第九页，讲稿共六十七页哦大学生句子句子主语主语 谓语谓语代词代词动词直接宾语动词直接宾语名词名词我是“我大学生是我大学生是”是否为是否为?第十页，讲稿共六十七页哦sentence subject This|Computers|Iverb-phrase|adverb neververb is|run|am|tellobject the|a|noun university|world|cheese

7、|liesThis is a university.Computers run the world.I am the cheese.I never tell lies.英语句子英语句子第十一页，讲稿共六十七页哦2 2、文法的形式化表示、文法的形式化表示、文法的形式化表示、文法的形式化表示l l符号：符号：符号：符号：表示一个语法单位；表示一个语法单位；=（）表示）表示“定义为定义为”；|表示为表示为“或或”。l l文法：文法：文法：文法：描述语言的形式结构的规则。描述语言的形式结构的规则。产生式，产生式，产生式左部，产生式左部，产生式右部产生式右部第十二页，讲稿共六十七页哦l l文法的一般构成

8、：文法的一般构成：文法的一般构成：文法的一般构成：pp一组终结符号：一组终结符号：一组终结符号：一组终结符号：仅出现在产生式右部的符号仅出现在产生式右部的符号 VT；pp一组非终结符号：一组非终结符号：一组非终结符号：一组非终结符号：至少在产生式左部出现过一次的符号至少在产生式左部出现过一次的符号VN；pp一个开始符号：一个开始符号：一个开始符号：一个开始符号：特殊的非终结符，表示了定义语言中特殊的非终结符，表示了定义语言中最感兴趣的语法范畴。最感兴趣的语法范畴。S；pp一组规则：一组规则：一组规则：一组规则：P G=VT，VN，S，P 例如例如 第十三页，讲稿共六十七页哦q VN，VT和和P

9、是是 非空有穷集；非空有穷集；q VN和和VT不含公共的元素，即不含公共的元素，即VN VT=；q 用用V表示表示VNVT，称文法，称文法G的字母表或字汇表；的字母表或字汇表；q 产生式是形如产生式是形如 或或 =的（的（，）有序对，其中有序对，其中 是是字母表字母表V的一个非空符号串的一个非空符号串(V+)，是是V中的一个符号串，可中的一个符号串，可为空串为空串(V*)。称为产生式左部，称为产生式左部，称作产生式右部。称作产生式右部。说说说说 明：明：明：明：第十四页，讲稿共六十七页哦2.3 由文法产生句子由文法产生句子1 1、推导、推导、推导、推导句子句子 主语主语谓语谓语 代词代词谓语谓

10、语 我我谓语谓语 过程：过程：过程：过程：文法的文法的文法的文法的开始符号开始符号开始符号开始符号开始，每次把当前串的一个开始，每次把当前串的一个开始，每次把当前串的一个开始，每次把当前串的一个非终结符非终结符非终结符非终结符号用于之对号用于之对号用于之对号用于之对应的应的应的应的产生式右部产生式右部产生式右部产生式右部来代换，得到一个新符号串，称来代换，得到一个新符号串，称来代换，得到一个新符号串，称来代换，得到一个新符号串，称一步推导一步推导一步推导一步推导。2 2、推导长度、推导长度、推导长度、推导长度第十五页，讲稿共六十七页哦l 文法的作用就是用有限条规则产生无限多句子。文法的作用就是

11、用有限条规则产生无限多句子。l 某一文法产生的全部句子所组成的集合某一文法产生的全部句子所组成的集合 该该文法产生的语言文法产生的语言。第十六页，讲稿共六十七页哦一、基本定义一、基本定义一、基本定义一、基本定义1、符号：符号：可以相互区别的记号（元素）。可以相互区别的记号（元素）。2、字母表字母表：符号（元素）的非空有穷集合。符号（元素）的非空有穷集合。3、符号串：符号串：由字母表由字母表 中的符号组成的任何有穷序列。中的符号组成的任何有穷序列。空符号串空符号串空符号串空符号串(没有符号的符号串没有符号的符号串)是是 上的符号串。上的符号串。若若x是是 上的符号串，上的符号串，a是是 的元素，

12、则的元素，则xa是是 上的符号串。上的符号串。y是是 上的符号串，当且仅当它可以由上的符号串，当且仅当它可以由1和和2导出。导出。例如：例如：=a,b ，a，b，aa，ab，aabba都是都是 上的符号串上的符号串2.4 有关定义和记号有关定义和记号第十七页，讲稿共六十七页哦4、符号串符号串s的头的头（前缀）（前缀）：移走符号串：移走符号串s尾部的零个或多于零个符号尾部的零个或多于零个符号得到的符号串。得到的符号串。如：如：b是符号串是符号串banana的一个前缀的一个前缀.banana是是 banana前前缀。缀。5、符号串符号串s的尾的尾（后缀）（后缀）：删去符号串：删去符号串s头部的零个

13、或多于零个符头部的零个或多于零个符号得到的符号串。号得到的符号串。如如:nana是符号串是符号串banana的一个后缀的一个后缀.banana是是 banana后缀。后缀。第十八页，讲稿共六十七页哦6、符号串符号串s的子串的子串：从：从s中删去一个前缀和一个后缀得到的符号中删去一个前缀和一个后缀得到的符号串。串。如如:ana是符号串是符号串banana的一个子串。的一个子串。7、符号串符号串s的真前缀的真前缀，真后缀真后缀，真子串真子串：任何非空符号串：任何非空符号串 x，是，是s的的前缀，后缀或子串，并且前缀，后缀或子串，并且 s x。8、符号串的长度符号串的长度：符号串中符号的个数。符号串

14、：符号串中符号的个数。符号串s的长度记为的长度记为|s|。的长度为的长度为0。对于每个符号串对于每个符号串s，s和和两者都是符号串两者都是符号串s的前缀，的前缀，后缀和子串。后缀和子串。第十九页，讲稿共六十七页哦1、连接：连接：符号串符号串x、y的连接，是把的连接，是把y的符号写在的符号写在x的符号之后得的符号之后得到的符号串到的符号串xy。如：如：x=ba,y=ck 则则 xy=back 有有a=a 2、方幂：方幂：符号串自身连接符号串自身连接n次得到的符号串。次得到的符号串。an 定义为定义为 aaaa n个个a a1=a,a2=aa a0=二、符号串的运算二、符号串的运算二、符号串的运算

15、二、符号串的运算第二十页，讲稿共六十七页哦三、符号串集合三、符号串集合三、符号串集合三、符号串集合 若集合若集合A中所有元素都是某字母表中所有元素都是某字母表 上的符号串，则称上的符号串，则称A为为字母表字母表 上的符号串集合。上的符号串集合。1、符号串集合乘积：符号串集合乘积：两个符号串集合两个符号串集合A和和B的乘积定义为的乘积定义为 AB=xy|x A且且y B 例如：若例如：若 集合集合A=ab，cde B=0，1 则则 AB=ab1，ab0，cde0，cde1 2、的闭包：的闭包：上的一切符号串（包括上的一切符号串（包括）组成的集合。记为）组成的集合。记为*第二十一页，讲稿共六十七页

16、哦3、的正闭包：的正闭包：上的上的除除外的所有符号串组成的集合。记为外的所有符号串组成的集合。记为+例：例：=a,b=a,b，求，求*和和。*=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,=a,b,aa,ab,ba,bb,aaa,aab,第二十二页，讲稿共六十七页哦 *包含包含包含包含 上的所有符号串，上的所有符号串，上的所有符号串，上的所有符号串，+包含包含包含包含 上除上除上除上除空串空串空串空串 外的任意符号串。外的任意符号串。外的任意符号串。外的任意符号串。第二十三页，讲稿共六

17、十七页哦1、语言：语言：由由句子句子句子句子组成的集合，为一符号串集合。组成的集合，为一符号串集合。即：字母表即：字母表 上上的一个语言是的一个语言是 上的一些符号串的集合，是上的一些符号串的集合，是*的一个子集。的一个子集。L=S|S*、都是语言都是语言例如：例如：字母表字母表=a,b=a,b 集合集合 w|ww|w*且且w=aw=an nb bn n,n1,n1为为 上上的一个语言。的一个语言。集合集合 w|ww|w*且且w=aw=an n,n1,n1 为为 上上的一个语言。的一个语言。四、语言四、语言四、语言四、语言上上上上的有关运算的有关运算的有关运算的有关运算第二十四页，讲稿共六十七

18、页哦2、语言语言“并并”运算：运算：语言语言L和和M的并为的并为 L M，是一个语言是一个语言:w|w is in L or is in M如：如：L1=a,b,y,z ，M1=1,28,9 L1 M1=a,b,y,z，1,28,9 设设L是（是（上的）一个语言，上的）一个语言，M是（是（上的）一个语言，上的）一个语言，语言语言L和和M的的“并并”，“交交”，“差差”，“连接连接”运算结果运算结果是一是一个语言。个语言。第二十五页，讲稿共六十七页哦3、语言语言L和和M的连接运算：的连接运算：记记为为 LM(可简记为可简记为LM)。LM=st|sL且且 tM 如：如：L=a,b,y,z ，M=1

19、,28,9 LM=a1,b1,y1,z1,a2,b2a9z9 特别的：有特别的：有L =L=L。L的的n次连接次连接Ln=LL.L第二十六页，讲稿共六十七页哦4、语言语言L的的 闭包：闭包：记记为为 L*，L*=L0 L1 L2 .L0=，Ln=L Ln-1=Ln-1 L(n 1)5、语言语言L的正的正 闭包：闭包：记记为为 L+，L+=L1 L2 L3.L+=LL*=L*L L*=L+如：如：L1 =a,b,=a,b,y,z My,z M1 1=1,2=1,28,9 8,9 （L1 M1 1）=a,b,=a,b,y,z y,z，1,21,28,98,9 （L1 M1 1）*=a,b,=a,b

20、,y,z y,z，1,21,28,98,9,aa,1a,aa,1a,xyz,xyz,6789st.6789st.L1（L1 M1 1）*=所有字母打头的字母和数字符号串所有字母打头的字母和数字符号串 第二十七页，讲稿共六十七页哦练习练习1：L=A,B,C,Z,a,b,cz D=0,1,2,3,4,5,6,7,8,9计算：计算：LD，LD，L4，L*，L(L D)*，D+练习练习2：考虑一个文法考虑一个文法G1:SbA AaA|a 它定义了一个什么语言呢？它定义了一个什么语言呢？从开始符从开始符S出发，我们可以推出如下句子：出发，我们可以推出如下句子：SbA ba SbA baA baa SbA

21、 baA baaa可以写为：可以写为：L(G1)=ban|n1第二十八页，讲稿共六十七页哦2.5 语言和文法的形式定义语言和文法的形式定义一个一个上下文无关文法上下文无关文法G定义为四元组定义为四元组(VN，VT，P，S)其中：其中：V VNN：非终结符号非终结符号(或语法实体，或变量或语法实体，或变量)集；集；V VT T：终结符号集；终结符号集；P P：产产生式生式(也称规则也称规则)的集合；的集合；A 其中，其中，(VN VT)*，A VN VN，VT和和P是是 非空有穷集。非空有穷集。S S：称作识别符号或开始符号的一个非终结符，它至少要在一条产生式称作识别符号或开始符号的一个非终结符

22、，它至少要在一条产生式中作为左部出现。中作为左部出现。S VN VN和和VT不含公共的元素，即不含公共的元素，即VN VT=用用V表示表示VN VT，称为文法，称为文法G的字母表或字汇表的字母表或字汇表1、上下文无关文法、上下文无关文法第二十九页，讲稿共六十七页哦例例 文法文法G=（VN，VT，P，S）VN=S,VT=0,1 P=S0S1,S01 S为开始符号为开始符号对此产生式可进行推导产生句子。对此产生式可进行推导产生句子。第三十页，讲稿共六十七页哦2、推导、推导l直接推导直接推导“”是文法是文法G G的产生式，若有的产生式，若有v,wv,w满足：满足：v=,w=v=,w=,其中其中VV*

23、,V,V*则称则称v v直接直接直接直接推导推导推导推导到到w,w,记作记作 v v w w；也称也称w w直接直接直接直接归约归约归约归约到到v v例：例：G G：S0S1，S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1第三十一页，讲稿共六十七页哦例：例：G G：S0S1，S01 S 0S1 00S11 000S111 00001111S S 00S11 00S11S 00001111 推导长度为推导长度为4 若存在若存在v=w0 w1.wn=w(n0)则记为则记为v w，称作，称作v推导出推导出w，或，或w归约到归约到v 若有若有v w

24、 或或 v=w，则记为则记为v wl 推导的长度（长度为推导的长度（长度为n的推导）的推导）第三十二页，讲稿共六十七页哦3、句型和句子句型和句子例：例：G：S0S1，S01S 0S1 00S11 000S111 00001111G的句型的句型 S，0S1，00S11，000S111，00001111G的句子的句子 00001111，01l 句型句型 有文法有文法GS，若，若S x，xV*，则称，则称x是文法是文法G的句型。的句型。l 句子句子 有文法有文法GS，若，若S x，且，且xVT*，则称，则称x是文法是文法G的句子。的句子。第三十三页，讲稿共六十七页哦例：例：GE E：EE+T|TEE

25、+T|T TT*F|F TT*F|F F(E)|a F(E)|a判断：判断：a+a*aa+a*a是否为该文法的句子是否为该文法的句子E EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a句子：用符号句子：用符号a，+，*，(和和)构成的算术表达式构成的算术表达式第三十四页，讲稿共六十七页哦4、语言、语言l l由文法由文法由文法由文法GG生成的语言记为生成的语言记为生成的语言记为生成的语言记为L(G)L(G)，它是文法，它是文法，它是文法，它是文法GG的的的的一切一切一切一切句子句子句子句子的的的的集合集合集合集合:语言中的每个句子可以由上下文无关文法的语言中的每个

26、句子可以由上下文无关文法的开始符号开始符号产生。产生。例：例：G=（0，1，S，S，P）P:S0S1，S01 L(G)=0n1n|n1L(G)=x|S x，S为文法的开始符号，且为文法的开始符号，且x VT*第三十五页，讲稿共六十七页哦q G生成的每个串都在生成的每个串都在L(G)中，中，L(G)中的每中的每个串确实能被个串确实能被G生成。生成。q 文法所产生的语言文法所产生的语言L(G)是无限语言，原是无限语言，原因是所定义的文法中含有递归。因是所定义的文法中含有递归。第三十六页，讲稿共六十七页哦5、文法的递归性、文法的递归性l递归、直接递归：递归、直接递归：如果文法中有形如如果文法中有形如

27、AAA的产生式，其中的产生式，其中，不同时为不同时为，则称产生式，则称产生式A 是直接递归。是直接递归。例：例：GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|aA A，直接递归，直接递归A A，递归，递归 A 称为递归和直接递归的非终结符号称为递归和直接递归的非终结符号若存在若存在 A A,则称则称A 是递归的。是递归的。l 左递归、右递归左递归、右递归 =，左递归左递归 ，=右递归右递归第三十七页，讲稿共六十七页哦 直接递归是递归的一种特殊情况，如果一个语直接递归是递归的一种特殊情况，如果一个语言是无限的，则定义此语法的文法必然是递归的。言是无限的，

28、则定义此语法的文法必然是递归的。例：语言例：语言L=anbbn|n 1,写出产生写出产生L的文法。的文法。GS:S aAb A aAb|b第三十八页，讲稿共六十七页哦q 从语法定义的角度，递归定义是一种较好的方式，从语法定义的角度，递归定义是一种较好的方式，因为它不仅使文法形式简练，而且也给无限语言的因为它不仅使文法形式简练，而且也给无限语言的有限表示提供了一种有效的方法。有限表示提供了一种有效的方法。q 然而左递归会影响某些语法分析方法实现，因此有时然而左递归会影响某些语法分析方法实现，因此有时需要对文法进行等价改造，以便消除其中的左递归。需要对文法进行等价改造，以便消除其中的左递归。第三十

29、九页，讲稿共六十七页哦6、文法的等价性、文法的等价性l 若若L（G1）=L（G2），则称文法），则称文法G1和和G2是是等价的。等价的。如文法如文法G G1AA：A0R A0R 与与G G2SS：S0S1 S0S1 等价等价 A01 S01A01 S01 RA1 RA1第四十页，讲稿共六十七页哦2.6 句型的分析句型的分析如何表示语言中的句子？任给的一个符号串是否为某一文法的句子如何表示语言中的句子？任给的一个符号串是否为某一文法的句子如何表示语言中的句子？任给的一个符号串是否为某一文法的句子如何表示语言中的句子？任给的一个符号串是否为某一文法的句子（型）？需要进行句型分析。（型）？需要进行句

30、型分析。（型）？需要进行句型分析。（型）？需要进行句型分析。qq自顶向下：自顶向下：自顶向下：自顶向下：从文法的开始符号，以给定的符号串为目标，试图从文法的开始符号，以给定的符号串为目标，试图从文法的开始符号，以给定的符号串为目标，试图从文法的开始符号，以给定的符号串为目标，试图推导出串。推导出串。推导出串。推导出串。qq自底向上：自底向上：自底向上：自底向上：给定符号串出发，反复用文法中有关产生式的左部替给定符号串出发，反复用文法中有关产生式的左部替给定符号串出发，反复用文法中有关产生式的左部替给定符号串出发，反复用文法中有关产生式的左部替换当前符号串中的相应子串，以期最后归约为文法开始符号

31、。换当前符号串中的相应子串，以期最后归约为文法开始符号。换当前符号串中的相应子串，以期最后归约为文法开始符号。换当前符号串中的相应子串，以期最后归约为文法开始符号。第四十一页，讲稿共六十七页哦例：例：GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|a E判定判定a+a*a是否为文法的句子？是否为文法的句子？E+TT+TF+Ta+Ta+T*F a+F*F a+a*Fa+a*a第四十二页，讲稿共六十七页哦1、规范推导、规范推导 规范句型规范句型最左（最右）推导：最左（最右）推导：最左（最右）推导：最左（最右）推导：推导的每一步推导的每一步推导的每一步推导的每

32、一步，其中，其中，其中，其中、是句型，是句型，是句型，是句型，都是对都是对都是对都是对中的最左（右）非终结符进行替换。中的最左（右）非终结符进行替换。中的最左（右）非终结符进行替换。中的最左（右）非终结符进行替换。规范推导：规范推导：规范推导：规范推导：最右推导称为规范推导。最右推导称为规范推导。最右推导称为规范推导。最右推导称为规范推导。规范句型：规范句型：规范句型：规范句型：由规范推导所得的句型称为规范句型。由规范推导所得的句型称为规范句型。由规范推导所得的句型称为规范句型。由规范推导所得的句型称为规范句型。注意：注意：注意：注意：文法中的每个文法中的每个文法中的每个文法中的每个句子句子句

33、子句子都必定有最左都必定有最左都必定有最左都必定有最左(右右右右)推导，但对于一个推导，但对于一个推导，但对于一个推导，但对于一个句句句句型型型型，则不一定。，则不一定。，则不一定。，则不一定。GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|a 对句型对句型T+a+T的推导：的推导：E E+T T*F+T T*a+T 第四十三页，讲稿共六十七页哦q 问题：问题：对于推导中的每一步，对于推导中的每一步，S X,如果如果X 1|2|3|k，（，（，）V*，XVN，则面临选哪一个则面临选哪一个i去匹配当前串的问题。使用不当易引起回溯。去匹配当前串的问题。使用不

34、当易引起回溯。2、句型分析过程、句型分析过程l自顶向下分析方法自顶向下分析方法 从文法的从文法的开始符号开始符号出发，反复使用出发，反复使用文法的产生式文法的产生式，寻，寻找与找与输入符号串输入符号串匹配匹配的的推导推导。例：文法例：文法G：S cAd A ab A a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子SSScAdcAd a b推导过程：推导过程：S cAd cAd cabd第四十四页，讲稿共六十七页哦l自底向上分析方法自底向上分析方法 从从输入符号串输入符号串开始开始，逐步进行逐步进行归约归约，直至，直至归约归约到到文文法的法的开始符号开始符号。例：文法例：

35、文法G：S cAd A ab A a识别输入串识别输入串w=cabd是否该文法的是否该文法的句子句子SAA c a b d c a b d c a b d 归约归约过程构造的推导：过程构造的推导：cAd cabd S cAd第四十五页，讲稿共六十七页哦 在在在在自下而上自下而上自下而上自下而上的分析方法中，在分析程序工作的每的分析方法中，在分析程序工作的每的分析方法中，在分析程序工作的每的分析方法中，在分析程序工作的每一步，都是一步，都是一步，都是一步，都是从当前串从当前串从当前串从当前串中选择一个中选择一个中选择一个中选择一个子串子串子串子串，将它，将它，将它，将它归约归约归约归约到某到某到

36、某到某个个个个非终结符号非终结符号非终结符号非终结符号，该子串称为，该子串称为，该子串称为，该子串称为“可归约串可归约串可归约串可归约串”。归约的子串应是当前句型的归约的子串应是当前句型的归约的子串应是当前句型的归约的子串应是当前句型的句柄句柄句柄句柄。第四十六页，讲稿共六十七页哦3、语法树和二义性、语法树和二义性l语法树：语法树：设设G=(VN,VT,P,S)为一为一cfg，若一棵树满足下列，若一棵树满足下列4个条件，则此树称作个条件，则此树称作G的语法树：的语法树：q 每个结点都有一个标记，此标记是每个结点都有一个标记，此标记是V的一个符号；的一个符号；q 根的标记是根的标记是Sq 若某结

37、点至少有一个子孙，并且该结点标记为若某结点至少有一个子孙，并且该结点标记为A，则，则AVVN N；q 若某结点标记若某结点标记A，其直接子孙结点从左到右的次序是，其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为，其标记分别为A1，A2，Ak，那么，那么AA1A2，Ak定是定是P中的一个产生式中的一个产生式第四十七页，讲稿共六十七页哦语法树语法树-句型推导句型推导的的直观表示直观表示给定上下文无关文法给定上下文无关文法G=(VN,VT,P,S)，对于，对于G的任何句型都能的任何句型都能构造与之相关的语法树构造与之相关的语法树(推导树推导树)n 定理：定理：G为上下文无关文法，为上下文

38、无关文法，对于对于 ，有，有S=*，当且仅当，当且仅当 文法文法G有以有以 为结果的一棵语法树为结果的一棵语法树(推导树推导树)第四十八页，讲稿共六十七页哦 例例:GS:SaASASbAASSSaAba句子句子aabbaa的语法树（推导树）的语法树（推导树）叶子结点：叶子结点：树中没有子孙的结点。树中没有子孙的结点。SaASSbAaaba第四十九页，讲稿共六十七页哦 推导过程中使用产生式的推导过程中使用产生式的顺序顺序 例例:GS:SaASASbA|SS|baSaSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaa

39、bAaaabbaa S a A S S b A a a b a第五十页，讲稿共六十七页哦 一棵一棵语语法法树树可表示一个句子的多种可能的不可表示一个句子的多种可能的不同推同推导过导过程，包括最左程，包括最左(最右最右)推推导导。一个句子是否只一个句子是否只对应对应唯一的一棵唯一的一棵语语法法树树?一个句子是否只有唯一的一个最左一个句子是否只有唯一的一个最左(最右最右)推推导导?第五十一页，讲稿共六十七页哦例：例：GE:GE:E iE iE E+EE E+EE E*EE E*EE (E)E (E)句型句型 i*i+i 的推导的推导，有，有两个不同两个不同的的最左推导最左推导：推导推导1：E E+

40、E E*E+E i*E+E i*i+E i*i+i推导推导2：E E*E i*E i*E+E i*i+E i*i+i E E E+E E+E E*E i E*E i i i i i E E E*E E*E i E+E i E+E i i i i第五十二页，讲稿共六十七页哦l 二义性文法二义性文法q 若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义二义的。的。q 若一个文法存在某个句子有两个不同的最左（右）推导，则称这个若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是文法是二义二义的的 注意：注意：判定任给的

41、一个上下文无关文法是否二义，或它是否判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件。可解的，但可以为无二义性寻找一组充分条件。第五十三页，讲稿共六十七页哦 一个文法兼有左右递归是导致二义性的最常见原因。一个文法兼有左右递归是导致二义性的最常见原因。二义文法改造为无二义文法二义文法改造为无二义文法 GE:E i GEGE:E i GE：E T|E+TE T|E+T E E+E T F|T*F E E+E T F|T*F E E*E F E E*E F （

42、E E）|i|i E (E)E (E)改写文法，消除同时存在的左右递归。改写文法，消除同时存在的左右递归。第五十四页，讲稿共六十七页哦4、短语和句柄、短语和句柄S A且且 A ，则称，则称是是句型句型相对于非终结符相对于非终结符A的的短语短语对于文法对于文法GS：n 句型的短语句型的短语句型的短语句型的短语n 句型的直接短语句型的直接短语句型的直接短语句型的直接短语若有若有A ，则称，则称是句型是句型相对于非终结符相对于非终结符A 的的直接短语直接短语n 句型的句柄句型的句柄句型的句柄句型的句柄一个句型的一个句型的最左直接短语最左直接短语称为称为该句型该句型的的句柄句柄第五十五页，讲稿共六十七

43、页哦i*i+i i*i+i 的短语、直接短语和句柄的短语、直接短语和句柄 E E +T T FT *F i3 短语短语：i1*i2+i3，i1*i2，F i2 i1，i2，i3。i1 直接短语直接短语：i1，i2，i3。句柄句柄：i1 例例：GEGE：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|i F(E)|i句型：句型：i*i+ii*i+i第五十六页，讲稿共六十七页哦GS:SaAS SaASbAASSAba句子句子aabbaa的最左推导，指出此句子的全部短语、各步的最左推导，指出此句子的全部短语、各步直接推导所得句型的句柄、该句子的句柄直接推导所得句型的句柄、该句子的句柄

44、 S1 a1 A1 S3 S2 b1 A2 a2 a3 b2 a4练练 习习第五十七页，讲稿共六十七页哦通过对产生式施加不同限制通过对产生式施加不同限制，Chomsky将文法分为四类：将文法分为四类：l0型文法：型文法：对任一产生式对任一产生式，有，有V+，V*;l1型文法：型文法：对任一产生式对任一产生式，有，有|(,V+)，仅仅 S除外。除外。或者形如或者形如A 产生式产生式,AVN,V+,V*l2型文法：型文法：对任一产生式对任一产生式A，都有，都有AVN V*;l3型文法：型文法：任一产生式的形式都为任一产生式的形式都为AB或或A(右线性右线性)，AB或或A（左线性）其中（左线性）其中

45、AVN，BVN，aV VT T+2.8 文法的类型文法的类型第五十八页，讲稿共六十七页哦四种四种文法文法之间之间的的逐级逐级“包含包含”关系关系0型文法型文法1型文法型文法2型文法型文法3型文法型文法第五十九页，讲稿共六十七页哦A hierarchy of grammarsType 0:free or unrestricted grammars These are the most general.Productions are of the form u v where both u and v are arbitrary strings of symbols in V,with u non

46、-null.There are no restrictions on what appears on the left or right-hand side other than the left-hand side must be non-empty.Type 1:context-sensitive grammars Productions are of the form uXw uvw where u,v and w are arbitrary strings of symbols in V,with v non-null,and X a single nonterminal.In oth

47、er words,X may be replaced by v but only when it is surrounded by u and w.第六十页，讲稿共六十七页哦Type 2:context-free grammars Productions are of the form X v where v is an arbitrary string of symbols in V,and X is a single nonterminal.Wherever you find X,you can replace with v(regardless of context).Type 3:re

48、gular grammars Productions are of the form X a or X aY where X and Y are nonterminals and a is a terminal.That is the left-hand side must be a single nonterminal and the right-hand side can be either a single terminal by itself or with a single nonterminal.These grammars are the most limited in term

49、s of expressive power.第六十一页，讲稿共六十七页哦例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法GSGS：SCDSCDAbbAAbbA CaCA CaCABaaBBaaB CbCB CbCBBbbBBbbBADaDADaD Ca CaBDbDBDbD Db DbAabDAabD第六十二页，讲稿共六十七页哦例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GS：SABABABS|0BS|0BSA|1SA|13 3型文法型文法GS：S0A|1B|00A|1B|0A0A|1B|0S0A|1B|0SB1B|1|01B|1|0第六十三页，讲稿共六十七

50、页哦文法和语言文法和语言0型文法产生的语言称为型文法产生的语言称为0型语言型语言(递归可枚举语言递归可枚举语言)；1型文法或上下文有关文法（型文法或上下文有关文法（CSG）产生的语言称为）产生的语言称为1型语言型语言(上下文有关上下文有关语言（语言（CSL）)2型文法或上下文无关文法（型文法或上下文无关文法（CFG）产生的语言称为）产生的语言称为2型语言型语言(上下文上下文无关语言（无关语言（CF L）)上下文无关文法有足够的能力描述程序设计语言的语法结构。上下文无关文法有足够的能力描述程序设计语言的语法结构。3型文法或正则（正规）文法（型文法或正则（正规）文法（RG）产生的语言称为）产生的语