编译原理2

2010年9月湖北大学数计学院计科系第2章形式语言概论（主要介绍形式语言理论中的一些基本概念和基础知识，包括文法、语言、语法树和分析方法等）2010年9月湖北大学数计学院计科系2.1字母表和符号串2.2文法及其分类2.3语言和语法树2.4关于文法和语言的几点说明2.5分析方法简介2.6小结2010年9月湖北大学数计学院计科系2.1字母表和符号串一、字母表和符号串字母表：符号的非空有限集例：={a，b，c}符号：字母表中的元素例：a，b，c符号串：符号的有穷序列例：a,aa,ac,abc，..空符号串：无任何符号的符号串(ε）符号串集合：由符号串构成的集合。符号串的形式定义有字母表，定义：（1）ε是上的符号串；（2）若x是上的符号串，且a，则ax或xa是上的符号串；（3）y是上的符号串，iff（当且仅当）y可由（1）和（2）产生。2010年9月湖北大学数计学院计科系二、符号串和符号串集合的运算1.符号串相等：若x、y是集合上的两个符号串，则x＝yiff（当且仅当）组成x的每一个符号和组成y的每一个符号依次相等。2.符号串的长度：x为符号串，其长度|x|等于组成该符号串的符号个数。例：x＝CCTV，|x|=4特别有|ε|＝0，即空符号串的长度等于零。2010年9月湖北大学数计学院计科系例：A＝{a,b},B={c,d},AB=？4.符号串集合的乘积运算：令A、B为符号串集合，定义AB＝{xy|x∈A,y∈B}注意：⑴因为εx＝xε＝x，所以{ε}A={ε}A=A⑵ΦA=AΦ=Φ其中，Φ为空集3.符号串的联接：若x、y是定义在Σ是上的符号串，且x＝XY，y＝YX，则x和y的联接xy＝XYYX也是Σ上的符号串。注意：一般xy≠yx，而εx＝xε{ac，ad，bc，bd}2010年9月湖北大学数计学院计科系5.符号串的方幂运算同一符号串的连接可以写成方幂形式。设x是一符号串，则定义x0=εx1=xx2=xxx3=x2x=xx2=xxx…xn=xxn-1=xx…xn个例如：x=abc则x2=abcabcx3=abcabcabc6.符号串集合的幂运算有符号串集合A，定义A0={ε},A1=A,A2=AA,A3=AAA,……An＝An-1A=AAn-1，n0例如：A={a,bc}则A2=AA={aa,abc,bca,bcbc}A3=A2A={aaa,abca,bcaa,aabc,abcbc,bcabc,bcbca,bcbcbc}2010年9月湖北大学数计学院计科系6.符号串集合的闭包运算设A是符号串集合，定义A＋＝A1∪A2∪A3∪……∪An∪……称为集合A的正闭包。A*＝A0∪A＋称为集合A的自反闭包。显然有A+=AA*=A*A例：A={x,y}A+＝？A*＝？{x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}A1A2A3{ε,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}A0A1A2A32010年9月湖北大学数计学院计科系★为什么对符号、符号串、符号串集合以及它们的运算感兴趣？若A为某语言的基本字符集A＝{a,b,……z,0,1,……,9,+,－,×,/,(,),=……}B为单词集B={begin,end,if,then,else,for,……,标识符,常量,……}则BA*。语言的句子是定义在B上的符号串。若令C为句子集合，则CB*,程序C2010年9月湖北大学数计学院计科系2.2文法及其分类★文法的非形式讨论1.什么是文法：文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称为“语法”）。例：有一句子：“我是大学生”。这是一个在语法、语义上都正确定句子，该句子的结构（称为语法结构）是由它的语法决定的。在本例中它为“主谓结构”。2010年9月湖北大学数计学院计科系2.语法规则：我们通过建立一组规则，来描述句子的语法结构。规定用“::=”表示“由……组成”或“定义为……”。句子::=主语谓语主语::=代词|名词代词::=你|我|他名词::=王民|大学生|工人|英语谓语::=动词直接宾语动词::=是|学习直接宾语::=代词|名词2010年9月湖北大学数计学院计科系3.由规则推导句子：有了一组规则之后，可以按照一定的方式用它们去推导或产生句子。推导方法：从一个要识别的符号开始推导，即用相应规则的右部来替代规则的左部，每次仅用一条规则去进行推导。句子=主语谓语主语谓语=代词谓语…………这种推导一直进行下去，直到所有带的符号都由终结符号替代为止。2010年9月湖北大学数计学院计科系句子=主语谓语=代词谓语=我谓语=我动词直接宾语=我是直接宾语=我是名词=我是大学生句子::=主语谓语主语::=代词|名词代词::=你|我|他名词::=王民|大学生|工人|英语谓语::=动词直接宾语动词::=是|学习直接宾语::=代词|名词推导方法：从一个要识别的符号开始推导，即用相应规则的右部来替代规则的左部，每次仅用一条规则去进行推导。2010年9月湖北大学数计学院计科系例：有一英语句子：Thebigelephantatethepeanut.句子::=主语谓语主语::=冠词形容词名词冠词::=the形容词::=big名词::=elephant谓语::=动词宾语动词::=ate宾语::=冠词名词名词::=peanut2010年9月湖北大学数计学院计科系句子=主语谓语=冠词形容词名词谓语=the形容词名词谓语=thebig名词谓语=thebigelephant谓语=thebigelephant动词宾语=thebigelephantate宾语=thebigelephantate冠词名词=thebigelephantatethe名词=thebigelephantatethepeanut句子::=主语谓语主语::=冠词形容词名词冠词::=the形容词::=big名词::=elephant|peanut谓语::=动词宾语动词::=ate宾语::=冠词名词2010年9月湖北大学数计学院计科系上述推导可写成句子=thebigelephantatethepeanut+说明：(1)有若干语法成分同时存在时，我们总是从最左的语法成分进行推导，这称之为最左推导，类似的有最右推导（一般推导）。(2)从一组规则可推出不同的句子，如以上规则还可推出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子，它们在语法上都正确，但在语义上都不正确。所谓文法是在形式上对句子结构的定义与描述，而未涉及语义问题。2010年9月湖北大学数计学院计科系产生式的定义设VN、VT分别是非空有限的非终结符号集和终结符号集，V=VN∪VT,VN∩VT=Φ。一个产生式是一个有序偶对（α,β）,其中α∈V+,β∈V*，通常表示为α→β或α::=β。称α为产生式的左部，称β为产生式的右部。产生式又称为重写规则，它意味着能将一个符号串用另一个符号串替换。2010年9月湖北大学数计学院计科系文法G=（VN，VT，P，S）VN：非终结符号集VT：终结符号集P：产生式或规则的集合S：开始符号（识别符号）S∈VN文法的定义规则：U::xU∈VN,x∈V*如果产生式集中的产生式有共同的左部，如α::=β，α::=γ则可将其简写成α::=β|γ2010年9月湖北大学数计学院计科系P={Z→无符号整数；无符号整数→数字串；数字串→数字串数字；数字串→数字；数字→0；数字→1；…………数字→9；}例：无符号整数的文法：G[无符号整数]=（VN，VT，P，E）VN＝{无符号整数,数字串,数字,E}VT={0,1,2,3,……9}2010年9月湖北大学数计学院计科系文法和语言分类Chomsky将文法分为四类：0型、1型、2型、3型这几类文法的差别在于对产生式施加不同的限制。0型：P：α::=β其中α∈(VN∪VT)＋，β∈(VN∪VT)*0型语言：L0这种语言可以用图灵机(Turing)接受.0型文法称为短语结构文法。规则的左部和右部都可以是符号串，一个短语可以产生另一个短语。2010年9月湖北大学数计学院计科系1型：P：γ1Aγ2::=γ1δγ2其中γ1,γ2∈(VN∪VT)*,A∈VN,δ∈(VN∪VT)+1型语言：L1这种语言可以由一种线性界限自动机接受.称为上下文有关文法或上下文敏感文法。也即只有在γ1,γ2这样的上下文中才能把A改写为δ。2010年9月湖北大学数计学院计科系2型：P：A::=δ其中A∈VN，δ∈(VN∪VT)+2型语言：L2这种语言可以由下推自动机接受.称为上下文无关文法。也即把A改写为δ时，不必考虑上下文。注意：2型文法与BNF表示相等价。2010年9月湖北大学数计学院计科系（左线性）P：A::=a或A::=Ba其中A、B∈VNa∈VT3型语言：L3又称正则语言、正则集合这种语言可以由有穷自动机接受.3型文法称为正则文法。它是对2型文法进行进一步限制。（右线性）P：A::=a或A::=aB其中A、B∈VNa∈VT3型文法：2010年9月湖北大学数计学院计科系根据上述分析，L0L1L2L30型文法可以产生L0、L1、L2、L3，但2型文法只能产生L2，不能产生L1。从0型文法到3型文法，各文法描述语言的能力依次减弱。2010年9月湖北大学数计学院计科系2.3语言和语法树★和推导有关的内容直接推导设文法G＝(VN,VT,P,S)(α,β)∈P，γ,δ∈(VN∪VT)*则称符号串γβδ为符号串γαδ应用产生式α::=β所得到的直接推导，记为γαδ=γβδ特别有，当γ＝δ＝ε时，有α=β即每个产生式得右部都是它左部的直接推导。2010年9月湖北大学数计学院计科系无符号整数数字串数字串数字数字数字1数字10(6)====(1)==(3)(5)====(2)当符号串已没有非终结符号时，推导就必须终止。因为终结符不可能出现在规则左部，所以将在规则左部出现的符号称为非终结符号。例如：G[无符号整数](1)无符号整数→数字串；(2)数字串→数字串数字(3)数字串→数字(4)数字→0;(5)数字→1;…………(13)数字→9;2010年9月湖北大学数计学院计科系推导文法G，U0,U1,U2,……，Un∈V+ifv=U0U1U2……Un＝u则vu＋==G==G==G==G==G例：无符号整数==数字串==数字串数字==数字数字==1数字==10即无符号整数10＋==G2010年9月湖北大学数计学院计科系多步推导文法G，v，w∈V+ifvw,或v=w，则vw*==G＋==G规范推导有xUy==xuy,ify∈Vt*,则此推导为规范的，记为xUy==xuy|直观意义：规范推导＝最右推导最右推导：若符号串中有两个以上的非终结符时，先推右边的。最左推导：若符号串中有两个以上的非终结符时，先推左边的。+若有v=U0==U1==U2==……==Un=w,则v==w。2010年9月湖北大学数计学院计科系句型、句子和语言文法G[Z]所产生的所有句子的集合形式语言理论可以证明以下两点：（1）G→L（G）；（2）L(G)→G1，G2，……，Gn；已知文法，求语言，通过推导；已知语言，构造文法，无形式化方法，更多是凭经验。文法G[Z]（1）句型：x是句型Zx,且x∈V*；（2）句