形式语言理论

形式语言理论第1页，共49页，2023年，2月20日，星期六形式语言Chomsky于1956年提出了一种用来描述语言的数学系统。人们把用一组数学符号和规则来描述语言的方式称为形式描述，而把所用的数学符号和规则称为形式语言。形式语言，只是从语法上研究语言。它是抽象的数学系统，用于模拟程序设计语言的语法，或者是并不很成功地模拟自然语言如英语的语法。形式语言理论是编译理论的重要基础，它主要研究组成符号语言的符号串的集合及它们的表示法、结构与特性。第2页，共49页，2023年，2月20日，星期六形式语言和编译理论中的最基本概念——符号串和符号串集合第3页，共49页，2023年，2月20日，星期六2.1字母表和符号串字母表定义:元素的非空有穷集合，记为∑。例：∑={0‚1}Α={a‚b,c}元素也称为符号，字母表也称符号集。程序语言的字母表由字母数字和若干专用符号组成。第4页，共49页，2023年，2月20日，星期六符号串定义:由字母表中的符号组成的任何有穷序列例：0,00,10是字母表∑={0‚1}上的符号串

a,ab,aaca是Α={a‚b,c}上的符号串在符号串中，符号是有顺序的，顺序不同,代表不同的符号串，如:ab和ba不同不含任何符号的符号串称为空串，用ε表示 注意:{ε}并不等于空集合{}符号串长度:符号串中含有符号的个数 如: |abc|=3 |ε|=0第5页，共49页，2023年，2月20日，星期六符号串的运算符号串的连接：设x、y是符号串,它们的连接是把y的符号写在x的符号之后得到的符号串xy

例如x="ST"，y="abu"，则xy="STabu"

显然εx=xε=x符号串的方幂：把符号串a自身连接n次得到的符号串an=

aa…aa例如a1=aa2=aaa0=ε第6页，共49页，2023年，2月20日，星期六符号串集合：定义:若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。符号串集合的乘积：符号串集合A和B的乘积定义为:AB={xy|x∈A且y∈B}，即AB是由A中的串x和B中的串y连接而成的串xy组成的集合。 若集合A=ab,cdeB=0,1

则AB=ab0,ab1,cde0,cde1

显然{ε}A=A{ε}=A第7页，共49页，2023年，2月20日，星期六符号串集合的方幂:设A是符号串的集合，则称Ai为符号串集A的方幂，其中i是非负整数。具体定义如下:A0={ε}A1=A,A2=AAAK=AA......A(k个)第8页，共49页，2023年，2月20日，星期六集合的闭包闭包 集合Σ的闭包Σ*定义如下：

Σ*=Σ0∪Σ1∪Σ2∪Σ3∪…

例：设有字母表Σ={0，1}

则Σ*=Σ0∪Σ1∪Σ2∪… ={ε,0,1,00,01,10,11,000,…}

即Σ*表示Σ上所有有穷长的串的集合。第9页，共49页，2023年，2月20日，星期六正闭包Σ+=Σ1∪Σ2∪Σ3∪…称为Σ的正闭包。

+

表示上的除ε外的所有有穷长串的集合自反闭包Σ*=Σ0∪Σ+ Σ+=ΣΣ*=Σ*Σ第10页，共49页，2023年，2月20日，星期六2.2文法和语言1、文法定义:文法G(Grammar)定义为四元组（VN，VT，P，S）

VN(Nonternimal)：非终结符集

VT(Terminal)：终结符集

P(Production)：产生式（规则）集合

S：开始符号或识别符号第11页，共49页，2023年，2月20日，星期六说明:V=VN∪VT，V称为文法G的字母表P中产生式形如：α→β,其中α∈V+且至少含一个非终结符，β∈V*VN,VT和P是非空有穷集VN∩VT=φS是一个非终结符，且至少要在一条产生式的左部出现非终结符代表一个语言中的语法成分，如<赋值语句>，它是构成程序的一个语法成分，这个符号本身不会在程序中出现，而终结符是组成程序的具体的符号。第12页，共49页，2023年，2月20日，星期六2.推导和规范推导： α→β是文法G的产生式，若有v，w满足： v=γαδ,w=γβδ,其中γ,δ∈V* 则称v直接推导出w,也称w直接归约到v, 记作vw直接推导就是用产生式的右部替换产生式的左部的过程直接归约就是用产生式的左部替换产生式的右部的过程第13页，共49页，2023年，2月20日，星期六2、直接推导序列：或+

若存在v=u0u1...un=w,(n>0)

则称v+w，v推导出w，或w归约到v（至少有1步推导），这个直接推导序列的长度为n。3、广义推导：或*

若有v+w或v=w，则记为v*w，v广义推导出w，w广义规约到v（可以包含0步推导）+*第14页，共49页，2023年，2月20日，星期六三种推导的比较直接推导（）的长度为1直接推导序列（+）的长度n≥1广义推导（*）的长度≥0第15页，共49页，2023年，2月20日，星期六规范推导与规范规约考虑两种特殊推导：最左推导和最右推导，即对于一个推导序列中的每一步直接推导，都是对最左（最右）非终结符进行替换。最右推导也称规范推导，它的逆过程称为最左规约，也称规范规约。

第16页，共49页，2023年，2月20日，星期六2.3文法的分类

Chomsky对文法中的规则施加不同限制，将文法和语言分为四大类：0型文法（PSG）0型语言或短语结构语言1型文法（CSG）1型语言或上下文有关语言2型文法（CFG）2型语言或上下文无关语言3型文法（RG）3型语言或正则（正规）语言第17页，共49页，2023年，2月20日，星期六如果对于某文法G，P中每个规则具有下列形式：

α→β其中α∈V+，β∈V*，则该文法G为（Chomsky）0型文法或短语结构文法。相应的语言称为0型语言或短语结构语言。如文法G，其中VN={A,B,S}VT={0,1}P={S→0AB1B→0B→SA|01A1→SB1A0→S0B}0型文法第18页，共49页，2023年，2月20日，星期六1型文法(上下文有关)

它是0型文法的特例, 对P中的任一产生式α→β，都有|β|≥|α|≥1，仅仅S→ε除外,但S不得出现在任何产生式的右部。 例文法G[S]：

S→aSBE S→aBE EB→BE aB→ab bB→bb bE→be eE→ee 1型文法产生式的一般形式是A→，,∈V*，A∈VN,

β∈V＋，它表示当A的上文为且下文为时可把A替换成，因此称1型文法为上下文有关文法。第19页，共49页，2023年，2月20日，星期六2型文法（上下文无关文法）

它是1型文法的特例，对任一产生式α→β，都有 α∈VN

，β∈(VN∪VT)*例文法G[S]： S→ABA→BS|0B→SA|12型文法产生式的一般形式是:A→，它表示不管A的上下文如何都可把A替换成，因此被称为上下文无关文法。通常程序设计语言的文法，可用2型文法来描述，因此我们重点研究2型文法。第20页，共49页，2023年，2月20日，星期六3型文法(右线性文法和正规文法)

它是2型文法的特例，任一产生式α→β的形式都为A→aB或 A→a，其中A，B∈VN，a∈VT* 在正规文法中，任一产生式α→β的形式都为A→aB或 A→a，其中A，B∈VN，a∈VT例如文法G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0在程序设计语言中，正规文法通常用来描述单词的结构。第21页，共49页，2023年，2月20日，星期六文法类别产生式形式产生的语言说明0型文法(短语文法)α→βα∈V+,且至少含一个非终结符，β∈V*0型语言对产生式基本无限制1型文法(上下文有关文法)α→β，|β|≥|α|1型语言（上下文有关语言）将A替换成时，必须考虑A的上下文2型文法(上下文无关文法)A→β，A∈VN

，β∈V*2型语言（上下文无关语言）无需考虑A在上下文中的出现情况3型文法(正规文法)A→aB或A→a，A,B∈VN，a∈VT3型语言(正规语言)产生式全部是规定的形式第22页，共49页，2023年，2月20日，星期六四种文法之间的逐级“包含”关系2型文法1型文法3型文法0型文法第23页，共49页，2023年，2月20日，星期六2.4．语言和语法1、句型和句子 设有文法G[S]，若符号串α是从开始符推导出来的,即S=>*α

，则称α是文法G的句型。若α仅由终结符组成,即S=>*α

，且α∈VT*，则称α是文法G的句子。例文法G[S]：S→0S1，S→01

因为S0S100S11000S11100001111

所以S,0S1,00S11,000S111,00001111都是G的句型,00001111是G的句子

由规范推导所得的句型称为规范句型第24页，共49页，2023年，2月20日，星期六2、语言的定义 由文法G生成的语言记为L(G),它是文法G的一切句子的集合,即 L(G)={x|S=>*x，且x∈VT*} 例文法G：S→0S1，S→01 S0S100S1103S13

…0n-1S1n-1

0n1n L(G)={0n1n|n≥1}3、文法和语言的关系： 文法G生成的每个终结符号串都在L(G)中 L(G)中的每个串确实能被G生成第25页，共49页，2023年，2月20日，星期六2.语法树1、定义：语法树是这样的一个语法结构，它的结点由符号组成。根结点对应于开始符号。只有非终结符号对应的结点有子结点。并且，一个结点和它的子结点分别对应于文法中的一个规则的左部和右部。2、引入语法树的意义：作为识别句子的辅助工具，语法树可以表示句子的结构。这一点对于其后的语义分析有非常重要的意义。第26页，共49页，2023年，2月20日，星期六3、作用:直观地描述上下文无关文法的句型推导过程。给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树第27页，共49页，2023年，2月20日，星期六语法树的相关概念结点：每个树的结点对应于一个符号。结点的名字就是该符号。边：两个结点之间的连线。根结点：没有边进入的结点。分支：某个结点向下射出的边和其结点称为分支。（父子结点，兄弟结点）子树：语法树的某个结点和它向下射出的部分末端结点：没有向下射出的边的结点成为末端结点。在相对于句型的语法树中，末端结点可能是非终结符号。第28页，共49页，2023年，2月20日，星期六语法树的特征给定文法G，G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树（推导树）。这棵树具有下列特征：1、根结点的标记是开始符号S；2、每个结点的标记都是V中的一个符号；3、若一棵子树的根结点为A，且其所有直接子孙的标记从左向右的排列次序为A1A2…AR，那么A→A1A2..AR一定是P中的一条规则；4、若一标记为A的结点至少有一个除它以外的子孙，则A∈VN5、若树的所有叶结点上的标记从左到右排列为字符串w，则w是文法G的句型；若w中仅含终结符号，则w为文法G所产生的句子。第29页，共49页，2023年，2月20日，星期六构造语法树方法：把开始符号做为根结点，对每一个直接推导画一个分支，分支的名字是直接推导中被替换的非终结符号，直到再无分支可画结束。例如：推导SABAcBdAccddabccddSBBdbaAcdc第30页，共49页，2023年，2月20日，星期六语法树的构造过程SABAcBdAccddabccddSSBASBBdAcSBBdAcdcSBBdbaAcdc（1）（2）（3）（5）（4）第31页，共49页，2023年，2月20日，星期六

例：文法G：E→E+T|T T→T×F|FF→（E）|i

句型T+T×F的推导过程与语法树EET+TFT×E=>E+TEET+TFT×E=>E+T=>E+T×F=>T+T×F=>T+T=>T+T×F从语法树中看不出句型中的符号被替代的顺序从左到右读出叶子结点得到的符号串，为文法的句型。也把该语法树称为该句型的语法树。第32页，共49页，2023年，2月20日，星期六2.5文法和语言的一些特性

1、无用非终结符：某个非终结符不出现在文法的任何一个句型中，并且不能从它推出终结符号串。含有该非终结符的规则即不可终止。2、不可达文法符号：如果一个非终结符不出现在该文法的任何其他的产生式的右部。该非终结符为不可达文法符号，含有该非终结符的规则即不可达规则3、有害规则：U→U,无用且引起文法的二义4、可空非终结符：

2型文法允许以下产生式

S→ε，该产生式称为空产生式，S称为可空非终结符。在消除左递归方法中用到空产生式。第33页，共49页，2023年，2月20日，星期六

例：文法G[S]：（1）S→Be（2）B→Ce （3）B→Af（4）A→Ae（5）A→e （6）C→Cf（7）D→f

多余规则为：（6）不可终止（7）不可到达第34页，共49页，2023年，2月20日，星期六文法G：E→E+E|E×E|（E）|i句子i×i+i对应的语法树两个不同的最左推导：推导1：E

E+EE×E+Ei×E+Ei×i+Ei×i+i推导2：EE×Ei×Ei×E+Ei×i+Ei×i+iiEE+EEE×iiEEE×iEE+ii2.5文法的二义性(Ambiguity)第35页，共49页，2023年，2月20日，星期六

如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的。二义性文法存在某个句子,它有两个不同的最左（右）推导。

第36页，共49页，2023年，2月20日，星期六为什么要避免文法产生二义性？二义性的文法将给编译程序的执行带来问题。当编译程序对二义性文法生成的句子结构进行语法分析时，就会产生两种甚至更多种不同的理解。语法结构上的不确定性，必将导致语义处理上的不确定性。因此，希望描述语言的文法是无二义性的。第37页，共49页，2023年，2月20日，星期六如何消除文法的二义性？(1)方法一：不改变文法中原有的语法规则，仅加进一些语法的非形式规定。如1：对于文法

G[E]:E→iE→E+EE→E*EE→(E)

规定运算符优先顺序和结合律，即*优先于+，+、*服从左结合。第38页，共49页，2023年，2月20日，星期六如何消除文法的二义性？(2)方法二：构造一个等价的无二义性的文法，即把排除二义性的规则合并到原有文法中，改写原有的文法。如文法

G[E]:E→iE→E+EE→E*EE→(E)

将运算符的优先顺序和结合规则加到原有文法中，则可构造无二义性的文法

G’[E]:E→T|E+TT→F|T*FF→（E）|i第39页，共49页，2023年，2月20日，星期六2.6分析方法简介对于2型文法,如何识别一个符号串是否为某文法的句型或句子，有两种分析方法：自顶向下分析法(Top-Downparsing)自底向上分析法(Bottom-Upparsing)第40页，共49页，2023年，2月20日，星期六2.6.1自顶向下的分析方法1、定义:从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。2、语法树的构造：将文法的开始符号作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。

第41页，共49页，2023年，2月20日，星期六

例文法G：S→cAd

A→ab

A→a

识别输入串w=cabd是否为该文法的句子S推导过程：cAdab=>cabdS=>cAd第42页，共49页，2023年，2月20日，星期六3、自顶向下方法的主要问题对输入串cabd自上而下构造语法树的另一过程不成功，不成功的原因是选错产生式A→a自顶向下分析的主要问题是选择产生式:假定要被代换的最左非终结符号是B，且有n条规则：B→A1|A2|…|An，那么如何确定用哪个右部去替代B？只能试探性地构造，如果选错了产生式，必须退回原来的状态，往前回退称为回溯。ScAda第43页，共49页，2023年，2月20日，星期六2.6.2确定的自顶向下的分析方法

当文法的某一个非终结符有几条产生式、而且每条产生式右部都是终结符时，应保证它们是互不相同的终结符。

第44页，共49页，2023年，2月20日，星期六2.6.3自底向上的分析方法1、定义:从输入符号串开始，在其中寻找