第二章 形式语言理论

第二章形式语言概论语言成分语言和文法文法的分类语言和语法文法和语言的一些特性分析方法简介2.1语言成分

对程序设计语言的描述是从语法、语义和语用三个因素来考虑。语法：是对语言结构的定义。语义：是描述了语言的含义。语用：则是从使用的角度去描述语言。例1：写出赋值语句s＝2*3.1416*r*(r+h)的非形式化的描述。语法：赋值语句由一个变量，后随一个赋值号“＝”，其后面再跟一个表达式构成；语义：首先计算语句右部表达式的值，然后把所得结果送给左部变量中；语用：赋值语句可用来计算和保存表达式的值。

用一组数学符号和规则来描述语言的方式称为形式描述，而把所用的数学符号和规则称为形式语言。形式语言：只是从语法上研究语言。它是抽象的数学系统，用于模拟程序设计语言的语法，或者是并不很成功地模拟自然语言（如英语的语法）。形式语言理论是编译理论的重要基础，它主要研究组成符号语言的符号串的集合及它们的表示法、结构与特性。形式语言字母表和符号字母表:元素的非空有穷集合，记为∑。

例如：∑={0‚1}∑1={a‚b,c}字母表中至少包含一个元素。字母表中的元素，可以是字母、数字或其他符号。不同的语言有不同的字母表。符号:字母表中的元素称为符号或字符。

由字母表中的符号组成的任何有穷序列。

例如：0,00,10是字母表∑={0‚1}上的符号串

a,ab,aaca是∑1={a‚b,c}上的符号串符号串中的符号是有序的，顺序不同,意义不同。例如:ab和ba不同不含任何符号的符号串称为空串，用ε表示。符号串长度:符号串中含有符号的个数。

例如:|abc|=3 |ε|=0符号串及其运算1.符号串的连接设x、y是符号串,它们的连接是把y的符号写在x的符号之后得到的符号串xy。

例如：x=ST，y=abu

，则xy=STabu

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

aa…aa。例如：a1=aa2=aa

a0=ε3.符号串集合的乘积若集合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注意:{ε}并不等于空集合{}4.符号串集合的方幂

设A是符号串的集合，则称An为符号串集A的方幂，其中n是非负整数。A0={ε}A1=AA2=AAAn=AA......A(n个)

例如：X={abc}X0

＝{

}，X1

＝{abc}，X2

＝{abcabc}5.符号串集合的正闭包

Σ+=Σ1∪Σ2∪Σ3∪…称为Σ的正闭包。

+

表示上的除ε外的所有有穷长串的集合。例如：设A={a,b}，则：

A+={a,b,aa,ab,ba,bb,aaa,aab,…}6.符号串集合的自反闭包

Σ*=Σ0∪Σ1∪Σ2∪Σ3∪…称为Σ的自反闭包。

Σ*表示Σ上所有有穷长的串的集合。

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

Σ*={ε,0,1,00,01,10,11,000,…}自反闭包与正闭包的关系

Σ*=Σ0∪Σ+Σ+=ΣΣ*=Σ*Σ例2：已知：字母表={a，b，c，d}，符号串x=ad，y=ac，集合A={ad，c}，B={d}

求xy，AB，x0，y3，A2，B0，A+，A*xy=adacAB={add，cd}x0=εy3=yyy=acacacA2=AA={adad，adc，cad，cc}B0={ε}A+=A1∪A2∪A3∪…..A*=A0∪

A1∪A2∪A3∪…..2.2文法和语言1.文法的定义是定义或描述语言的语法结构的一组形式规则。文法G（Grammar）定义为四元组（VN，VT，P，S）

VN(Nonternimal)：非终结符集。

VT(Terminal)：终结符集。

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

S：开始符号或识别符号。是出现在规则左部能派生出符号或符号串的那些符号，即每个非终结符号表示一定符号串的集合，用大写字母表示或用尖括号把非终结符号括起来。是组成语言的基本符号，是一个语言的不可再分的基本符号，通常用小写字母表示。是一个非终结符，且至少要在一条产生式的左部出现。P中产生式（重写规则）形如：A→α|β

其中A∈VN且至少含一个非终结符，α,β∈V*。VN,VT和P是非空有穷集。VN∩VT=φ。V=VN∪VT，V称为文法G的字母表。例如：文法G=(VN，VT，P，S)VN={A}VT={0，1}P:A→0|1|A0|A1S=A2.推导和直接推导

α→β是文法G的产生式，若有v，w满足：

v=γαδ,w=γβδ,其中γ,δ∈V*则称v直接推导出w，或w直接归约到v，记作vw。直接推导：用产生式的右部替换产生式的左部的过程。直接归约：用产生式的左部替换产生式的右部的过程。直接推导序列：

或+

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

则称v

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

若有vw或v=w，则记为vw，v广义推导出w，w广义规约到v（可以包含0步推导）。+*

+

+*三种推导的比较直接推导（）的长度为1。直接推导序列（+）的长度n≥1。广义推导（*）的长度≥0。推导和规则的区别形式上的区别：推导用“”，规则用“”。对文法G中任何规则A，我们有A，即推导的依据是规则。2.3文法的分类

对文法中的规则施加不同限制，将文法和语言分为四大类：0型文法（PSG）：

0型语言或短语结构语言。1型文法（CSG）：1型语言或上下文有关语言。2型文法（CFG）：2型语言或上下文无关语言。3型文法（RG）：3型语言或正则（正规）语言。

如果对于文法G，P中每个规则具有下列形式：

α→β

其中α∈V+，β∈V*，则该文法G为0型文法。相应的语言称为0型语言。例如：文法G=(VN,VT,P,S)，其中VN={A,B,S}VT={0,1}P={S→0AB，1B→0，B→SA|01，A1→SB1，A0→S0B}

描述的0型语言为L0(G[S])={}1.0型文法2.1型文法(上下文有关)

若文法G=(VN,VT,P,S)中的每一条规则的形式为：

αAβαμβ

其中AVN,α,β(VN∪VT)*,μ(VN∪VT)+，则该文法G为1型文法。相应的语言称为1型语言。例如：文法G=(VN,VT,P,S)，其中VN={B,S}VT={a,b,c}

P={

S→abc|aSBc,bB→bb,cB→Bc }

描述的1型语言为L1(G[S])={anbncn|n1}3.2型文法(上下文无关)

若文法G=(VN,VT,P,S)中的每一条规则的形式为：

Aβ

其中AVN,β(VN∪VT)*,则该文法G为2型文法。相应的语言称为2型语言。例如：文法G=(VN,VT,P,S)，其中VN={A,B,S}VT={a,b}

P={S→aB|bA,A→a|aS|bAA，B→b|bS|aBB}

描述的2型语言为L2(G[S])={x|x{a,b}+

且x中a和b的个数相同}4.3型文法(右线性文法和正规文法)

若文法G=(VN,VT,P,S)中的每一条规则的形式为：

Aa或

AaB其中A，BVN,aVT*,则该文法G为3型文法。相应的语言称为3型语言。例如：定义标识符，用I代表标识符;l代表任意一个字母;d代表任意一个数字;则定义标识符的文法为：

P:I→l|lI|dI文法类别产生式形式产生的语言说明0型文法(短语文法)α→βα∈V+,且至少含一个非终结符，β∈V*0型语言对产生式基本无限制1型文法(上下文有关文法)α→β，|β|≥|α|α=r1Ar2，β=r1br2A∈VN,α,β∈V*b∈V+1型语言（上下文有关语言）将A替换成b时，必须考虑A的上下文2型文法(上下文无关文法)A→β，A∈VN

，β∈V*2型语言（上下文无关语言）无需考虑A在上下文中的出现情况3型文法(右线性文法)A→aB

或

A→a，A,B∈VN

，a∈VT*3型语言产生式全部是规定形式4种文法的比较a∈VT，正规文法例3：试分析书中P22的例2.6、2.7、2.8、2.9、2.10的文法。如何判断4种文法

1型文法：|β|≥|α|≥1，规则左部至少有一个非终结符；

2型文法：规则左部是单个非终结符；

3型文法：看格式。练习：设有文法G[A]:A→yB，B→xB|x，写出该文法的完整形式及推导。设有文法G[A1]:S→AB，A→aA|a，B→bB|b，写出该文法的完整形式及推导。2.4．语言和语法1.句型、句子和语言设有文法G[S]，若符号串α是从开始符推导出来的,即S=>*α

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

，且α∈VT*，则称α是文法G的句子。

所有的句子一定是句型，句型不一定是句子。例如：文法G[S]：S→0S1，S→01S0S100S11000S11100001111

句型：S，0S1，00S11，000S111，00001111

句子：00001111语言：由文法G生成的语言记为L(G),它是文法G的一切句子的集合,即 L(G)={x|S

=>+x，且x∈VT*}例如：文法G：S→0S1，S→01S0S100S1103S13

…0n-1S1n-1

0n1nL(G)={0n1n|n≥1}

文法G生成的每个终结符号串都在L(G)中，L(G)中的每个串确实能被G生成。文法一旦确定，语言也就唯一，语言可由不同的文法表示。2.语法树

例如：TheyarestudentsandteachersofthePhysicsDepartment.

它的结点由符号组成。根结点对应于开始符号。只有非终结符号对应的结点有子结点。并且，一个结点和它的子结点分别对应于文法中的一个产生式的左部和右部。作为识别句子的辅助工具，语法树可以表示句子的结构。直观地描述上下文无关文法的句型推导过程。给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树。语法树的相关概念

结点：每个树的结点对应于一个符号。结点的名字就是该符号。边：两个结点之间的连线。根结点：没有边进入的结点。分支：某个结点向下射出的边和其结点称为分支。末端结点：没有向下射出的边的结点成为末端结点。在相对于句型的语法树中，末端结点可能是非终结符号。语法树的特征

给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树。这棵树具有下列特征：根结点的标记是开始符号S；每个结点的标记都是V中的一个符号；若一棵子树的根结点为A，且其所有直接子孙的标记从左向右的排列次序为A1A2…AR，那么A→A1A2..AR一定是P中的一条规则；若一标记为A的结点至少有一个除它以外的子孙，则A∈VN。构造语法树方法：把开始符号做为根结点，对每一步直接推导画一个分支，分支的名字是所用产生式右部的符号（按左右顺序依次出现），分支的个数是产生式右部符号串的长度。以此往下，直到再无分支可画结束。例如：文法G[S]:S→AB,B→cBd,

A→ab,B→cd符号串abccdd的推导过程如下：SABAcBdAccddabccddSBBdbaAcdcS（1）SBA（2）SBBdAc（3）SBBdbaAcdc（5）SBBdAcdc（4）SABAcBdAccddabccdd例4：已知文法G：E→E+T|T，T→T×F|F，F→（E）|i

求句型T+T×F的推导过程与语法树。EET+TFT×E=>E+T

=>T+T=>T+T×FEET+TFT×E=>E+T=>E+T×F=>T+T×F从语法树中看不出句型中的符号被替代的顺序。2.5文法和语言的一些特性

无用非终结符：某个非终结符不出现在文法的任何一个句型中，并且不能从它推出终结符号串。含有该非终结符的规则即不可终止。不可达文法符号：如果一个非终结符（开始符号除外）不出现在该文法的任何其他的产生式的右部。该非终结符为不可达文法符号，含有该非终结符的规则即不可达规则。

有害规则：U→U，无用且引起文法的二义。可空非终结符：

2型文法允许以下产生式

S→ε，该产生式称为空产生式，S称为可空非终结符。在消除左递归方法中用到空产生式。

例如：文法G[S]：（1）S→Be

（2） B→Af

（3）A→Ae

（4）A→e

（5）C→Cf

（6）D→f

多余规则为：（5）不可终止（6）不可到达最左推导、最右推导和规范推导

最左推导：是指对于一个推导序列中的每一步直接推导α=>β，都对α中的最左非终结符进行替换。

最右推导：是指对于一个推导序列中的每一步直接推导α=>β，都对α中的最右非终结符进行替换。最右推导也称为规范推导，用规范推导推导出的句型称为规范句型。例5：已知文法G[S]：S→AB，A→A0|1B，B→0|S1

求句子101001的最右、最左推导。S右=>AB=>AS1=>AAB1=>AA01=>A1B01=>A1001=>1B1001=>101001S左=>AB=>1BB=>10B=>10S1=>10AB1=>101BB1=>1010B1=>101001例如：文法G：E→E+E|E×E|（E）|i

句子i×i+i

对应的语法树最左推导1：EE+EE×E+Ei×E+Ei×i+Ei×i+i最左推导2：EE×Ei×Ei×E+Ei×i+Ei×i+iiEE+EEE×iiEEE×iEE+ii文法的二义性(Ambiguity)

如果一个文法存在某个句子对应两棵或者两棵以上不同的语法树，则说这个文法是二义的。二义性文法存在某个句子,它有两个不同的最左（右）推导。二义性的文法将给编译程序的执行带来问题。当编译程序对二义性文法生成的句子结构进行语法分析时，就会产生两种甚至更多种不同的理解。语法结构上的不确定性，必将导致语义处