第二章 形式语言理论

1、第二章第二章 形式语言概论形式语言概论n语言成分语言成分n语言和文法语言和文法n文法的分类文法的分类n语言和语法语言和语法n文法和语言的一些特性文法和语言的一些特性n分析方法简介分析方法简介2.1 语言成分语言成分 对程序设计语言的描述是从对程序设计语言的描述是从语法、语义和语用语法、语义和语用三个因素来考虑。三个因素来考虑。语法：语法：是对语言结构的定义。是对语言结构的定义。语义：语义：是描述了语言的含义。是描述了语言的含义。语用：语用：则是从使用的角度去描述语言。则是从使用的角度去描述语言。例例1： 写出赋值语句写出赋值语句 s2*3.1416*r*(r+h)的非的非形式化的描述。形式化的

2、描述。语法：赋值语句由一个变量，后随一个赋值号语法：赋值语句由一个变量，后随一个赋值号“”，其后面再跟一个表达式构成；，其后面再跟一个表达式构成；语义：首先计算语句右部表达式的值，然后把所得语义：首先计算语句右部表达式的值，然后把所得结果送给左部变量中；结果送给左部变量中；语用：赋值语句可用来计算和保存表达式的值。语用：赋值语句可用来计算和保存表达式的值。 用一组用一组数学符号数学符号和和规则规则来描述语言的方式称为来描述语言的方式称为形形式描述式描述，而把所用的数学符号和规则称为，而把所用的数学符号和规则称为形式语言形式语言。n 形式语言：只是从语法上研究语言。它是抽象的形式语言：只是从语法

3、上研究语言。它是抽象的数学系统，用于模拟程序设计语言的语法，或者是数学系统，用于模拟程序设计语言的语法，或者是并不很成功地模拟自然语言（如英语的语法）。并不很成功地模拟自然语言（如英语的语法）。n 形式语言理论是编译理论的重要基础，它主要研形式语言理论是编译理论的重要基础，它主要研究组成究组成符号语言的符号串的集合及它们的表示法、符号语言的符号串的集合及它们的表示法、结构与特性。结构与特性。形式语言形式语言字母表和符号字母表和符号n字母表字母表: :元素的非空有穷集合，记为元素的非空有穷集合，记为。 例如：例如：=0=01 1 1=1=a ab,cb,c n字母表中至少包含一个元素。字母表中至

4、少包含一个元素。n字母表中的元素，可以是字母、数字或其他符号。字母表中的元素，可以是字母、数字或其他符号。n不同的语言有不同的字母表。不同的语言有不同的字母表。符号符号: :字母表中的元素称为符号或字符。字母表中的元素称为符号或字符。 由字母表中的符号组成的任何有穷序列。由字母表中的符号组成的任何有穷序列。 例如：例如：0,00,100,00,10是字母表是字母表=0=011上的符号串上的符号串 a,ab,aacaa,ab,aaca是是1=1=a ab,cb,c 上的符号串上的符号串n符号串中的符号是有序的，顺序不同符号串中的符号是有序的，顺序不同, ,意义不同。意义不同。 例如例如: : a

5、bab和和baba不同不同n不含任何符号的符号串称为不含任何符号的符号串称为空串空串，用，用表示。表示。n符号串长度符号串长度: : 符号串中含有符号的个数。符号串中含有符号的个数。 例如例如: |: |abcabc|=3|=3| |=0 | |=0 符号串及其运算符号串及其运算1.1.符号串的连接符号串的连接 设设x x、y y是符号串是符号串, ,它们的连接是把它们的连接是把y y的符号写的符号写在在 x x的符号之后得到的符号串的符号之后得到的符号串xyxy。 例如：例如： x=STx=ST，y=y=abuabu ，则，则 xyxy= =STabuSTabu 显然显然xx = = xx=

6、x=x2.2.符号串的方幂符号串的方幂 把符号串把符号串a a自身连接自身连接n n次得到的符号串次得到的符号串a an n = = aaaaaaaa。例如：例如： a a1 1=a a=a a2 2= =aaaa a a0 0=3.3.符号串集合的乘积符号串集合的乘积 若集合若集合A A中所有元素都是某字母表中所有元素都是某字母表 上的符号上的符号串，则称串，则称A A为字母表为字母表 上的符号串集合。上的符号串集合。n符号串集合符号串集合A A和和B B的乘积定义为的乘积定义为: : AB = AB = xy|xAxy|xA且且yByB ，即，即ABAB是由是由A A中的串中的串x x和和

7、B B中的串中的串y y连接而成的串连接而成的串xyxy组成的集合。组成的集合。 例如：集合例如：集合A = A = ab,cdeab,cde B = B = 0,10,1 则则 AB = AB = ab0,ab1,cde0,cde1ab0,ab1,cde0,cde1 显然显然 AA = = AA = A = A 注意注意:并不等于空集合并不等于空集合 4.4.符号串集合的方幂符号串集合的方幂 设设A A是符号串的集合，则称是符号串的集合，则称A An n为符号串集为符号串集A A的方的方幂，其中幂，其中n n是非负整数。是非负整数。A A0 0 = = A A1 1 = A = A A A2

8、 2 = A A= A AA An n = AA. = AA.A(nA(n个个) ) 例如：例如： X= abc X0 ，X1 abc ，X2 abcabc5.5.符号串集合的正闭包符号串集合的正闭包 + + = = 1 12 23 3称为称为的正闭包。的正闭包。 + + 表示表示 上的上的除除外的所有有穷长串的集合。外的所有有穷长串的集合。例如：例如：设A= a, b ，则： A+= a, b, aa, ab, ba, bb, aaa, aab, 6.6.符号串集合的自反闭包符号串集合的自反闭包* *=0 01 12 23 3称为称为的自反闭包。的自反闭包。 * *表示表示上所有有穷长的串的

9、集合。上所有有穷长的串的集合。 例如：设有字母表例如：设有字母表=0=0，11，则，则 * *=,0,1,00,01,10,11,000,=,0,1,00,01,10,11,000, n自反闭包与正闭包的关系自反闭包与正闭包的关系 * * = = 0 0+ + + + = = * * = = * *例例2：已知：字母表已知：字母表y3=yyy=acacacA2=AA=adad，adc，cad，ccB0=A+= A1A2A3.A*= A0 A1A2A3.2.2 文法和语言文法和语言1 1. .文法的定义文法的定义 是定义或描述语言的语法结构的一组形式规则。是定义或描述语言的语法结构的一组形式规则

10、。n文法文法G G（GrammarGrammar）定义为四元组）定义为四元组（V VN N，V VT T，P P，S S） V VN N(Nonternimal(Nonternimal) )：非终结符集。：非终结符集。 V VT T(Terminal(Terminal) )：终结符集。：终结符集。 P(ProductionP(Production) )：产生式（规则）集合。：产生式（规则）集合。 S S：开始符号或识别符号。：开始符号或识别符号。是出现在规则左部能派生出符号或符是出现在规则左部能派生出符号或符号串的那些符号，即每个非终结符号号串的那些符号，即每个非终结符号表示一定符号串的集合，

11、用表示一定符号串的集合，用大写字母大写字母表示表示或用尖括号把非终结符号括起来。或用尖括号把非终结符号括起来。是组成语言的基本符是组成语言的基本符号，是一个语言的不号，是一个语言的不可再分的基本符号，可再分的基本符号，通常用通常用小写字母小写字母表示。表示。是一个非终结符，且是一个非终结符，且至少要在一条产生式至少要在一条产生式的左部出现。的左部出现。P P中产生式（重写规则）形如：中产生式（重写规则）形如： A|A| 其中其中AVAVN N且至少含一个非终结符，且至少含一个非终结符，,V,V* *。nV VN N,V,VT T和和P P是非空有穷集。是非空有穷集。nV VN NVVT T=。

12、nV=VV=VN NVVT T，V V称为文法称为文法G G的字母表。的字母表。例如：文法例如：文法 G=(VN，VT，P，S ) VN=A VT=0，1 P: A 0 | 1 | A0 | A1 S=A2. 2. 推导和直接推导推导和直接推导 是文法是文法G G的产生式，若有的产生式，若有v v，w w满足：满足： v=v=,w,w= =, , 其中其中,V,V* *则称则称v v直接推导直接推导出出w w，或，或w w直接归约直接归约到到v v，记作记作v vw w。n 直接推导：直接推导：用产生式的右部替换产生式的左部的用产生式的右部替换产生式的左部的过程。过程。n 直接归约：直接归约：

13、用产生式的左部替换产生式的右部的用产生式的左部替换产生式的右部的过程。过程。n直接推导序列：直接推导序列： 或或 + + 若存在若存在v=uv=u0 0 u u1 1 . . u un n=w=w, (n0), (n0) 则称则称v v w w，v v推导推导出出w w，或，或w w归约归约到到v v（至少有（至少有1 1步步推导），这个直接推导序列的长度为推导），这个直接推导序列的长度为n n。n广义推导：广义推导： 或或 * * 若有若有v w v w 或或 v=wv=w， 则记为则记为v wv w，v v广义推导广义推导出出w w，w w广义规约广义规约到到v v（可（可以包含以包含0

14、0步推导）。步推导）。 + * + + *三种推导的比较三种推导的比较n直接推导（直接推导（）的长度为）的长度为1 1。n直接推导序列（直接推导序列（ + +）的长度）的长度n1n1。n广义推导（广义推导（ * *）的长度）的长度0 0。推导和规则的区别推导和规则的区别n 形式上的区别：形式上的区别：推导用推导用“”，规则用规则用“”。n 对文法对文法G G中任何规则中任何规则A A，我们有，我们有A A，即，即推导推导的依据是规则的依据是规则。2.3 文法的分类文法的分类 对文法中的规则施加不同限制，将文法和语言对文法中的规则施加不同限制，将文法和语言分为四大类：分为四大类：v0 0型文法（

15、型文法（PSGPSG）：）： 0 0型语言或短语结构语言。型语言或短语结构语言。v1 1型文法（型文法（CSGCSG）：）：1 1型语言或上下文有关语言。型语言或上下文有关语言。v2 2型文法（型文法（CFGCFG）：2 2型语言或上下文无关语言。型语言或上下文无关语言。v3 3型文法（型文法（RGRG）：3 3型语言或正则（正规）语言。型语言或正则（正规）语言。 如果对于文法如果对于文法G G，P P中每个规则具有下列形式：中每个规则具有下列形式： 其中其中VV+ + ，VV* *，则该文法，则该文法G G为为0 0型文法型文法。相应。相应的语言称为的语言称为0 0型语言型语言。例如：文法例

16、如：文法G=(VG=(VN N,V,VT T, P, S), P, S)，其中，其中V VN N=A,B,S V=A,B,S VT T=0,1=0,1 P= S0AB P= S0AB，1B01B0，BSA|01BSA|01，A1SB1A1SB1，A0A0S0B S0B 描述的描述的 0 0 型语言为型语言为 L L0 0(GS)= (GS)= 1.01.0型文法型文法2.1.1型文法型文法( (上下文有关上下文有关) ) 若文法若文法G=(VG=(VN N,V,VT T, P, S), P, S)中的每一条规则的形式为：中的每一条规则的形式为： AA 其中其中A VN N , , (VN NV

17、T T)* , (VN NVT T)+，则该文法则该文法G G为为1 1型文法型文法。相应的语言称为。相应的语言称为1 1型语言型语言。例如：文法例如：文法G=(VG=(VN N,V,VT T, P, S), P, S)，其中，其中V VN N=B,S V=B,S VT T=a,b,ca,b,c P=P= Sabc|aSBcSabc|aSBc , , bBbbbBbb , , cBBccBBc 描述的描述的1 1型语言为型语言为L L1 1(GS)=(GS)=a an nb bn nc cn n | n | n 113.2.2型文法型文法( (上下文无关上下文无关) ) 若文法若文法G=(VG

18、=(VN N,V,VT T, P, S), P, S)中的每一条规则的形式为：中的每一条规则的形式为： A A 其中其中A VN N , (VN NVT T)* , 则该文法则该文法G G为为2 2型文法型文法。相。相应的语言称为应的语言称为2 2型语言型语言。例如：文法例如：文法G=(VG=(VN N,V,VT T, P, S), P, S)，其中，其中V VN N=A,B,S V=A,B,S VT T=a,ba,b P=P=SaB|bASaB|bA, , Aa|aS|bAAAa|aS|bAA，Bb|bS|aBBBb|bS|aBB 描述的描述的2 2型语言为型语言为L L2 2(GS)=(G

19、S)=x|xx|x a,ba,b + + 且且x x中中a a和和b b的的个数相同个数相同 4.3.3型文法型文法( (右线性文法和正规文法右线性文法和正规文法) ) 若文法若文法G=(VG=(VN N,V,VT T, P, S), P, S)中的每一条规则的形式为：中的每一条规则的形式为： A Aa a或或 A AaBaB其中其中A，B VN N , a VT T* , 则该文法则该文法G G为为3 3型文法型文法。相应。相应的语言称为的语言称为3 3型语言型语言。例如：例如：定义标识符，定义标识符，用用I I代表标识符代表标识符; l; l代表任意一个字母代表任意一个字母; d; d代表

20、任意一个数字代表任意一个数字; ; 则定义标识符的文法为：则定义标识符的文法为： P: I l | P: I l | lIlI | | dIdI文法类别文法类别产生式形式产生式形式产生的语言产生的语言说明说明0 0型文法型文法( (短语文法短语文法) )VV+ + , ,且至少含一且至少含一个非终结符，个非终结符，VV* *0 0型语言型语言对产生式基对产生式基本无限制本无限制1 1型文法型文法( (上下文有关文法上下文有关文法) )，| | |=r=r1 1A Ar r2 2，=r=r1 1b br r2 2AVAVN N, , ,V,V* * bVbV+ + 1 1型语言（上下型语言（上下

21、文有关语言）文有关语言）将将A A替换成替换成b b时，必须考时，必须考虑虑A A的上下的上下文文2 2型文法型文法( (上下文无关文法上下文无关文法) )AA，AVAVN N ， VV* *2 2型语言（上下型语言（上下文无关语言）文无关语言）无需考虑无需考虑A A在上下文中在上下文中的出现情况的出现情况3 3型文法型文法( (右线性文法右线性文法) )AaBAaB 或或 AaAa，A,BVA,BVN N ，aVaVT T* *3 3型语言型语言产生式全部产生式全部是规定形式是规定形式4种文法的比较种文法的比较aaV VT T，正规文法，正规文法例例3：试分析书中：试分析书中P22的例的例2

22、.6、2.7、2.8、2.9、2.10的文法。的文法。n如何判断如何判断4种文法种文法 1 1型文法：型文法：|1|1，规则左部至少有一个非，规则左部至少有一个非终结符；终结符； 2 2型文法：规则左部是单个非终结符；型文法：规则左部是单个非终结符； 3 3型文法：看格式。型文法：看格式。练习：练习：1.设有文法设有文法GA: AyB，BxB|x，写出该文法，写出该文法的完整形式及推导。的完整形式及推导。2.设有文法设有文法GA1: S A B，A a A | a，B b B | b，写出该文法的完整形式及推导。，写出该文法的完整形式及推导。2.4语言和语法语言和语法1.1.句型、句子和语言句

23、型、句子和语言 设有文法设有文法GSGS，若符号串，若符号串是从开始符推导出来是从开始符推导出来的的, ,即即 S S =* * ，且，且VV* *，则称，则称是文法是文法G G的的句型句型。若若仅由终结符组成仅由终结符组成, ,即即 S S =* * ，且，且VVT T* *，则，则称称是文法是文法G G的的句子句子。 所有的句子一定是句型，句型不一定是句子。所有的句子一定是句型，句型不一定是句子。例如：文法例如：文法GS： S0S1， S01 S 0S1 00S11 000S111 00001111 句型：句型：S，0S1，00S11，000S111，00001111 句子：句子：0000

24、1111语言：语言：由文法由文法G G生成的语言记为生成的语言记为L(G),L(G),它是文法它是文法G G的一的一切句子的集合切句子的集合, ,即即 L(G)=L(G)=x|Sx|S =+ + x x，且，且 xVxVT T* * 例如：文法例如：文法G G： S0S1S0S1， S01S01 S S0S1 0S1 00S11 00S11 0 03 3S1S13 3 0 0n-1n-1S1S1n-1n-1 0 0n n1 1n n L(G)=0 L(G)=0n n1 1n n|n1|n1 文法文法G G生成的每个终结符号串都在生成的每个终结符号串都在L(G)L(G)中中，L(G)L(G)中的

25、每个串确实能被中的每个串确实能被G G生成生成。文法一旦确定，语言也。文法一旦确定，语言也就唯一，语言可由不同的文法表示。就唯一，语言可由不同的文法表示。2.2.语法树语法树 例如：例如：They are students and They are students and teachers of the Physics teachers of the Physics Department.Department.句子句子主语主语系词系词表语表语代词代词Theyare名词名词连接词连接词名词名词定语定语前置词前置词冠词冠词名词名词名词名词studentsandteachersofthePhysi

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

27、能构的任何句型都能构造与之关联的语法树。造与之关联的语法树。语法树的相关概念语法树的相关概念n 结点：每个树的结点对应于一个符号。结点的名结点：每个树的结点对应于一个符号。结点的名字就是该符号。字就是该符号。n 边：两个结点之间的连线。边：两个结点之间的连线。n 根结点：没有边进入的结点。根结点：没有边进入的结点。n 分支：某个结点向下射出的边和其结点称为分支。分支：某个结点向下射出的边和其结点称为分支。n 末端结点：没有向下射出的边的结点成为末端结末端结点：没有向下射出的边的结点成为末端结点。在相对于句型的语法树中，末端结点可能是非点。在相对于句型的语法树中，末端结点可能是非终结符号。终结符

28、号。语法树的特征语法树的特征 给定文法给定文法G=(VG=(VN N,V,VT T,P,S),P,S)，对于，对于G G的任何句型都能构造的任何句型都能构造与之关联的语法树。这棵树具有下列特征：与之关联的语法树。这棵树具有下列特征：n 根结点的标记是根结点的标记是开始符号开始符号S S；n 每个结点的标记都是每个结点的标记都是V V中的一个符号；中的一个符号；n 若一棵子树的根结点为若一棵子树的根结点为A A，且其所有直接子孙的标记，且其所有直接子孙的标记从左向右的排列次序为从左向右的排列次序为A A1 1A A2 2A AR R，那么，那么 A AA A1 1A A2 2.A.AR R一一定

29、是定是P P中的一条规则；中的一条规则；n 若一标记为若一标记为A A的结点至少有一个除它以外的子孙，则的结点至少有一个除它以外的子孙，则AVAVN N。构造语法树构造语法树方法：方法：把开始符号做把开始符号做为根结点，对每一步为根结点，对每一步直接推导画一个分支，直接推导画一个分支，分支的名字是所用产分支的名字是所用产生式右部的符号（按生式右部的符号（按左右顺序依次出现），左右顺序依次出现），分支的个数是产生式分支的个数是产生式右部符号串的长度。右部符号串的长度。以此往下，直到再无以此往下，直到再无分支可画结束。分支可画结束。例如：文法例如：文法GS:GS: SAB, SAB, BcBdBc

30、Bd, , AabAab, , BcdBcd符号串符号串abccddabccdd的的推导过程如下：推导过程如下：S SA AB BAcAcB Bd dA AccddccddabccddabccddSBBdbaAcdcS（1）SBA（2）SBBdAc（3）SBBdbaAcdc（5）SBBdAcdc（4）SABAcBdAccddabccdd例例4：已知：已知文法文法G G：EE+T|TEE+T|T，TTTTF|FF|F，FF（E E）|i|i 求句型求句型T+TT+TF F的推导过程与语法树。的推导过程与语法树。EET+TFTE=E+T =T+T=T+TFEET+TFTE=E+T =E+TF =T

31、+TF从语法树中看不出句型中的符号被替代的顺序。从语法树中看不出句型中的符号被替代的顺序。2.5 文法和语言的一些特性文法和语言的一些特性n 无用非终结符：无用非终结符：某个非终结符不出现在文法的任何一个句型中，并且不能从它推出终结符号串。含有该非终结符的规则即不可终止。n 不可达文法符号：不可达文法符号：如果一个非终结符（开始符号除外）不出现在该文法的任何其他的产生式的右部。该非终结符为不可达文法符号，含有该非终结符的规则即不可达规则。n 有害规则：有害规则：UU ，无用且引起文法的二义。n 可空非终结符：可空非终结符： 2型文法允许以下产生式 S，该产生式称为空产生式，S称为可空非终结符。

32、在消除左递归方法中用到空产生式。 例如：文法例如：文法GS： （1）SBe （2） BAf （3） AAe （4） Ae （5） CCf （6） Df 多余规则为：（多余规则为：（5）不可终止）不可终止 （6）不可到达）不可到达最左推导、最右推导和规范推导最左推导、最右推导和规范推导是指对于一个推导序列中的每一步直接是指对于一个推导序列中的每一步直接推导推导 =，都对，都对 中的中的最左最左非终结符进行替换。非终结符进行替换。是指对于一个推导序列中的每一步直接是指对于一个推导序列中的每一步直接推导推导 =，都对，都对 中的中的最右最右非终结符进行替换。非终结符进行替换。n 最右推导也称为最右推

33、导也称为规范推导规范推导，用规范推导推导出的句，用规范推导推导出的句型称为型称为规范句型规范句型。例例5：已知：已知文法文法GSGS：SABSAB，AA0|1BAA0|1B，B0|S1B0|S1 求求句子句子101001的最右、最左推导。的最右、最左推导。S右右=A =AS1=AAB1=AA01 =A1B01=A1001=1B1001=101001S左左=AB=1BB=10B=10S1=10AB1 =101BB1=1010B1=101001例如：文法例如：文法G G：EE+E|EEE+E|EE|E|（E E）|i|i 句子句子 i ii+ii+i 对应的语法树对应的语法树最左推导最左推导1 1

34、：E EE E+E+EE EE E+E+Ei iE E+E+Ei ii i+ +E Ei ii+i+i i最左推导最左推导2 2：E EE EE Ei iE Ei iE E+E+Ei ii i+ +E Ei ii+i+i iiEE+EEEiiEEEiEE+ii文法的二义性文法的二义性(Ambiguity)(Ambiguity) 如果一个文法存在某个句子对应两棵或者两棵如果一个文法存在某个句子对应两棵或者两棵以上不同的语法树，则说这个文法是以上不同的语法树，则说这个文法是二义的二义的。二义二义性文法存在某个句子性文法存在某个句子, ,它它有两个不同的最左（右）有两个不同的最左（右）推导。推导。

35、二义性的文法将给编译程序的执行带来问题。二义性的文法将给编译程序的执行带来问题。当编译程序对二义性文法生成的句子结构进行语法当编译程序对二义性文法生成的句子结构进行语法分析时，就会产生两种甚至更多种不同的理解。语分析时，就会产生两种甚至更多种不同的理解。语法结构上的不确定性，必将导致语义处理上的不确法结构上的不确定性，必将导致语义处理上的不确定性。因此，希望描述语言的文法是无二义性的。定性。因此，希望描述语言的文法是无二义性的。消除文法的二义性消除文法的二义性n 方法一：方法一：不改变文法中原有的语法规则，仅加不改变文法中原有的语法规则，仅加进一些语法的非形式规定。进一些语法的非形式规定。n 方法二：方法二：构造一个等价的无二义性的文法，即构造一个等价的无二义性的文法，即把排除二义性的规则合并到原有文法中，改写原把排除二义性的规则合并到原有文法中，改写原有的文法。有的文法。2.6 分析方法简介分析方法简介