《编译第三章.ppt》由会员分享，可在线阅读，更多相关《编译第三章.ppt（82页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章第三章 文法和语言文法和语言教学要求教学要求 掌掌握握：文文法法的的概概念念，语语言言的的定定义义，符符号号串串，文文法法的的形形式式定定义义，0 0型型文文法法，1 1型文法，型文法，2 2型文法，型文法，3 3型文法型文法理理解解：自自上上而而下下与与自自下下而而上上的的分分析方法析方法了解：上下文无关文法中的规则了解：上下文无关文法中的规则一个程序设计语言是一个记号系统，一个程序设计语言是一个记号系统，其完整定义应包括语法和语义两个方其完整定义应包括语法和语义两个方面。面。语法语法是指一组规则，用它可以形成和是指一组规则，用它可以形成和和产生一个合法的程序，定义什么样和产生一个合法
2、的程序，定义什么样的符号系列是合法的，与符号含义无的符号系列是合法的，与符号含义无关。关。语义：语义：类型匹配，变量作用域等类型匹配，变量作用域等静态语义：一系列语法规则，确定哪些静态语义：一系列语法规则，确定哪些合乎语法的程序是合适的合乎语法的程序是合适的动态语义：程序要做什么动态语义：程序要做什么3.1 3.1 文法的直观概念文法的直观概念文法文法：一种语言描述，用：一种语言描述，用来定义句子的结构，用有来定义句子的结构，用有限的规则把语言的全部句限的规则把语言的全部句子描述出来，是以有穷的子描述出来，是以有穷的集合刻划无穷的集合的工集合刻划无穷的集合的工具。具。当我们表述一种语言时，无非
3、是当我们表述一种语言时，无非是说明这种语言的句子，如果语说明这种语言的句子，如果语言只含有有穷多个句子，则只言只含有有穷多个句子，则只需列出句子的有穷集就行了，需列出句子的有穷集就行了，但对于含有无穷句子的语言来但对于含有无穷句子的语言来讲，存在着如何给出它的有穷讲，存在着如何给出它的有穷表示的问题。表示的问题。以自然语言为例，人们无法列出全以自然语言为例，人们无法列出全部句子，但是人们可以给出一些部句子，但是人们可以给出一些规则，用这些规则来说明规则，用这些规则来说明(或者或者定义定义)句子的组成结构，比如汉句子的组成结构，比如汉语句子可以是语句子可以是由主语后随谓语而成，构成谓语的由主语后
4、随谓语而成，构成谓语的是动词和直接宾语，我们采用第是动词和直接宾语，我们采用第2 2章所介绍的章所介绍的EBNFEBNF来表示这种句来表示这种句子的构成规则：子的构成规则：“我是大学生我是大学生”。是汉语的一个句子。是汉语的一个句子句子句子=主语主语谓语谓语主语主语=代词代词名词名词代词代词=我我你你他他名词名词=王明王明大学生大学生工人工人英英语语谓语谓语=动词动词直接宾语直接宾语动词动词=是是学习学习直接宾语直接宾语=代词代词名词名词 有了一组规则以后，按照如下方式用有了一组规则以后，按照如下方式用它们导出句子：开始去找它们导出句子：开始去找=左端左端的带有的带有句子句子的规则并把它由的规
5、则并把它由=右端的符号串代替，这个动作右端的符号串代替，这个动作表示成：表示成：句子句子 主语主语谓语谓语，然后在得到的串然后在得到的串主语主语谓语谓语中，选取中，选取主语主语或或谓语谓语，再用相应规则的再用相应规则的=右端代替之。右端代替之。句子：句子：“我是大学生我是大学生”的全部动作过的全部动作过程是：程是：句子句子 主语主语谓语谓语 代词代词谓语谓语 我我谓语谓语 我我动词动词直接宾语直接宾语 我是我是直接宾语直接宾语 我是我是名词名词 我是大学生我是大学生 “我是大学生我是大学生”的构成符合上述规的构成符合上述规则，而则，而“我大学生是我大学生是”不符合上不符合上述规则，我们说它不是
6、句子。这述规则，我们说它不是句子。这些规则成为我们判别句子结构合些规则成为我们判别句子结构合法与否的依据，换句话说，这些法与否的依据，换句话说，这些规则看成是一种元语言，用它描规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语的结构描述。其中一种描述元语言称为文法。言称为文法。3.2 3.2 符号和符号串符号和符号串字母表字母表：元素的非空有穷集：元素的非空有穷集合合 符号符号：字母表中的元素：字母表中的元素符号串符号串：由字母表中的符号：由字母表中的符号串组成的任何有穷系列产品串组成的任何有穷系列产品 x=STRx=STR有关定义
7、和记号有关定义和记号回回顾顾 符号串符号串s的头的头（前缀）：移走符号串（前缀）：移走符号串s尾尾部的零个或多于零个符号得到的符号串部的零个或多于零个符号得到的符号串.如：如：b是符号串是符号串banana的一个前缀的一个前缀.符号串符号串s的尾的尾（后缀）：删去符号串（后缀）：删去符号串s头头部的零个或多于零个符号得到的符号串部的零个或多于零个符号得到的符号串.如如:nana是符号串是符号串banana的一个后缀的一个后缀.符号串符号串s的子串：从的子串：从s中删去一个前缀和中删去一个前缀和一个后缀得到的符号串一个后缀得到的符号串.如如:ana是符号串是符号串banana的一个子串的一个子串
8、.对于每个符号串对于每个符号串s s，s s和和两者两者都都是符号串是符号串s s的前缀，后缀和子的前缀，后缀和子串。串。符号串符号串s s的真前缀，真后缀，真的真前缀，真后缀，真子串：任何非空符号串子串：任何非空符号串 x,x,相应相应地，是地，是s s的前缀，后缀或子串，的前缀，后缀或子串，并且并且 s s x x 符号串的运算符号串的运算 符号串的长度符号串的长度：符号串中：符号串中符号的个数符号的个数.符号串符号串s s的长度的长度记为记为|s|s|。的长度为的长度为0 0 x=STR x=STR 符号串的长度：符号串的长度：|x|=3|x|=3符号串连接符号串连接：符号串：符号串x
9、x、y y的连接的连接,是是把把y y的符号写在的符号写在x x的符号之后得到的符号之后得到的符号串的符号串xyxy 如如 x=x=ab,yab,y=cdcd 则则 xyxy=abcdabcd 有有a=a a=a 符号串方幂符号串方幂：符号串自身连接：符号串自身连接n n次得次得到的符号串到的符号串 a an n 定义为定义为 aaaaaaaa n n个个a aa a1 1=a,a=a,a2 2=aaaa则则a a0 0=符号串集合符号串集合：若集合：若集合A A中所有元素都是某中所有元素都是某字母表字母表 上的符号串，则称上的符号串，则称A A为字母表为字母表 上的符号串集合。上的符号串集合
10、。两个符号串集合两个符号串集合A A和和B B的乘积定义为的乘积定义为 AB=AB=xy|xxy|x A A且且y y B B 若若 集合集合A=A=ab,cdeab,cde B=B=0,10,1 则则 AB=AB=ab1,ab0,cde0,cde1ab1,ab0,cde0,cde1。使用使用 *表示表示 上的一切符号上的一切符号串（包括串（包括）组成的集合。组成的集合。*称为称为的闭包。的闭包。上的上的除除外的所有符号串组成外的所有符号串组成的集合记为的集合记为+。+称为称为的正的正闭包闭包。例：例：=a,b *=,a,b,aa,ab,ba,bb,aaa,+=a,b,aa,ab,ba,bb,
11、aaa,aab,指定字母表指定字母表，*表示表示上的上的所有有穷长所有有穷长的串的集合。的串的集合。=0，1 *=，0，1，00，01，10，11，000，001，010，*=0U 1U 2 U U n U *称为集合称为集合的闭包的闭包:正闭包正闭包:+=1U 2 U U n U *=0U+=*=*3.3文法和语言的形式定义文法和语言的形式定义如何来描述一种语言？如何来描述一种语言？如果语言是有穷的（只含有有穷如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列多个句子），可以将句子逐一列出来表示出来表示如果语言是无穷的，找出语言的如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两
12、有穷表示。语言的有穷表示有两个途经：个途经：生成方式生成方式 （文法）（文法）：语言中的：语言中的每个句子可以用严格定义的规则每个句子可以用严格定义的规则来构造。来构造。识别方式（自动机）识别方式（自动机）：用一个：用一个过程，当输入的一任意串属于语过程，当输入的一任意串属于语言时，该过程经有限次计算后就言时，该过程经有限次计算后就会停止会停止并回答并回答“是是”，若不属于，若不属于，要麽能停止要麽能停止并回答并回答“不是不是”，（要麽永远继续下去。）（要麽永远继续下去。）规则规则(也称也称重写规则重写规则、产生产生式式或或生成式生成式)：是形如是形如 或或:=:=的的(,)(,)有序有序对，
13、对，其中其中为为字母表的正闭包中的字母表的正闭包中的符号，符号，为字母表的闭包中为字母表的闭包中的符号，的符号，称为规则的左部，称为规则的左部，称为规则的右部。称为规则的右部。文法的定义：文法的定义：文法文法G:定义为四定义为四元元组（组（VN,VT,P,S），），其中其中VN为非为非终结符号的集合，终结符号的集合，VT为终结符号的为终结符号的集合，集合，P为产生式的集合，为产生式的集合，VN,VT,p 是非是非空有穷集，空有穷集，S为开始符，是一个非终结符，为开始符，是一个非终结符，至少要在一条规则中作为左部出现。至少要在一条规则中作为左部出现。VNn VT=VNUVT=V字母表或词汇表字母
14、表或词汇表例例文法文法G=G=（V VN N,V,VT T,P,S,P,S），），其中其中V VN N=S,=S,V VT T=0,1,P=S 0S1,S 01=0,1,P=S 0S1,S 01 可见该文法中非终结符中只含一个可见该文法中非终结符中只含一个符号符号S S，终结符中含两个符号终结符中含两个符号0 0和和1 1，由两个产，由两个产生式，开始符号是生式，开始符号是S.S.很多时候不用将文法的四元组显式地表很多时候不用将文法的四元组显式地表示出来，而只将产生式写出。示出来，而只将产生式写出。一般约定：第一条产生式的左部是识别一般约定：第一条产生式的左部是识别符号；用尖括号括起来的是非终
15、结符符号；用尖括号括起来的是非终结符号；不用尖括号括起来的是终结符号。号；不用尖括号括起来的是终结符号。或者用大写字母表示非终结符号，小或者用大写字母表示非终结符号，小写字母表示终结符号。写字母表示终结符号。如如：G:S 0S1G:S 0S1 S 01 S 01例例 文法文法G=（VN，VT，P，S）VN=标识符，字母，数字标识符，字母，数字VT=a,b,c,x,y,z,0,1,9P=a,zz 0,0,99 S=文法的写法文法的写法 1 G1 G：SaAbSaAb AabAab AaAbAaAb A A 2 GS 2 GS：SaAbSaAb AabAab AaAbAaAb A A 3 GS 3
16、 GS：SaAbSaAb AabAab|aAbaAb|推导的定义推导的定义:(、)1.1.是文法是文法G G的产生式，若有的产生式，若有v,wv,w满足：满足：v=,w=,v=,w=,其其中中VV*,V,V*则称则称v v直接直接推导推导到到w w,记作记作 v v w w 也称也称w w直接直接归约归约到到v v+*例例 G G：S0S1S0S1，S01S01 0S1 0S1 00S1100S11 00S11 00S11 000S111000S111 000S111 000S111 0000111100001111 S S 0S10S1.VARVAR;BEGIN READ(;BEGIN RE
17、AD()END.)END.VAR A;BEGIN READ(VAR A;BEGIN READ()END.END.2.2.若存在若存在v v w w0 0 w w1 1 .w wn n=w,(n0)=w,(n0)则记则记为为v=wv=w，v v推导出推导出w w，或，或w w归约到归约到v v3.3.若有若有v=wv=w，或，或v=wv=w，则记为则记为v=wv=w*+例：例：G G：S0S1，S010S1 00S1100S11 000S111000S111 00001111 S 0S1 00S11 000S111 00001111 S=00001111 S=S 00S11=00S11+*句型、
18、句子的定义句型、句子的定义句型句型:有文法有文法G G，若，若S S=x x，则称则称x x是文法是文法G G的句型。的句型。句子句子有文法有文法G G，若，若S S=x x，且，且xVxVT T*，则称则称x x是文法是文法G G的的句子。句子。例：例：G G：S0S1S0S1，S01S01S S 0S1 0S1 00S11 00S11 000S111 000S111 0000111100001111G G的句型的句型S,S,0S1,00S11,000S111,000011110S1,00S11,000S111,00001111G G的句子的句子00001111,00001111,0101*
19、例：例：GE：EE+T|T TT*F|F F(E)|aEE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a句子：用符号句子：用符号a，+，*，(和和)构成的构成的算术表达式算术表达式语言的定义语言的定义由文法由文法G生成的语言记为生成的语言记为L(G),它是文它是文法法G的一切句子的集合的一切句子的集合:L(G)=x|S=x，其中其中S为文法的为文法的开始符号，开始符号，且且x VVT T*例：例：G G：S0S1，S01L(G)=0n1n|n1*例例 文法文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEee
20、 L（G）=anbnen|n1 使用产生式使用产生式(1)n-1次，得到推导序列：次，得到推导序列：S=an-1S(BE)n-1，然后使用产生式然后使用产生式(2)一一次，得到：次，得到：S=an-1S(BE)n-1 an(BE)n。然后从然后从an(BE)n继续推导，总是对继续推导，总是对EB使使用产生式用产生式(3)的右部进行替换，而最终的右部进行替换，而最终在得到的串中，所有的在得到的串中，所有的B都先于所有的都先于所有的E。例如，例如，若若n=3,aaaBEBEBE aaaBBEEBE aaaBBEBEE aaaBBBEEE。即有：即有：S=anBnEn*接着，使用产生式接着，使用产生
21、式(4)一次，得到一次，得到S=*anbBn-1En，然后使用产生式然后使用产生式(5)n-1次得到：次得到：S=anbnEn，最后使用产生式最后使用产生式(6)一次，使用产生式一次，使用产生式(7)n-1次，得次，得到：到：S=anbnen 也能证明，对于也能证明，对于n1，串，串anbnen是唯是唯一形式的终结符号串一形式的终结符号串*S a S BE (SaSBE)a aBEBE (SaBE)aabEBE(aBab)aabBEE(EBBE)aabbEE（bBbb)aabbeE（bEbe)aabbee（eEee)文法和语言的关系：文法和语言的关系：G生成的每个串都在生成的每个串都在L(G)
22、中中L(G)中的每个串确实能被中的每个串确实能被G生成生成文法的等价文法的等价若若L L（G G1 1）=L=L（G G2 2），），则称文法则称文法G G1 1和和G G2 2是等价的。是等价的。如文法如文法G G1 1AA：A0R A01 RA1A0R A01 RA1与与G G2 2SS：S0S1 S01S0S1 S01等价等价 3.4文法的类型文法的类型通过对产生式施加不同的限制，通过对产生式施加不同的限制，ChomskyChomsky将文法分为四种类型：将文法分为四种类型：0 0型文法型文法：对任一产生式：对任一产生式，都有都有(V(VN NVVT T)+，(V(VN NVVT T)*
23、1 1型文法型文法：对任一产：对任一产生式生式，都有都有|，仅仅仅仅 SS除外除外例：例：1 1型（上下文有关文法）型（上下文有关文法）文法文法GSGS：SCDSCD AbbAAbbA CaCACaCABaaBBaaB CbCBCbCBBbbBBbbB ADaDADaD C C BDbDBDbD D D AabDAabD2 2型文法型文法：对任一产生式：对任一产生式，都有都有VVN N ，(V(VN NVVT T)*例：例：2 2型（上下文无关文法）型（上下文无关文法）GSGS：SABSABABS|0ABS|0BSA|1BSA|13 3型文法型文法：任一产生式：任一产生式的形式都为的形式都为A
24、aBAaB或或AaAa，其中其中AVAVN N ，BVBVN N ，aVaVT T例：例：3 3型文法型文法GS：S0A|1B|00A|1B|0A0A|1B|00A|1B|0S SB1B|1|01B|1|0GI：I lTlTI l lT lTlTT dTdTT l lT d d文法的类型文法的类型2型文法型文法1型文法型文法0型文法型文法四种四种文法文法之间之间的的逐级逐级“包含包含”关系关系3型文法型文法文法和语言文法和语言0 0型文法产生的语言称为型文法产生的语言称为0 0型语言型语言1 1型文法或上下文有关文法产生的语言型文法或上下文有关文法产生的语言称为称为1 1型语言或上下文有关语言
25、型语言或上下文有关语言2 2型文法或上下文无关文法产生的语言型文法或上下文无关文法产生的语言称为称为2 2型语言或上下文无关语言型语言或上下文无关语言 3 3型文法或正则（正规）文法产生的语型文法或正则（正规）文法产生的语言称为言称为3 3型语言正则（正规）语言型语言正则（正规）语言 3.53.5上下文无关文法及其语法树上下文无关文法及其语法树上下文无关文法有足够的能力描述程上下文无关文法有足够的能力描述程序设计语言的语法结构序设计语言的语法结构语法树语法树-句型推导句型推导的的直观表示直观表示例文法G=(E,+,*,i,(,),P,E)其中P为：Ei ,EE+E ,EE*E,E(E)E表示算
26、术表达式,i表示程序的“变量”，该文法定义了由变量，+，*,(和)组成的算术表达式的语法结构，即：变量是算术表达式；若E1和E2是算术表达式，则E1+E2，E1*E2和(E1)也是算术表达式描述一种简单赋值语句的产生式：描述一种简单赋值语句的产生式：赋值语句赋值语句i=Ei=E描述条件语句的产生式：描述条件语句的产生式：条件语句条件语句ifif条件条件thenthen语句语句 ifif条件条件thenthen语句语句elseelse语句语句句型、推导句型、推导GE：EE+T|T TT*F|F F(E)|aEE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a EE+T
27、 E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*aEE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a规范推导规范推导 规范句型规范句型最左（最右）推导最左（最右）推导：在推导的任何：在推导的任何一步一步，其中其中、是句型，是句型，都是对都是对中的最左（右）非终结符中的最左（右）非终结符进行替换进行替换最右推导被称为最右推导被称为规范推导规范推导。由规范推导所得的句型称为规范句由规范推导所得的句型称为规范句型型语法语法树树设设G=(G=(V VN N,V,VT T,P,S,P,S)，若一棵树满足下列若一棵树满足下列4 4个条
28、件，则此树称作个条件，则此树称作G G的语法树的语法树(推推导树导树)：1.1.每个结点都有一个标记，此标记每个结点都有一个标记，此标记是是V V的一个符号的一个符号2.2.根的标记是根的标记是S S3.3.若一结点若一结点n n至少有一个它自己除至少有一个它自己除外的子孙，并且有标记外的子孙，并且有标记A A，则，则肯定肯定AVAVN N4.4.如果结点如果结点n n有标记有标记A,A,其直接子孙其直接子孙结点从左到右的次序是结点从左到右的次序是n n1 1，n n2 2，n nk k，其标记分别为其标记分别为A A1 1，A A2 2，A Ak k，那么那么AAAA1 1A A2 2，A
29、Ak k一一定是定是P P中的一个产生式中的一个产生式语法树的结果：语法树的结果：从左到右读出叶子的标记而构成的从左到右读出叶子的标记而构成的行谓之句子行谓之句子语法树语法树-句型推导句型推导的的直观表示直观表示给定文法给定文法G=(G=(V VN N,V,VT T,P,S,P,S)，对于对于G G的任何句型都的任何句型都能构造与之关联的语法树能构造与之关联的语法树(推导树推导树)定理：定理：G G为上下文无关文法，为上下文无关文法，对于对于，有，有S S=，当且仅当当且仅当文法文法G G有以有以为结果的一棵语法树为结果的一棵语法树(推导推导树树)*构造语法树构造语法树GE E：EE+T|TE
30、E+T|T TT*F|F TT*F|F F(E)|a F(E)|aE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a E EE+T E +T T E E +T T FE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*aE EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*aE EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a E E E+T E+T T T*F T T*F F F a F F a a a a a 看不出句型中的符号被替看不出句型中的符
31、号被替代的顺序代的顺序上下文无关文法的语法树的用处上下文无关文法的语法树的用处用于描述上下文无关文法用于描述上下文无关文法句型推导句型推导的的直观方法直观方法 例例:GS:SaASASbAASSSaAba S a A S S b A a a b a句型句型aabbaa的的语法树语法树（推导树）（推导树）叶子结点叶子结点：树中：树中没有子孙的结点没有子孙的结点。从左到右从左到右读出推导树的读出推导树的叶子标记叶子标记连接成的连接成的文文法符号法符号串串，为，为GS的的句型句型。也把该推导树称。也把该推导树称为该为该句型句型的的语法树语法树。上下文无关文法的语法树上下文无关文法的语法树推导过程中推
32、导过程中施用施用产生式产生式的的顺序顺序 例例:GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa一棵语法树表示了一个句型的一棵语法树表示了一个句型的种种可能的种种可能的(但未必是所有的但未必是所有的)不同推导过程，包括最左不同推导过程，包括最左(最最右右)推导。但是，一个句型是推导。但是，一个句型是否只对应唯一的一棵语法树呢否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一一个句型是否只有唯一的一个最左个最左(
33、最右最右)推导呢推导呢?例：例：GE:E iE E+EE E*EE (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：E E+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二义文法二义文法 若一个文法存在某个句子有两个不同的若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是最左（右）推导，则称这个文法是二义二义的的 判定任给的一个上下文无关文法是判定任给
34、的一个上下文无关文法是否二义，或它是否产生一个先天二义否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找归不可解的，但可以为无二义性寻找一组充分条件一组充分条件 文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法的文法G G和和GG，其中其中G G是二义的，但是却是二义的，但是却有有L(G)=L(G)L(G)=L(G)，也就是说，也就是说，这两个文法所产生的语言是相同的。这两个文法所产生的语言是相同的。二义文法改造为无二义文法二义文法改造
35、为无二义文法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 （E E）|i|i E (E)E (E)规定优先顺序和结合律规定优先顺序和结合律 如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。的，因为希望对它的每个语句的分析是唯一的。3.6句型的分析句型的分析
36、句型分析句型分析就是就是识别识别一个符号串是否为某文法一个符号串是否为某文法的的句型句型，是某个，是某个推导推导的构造过程。的构造过程。在语言的编译实现中，把在语言的编译实现中，把完成句型分析完成句型分析的的程程序序称为称为分析程序分析程序或或识别程序识别程序。分析算法又。分析算法又称称识别算法识别算法。从左到右的分析算法从左到右的分析算法，即，即总是从总是从左左到到右右地地识识别输入符号串别输入符号串，首先识别符号串中的，首先识别符号串中的最左最左符号，进而符号，进而依次识别右边依次识别右边的一个符号，的一个符号，直直到分析结束到分析结束。句型的句型的分析算法分类分析算法分类分析算法可分为：
37、分析算法可分为：自上而下分析法自上而下分析法：从文法的开始符号出发从文法的开始符号出发，反复使用文法的，反复使用文法的产生式，产生式，寻找寻找与与输入符号串输入符号串匹配匹配的的推导推导。自下而上分析法自下而上分析法：从从输入符号串输入符号串开始开始，逐步进行逐步进行归约归约，直至，直至归约归约到到文法的文法的开始符号开始符号。两种方法反映了两种语法树的构造过程。两种方法反映了两种语法树的构造过程。自上而下方法自上而下方法是从文法符号开始，是从文法符号开始，将它做为语法树的根，向下逐步将它做为语法树的根，向下逐步建立语法树，使语法树的结果正建立语法树，使语法树的结果正好是输入符号串好是输入符号
38、串自下而上方法自下而上方法则是从输入符号串开则是从输入符号串开始，以它做为语法树的结果，自始，以它做为语法树的结果，自底向上地构造语法树底向上地构造语法树自上而下的语法分析自上而下的语法分析例：文法例：文法G：S cAd A ab A a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子SSScAdcAd a b推导过程：推导过程：S cAd cAd cabd自下而上的语法分析自下而上的语法分析例：文法例：文法G：S cAd A ab A a识别输入串识别输入串w=cabd是否该文法的是否该文法的句子句子SAA c a b d c a b d c a b d 规约规约过程构造
39、的推导：过程构造的推导：cAd cabd S cAd(1)S cAd (2)A ab (3)A a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子自上而下的语法分析自上而下的语法分析若若S S cAdcAd 后选择后选择(3)(3)扩展扩展A A，S S cAdcAd cad cad那将会？那将会？w w的第二个符号可以与叶子结点的第二个符号可以与叶子结点a a得以匹配，但第三个符号却不得以匹配，但第三个符号却不能与下一叶子结点能与下一叶子结点d d匹配匹配？宣告分析失败（其意味着，识？宣告分析失败（其意味着，识别程序不能为串别程序不能为串cadcad构造语法树，构造语法树
40、，即即cadcad不是句子）不是句子）-显然是错误的结论。显然是错误的结论。导致失败的原因是在分析中对导致失败的原因是在分析中对A A的的选择不是正确的。选择不是正确的。S c A d a(1)S cAd (2)A ab (3)A a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子自下而上的语法分析自下而上的语法分析对串对串cabd的分析中，如的分析中，如果不是选择果不是选择ab用产生用产生式式(2),而是选择而是选择a用用产生式产生式(3)将将a归约到归约到了了A，那么最终就达那么最终就达不到归约到不到归约到S的结果，的结果，因而也无从知道因而也无从知道cabd是一个句子
41、是一个句子c a b d c A b d a句型分析的有关问题句型分析的有关问题1 1）在自上而下的分析方法中）在自上而下的分析方法中如何如何选择选择使用使用哪个哪个产生式进行推导产生式进行推导？假定要被代换的最左非终结符假定要被代换的最左非终结符号是号是B B，且有且有n n条规则：条规则：BA1|A2|AnBA1|A2|An，那么如何确那么如何确定用哪个右部去替代定用哪个右部去替代B B？2 2）在自下而上的分析方法中在自下而上的分析方法中如如何何识别可归约的串识别可归约的串？在分析程序工作的每一步，在分析程序工作的每一步，都是从当前串中都是从当前串中选择一个选择一个子子串串，将它，将它归
42、约归约到到某个非终结某个非终结符号符号，该子串称为，该子串称为“可归约可归约串串”刻画刻画“可归约可归约串串”文法文法GSGS句型的短语句型的短语S S=A A且且 A A =，则则称称是是句型句型相对于非相对于非终结符终结符A A的的短语短语*+句型的直接短语句型的直接短语:若有若有A A ，则称则称是句型是句型相对于非终结符相对于非终结符A A 的的直接直接短语短语句型的句柄句型的句柄:一个句型的一个句型的最左直接短语最左直接短语称为称为该该句型句型的的句柄句柄例例i*i+ii*i+i例例 ：i*i+i i*i+i 的短语、直接短语和句柄的短语、直接短语和句柄 E E +T T FT *F
43、 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+i3.7文法实用中的一些说明文法实用中的一些说明 文法中文法中不含有不含有有害规则有害规则和和多余规则多余规则有害规则有害规则：形如：形如UU的产生式。会的产生式。会引起引起文法的文法的二义二义性性多余规则多余规则：指文法中：指文法中任何句子的推导任何句子的推导都都不会用到的规不会用到的规则则文法中文法中不含有不含有不可到达和不可终止的不可到达
44、和不可终止的非终结符非终结符1）文法中某些）文法中某些非终结符不在任何规则的右部出现非终结符不在任何规则的右部出现，该非终结符称为该非终结符称为不可到达不可到达。2）文法中某些）文法中某些非终结符非终结符，由它，由它不能推出终结符号不能推出终结符号串串，该非终结符称，该非终结符称为为不可终止不可终止。对于文法对于文法GS，为了保证任一非终结符为了保证任一非终结符A在在句子句子推导中出现，必须满足如下两个推导中出现，必须满足如下两个条件：条件：1.A必须在某句型中出现必须在某句型中出现 即有即有S=*A，其中其中，属于属于V V*2.必须能够从必须能够从A推出终结符号串推出终结符号串t来来 即即
45、A=*t，其中其中tVT*化简文法例：例：GS：1)SBe 2)BCe D为不可到达为不可到达 3)BAf C为不可终止为不可终止 4)AAe 5)Ae 6)CCf 7)Df 产生式产生式 2），），6），），7）为）为多余规则多余规则应去应去掉。掉。上下文无关文法中的上下文无关文法中的规则规则上下文无关文法中某些规则可具有形式上下文无关文法中某些规则可具有形式A，称这称这种规则为种规则为规则规则因为因为规则会使得有关文法的一些讨论和证明变得复规则会使得有关文法的一些讨论和证明变得复杂杂,有时会限制这种规则的出现有时会限制这种规则的出现两种定义的唯一差别是两种定义的唯一差别是句子在不在语言中句
46、子在不在语言中文法构思的启示是要找出语言的有穷描述，而如果文法构思的启示是要找出语言的有穷描述，而如果语言语言L有一个有穷的描述，则有一个有穷的描述，则L1=L也同样也同样有一个有穷的描述，并且可以证明，若有一个有穷的描述，并且可以证明，若L是上下文是上下文有关语言、上下文无关语言或正规语言，有关语言、上下文无关语言或正规语言，则则L和和L-分别是上下文有关语言、上下分别是上下文有关语言、上下文无关语言和正规语言。文无关语言和正规语言。思考思考本章目的为语言的语法描述寻求工具本章目的为语言的语法描述寻求工具,以便：以便：对源程序给出精确无二义的语法描述。（严谨、对源程序给出精确无二义的语法描述
47、。（严谨、简洁、易读）简洁、易读）根据语言文法的特点来进行语法分析根据语言文法的特点来进行语法分析1.1.什麽是文法什麽是文法,什麽是它的语言什麽是它的语言?2.2.我们为什麽关注上下文无关文法我们为什麽关注上下文无关文法?3.3.语法分析方法的分类语法分析方法的分类?本章小结本章小结 考察本章知识点最典型的题目是考察本章知识点最典型的题目是 答案答案1:GE EE+T|T TT*F|F F(E)|a答案答案2:GE EE+E|E*E|(E)|a2.给出语言描述，构造文法给出语言描述，构造文法.如：构造一文法如：构造一文法,其定义的语言是由算符其定义的语言是由算符+,*,(,)和运算对象和运算对象a构成的算构成的算术表达式的集合术表达式的集合.答案答案:GA定义的语言由定义的语言由0、1符号串组成，串中符号串组成，串中0和和1的个数相同的个数相同.1.已知文法已知文法GA，写出它定义的语言描述，写出它定义的语言描述 如：如：GA:A 0B|1C B 1|1A|0BB C 0|0A|1CC