第四章 文法和语言.ppt

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

1、第四章第四章 文法和语言文法和语言本章目的本章目的 为语言的语法描述寻求工具为语言的语法描述寻求工具工具要对程序设计语言给出精确无二义的语法描工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）述。（严谨、简洁、易读）形式形式工具工具-形式语言抽象地定义为一个数学形式语言抽象地定义为一个数学系统。系统。“形式形式”是指这样的事实：语言的是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来所有规则只以什麽符号串能出现的方式来陈述陈述1本章知识点本章知识点(内容内容)引言和预备知识文法和语言的形式定义文法和语言的形式定义文法的类型文法的类型上下文无关文法及其语法树上下文无关文法

2、及其语法树上下文无关文法上下文无关文法的的句型分析句型分析有关文法实用中的一些说明有关文法实用中的一些说明2文法的直观概念和语言概述语言概述当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用第2章所介绍的EBNF来表示这种句子的构成规则：3“我是大学生”。是汉语的一个句子句子=主语谓语主语=代词名

3、词代词=我你他名词=王明大学生工人英语谓语=动词直接宾语动词=是学习直接宾语=代词名词 4有了一组规则以后，按照如下方式用它们导出句子：开始去找=左端的带有句子的规则并把它由=右端的符号串代替，这个动作表示成：句子主语谓语，然后在得到的串主语谓语中，选取主语或谓语，再用相应规则的=右端代替之。比如，选取了主语，并采用规则主语=代词，那么得到：主语谓语代词谓语，重复做下去，句子：“我是大学生”的全部动作过程是：句子主语谓语代词谓语我谓语我动词直接宾语我是直接宾语我是名词 我是大学生 5“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构

4、合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。6英语句子sentence subject This|Computers|Iverb-phrase|adverb neververb is|run|am|tellobject the|a|noun university|world|cheese|liesThis is a university.Computers run the world.I am the cheese.I never tell lies.7语言概述语言概述语言是由句子组成的集合，是由一组符号所构成的

5、语言是由句子组成的集合，是由一组符号所构成的集合。集合。汉语汉语-所有符合汉语语法的句子的全体所有符合汉语语法的句子的全体英语英语-所有符合英语语法的句子的全体所有符合英语语法的句子的全体程序设计语言程序设计语言-所有该语言的程序的全体所有该语言的程序的全体 每个句子构成的规律每个句子构成的规律研究语言研究语言 每个句子的含义每个句子的含义 每个句子和使用者的关系每个句子和使用者的关系8研究程序设计语言研究程序设计语言 每个程序构成的规律每个程序构成的规律 每个程序的含义每个程序的含义 每个程序和使用者的关系每个程序和使用者的关系语言研究的三个方面语言研究的三个方面 语法语法 Syntax 语

6、义语义 Semantics 语用语用 Pragmatics9语法语法-表示构成语言句子的各个记号之间的表示构成语言句子的各个记号之间的组合规律组合规律语义语义-表示各个记号的特定含义。（各个记表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）号和记号所表示的对象之间的关系）语用语用-表示在各个记号所出现的行为中，它表示在各个记号所出现的行为中，它们的来源、使用和影响。们的来源、使用和影响。10每每种种语语言言具具有有两两个个可可识识别别的的特特性性，即即语语言言的的形式和该形式相关联的意义。形式和该形式相关联的意义。语语言言的的实实例例若若在在语语法法上上是是正正确确的的，其其相

7、相关关联联的的意意义义可可以以从从两两个个观观点点来来看看，其其一一是是该该句句子子的的创创立立者者所所想想要要表表示示的的意意义义，另另一一是是接接收收者者所所检检验验到到的的意意义义。这这两两个个意意义义并并非非总总是是一一样样的的，前前者者称称为为语语言言的的语语义义，后后者者是是其其语语用用意意义义。幽幽默默、双双关关语语和和谜谜语语就就是是利利用这两方面意义间的差异。用这两方面意义间的差异。11如如果果不不考考虑虑语语义义和和语语用用，即即只只从从语语法法这这一一侧侧面面来来看看语语言言，这这种种意意义义下下的的语语言言称称作作形形式式语语言言。形形式式语语言言抽抽象象地地定定义义为

8、为一一个个数数学学系系统统。“形形式式”是是指指这这样样的的事事实实：语语言言的的所所有有规规则则只只以以什什麽麽符符号号串串能能出出现现的的方方式式来来陈陈述述。形形式式语语言言理理论论是是对对符符号号串串集集合合的的表表示示法法、结结构构及及其其特特性性的的研研究究。是是程程序序设设计计语语言言语语法法分分析析研研究的基础。究的基础。12有关定义和记号有关定义和记号回回顾顾符号：可以相互区别的记号（元素）。符号：可以相互区别的记号（元素）。字母表字母表：符号（元素）的非空有穷集合。：符号（元素）的非空有穷集合。符号串：由字母表符号串：由字母表 中的符号组成的任何有穷序中的符号组成的任何有穷

9、序列称为该字母表上的符号串。列称为该字母表上的符号串。1.空符号串空符号串(没没有有符号的符号串符号的符号串)是是 上的符号串上的符号串 2.若若x是是 上上的符号串的符号串,a是是 的元素的元素,则则xa是是 上的符号串上的符号串 3.y是是 上的符号串上的符号串,当且仅当它可以由当且仅当它可以由1和和2导出。导出。例如：例如：=a,b =a,b ,a,b,a,b,aaaa,abab,aabbaaabba都都是是 上的符号串上的符号串13有关定义和记号有关定义和记号回回顾顾 符号串符号串s的头（前缀）：移走符号串的头（前缀）：移走符号串s尾部的零尾部的零个或多于零个符号得到的符号串个或多于零

10、个符号得到的符号串.如：如：b是符号串是符号串banana的一个前缀的一个前缀.符号串符号串s的尾（后缀）：删去符号串的尾（后缀）：删去符号串s头部的零头部的零个或多于零个符号得到的符号串个或多于零个符号得到的符号串.如如:nana是符号串是符号串banana的一个后缀的一个后缀.符号串符号串s的子串：从的子串：从s中删去一个前缀和一个后中删去一个前缀和一个后缀得到的符号串缀得到的符号串.如如:ana是符号串是符号串banana的一个子串的一个子串.14对于每个符号串对于每个符号串s，s和和两者两者都都是符号串是符号串s的前的前缀，后缀和子串。缀，后缀和子串。符号串符号串s的真前缀，真后缀，真

11、子串：任何非空的真前缀，真后缀，真子串：任何非空符号串符号串 x,相应地，是相应地，是s的前缀，后缀或子串，的前缀，后缀或子串，并且并且 s x 符号串的运算符号串的运算符号串的长度：符号串中符号的个数符号串的长度：符号串中符号的个数.符号串符号串s的长度的长度记为记为|s|。的长度为的长度为0连接：符号串连接：符号串x x、y y的连接的连接,是把是把y y的符号写在的符号写在x x的符号的符号之后得到的符号串之后得到的符号串xy xy 如如 x=x=abab,y=,y=cd cd 则则 xyxy=abcd abcd 有有a=a a=a 方幂：符号串自身连接方幂：符号串自身连接n n次得到的

12、符号串次得到的符号串 a an n 定义为定义为 aaaaaa aa n n个个a aa a1 1=a,a=a,a2 2=aaaa则则a a0 0=15符号串集合：若集合符号串集合：若集合A中所有元素都是某字母中所有元素都是某字母表表 上的符号串，则称上的符号串，则称A为字母表为字母表 上的符号上的符号串集合。串集合。两个符号串集合两个符号串集合A和和B的乘积定义为的乘积定义为 AB=xyxy|x|x A A且且y y B B 若若 集合集合A=abab,cdecde B=0,10,1 则则 AB=ab1,ab0,cde0,cde1ab1,ab0,cde0,cde1 使用使用 *表示表示 上的

13、一切符号串（包括上的一切符号串（包括）组组成的集合。成的集合。*称为称为的闭包的闭包。上的上的除除外外的所有符号串组成的集合记为的所有符号串组成的集合记为+。+称为称为的正闭包的正闭包。16例：例：=a,b=a,b *=,a,b,=,a,b,aaaa,abab,baba,bb,bb,aaaaaa,aabaab,+=a,b,=a,b,aaaa,abab,baba,bb,bb,aaaaaa,aabaab,17有关定义和记号有关定义和记号语言语言是由句子组成的集合，是由一组符号所构成的集合。换言之,字母表上的一个语言是上的一些符号串的集合 (字母表上的每个语言是*的一个子集)。例如：字母表=a,b,

14、*=,a,b,aa,ab,ba,bb,aaa,aab,集合ab,aabb,aaabbb,anbn,或表示为w|w*且w=anbn,n1为字母表上的一个语言。集合a,aa,aaa,或表示为w|w*且w=an,n1 为字母表上的一个语言。是一个语言。即 是一个语言。18给出语言给出语言上上的有关运算的有关运算 设设L是（是（上的）一个语言上的）一个语言,M是（是（上的）一个语上的）一个语言言,语言语言L和和M的并，交，差，补的并，交，差，补是一个语言。是一个语言。语言语言L和和M的并为的并为 L M，是一个语言是一个语言:w|w is w|w is in L or is in M in L or

15、is in M 如：如：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,9 8,9 语言语言L和和M的连接的连接是一个语言，记是一个语言，记为为 LM LM=stst|s|sL且且 t tM 如：如：L1M1=a1,b1,=a1,b1,y1,z1,a2,b2y1,z1,a2,b2a9a9z9 z9 有有L =L=L。L的的n次连接次连接Ln=LL.L 19语言语言上上的运算的运算 语言语言L的的 闭包闭包记记为为 L*，L*=L0 L1 L2 .L0=，Ln=L Ln-1=Ln-1 L,n 1

16、语言语言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,y,z y,z，1,21,28,98,9，aa,1a,xyz,6789st.L1（L1 M1 1）*=所有字母打头的字母和数字符号所有字母打头的字母和数字符号串串 20文法和语言的形式定义文法和语言的形式定义如何来描述一种语言？如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），

17、可以将如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的有如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：穷表示有两个途经：生成方式生成方式（文法）：语言中的每个句子可以用严格（文法）：语言中的每个句子可以用严格定义的规则来构造。定义的规则来构造。识别方式识别方式（自动机）：用一个过程，当输入的一任（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止意串属于语言时，该过程经有限次计算后就会停止并回答并回答“是是”，若不属于，要麽能停止，若不属于，要麽能停止并回答并回答“不不是

18、是”，（要麽永远继续下去。），（要麽永远继续下去。）21文法即是生成方式描述语言的：语言中的每文法即是生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造个句子可以用严格定义的规则来构造.下面下面给出文法的定义给出文法的定义.进而在进而在文法的定义的基础文法的定义的基础上上,给出给出推导的概念推导的概念,句型、句子和语言的句型、句子和语言的定义定义.22定义定义文法G定义为四元组(VN，VT，P，S)其中VN为非终结符号(或语法实体，或变量)集；VT为终结符号集；P为产生式(也称规则)的集合；VN，VT和P是非空有穷集。S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中

19、作为左部出现。VN和VT不含公共的元素，即VN VT=用V表示VN VT，称为文法G的字母表或字汇表规则规则，也称重写规则重写规则、产生式产生式或生成式生成式，是形如或=的(，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。称为规则的左部，称作规则的右部。23Define a grammarDefine a grammarA A grammar G grammar G is defined as a 4-is defined as a 4-tuple tuple(VN，VT，P，S)VN is a set of nonterminals VT is a set of te

20、rminals P is a set of productions，each production consists of a left side,an arrow(or:=),and a right side S is a designation of one of the nonterminalsasthestart symbolV=VN VT is the alphabet of G24文法的定义文法的定义例例 文法文法G=（VN，VT，P，S）VN=S,VT=0,1 P=S0S1,S01 S为开始符号为开始符号25例例 文法文法G=（VN，VT，P，S）VN=标识符，字母，数字标识符，

21、字母，数字VT=a,b,c,x,y,z,0,1,9P=a,z z 0,0,99 S=26文法的写法文法的写法 1 1 G G：S Sa aA Ab A Aabab A Aa aA Ab A A 2 GS 2 GS：A Aabab A Aa aA Ab A A S Sa aS Sb 3 GSGS：A Aabab|a aA Ab|S Sa aS Sb27元元符号:=|习惯表示习惯表示 大写字母：终结符大写字母：终结符 小写字母：非终结符小写字母：非终结符S ABA Ax|yB z28推导的定义推导的定义直接推导直接推导“”是文法是文法G G的产生式，若有的产生式，若有v,wv,w满足：满足：v=,

22、w=,v=,w=,其中其中VV*,V,V*则称则称v v直接直接推导推导到到w,w,记作记作 v v w w 也称也称w w直接直接归约归约到到v v例：例：G G：S0S1，S01 0S100S1100S11000S111000S11100001111 S 0S129.VAR;BEGINREAD()END.VARA;BEGINREAD()END.30推导的定义推导的定义若存在若存在vw0w1.wn=w,(n0)则记为则记为v=+w，v推导出推导出w，或或w归约到归约到v若有若有v=+w，或或v=w，则记为则记为v=*w31例：例：G G：S0S1，S010S100S1100S11000S11

23、1000S11100001111 S 0S100S11000S11100001111 S=+00001111 S=*S 00S11=*00S1132What are DerivationsDerivationisawaythatagrammardefinesalanguage.IntheprocessofderivationaproductionistreatedasarewritingruleinwhichthenonterminalontheleftsideisreplacedbythestringontherightsideoftheproductionAproductionu v is

24、usedbyreplacinganoccurrenceofu byv.Formally,ifweapplyaproductionp Ptoastringofsymbolsw inVtoyieldanewstringofsymbolsz inV,wesaythatz derivedfromw usingp,writtenasfollows:w=pz.Wealsouse:w=z z derivesfromw(productionunspecified)w=*z z derivesfromw usingzeroormoreproductionsw=+z z derivesfromw usingone

25、ormoreproductions33句型、句子的定义句型、句子的定义句型句型有文法有文法G，若若S=*x，则称则称x是文法是文法G的句型。的句型。句子句子有文法有文法G，若若S=*x，且且xVVT T*，则称则称x是文法是文法G的句子。的句子。例：例：G G：S0S1，S01S 0S100S11000S11100001111G的句型S,0S1,00S11,000S111,00001111G的句子00001111,0134例：例：GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|aE EE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a句子：

26、用符号句子：用符号a，+，*，(和和)构成的算术表达式构成的算术表达式35文法，语言的定义文法，语言的定义由文法由文法G生成的语言记为生成的语言记为L(G),它是文法它是文法G的的一切句子的集合一切句子的集合:L(G)=x|S=*x，其中其中S为文法的开始为文法的开始符号，且符号，且x VVT T*例：例：G G：S0S1，S01L(G)=0n1n|n136例例 文法文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEeeL（G）=anbnen|n1 37S aSBE(SaSBE)aaBEBE(SaBE)aabEBE(aBab)aabBEE

27、(EBBE)aabbEE（bBbb)aabbeE（bEbe)aabbee（eEee)G生成的每个串都在生成的每个串都在L(G)中中L(G)中的每个串确实能被中的每个串确实能被G生成生成38使用产生式(1)n-1次，得到推导序列：S=*an-1S(BE)n-1，然后使用产生式(2)一次，得到：S=*an-1S(BE)n-1an(BE)n。然后从an(BE)n继续推导，总是对EB使用产生式(3)的右部进行替换，而最终在得到的串中，所有的B都先于所有的E。例如，若n=3,aaaBEBEBEaaaBBEEBEaaaBBEBEEaaaBBBEEE。即有：S=*anBnEn接着，使用产生式(4)一次，得到

28、S=*anbBn-1En，然后使用产生式(5)n-1次得到：S=*anbnEn，最后使用产生式(6)一次，使用产生式(7)n-1次，得到：S=*anbnen也能证明，对于n1，串anbnen是唯一形式的终结符号串39文法的等价文法的等价z若若L（G1）=L（G2），），则称文法则称文法G1和和G2是是等价的。等价的。如文法如文法G G1AA：A0R A0R 与与G G2SS：S0S1 S0S1 等价等价 A01 A01 S01 S01 RA1 RA140文法的类型文法的类型通过对产生式施加不同的限制，通过对产生式施加不同的限制，Chomsky将将文法分为四种类型：文法分为四种类型：0型文法：对

29、任一产生式型文法：对任一产生式，都有都有(V(VN NVVT T)+，(V(VN NVVT T)*1 1型文法：型文法：对任一产生式对任一产生式，都有都有|，仅仅仅仅 SS除外除外2 2型文法：型文法：对任一产生式对任一产生式，都有都有VVN N ，(V(VN NVVT T)*3 3型文法：型文法：任一产生式任一产生式的形式都为的形式都为AAaBaB或或AaAa，其中其中AVAVN N ，BVBVN N ，aVaVT T41A hierarchy of grammarsType0:freeorunrestrictedgrammarsThesearethemostgeneral.Producti

30、onsareoftheformu v wherebothu andv arearbitrarystringsofsymbolsinV,withu non-null.Therearenorestrictionsonwhatappearsontheleftorright-handsideotherthantheleft-handsidemustbenon-empty.Type1:context-sensitivegrammarsProductionsareoftheformuXw uvw whereu,v andw arearbitrarystringsofsymbolsinV,withv non

31、-null,andX asinglenonterminal.Inotherwords,X maybereplacedbyv butonlywhenitissurroundedbyu andw.(i.e.inaparticularcontext).42Type2:context-freegrammarsProductionsareoftheformX v wherev isanarbitrarystringofsymbolsinV,andX isasinglenonterminal.WhereveryoufindX,youcanreplacewithv(regardlessofcontext).

32、Type3:regulargrammarsProductionsareoftheformX a orX aY whereX andY arenonterminalsanda isaterminal.Thatistheleft-handsidemustbeasinglenonterminalandtheright-handsidecanbeeitherasingleterminalbyitselforwithasinglenonterminal.Thesegrammarsarethemostlimitedintermsofexpressivepower.43文法的类型文法的类型例：例：1 1型（

33、上下文有关）文法型（上下文有关）文法 文法文法GSGS：S SCDCDAbAbbAbA C CaCAaCABaBaaBaB C CbCBbCBBbBbbBbBADADaDaD CCBDBDbDbD DDAaAabDbD44文法的类型文法的类型例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GS：SABABABS|0BS|0BSA|1SA|1453 3型文法型文法GS：S0A|1B|00A|1B|0A0A|1B|0S0A|1B|0SB1B|1|01B|1|0GI：I lT lTI l lT lT lTT dT dTT l lT d d46文法的类型文法的类型2型文法型文法1型文法

34、型文法0型文法型文法四种四种文法文法之间之间的的逐级逐级“包含包含”关系关系3型文法型文法47文法和语言文法和语言0型文法产生的语言称为型文法产生的语言称为0型语言型语言1 1型文法或上下文有关文法（型文法或上下文有关文法（CSG ）产生的语言产生的语言称为称为1 1型语言型语言或上下文有关或上下文有关语言（语言（CSL）2 2型文法或上下文无关文法（型文法或上下文无关文法（CFG ）产生的语言产生的语言称为称为2型语言型语言或上下文无关或上下文无关语言（语言（CF L）3 3型文法或正则（正规）文法（型文法或正则（正规）文法（RG）产生的语言产生的语言称为称为3型语言型语言正则（正规）正则（

35、正规）语言（语言（RL）48文法和语言文法和语言 四种文法之间的关系四种文法之间的关系 是将产生式做进一步是将产生式做进一步限制而定义的。限制而定义的。语言之间的关系依次：有不是上下文有关语言之间的关系依次：有不是上下文有关语言的语言的0型语言，有不是上下文无关语言的型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语型语言，有不是正则语言的上下文无关语言。言。49根据形式语言理论根据形式语言理论,文法和识别系文法和识别系统间有这样的关系统间有这样的关系 0型文法（短语结构文法）的能力相当于图型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且灵机，可以表征

36、任何递归可枚举集，而且任何任何0型语言都是递归可枚举的型语言都是递归可枚举的 1型文法（上下文有关文法）：产生式的形型文法（上下文有关文法）：产生式的形式为式为1 1AA2 21 12 2，即只有即只有A A出现在出现在1 1和和2 2的上下文中时，才允许的上下文中时，才允许取代取代A A。其识其识别系统是线性界限自动机。别系统是线性界限自动机。50带带a0a1a2a3a4a5a6a7a8an-1an有限控制器有限控制器磁头磁头任何能用图灵机描述的计算都能机械实现，任何能在现任何能用图灵机描述的计算都能机械实现，任何能在现代计算机上实现的计算都能用图灵机描述代计算机上实现的计算都能用图灵机描述

37、51 2型文法（上下文无关文法型文法（上下文无关文法CFG）：）：产生式产生式的形式为的形式为AA，取代取代A A时与时与A A的上下文无的上下文无关。其识别系统是不确定的下推自动机。关。其识别系统是不确定的下推自动机。3型文法（正规文法型文法（正规文法RG）：）：产生的语言是产生的语言是有穷自动机（有穷自动机（FA）所接受的集合所接受的集合52 3型文法产生的语言是有穷自动机（型文法产生的语言是有穷自动机（FA）所接所接受的集合受的集合.定理定理 设设G=（VN，VT，P，S）是3 3型型文法文法，则存在，则存在一个有穷自一个有穷自 动机动机 M=(K,f,A,Z)M=(K,f,A,Z)，使

38、得使得L(M)=L(G)L(M)=L(G)有穷自动机有穷自动机NFA M NFA M 这样构造：这样构造：=VT K=K=VN N,NN,N为一个新状态为一个新状态,它它不不在在VN中 A=S A=S Z=N Z=N 对对G G中的形如中的形如 DDtBtB的产生式的产生式,t t为终结符或为终结符或,有有f(D,t)=Bf(D,t)=B；对对G G中形如中形如DtDt的产生式，的产生式，t t为终结符或为终结符或,有有f(D,t)=N;f(D,t)=N;对对VT中的每一个a,有有f(N,a)=f(N,a)=53G：SaA|bBAbB|aD|aBaA|bD|bDaD|bD|a|bBASaaab

39、bba,bDZabab54定理定理已知一有穷自动机M=(K,f,A,Z),存在有一个3型文法G=（VN，VT，P，S）,使得L(G)=L(M)G 的定义：VT=VN=K S=A 若 f(D,t)=B，则DtB在P中 若 f(D,t)=B，且B在Z中，则Dt在P中55G：SaA|bBAbB|aD|aBaA|bD|bDaD|bD|a|bDBASaaabba,bb56正规文法和正规式 对上的正规式r,存在一个RG=(VN,VT,P,S)：L(G)=L(r)初始，VT=,S VN，生成正规产生式 Sr (R.1)对形如 Ar1r2的正规产生式：Ar1B Br2 BVN (R 2)对形如Arr1的正规产

40、生式：ArB Ar1 BrB Br1 BVN (R 3)对形如Ar1r2的正规产生式:Ar1 A r2 不断应用R做变换，直到每个产生式右端至多有一个VN57例 r=a(ad)Sa(ad)SaA A(ad)A(ad)B A B(ad)B B Gs:SaA A VT=a,d AaBVN=S,A,B AdB BaB BdB B58正规文法和正规式 对G=(VN,VT,P,S),存在一个=VT上的正规式r:L(r)=L(G)AxB,By A=xy AxAy A=xy Axy A=xy59正规文法和正规式Gs:SaA|a AaAadAd A(ad)A(ad)A(ad)(ad)S=a(ad)(ad)a=

41、a(ad)(ad)=a(ad)R=a(ad)60上下文无关文法及其语法树上下文无关文法及其语法树上下文无关文法有足够的能力描述程序设计语言的上下文无关文法有足够的能力描述程序设计语言的语法结构语法结构语法树语法树-句型推导句型推导的的直观表示直观表示61例文法G=(E,+,*,i,(,),P,E)其中P为：Ei,EE+E,EE*E,E(E)E表示算术表达式,i表示程序的“变量”，该文法定义了由变量，+，*,(和)组成的算术表达式的语法结构，即：变量是算术表达式；若E1和E2是算术表达式，则E1+E2，E1*E2和(E1)也是算术表达式描述一种简单赋值语句的产生式：赋值语句i=E描述条件语句的产

42、生式：条件语句if条件then语句if条件then语句else语句62句型、推导GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|aE EE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*aE EE+TE+T*FE+T*aE+F*aE+a*aT+a*aF+a*aa+a*aE EE+TT+TT+T*FF+T*FF+F*Fa+F*Fa+F*aa+a*a63规范推导规范推导规范句型规范句型最左（最右）推导：在推导的任何一步最左（最右）推导：在推导的任何一步，其中其中、是句型，都是对是句型，都是对中中的最左（右）非终结符进行替换的最左（右）非终结符进行

43、替换最右推导被称为规范推导。最右推导被称为规范推导。由规范推导所得的句型称为规范句型由规范推导所得的句型称为规范句型64语法树语法树设G=(VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树(推导树)(派生树）：1.每个结点都有一个标记，此标记是V的一个符号2.根的标记是S3.若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定AVN4.如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式语法树的结果：语法树的结果：从左到右读出叶子的标记而构成的行谓之65语法树语法树-句型

44、推导句型推导的的直观表示直观表示给定文法给定文法G=(VN,VT,P,S)，对于对于G的任何句型都能的任何句型都能构造与之关联的语法树构造与之关联的语法树(推导树推导树)定理：定理：G为上下文无关文法，为上下文无关文法，对于对于，有有S=*，当且仅当当且仅当文法文法G有以有以为结果的一棵语法树为结果的一棵语法树(推导树推导树)66构造语法树构造语法树GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|aE EE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a E EE+T E +T T E E +T T F67E EE+TT+TF+Ta+Ta+

45、T*Fa+F*Fa+a*Fa+a*aE EE+TE+T*FE+T*aE+F*aE+a*aT+a*aF+a*aa+a*aE EE+TT+TT+T*FF+T*FF+F*Fa+F*Fa+F*aa+a*a E E E+T E+T T T*F T T*F F F a F F a a a a a 看不出句型中的符号被替代看不出句型中的符号被替代的顺序的顺序68上下文无关文法的语法树的用处用于描述上下文无关文法用于描述上下文无关文法句型推导句型推导的的直观方法直观方法例例:GS:SaASASbAASSSaAbaSaASSbAaaba句型句型aabbaa的的语法树语法树（推导树）（推导树）叶子结点叶子结点：树

46、中：树中没有子孙的结点没有子孙的结点。从左到右从左到右读出推导树的读出推导树的叶子标记叶子标记连接成的连接成的文文法符号法符号串串，为，为GS的的句型句型。也把该推导树称。也把该推导树称为该为该句型句型的的语法树语法树。69上下文无关文法的语法树上下文无关文法的语法树z推导过程中推导过程中施用施用产生式产生式的的顺序顺序例例:GS:SaASASbAASSSaAbaSaASSbAaabaSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa70一棵一棵语语法法树树表示了一个句型的种种可能的表示了一个句

47、型的种种可能的(但但未必是所有的未必是所有的)不同推不同推导过导过程，包括最左程，包括最左(最最右右)推推导导。但是，一个句型是否只。但是，一个句型是否只对应对应唯一唯一的一棵的一棵语语法法树树呢呢?一个句型是否只有唯一的一个句型是否只有唯一的一个最左一个最左(最右最右)推推导导呢呢?71例：例：GE:GE:E E i iE E+EE E+EE E*EE E*EE (E)E (E)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句型句型i*i+i的两个不同的最左推导：的两个不同的最左推导：推导推导1：EE+EE*E+

48、Ei*E+Ei*i+Ei*i+i推导推导2：EE*Ei*Ei*E+Ei*i+Ei*i+i72二义文法二义文法 若一个文法存在某个句子对应两棵不同的语法树，若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是则称这个文法是二义二义的的或者，若一个文法存在某个句子有两个不同的最或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是左（右）推导，则称这个文法是二义二义的的 判定任给的一个上下文无关文法是否二义，判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可语言，这两个问题是递归不

49、可解的，但可以为无二义性寻找一组充分条件以为无二义性寻找一组充分条件 73文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法的文法G G和和GG，其中其中G G是二义的，但是却有是二义的，但是却有L(G)=L(G)L(G)=L(G)，也就是说，也就是说，这两个文法所产生的语言是相同的。这两个文法所产生的语言是相同的。二义文法改造为无二义文法二义文法改造为无二义文法GE:E GE:E i GE 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

50、F （E E）|i|i E (E)E (E)规定优先顺序和结合律规定优先顺序和结合律 如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。的，因为希望对它的每个语句的分析是唯一的。74句型的分析句型的分析句型分析句型分析就是就是识别识别一个符号串是否为某文法一个符号串是否为某文法的的句型句型，是某个，是某个推导推导的构造过程。的构造过程。在语言的编译实现中，把在语言的