编译原理3课件

第三章文法和语言3.1文法的直观概念3.2符号和符号串3.3文法和语言的形式定义3.4文法的类型3.5上下文无关文法及其语法树3.6句型分析语言和文法为什么关心文法问题？

为语言的描述寻求一种工具(以确定什么样的句子属于该语言)。穷举法是不合适的(原因？)。提供有限的描述语言特性的法则—文法要对程序设计语言给出精确无二义的语法描述，严谨、简洁、易读形式化工具

“形式化”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述，形式化很像是数学的符号化文法的直观概念以自然语言为例，人们罗列出所有的句子，但人们可以给出一些规则，用它们来说明或定义句子合理的组成结构这里采用前面介绍过的EBNF来如下简单地表示自然语言中句子的构成规则：<句子>::=<主语><谓语><主语>::=<代词>|<名词><代词>::=我|你|他符号和符号串语言离不开符号的使用字母表：

字母表是符号的非空有穷集合，因此，字母表也可称为符号集不同的语言可以有不同的字母表符号串：

由字母表中的符号组成的任何有穷的符号序列称为符号串符号串及若干相关运算符号串的头尾，固有头和固有尾：

如果z=xy是一个符号串，那么称x是z的头，y是z的尾；如果x是非空的，那么y称为固有尾；同样，如果y非空，那么称x是固有头例，对于z=abc，那么z的头是,a,ab,abc，除abc外，其他都是固有头；z的尾是,c,bc,abc，z的固有尾是,c,bc求符号串长度：

如果某符号串x中有m个符号，则称其长度为m，并表示为|x|=m例，|001110|=6符号串上的运算符号串的连接：设x和y是符号串，它们的连接xy是把y放在x之后得到的符号串显然，x=x=x；|xy|=|x|+|y|符号串的方幂：

把x连接n次得到的符号串，如z=xx，写作z=xn

例，x0=，x1=x等等；如果x=AB，则x2=ABAB字符串集合：

如果集合A中的元素都是某字母表上的符号串(符号串的集合)，则称A为该字母表上的符号串集合文法定义定义：文法G为四元组(VN,VT,,P,S)其中，VN，VT和P都是非空有穷集。具体地，VN是非终结符号(或语法实体，或语法变量)集；VT终结符号集；P是规则的集合S是称作识别符号或开始符号的一个非终结符，它至少要在一条产生式中作为左部出现VN和VT不含公共的元素，即VN∩VT=φ用V表示VN∪

VT，称为文法G的字母表或字汇表规则，也称重写规则、产生式或生成式，是形如→或::=的(,)有序对，其中是字母表V的正闭包V+中的一个符号且至少含一个非终结符，是V*中的一个符号。称为规则的左部，称作规则的右部文法定义例，文法G=(VN,VT,P,S） VN={S},VT={0,1} P={S→0S1,S→01} S为开始符号文法的写法

元符号:→::=|<>

习惯:大写字母表示非终结符,小写字母表示终结符(1)G:S→aAbA→abA→aAbA→(2)G[S]:A→abA→aAbA→

S→aSb(3)G[S]:A→ab|aAb|εS→aSb推导例，有下面的推导，括号里是相应的文法：<程序><分程序>.(<程序><分程序>.)<分程序>.<变量说明部分><语句>.(<分程序><变量说明部分><语句>)VAR<标识符>;BEGINREAD(<标识符>)END.VARA;BEGINREAD(<标识符>)END.(<标识符>A)VARA;BEGINREAD(<标识符>)END.VARA;BEGINREAD(A)END.(<标识符>A)推导若存在v=w0w1...wn=w,(n>0)，则记为v=>+w，称作v推导出w，或w归约到v若有v=>+w或v=w，则记为v=>*w例，有文法G：S→0S1，S→01，则可确定存在下面一些推导0S100S1100S11000S111000S11100001111S0S100S11000S11100001111于是，S

+00001111S*S00S11*00S11句子和句型例，设有文法G[E]：E→E+T|T

T→T*F|F

F→(E)|a

有推导EE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a，等等通过观察可以知道，上述文法定义的句子是用符号a，+，*，(以及)构成的算术表达式语言、文法和句子例，由文法G生成的语言记为L(G),它是文法G的一切句子的集合:L(G)={x|S*x，其中S为文法的开始符号，且x∈VT*}

例：G：S→0S1，S→01L(G)={0n1n|n≥1}集合表示形式文法、语言和句子例文法G[S]： （1）S→aSBE （2）S→aBE （3）EB→BE （4）aB→ab （5）bB→bb （6）bE→be （7）eE→ee

L(G)={anbnen|n≥1}G生成的每个串都在L(G)中L(G)中的每个串确实能被G生成文法的类型通过对产生式施加不同的限制，学者Chomsky将文法分为四种类型：0型文法：对任一产生式→，都有

(VN∪VT)+，(VN∪VT)*1型文法：对任一产生式→，都有||≥||，仅仅S→除外2型文法：对任一产生式→，都有VN

3型文法：任一产生式→的形式都为A→aB或A→a，其中A∈VN，B∈VN，a∈VT*文法的类型例，下面是1型(上下文有关)文法文法G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→a BD→bD D→b Aa→bD文法与类型例，下面是2型(上下文无关)文法

文法G[S]： S→AB A→BS|0 B→SA|1不同类型文法之间的关系四类文法之间存在逐级包含的关系2型文法1型文法3型文法0型文法文法和语言文法和它所产生的语言之间存在对应关系0型文法产生的语言称为0型语言1型文法或上下文有关文法(CSG)产生的语言称为1型语言或上下文有关语言(CSL)2型文法或上下文无关文法(CFG)产生的语言称为2型语言或上下文无关语言(CFL)3型文法或正则(正规)文法(RG)产生的语言称为3型语言正则(正规)语言(RL)几个理论共识结论3：任何能用图灵机描述的计算都能机械实现，任何能在现代计算机上实现的计算都能用图灵机描述带a0a1a2a3a4a5a6a7a8…an-1an…有限控制器磁头几个理论共识结论4：2型文法产生式的形式为A→，取代A时与A的上下文无关。其识别系统是不确定的下推自动机结论5：3型文法(正规文法RG)产生的语言是有穷自动机(FA)所接受的集合3型文法与有穷自动机定理：设G=(VN,VT,P,S)是3型文法，则存在一个有穷自动机M=(K,,f,A,Z)，使得L(M)=L(G)可以从文法直接构造相应的自动机：=VT

Z={N}，N是新增加的一个状态A=SK={VN}{N}f的设置需视情况来定

a,对G中的形如D→tB的产生式,t为终结符或，有f(D,t)=Bb,对G中形如D→t的产生式，t为终结符或ε,有f(D,t)=Nc,对VT中的每一个a,有f(N,a)=φ从3型文法到有穷自动机从3型文法按前述方法可直接构造相应的有穷自动机G[S]：S→aA|bB

A→bB|aD|aB→aA|bD|bD→aD|bD|a|bASaabbba,bZababBD从有穷自动机到3型文法定理：已知一有穷自动机M=(K,,f,A,Z)，那么存在一个3型文法G=(VN,VT,P,S)，使得L(G)=L(M)3型文法的构造方法：VT=VN=KS=A对转换函数

a,若f(D,t)=B，则D→tB在P中

b,若f(D,t)=B，且B在Z中，则D→t在P中从有穷自动机到3型文法下面的例子是从有穷自动机到3型文法的直接转换G[S]：S→aA|bB

A→bB|aD|aB→aA|bD|bD→aD|bD|a|bDBASaaabba,bb正规式与3型文法定理：对上的正规式r，存在一个RG=(VN,VT,P,S)使得L(G)=L(r)成立转换方法：初始时，VT=

，SVN，生成正规产生式Sra,对形如Ar1r2的正规式得到产生式：Ar1B Br2将B加入VNb,对形如Arr1的正规式得到产生式：ArB，将B加入VNAr1

BrBBr1c,对形如Ar1r2的正规式得到产生式：Ar1Ar2

不断应用(R.x)做变换，直到每个产生式右端至多有一个VN从正规式到正规文法转换实例对正规式r=a(ad)*，有下面的转换过程(1)Sa(ad)*(2)SaAA(ad)*

(3)A(a|d)BAB(a|d)BB从而得到下面转换后的文法：G[s]：SaAA AaBAdBBaBBdB BVT={a,d}VN={S,A,B}从正规文法到正规式定理：已知G=(VN,VT,P,S)，那么存在一个=VT上的正规式r，使得L(r)=L(G)成立转换方法：对AxB，By，得到正规式A=xy对AxA|y，得到正规式A=x*y对Ax|y，得到正规式A=x|y从正规文法到正规式的实例对于文法G[s]:SaA|aAaA|a|dA|d有下面的转换过程：A(ad)A(ad)A(ad)(ad)S=a(ad)(ad)a=a((ad)(ad))=a((ad))从而得到：

R=a(ad)上下文无关文法结论：

上下文无关文法有足够的能力描述程序设计语言的语法结构以语法树的形式给出句型推导直观表示文法、推导、句型和句子设有文法G[E]：E→E+T|T

T→T*F|F

F→(E)|a

有下面的推导成立

EE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a

EE+TE+T*FE+T*aE+F*aE+a*a

T+a*aF+a*aa+a*a

EE+TT+TT+T*FF+T*FF+F*F

a+F*Fa+F*aa+a*a规范推导与规范句型最左推导：在推导的任何一步，其中、是句型，都是对中的最左非终结符进行替换最右推导：在推导的任何一步，其中、是句型，都是对中的最右非终结符进行替换最右推导被称为规范推导由规范推导所得的句型称为规范句型语法树及其形式表示定义：设G=(VN,VT,P,S)为一上下文无关文法，若一棵树满足下列4个条件，则此树称作G的语法树(也称推导树或派生树)：1.每个结点都有一个标记，此标记是V的一个符号2.根的标记是S3.若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定AVN4.如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，…，nk，其标记分别为A1，A2，…，Ak，那么A→A1A2，…，Ak一定是P中的一个产生式语法树的结果：从左到右读出叶子的标记而构成的行谓之上下文无关文法的语法树句型aabbaa可能的推导序列和语法树例:G[S]: S→aAS A→SbA A→SS S→a A→baS

aASSbAa

a

b

aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa推导的唯一问题一棵语法树表示了一个句型一种可能的推导过程，但存在下面问题值得考虑对任何一个句型，是否其推导过程只对应唯一的一棵语法树呢?对任一句型，它是否只有唯一的一个最左或最右推导呢?两个不同推导对下面的文法，存在两棵不同的语法树显然，对句型i*i+i有两个不同的最左推导：推导1：EE+EE*E+Ei*E+Ei*i+Ei*i+i

推导2：EE*Ei*Ei*E+Ei*i+Ei*i+i例：G[E]:

E→i E→E+E E→E*E E→(E)EE+EE*EiiiEE*EiE+Eii二义文法定义1：

若一个文法存在某个句子有两个不同的最左或最右推导，则称这个文法是二义的定义2：

若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的文法二义性与语言二义性文法二义性和语言二义性是两个不同的概念。因为可能有两个不同的文法G和G，其中G是二义文法，但是却有L(G)=L(G)，也就是说，这两个文法所产生的语言是相同的如果一个上下无关语言，能产生它的每一个文法都是二义的，则说此语言是先天二义的显然，对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的二义文法到无二义文法可以将二义文法改造为无二义文法例：将左边的文法改造为右边的文法，便可消除二义原因分析：通过规定运算符的优先性和结合性来消除二义G[E]：E→iE→E+EE→E*EE→(E)G[E]：E→T|E+TT→T|T*FF→(E)|i上下文无关文法的句型分析句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束句型分析方法分类主要有下面两类：自上而下分析法它从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导，或者说，为输入串寻找一个最左推导自下而上分析法从输入符号串开始，逐步进行归约，直至归约到文法的开始符号两种方法反映了两种语法树的构造过程自上而下方法从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果(通过从左往右遍历语法树而得到)正好是输入符号串自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树自上而下的语法分析例，文法G：S→cAd

A→ab

A→a

识别输入串w=cabd是否为该文法的句子 S S S

c A d

c A d

a

b推导过程：S

cAd

cAd

cabd自下而上的语法分析例，文法G：S→cAd

A→ab

A→a

识别输入串w=cabd是否该文法的句子 S

A

A

cabd

ca

bd

ca

b

d

规约过程构造的推导：cAd

cabdScAd自上而下的语法分析前述的方法会否碰到问题？对文法G:(1)S→cAd(2)A→ab(3)A→a

识别输入串w=cad是否为该文法的句子从S出发得到S→cAd，下面对A有两条规则能用，用那条？这里使用第二条A→ab，那么S→cabd，得不到所要识别的句子，此时能否宣告分析失败：该句子无法识别？不能，因为换作第三条便可问题的解决对于前面的问题，可按右面的方法解决ScAdab这时应该回朔，把A为根的子树剪掉，扫描过的输入串中的a吐出来,再试探用产生式(3)自下而上的文法分析对前面文法(1)S→cAd(2)A→ab(3)A→a

采用自下而