编译原理-2前后文无关文法和语言教学课件

编译原理2前后文无关文法和语言16、云无心以出岫，鸟倦飞而知还。17、童孺纵行歌，斑白欢游诣。18、福不虚至，祸不易来。19、久在樊笼里，复得返自然。20、羁鸟恋旧林，池鱼思故渊。编译原理2前后文无关文法和语言编译原理2前后文无关文法和语言16、云无心以出岫，鸟倦飞而知还。17、童孺纵行歌，斑白欢游诣。18、福不虚至，祸不易来。19、久在樊笼里，复得返自然。20、羁鸟恋旧林，池鱼思故渊。2021/3/23第二章上下文无关文法和语言2.1文法和语言的表示2.2文法和语言的定义2.3 句型的分析2.4文法的化简和改造2.5文法和语言的Chomsky分类2021/3/23所谓形式化方法，简单地说，就是用一整套带有严格规定的符号体系来描述问题的理论和方法。用形式化方法描述的语言（语法和语义）便是形式语言。本章将从形式语言的角度系统地介绍什么是程序设计语言的文法、文法和语言的关系等问题。本章是本课程的理论基础。2.2文法和语言的定义基本概念和术语文法和语言的形式定义递归规则和递归文法2023/7/232.2.1基本概念和术语1.字母表：元素的非空有穷集合；符号符号集2.符号串：字母表中的符号所组成的任何有穷序列；例如：{a，b，c，+，.}特别的：空符号串ε（不包含任何符号）在编译中起非同小可的作用2023/7/233.字母表∑上的符号串的递归定义ε是∑上的符号串；若x是∑上的符号串，且a∈∑，则xa或ax是∑上的符号串；

若y是∑上的符号串，当且仅当y可由（1）和（2）产生；特别的：εx=xε=x2023/7/23ε是∑上的符号串∑上的所有符号串：ε，b,c,bb，bc，cb，cc,bbb，bbc，bcb，bcc，cbb，bcb，ccb，ccc……εb和εc即b，c是∑上的符号串bb，bc，cb，cc是∑上的符号串bbb，bbc，bcb，bcc，cbb，bcb，ccb，ccc是∑上的符号串…….例如：∑={b，c}，求∑上的所有符号串2023/7/234.符号串的前缀、后缀和子串：设x是一符号串，从x的尾部（头部）删去若干个（包括0个）符号之后所剩余下的部分称为x的前缀（后缀）；若x的前缀（后缀）不是x本身，则称为x的真前缀（真后缀）；从一个符号串中删去它的一个前缀和一个后缀之后所剩下的部分称为此符号串的子串；2023/7/23x的前缀：x的真前缀：x的后缀：x的真后缀：x的子串：例如：设x=abcε，a，ab，abcε，a，abε，c，bc，abcε，c，bcε，abc，ab，a，bc，b，cx=εaεbεcε2023/7/236.符号串的连接和方幂：设有符号串x,y，把y的符号写在x的符号之后所得的符号串，叫做x与y的连接，记xy；设有符号串x，则x的n次自身连接称为x的n次方幂，记为xn

；x0=ε例如：符号串为x=ab，则其长度|x|=25.符号串的长度：符号串所含符号的个数；特别的：2023/7/237.符号串集合A与B的和与积：A+B={w|w∈A或w∈B}AB={xy|x∈A且y∈B}8.符号串集合的方幂：设有符号串集合A，则定义A0={ε}，A1=A，A2=AA，A3=AAA=A2A，…例如：A={a,b,c}，B={00,11}A+B={a,b,c,00,11}AB={a00,b00,c00,a11,b11,c11}2023/7/239.符号串集合的正闭包：设A为符号串集合，则定义A的正闭包A+为：A+=A1∪A2∪A3∪……∪An∪……

例如：A={a,b}A＋

={a,b}∪{aa,ab,ba,bb}∪……={a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,bab,bba,bbb,……}2023/7/2310.集合A的闭包A*

：比A+多一个ε

设A为符号集合，则定义A的闭包A*为：A*=A0∪A+={ε}∪A+

；A*由A上的元素a,b构成的所有符号串的集合；2023/7/232.2.2文法和语言的形式定义文法的形式定义推导的形式定义语言的形式定义2023/7/232.2.2.1文法的形式定义规则（产生式）：定义有序对（U，x）记为U::＝x或U→x；x是有穷符号串规则的右部U是符号规则的左部例如：S→abc<主函数>→main（参数表）<参数说明>(函数体)文法G[Z]：规则的非空有穷集合

Z：开始符号（识别符号），至少在一条规则的左部出现；U定义为x2023/7/23字汇表V：规则左右部中所有符号组成的集合

非终结符号：规则左部出现的符号为非终结符号，组成的集合为Vn

；终结符号集合：规则中不属于Vn的符号为终结符号，组成集合Vt

；V=VnUVt

2023/7/23文法的四元式表示：G=（Vn

，Vt

，P，Z）

Vn

：非终结符号集；

Vt

：终结符号集；

P：规则的集合；

Z：开始符号；当规则中有相同的左部时：V→x，V→y，…V→z，可以写成：V→x|y|…|z；2023/7/23例如：G=(Vn,Vt,P,S)其中Vn={S,A,B},Vt={a,b}P:S→aB|bA，A→a|aS|bAA，B→b|bS|aBBG[S]：S→aB|bA A→a|aS|bAA B→b|bS|aBB一般规定：第一条规则的左部为开始符号

2023/7/23问题： 有了文法，如何确定语言呢？2023/7/232.2.2.2推导的形式定义直接推导：如果U→u是G中的一条规则，而x，y∈V*，则将规则U→u用于符号串r=xUy上得到符号串w=xuy，记为：xUy=>xuy(r=>w)，称符号串w是符号串r的直接推导，或符号串r直接产生了符号串w，称w直接归约到r。

V*是字汇表的闭包，即x，y是字汇表上任意的两个字符串；如果x=ε，y=ε，则U=>u；2023/7/23例如：G[S]：S→aB|bA A→a|aS|bAA B→b|bS|aBBS=>aBU=>u（规则U→u,x,y均为ε）abS=>abbAxU=>xu（规则U→u,x为ab,y为ε）aB=>aaBBxU=>xu（规则U→u,x为aaB,y为ε）每一步只能替换一个非终结符号

2023/7/23U→u：U=>u：

规则（产生式），可以用到不同的场合；推导的动作；从语义的角度上来讲，是完全不同的。

2023/7/23推导（长度为n）：设u0,u1,…,un(n>0)均为V*中的符号串，且有

r=u0=>u1=>……=>un-1=>un=w，记为rw， 则称以上序列为长度n的推导，也称r产生w(w归约为r)。特例：如果rw（一步或一步以上）或r=w（0步），记为rw；2023/7/23推导过程

使用规则

S=>aB

S→aB

=>abS

B→bS

=>abbA

S→bA=>abbbAA

A→bAA=>abbbaA

A→a

=>abbbaa

A→a只要符号串中存在非终结符号，推导就能继续，直至符号串全部由终结符号组成，这也是为什么称终结符和非终结符的原因。例如：文法G[S]可进行的推导文法BNF表示为G[S]:S→aB|bAA→a|aS|bAAB→b|bS|aBB2023/7/232.2.2.3语言的形式定义句型：设有文法G[Z]，如果有Zx，x∈V*，则称x是文法G的一个句型。句型中既含有终结符号，又包括非终结符号；凡是由开始符号（识别符号）推导出来的字汇表V上的任意符号串都叫做句型；任何文法的开始符号都是该文法的一个句型；

Zx，可以有Z=x2023/7/23句子：设有文法G[Z]，如果有Zx，x∈Vt*，则称x是文法G的一个句子。也有的版本写成Zx

；句子是句型的一个子集；

例如：S=>bA=>bbAA=>bbaA=>bbaa句型句子2023/7/23语言L(G[Z])：文法G[Z]所产生的所有句子的集合，称为文法G[Z]所定义的语言。

L(G[Z])={x|x∈Vt*且Zx}

2023/7/23文法

推导句型句子文法的语言规则非空有穷集合同一个句子可以由不同的推导序列推导出来Zx，x∈V*Zx，x∈Vt*2023/7/23问题： 文法与语言之间存在一一对应的关系吗？2023/7/23例如：G1[A]：A→BbB→aL(G1)={ab}G2[A]：A→abL(G2)={ab}G1≠G2但L(G1)=L(G2)，称G1和G2为等价文法

2023/7/23给定文法后，可以确定它的语言，但由语言写出它的文法是比较难的，这里形式语言理论可以证明两点：给定一文法，就能从结构上唯一确定其语言，即G→L(G)；给定一语言，能确定其文法，但这种文法不是唯一的，即L→G1或G2…；2023/7/23设G=(Vn，Vt，P，S)为一文法，并设W→xVy是P中一产生式，且V→β1|β2|β3……|βn是P中V的全部产生式；又设G1=(Vn，Vt，P1，S)是其中P1从P中删去W→xVy，加入W→xβ1y，W→xβ2y，…W→xβny所组成的集合，则L(G1)=L(G)；2023/7/23问题： 语言为无限集时，该用什么样的文法来表示呢？2023/7/232.2.3递归规则与递归文法

递归规则：形如V→xVy，V∈Vn，左右具有相同的非终结符号的规则。V→Vy(x=ε)，左递归规则；V→xV(y=ε)，右递归规则；V→xVy(x,y≠ε)，自嵌入递归规则；递归规则是对其左部的非终结符号进行递归定义2023/7/23文法的递归性：直接递归性：文法中至少包含一条递归规则；

e.g.：Z→aZb, Z→ab间接递归性：文法的任一非终结符号经一步以上推导产生的递归性文法的递归性原则：文法具有直接递归性或间接递归性，否则，文法无递归性；2023/7/232.3句型的分析源程序的翻译工作，基本任务不是生成句子，而是识别句子和句子的结构，以确定一符号串是不是文法的句子；用来进行句型分析的方法大致分为两类：即自顶向下的分析和自底向上的分析。

2023/7/232.3.1规范推导和规范规约

例如： G[<标识符>]：

<标识符>→<字母>|<标识符><字母>| <标识符><数字> <字母>→a|b|…|z|A|…|Z<数字>→0|1|2|…|9句子a4y??2023/7/23对句子的结构进行确定性的分析，往往只采用两种特殊的推导方式。

最左推导

最右推导2023/7/23最左（右）推导：在任一步直接推导V=>w中，都是对符号串V的最左（最右）非终结符号进行替换，称为最左(右)推导。每一个句子都必定有最左推导和最右推导，但不是每一句型都有；

<标>=><标><字>=><标><数><字>=><标>4<字>

<标>=><标><字>=><标><数><字>=><标>4<字>

2023/7/23左（右）句型：由最左（右）推导所得的句型；规范推导：即最右推导；规范句型：由规范推导所得的句型；规范归约：规范推导的逆过程，即最左归约；

2023/7/23最左推导最右推导规范归约

逆过程

逆过程最右归约最左归约规范推导推导2023/7/23自顶向下的分析：从文法的开始符号出发，以给定的符号串为目标，试图推导出此符号串；若采用自顶向下的语法分析来某一符号串是否是语言的句子，通常的做法是为该符号串建立一个从开始符号到此符号串的最左推导；2023/7/23如何正确选择规则？——语法分析<标>=><标><字>=><标><数><字>=><字><数>

<字>=>a<数><字>=>a4

<字>=>a4

y2023/7/23自底向上的分析：从给定的符号串出发，反复用文法中有关产生式的左部去替换当前符号串中的相应子串，从而“归约”为文法的开始符号；若采用自底向上的语法分析来某一符号串是否是语言的句子，通常的做法是从该符号串出发，建立一个最右推导；2023/7/23<标>=><标><字>

=><标>y=><标><数>y=><标>4y=><字>4y=>a4y问题：如何正确选择可归约串？<标><≠<标><字>

<≠<标>y<≠<标><数>y<≠<标>4y<≠<字>4y<≠a4y2023/7/232.3.2短语、简单短语和句柄

短语：设ω=xuy是文法G[Z]的一个句型，其中x，y∈V*，u∈V+，如有ZxVy，且V u，V∈Vn，称u是句型ω相对于非终结符号V的短语。

简单短语（直接短语）：设ω=xuy是文法G[Z]的一个句型，其中x，y∈V*，u∈V+，如有

ZxVy，且V=>u，V∈Vn，称u是句型ω相对于非终结符号V的简单短语。

2023/7/23短语或简单短语必须是针对某一句型来说的，并且是该句型的一个子串；短语或简单短语必须是相对某一非终结符号的；两个条件缺一不可；一个句型可以有几个短语和简单短语；

2023/7/23句柄：句型的最左简单短语为该句型的句柄；一句型只有一个句柄。

2023/7/23例如：G[S]：S→AB，

A→Aa|bB，

B→a|Sb对于句型baSb，求短语、简单短语和句柄

S=>AB=>bBB=>baB，且B=>Sb，Sb是句型baSb相对于B的短语，且为简单短语；S=>AB=>ASb，且Aba，ba是句型baSb相对于A的短语；S=>AB=>ASb=>bBSb，且B=>a，a是句型baSb相对于B的短语，且为简单短语；句柄2023/7/23利用定义来找短语、简单短语、句柄，比较抽象，下面介绍语法树的概念，利用语法树可以直观地找到句型的短语、简单短语和句柄。

2023/7/232.3.3语法树语法树：一个句型或句子推导过程的图示法表示，形成一棵语法树；例如：G[S]：S→AB，

A→Aa|bB，

B→a|Sb对于句型baSb的推导形成的语法树

2023/7/23推导1：

S=>AB=>bBB=>baB=>baSbSABbBaSbG[S]：S→AB，

A→Aa|bB，

B→a|Sb2023/7/23推导2：

S=>AB=>ASb=>bBSb=>baSbSABbBaSbG[S]：S→AB，

A→Aa|bB，

B→a|Sb2023/7/23SABbBaSb根：文法的开始符号子树：某一非终结符号(子树的根)及其下面的分支

叶：末端结点

2023/7/23有了语法树，我们就可以利用这种概念和工具直观的确定句型的短语、简单短语和句柄。2023/7/23短语：子树的末端结点形成的符号串；短语相对的句型：整个树的末端结点；简单短语：简单子树，只有一层分支的子树；

SABbBaSb2023/7/23对于句型baSb共有三棵子树，三个短语：ba，a，Sb简单短语：a，Sb句柄：aSABbBaSb2023/7/23从语法树的角度来看归约：

S <≠AB <≠ASb <≠bBSb <≠baSbSABbBaSbABbBaSb用产生式的左部替换当前句型中的相应子串每次归约的都是当前句型中的某一直接短语2023/7/23因此，最左归约归约的是当前句型的句柄

归约非常重要，因为源程序都是符号串形式的，这就需要把它归约为开始符号（程序）才算正确。它是语法分析所采用的方法，而要想从开始符号推导出你的源程序是相当困难的（对计算机来说，工作量非常大），因为一般来说，语言是无穷的。2023/7/23对每个语法树，至少存在一个推导；对于每个推导，都有一个相应的语法树（但不同的推导可能有相同的语法树）；树的末端结点形成所要推导的句型；

结论：相同句型也可能对应两棵不同的语法树

2023/7/232.3.4文法的二义性如果文法G的某一个句子存在两棵或两棵以上不同的语法树，则称句子是二义性的；如果一个文法所定义的句子中含有二义性的句子，则称该文法是二义性的，否则该文法是无二义性的；2023/7/23例如：E→E+E|E*E|(E)|i句子i+i*i，同是最左推导，对应两棵不同的语法树：E=>E+E =>i+E =>i+E*E =>i+i*E =>i+i*i最左推导1：EEEiEEii+*2023/7/23例如：E→E+E|E*E|(E)|i句子i+i*i，同是最左推导，对应两棵不同的语法树：E=>E*E =>E+E*E =>i+E*E

=>i+i*E

=>i+i*i最左推导2：EEEEEi*i+i2023/7/23句柄：i,i,i,E*E,E+E表示：i+(i*i)句柄：i,i,E+E,i,E*E表示：(i+i)*iEEEiEEii+*EEEEEi*i+i语法树1：语法树2：2023/7/23文法的二义性：某一句子有二个不同的最左（右）推导或二个不同的最左（规范）归约；文法的二义性是不可判定的：不存在一种算法，只能用一些简单条件来判定是充分的，不是必要的，即满足某些条件的文法可以说是二义性的；特例：若一文法G既含左递归又含右递归，则G必是二义性文法；

2023/7/23以上的分析中，忽略了两个问题：自顶向下分析时：如有V→x1|x2…|xn，选哪一产生式可一次推导成功？自底向上分析时，如何尽快找到当前句型的句柄？（进行归约）这些问题将在语法分析时解决2023/7/232.4文法的化简和改造

文法的实用限制无用符号和无用产生式的删除ε-产生式的消除（自己看书）单产生式的消除（自己看书）扩充的BNF表示2023/7/232.4.1文法的实用限制在实用中，我们将限制文法中不含有：一、无用产生式二、有害产生式2023/7/23无用产生式：一个产生式的左部或右部含有无用符号。2.4.1文法的实用限制设G=（Vn，Vt，P，S）是一文法，G中的符号X∈Vn∪Vt是有用的，则X必满足：①存在α，β∈V*，有SαXβ；②存在w∈Vt*，使得αXβw；否则，称符号X是无用的；一、无用产生式：至少在某一推导过程中出现由X能推出终结符号2023/7/23二、有害产生式：V→V即使V是一个有用的符号，此类产生式也是不必要的；如果一个句型中含有非终结符号V，那么可以任意多次使用产生式V→V，这样会引起二义性；2023/7/23例如：G1[S]：S→0S1|01G1无二义性文法G2[S]：S→0S1|01|S

G2二义性文法对于句子0011的语法树

2023/7/23G2文法句子0011的两棵不同语法树.SSS

0S10S1

010174北京交通大学于双元不含无用产生式；不含形如V→V的产生式；满足上述条件的文法称化简过或压缩过的文法。

2023/7/232.4.2无用符号和无用产生式的删除

算法2.1：将文法G=(Vn，Vt，P，S)改造为等价文法G1=(Vn①，Vt，P①，S)，使得对于任意X∈Vn①，满足Xw1，其中w1∈Vt*，即G1中的任一非终结符号均能推导出终结符号串；算法2.2：对于给定文法G改造为等价G’=(Vn’，Vt’，P’，S)，使得使得对于任意X∈Vn’∪Vt’，都存在α，β∈(Vn’∪Vt’)*，有SαXβ；

假定L(G)≠Ø2023/7/23算法2.1：①分别置Vn①，P①为Ø；②对于P中的每一产生式A→δ，若δ∈Vt*，则将A置于Vn①中；③对于P中的每一个产生式A→X1X2X3……Xm，若每一个Xi都属于Vt或Vn①则将A置于Vn①中；④重复步骤③，直到Vn①不再增大为止；⑤对于P中的每一产生式B→Y1Y2……Yn，若B及每一个Yi都属于Vn①∪Vt，则将此产生式B→Y1Y2……Yn置于P①；

2023/7/23算法2.2：①分别置Vn’，Vt’及P’为Ø；②将文法G的开始符号S置于Vn’中；③对于G中任何形如A→α1|α2|…|αm的产生式，如果A∈Vn’，则将符号串α1，α2，……αm中全部的非终结符号置于Vn’中，而将其中的全部终结符号置于Vt’中；④重复步骤③，直到Vn’和Vt’都不再增大为止；⑤将P中左右部仅含Vn’∪Vt’中的符号的所有产生式置于P’；

2023/7/23例如：文法G=({S，U，V，W}，{a，b，c}，P，S)P由如下的产生式组成：

S→aS|W|U U→a V→bV|acW→aW2023/7/23执行算法2.1：①置Vn①，P①为Ø；②由U→a，V→ac，故Vn①={U，V}；③由S→U，则S∈Vn①，Vn①={S，U，V}，Vn①不再增大；故G1={{S，U，V}，{a，b，c}，P1，S}P1

：S→aS|UU→aV→bV|ac2023/7/23执行算法2.2：①分别置Vn’，Vt’及P’为Ø；②Vn’={S}；③由S→aS|U，则Vn’={S，U}，Vt’={a}， 由U→a，则Vn’={S，U}不再增大，Vt’={a}不再增大

G’={S，U}，{a}，P’，S}P’：S→aS|UU→a压缩过的文法2023/7/232.4.3ε-产生式、单产生式的消除ε-产生式：右部为空符号串ε的产生式；某些词法分析算法要求文法不含ε-产生式单产生式：右部仅含有一个非终结符号的产生式A→B（A，B∈Vn）；如果一个文法含有过多的单产生式，将会增加编译程序在工作时所需的时间和存储空间，因此必要时应该设法消除；2023/7/232.4.4扩充的BNF表示

例如：规则中有相同的左部时：

V→x，V→y，…V→z

写成：V→x|y|…|z元符号

由元符号组成的巴科斯范式（元语言公式）是用以描述算法语言的元语言；

2023/7/23BNF（巴科斯范式）：

<，>，：：=(→)，∣扩充的BNF（巴科斯范式）：

<，>，：：=(→)，∣，

(，

)

，{，}，[，]

2023/7/231、{}t∈V*，符号串t自重复n到m次；

{t}t∈V*，符号串t自重复0到无穷次；例如：BNF：G[<无符号整数>]<无符号整数>→<数字>∣<无符号整数><数字><数字>→0∣1∣2∣3∣……∣9扩充的BNF：G[<无符号整数>]<无符号整数>→<数字>{<数字>}

<数字>→0∣1∣2∣3∣……∣92023/7/232、[][t]t∈V*，

t符号串可有可无；

例如：BNF：