1、第二章 编译基础-形式语言本讲内容本讲内容n字母表、串、语言字母表、串、语言n文法的引例文法的引例n文法的形式定义（定义、分类）文法的形式定义（定义、分类）n正规文法与有穷自动机正规文法与有穷自动机n上下文无关文法上下文无关文法第一节第一节 字母表、串、语言字母表、串、语言1 字母表字母表：有穷非空字符集：有穷非空字符集 语言允许使用的语言允许使用的字符集字符集可识别符号可识别符号例：例： =a-z,A-Z,0-9,+,_,*,/,/(,),=.2 字符串：字符串：字母表中符号组成的任何字母表中符号组成的任何有穷序列有穷序列单词单词例：例：scanf,int,3.1415,x1,100,asc
2、anf,int,3.1415,x1,100,a3 字符串运算：字符串运算： A、B为字符串集合为字符串集合 x，y为字符串为字符串连接：连接： xy 称为称为x和和y的连接的连接 例：例：int x x=100积：积：AB=xy/x A,而而y B 闭包：闭包：A*=A0 A1 A2. . An 其中：其中： A0= ， Ai= = Ai-1 A A+= = A*- - A+中的每一个元素即为一个语句例： x=3.14159*r*r形式语言是一个字母表上按某种规则构成的所有串的集合。在语言中这些串称为句子。对于一个句子，存在两个过程：读-识别过程-编译的过程写-推导过程-书写源程序第二节 文法
3、的引例 句子：I am a teach.Iamateacher amateacher i第三节第三节 文法的形式定义文法的形式定义一、几个概念一、几个概念1、非终结符、非终结符语法变量语法变量2、终结符、终结符单词单词3、产生式、产生式规则规则二、文法的定义二、文法的定义文法是一个四元组，表示为：文法是一个四元组，表示为： G=（VN，VT，P，S）其中：其中： VN -非终结符集合非终结符集合 VT -终结符集合终结符集合 P-产生式集合产生式集合 S-开始符号开始符号P： VV+ + ， V V* * V=VN VT例：描述系表结构的文法，其形式描述例：描述系表结构的文法，其形式描述为为G
4、=（VN，VT，P，S）VN = VT =I，am ,a ,teacherS= amateacher P=i再给出一个描述算术表达式的文法例子再给出一个描述算术表达式的文法例子 p=EE+T|T p=EE+T|T TT TT* *F|FF|F F(E)|a F(E)|a 文法文法G G（E E）：）：G=（VN，VT，P，S）VN =E，T，FVT =+，*，（，），（，），aS= E *句型：句型：S= , , V V* * 为句型为句型例：例： I am I am *句子句子：S= w, ww, w V VT T* * w w为句子为句子例：例：Iam a teacherIam a tea
5、cher *语言语言：L=w/w w w V VT T* * , , 且且S=w例：例：I am a teacher推导的定义推导的定义若存在若存在v v ww0 0 ww1 1 . . wwn n=w(n0)=w(n0) 则记为则记为v v =+ w w，v v推导出推导出ww，或，或ww归约到归约到v v若有若有v v =+ w w，或，或v=wv=w， 则记为则记为v v =* w w例：例：GEGE： EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|aE EE+T E+T T+T T+T F+T F+T a+T a+T a+Ta+T* *F F a+Fa
6、+F* *F F a+aa+a* *F F a+aa+a* *a a句子：用符号句子：用符号a a，+ +，* *，( (和和) )构成的构成的算术表达式算术表达式EE+TTFaT*FFaaE EE+T E+T T+T T+T F+T F+T a+T a+T a+Ta+T* *F F a+Fa+F* *F F a+aa+a* *F F a+aa+a* *a a 通过对产生式施加不同的限制，通过对产生式施加不同的限制，ChomskyChomsky将文法将文法分为四种类型：分为四种类型：0 0型文法：对任一产生式型文法：对任一产生式，都有，都有 (V(VNNVVT T) )+ +， (V(VNNV
7、VT T) )* *1 1型文法：对任一产生式型文法：对任一产生式，都有，都有|， 仅仅仅仅 SS除外除外2 2型文法：对任一产生式型文法：对任一产生式AA，都有，都有AVAVNN ， (V(VNNVVT T) )* *3 3型文法：任一产生式型文法：任一产生式AA的形式都为的形式都为AaBAaB或或 AaAa，其中，其中AVAVNN ，BVBVNN ，aVaVT T文法分类：文法的类型文法的类型自然语言属于上下文有关文法例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法GSGS：SCDSCDAbbAAbbACaCACaCABaaBBaaBCbCBCbCBBbbBBbbBADaD
8、ADaD C CBDbDBDbD D DAabDAabD文法的类型文法的类型是语法分析的基础例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GSGS：SABABABS|0BS|0BSA|1SA|13 3型文法型文法GS： S0A|1B|00A|1B|0A0A|1B|0S0A|1B|0SB1B|1|01B|1|0GI：I lT lTI l lT lT lTT dT dTT l lT d d是词法分析的基础文法的类型文法的类型四种四种文法文法之间之间的的逐级逐级“包含包含”关系关系0型文法1型文法2型文法3型文法文法和语言文法和语言n0 0型文法产生的语言称为型文法产生的语言称为0
9、 0型语言型语言1 1型文法或上下文有关文法（型文法或上下文有关文法（ CSG CSG ）产生的）产生的语言称为语言称为1 1型语言或上下文有关语言（型语言或上下文有关语言（CSLCSL）2 2型文法或上下文无关文法（型文法或上下文无关文法（ CFG CFG ）产生的）产生的语言称为语言称为2 2型语言或上下文无关语言（型语言或上下文无关语言（ CF L CF L ） 3 3型文法或正则（正规）文法（型文法或正则（正规）文法（ RG RG ）产生的）产生的语言称为语言称为3 3型语言正则（正规）语言（型语言正则（正规）语言（ RL RL ） 根据形式语言理论根据形式语言理论, ,文法和识别系文
10、法和识别系统间有这样的关系统间有这样的关系 0 0型文法（短语结构文法）的型文法（短语结构文法）的能力相当于能力相当于图灵机，图灵机，可以表征任何递归可枚举集，可以表征任何递归可枚举集，而且任何而且任何0 0型语言都是递归可枚举的型语言都是递归可枚举的 1 1型文法（上下文有关文法）：产生式的型文法（上下文有关文法）：产生式的形式为形式为1 1AA2 21 12 2，即只有，即只有A A出出现在现在1 1和和2 2的上下文中时，才允许的上下文中时，才允许取代取代A A。其。其识别系统是线性界限自动机。识别系统是线性界限自动机。 2 2型文法（上下文无关文法型文法（上下文无关文法CFGCFG）：
11、）：产生式的形式为产生式的形式为AA，取代取代A A时时与与A A的上下文无关。的上下文无关。其识别系统是其识别系统是不确定的下推自动机。不确定的下推自动机。 3 3型文法（正规文法型文法（正规文法RGRG）：产生的语）：产生的语言是言是有穷自动机有穷自动机（FAFA）所接受的集）所接受的集合合第四节 正规文法与有穷自动机一、正规文法1. 正规文法 能 产生语言L(G)2. 写出产生语言L(G)的正规文法第四节 正规文法与有穷自动机1、正规文法 产生的语言的推导例：文法 G=（VN，VT，P，S）其中： VN=A，B，C VT=a,b,c S=AP:A aB A aA aB A aA B bB
12、 B bB B bCbC C cC C c C cC C cL(G)=aL(G)=ammb bn nc cp p/m,n,p/m,n,p1 1A=aA=aaA=A=aA=aaA=.=aa.=aaaBaB =aa =aaabB=aaabB=aaabbabbbCbC =aa =aaabbabbbcC= aabcC= aaabbabbbccCbccC = aa = aaabbabbbccbccc c最小句子：abcP:A aB A aA aB A aA B bB B bB B bCbC C cC C c C cC C c例例1 1：写出产生语言：写出产生语言L(G)=aL(G)=ammbcbcn n
13、/m,n/m,n00的正规文法的正规文法解：文法 G=（VN，VT，P，S）其中： VN=A，C VT=a,b S=AP:最小语言：bA aAaAA bA bA bCA bCC cCcCCcCc2. 写出产生语言写出产生语言L(G)的正规文法的正规文法例例2 2：C C语言标识符的文法描述语言标识符的文法描述L L（G G）=w/w=w/w为字母或为字母或- -打头的字母数字串打头的字母数字串 解：P:IaB I -BaB I -B B aB B aB B dB Ba B ddB Ba B dI aI aIBT Ta-a,d 其它其它2. 写出产生语言写出产生语言L(G)的正规文法的正规文法二
14、、有穷自动机二、有穷自动机正规文法产生的正规语言用有穷自动机正规文法产生的正规语言用有穷自动机来识别来识别根据文法-写程序 -编译时用有穷自动机识别二、有穷自动机二、有穷自动机1 1、特点：接收离散输入，状态有穷，只、特点：接收离散输入，状态有穷，只需考虑当前输入和当前内部状态需考虑当前输入和当前内部状态2 2、原理：、原理：有穷自动机控制器有穷自动机控制器读头自左向读头自左向右逐个扫描并读入右逐个扫描并读入输入符号输入符号，并且根据，并且根据控制器的控制器的当前状态当前状态和和当前输入符号当前输入符号控制控制转入转入下一个状态下一个状态、模型、模型Main ( ) int I , j , k
15、 ;有穷控制器、表示、表示状态图状态图IBT Ta-a,d 其它其它例：例：C C语言的标识符语言的标识符、形式定义、形式定义确定的有穷自动机是一个五元组确定的有穷自动机是一个五元组 M=M=（QQ， ， ，q q0 0，Z Z）其中：其中：QQ是一有穷状态集是一有穷状态集是有穷输入字母表是有穷输入字母表是是Qx Qx QQ的映射函数的映射函数 其含义：其含义： （ q q1 1,a)= ,a)= q q2 2q q0 0 Q,Q,唯一的初态唯一的初态Z Z是的子集，是终态集是的子集，是终态集 例：奇偶测试器例：奇偶测试器q00q11q101自动机：（自动机：（QQ， ， ，q q0 0，Z
16、Z）QQ q q0 0, q, q1 1 =0,1 =0,1 q q0 0=q=q0 0 Z=q Z=q1 1 映射函数映射函数：（ q q, ,)= )= q q（ q q, ,)= )= q q（ q q1 1, ,)= )= q q（ q q1 1, ,)= )= q q例例：q00q11q101三、正规表达式与有穷自动机三、正规表达式与有穷自动机关系：等价、交换关系：等价、交换文法文法 G=（VN，VT，P，S）和）和自动机自动机 M=M=（QQ， ， ，q q0 0，Z Z）可转换为：可转换为： VN为终态为终态q q0 0 VT，S若 映射函数映射函数：、：、： a a2 2 ,
17、, 则则（ ,a)= ,a)= A A2 22 2、：、： a, a, 则则（ ,a)= ,a)= T T3 3、（ ,a)= ,a)= 空动作空动作例：已知正规文法例：已知正规文法（A,B,C,A,B,C,a,b,c,P,S a,b,c,P,S 其中：其中：P:A aA A aB B bB aA A aB B bB B bC B bC C cC CccC Cc试写出与其等价的试写出与其等价的解：解：(A,B,C,a,b,c, (A,B,C,a,b,c, ,S,T),S,T)ABCTaabbcc映射函数映射函数：（ A A,a)= ,a)= A A （ A A,a)= ,a)= B B（B,b
18、)= B,b)= B B （B,b)= B,b)= C C（C,c)= C,c)= C C （C,c)= C,c)= T T练习：练习：w/ww/w是和的个数都为是和的个数都为偶数的、串偶数的、串试写出能识别该语言的自动机和描述该试写出能识别该语言的自动机和描述该语言的文法语言的文法第五节上下文无关文法语法基础第五节上下文无关文法语法基础一、上下文无关文法一、上下文无关文法文法文法 G=（VN，VT，P，S） ： A （ VN VT)例：例：anbn/n 1P: S aSbaSb S abab 二、自嵌套性二、自嵌套性如果上下文无关文法中存在一个如果上下文无关文法中存在一个终结符，且终结符，且
19、 ( ( , 不空），称该上下文无关文法具有可嵌不空），称该上下文无关文法具有可嵌套性套性例：例：wcwr/w （a | |b), wr是是w的反置的反置P: S aSaaSa S bSbbSb ， S c c句子abbacabba三、下推自动机三、下推自动机、模型、模型输入带有穷控制器下推栈、操作、操作、接收、接收b.b.空动作空动作（ q q, , ,Z)= ,Z)= (q1, )(q1, )A A、读入输入符号，替换栈顶，改变状、读入输入符号，替换栈顶，改变状 态，读头右移态，读头右移（ q q,a,Z)= ,a,Z)= (q1, )(q1, )空栈：输入串空，栈内也空空栈：输入串空，栈
20、内也空终态：规定终态，导致进入终态的串被终态：规定终态，导致进入终态的串被 认为接收。此时，栈内可能不为认为接收。此时，栈内可能不为 空空、定义、定义是一个七元组，是一个七元组， M=M=（Q,Q, , , ,q ,q0 0, , 0 0 , , ）是有穷输入字母表；是有穷输入字母表；其中：其中：QQ是一有穷状态集是一有穷状态集是下推字母表是下推字母表是是Qx(Qx( )x Q Q x* *的映射函的映射函 数数, , 其含义：其含义： ( ( q q1 1,a,Z)= (,a,Z)= (q q2, 2, )q q0 0 Q,Q,唯一的初态唯一的初态; ;F F是的子集，是终态集是的子集，是终
21、态集0 0 是栈底符号是栈底符号例：例：wcwr/w （a | |b), wr是是w的反置的反置,写出识别该语言的写出识别该语言的解：解：M=M=（Q,Q, , , ,q ,q0 0, , 0 0 , , ）QQ q q0 0， q q， q qa,ba,b；=Z Z0 0，q q0 0 q q0 00 0 = =0 0 映射函数：映射函数：( ( q q0 0,a,Z,a,Z0 0)= ()= (q q1, 1, A AZ Z0 0), ),( ( q q0 0,b,Z,b,Z0 0)= ()= (q q1, 1, B BZ Z0 0) )( ( q q1 1,a,A)= (,a,A)= (
22、q q1, 1, AAAA), ),( ( q q1 1,a,B)= (,a,B)= (q q1, 1, ABAB) )( ( q q1 1,b,A)= (,b,A)= (q q1, 1, BABA), ),( ( q q1 1,b,B)= (,b,B)= (q q1, 1, BBBB) )( ( q q1 1,c,A)= (,c,A)= (q q2, 2, A A), ),( ( q q1 1,c,B)= (,c,B)= (q q2, 2, B B) )( ( q q2 2,a,A)= (,a,A)= (q q2, 2, ), ),( ( q q2 2,b,B)= (,b,B)= (q q2
23、, 2, ) )( ( q q2 2, , , Z, Z0 0)= ()= (q q0, 0, ), ),( ( q q0 0, , c, Z, Z0 0)= ()= (q q0, 0, ) )句型、推导E EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*aGE E： EE+T|TEE+T|TTTTT* *F|FF|FF(E)|aF(E)|aE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*aE EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a对于句子a+a*a 有不同的推导规范推
24、导规范推导 规范句型规范句型最左（最右）推导：在推导的任何一步最左（最右）推导：在推导的任何一步，其中，其中、是句型，都是对是句型，都是对中的最左（右）非终结符进行替换中的最左（右）非终结符进行替换最右推导被称为最右推导被称为规范推导规范推导。由规范推导所得的句型称为由规范推导所得的句型称为规范句型规范句型语法树语法树设G=( VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树(推导树)(派生树）：1. 每个内结点都有一个标记，此标记是VN的一个符号2. 根的标记是S3. 若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定AVN4. 如果结点n有标记A,其直
25、接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式语法树语法树-句型推导句型推导的的直观表示直观表示给定文法给定文法G=(G=(VN,VT,P,S) )，对于，对于G G的任何句的任何句型都能构造与之关联的语法树型都能构造与之关联的语法树( (推导树推导树) )语法树的结果：语法树的结果： 从左到右读出叶子的标记所构成的符号串称为句子构造语法树构造语法树E EE+TGE E： EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|aT+TF+T a+Ta+T*Fa+F*Fa+a*Fa+a*aEE+TTF
26、EE+TTEE+T构造语法树构造语法树E EE+TGE E： EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|aT+TF+T a+Ta+T*Fa+F*Fa+a*Fa+a*aEE+TTFaT*FFaaa+a*aE EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*aE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*aE EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*aEE+TTFaT*FFaa语法树看不出推导顺序上下文无关文法的语法树的用处用于描述上下文
27、无关文法用于描述上下文无关文法句型推导句型推导的的直观方法直观方法 例例: GS:SaASASbAASSSaAba S a A S S b A a a b a句型句型aabbaaaabbaa的的语法树语法树（推导树（推导树）叶子结点叶子结点：树中：树中没有子孙的结点没有子孙的结点。从左到右从左到右读出推导树的读出推导树的叶子标记叶子标记连接成的连接成的文文法符法符号串号串，为，为GSGS的的句型句型。也把该推导树称为该。也把该推导树称为该句型句型的的语法树语法树。 但是，一个句型是否只对应唯一但是，一个句型是否只对应唯一的一棵语法树呢的一棵语法树呢? ?一个句型是否只有唯一个句型是否只有唯一的
28、一个最左一的一个最左( (最右最右) )推导呢推导呢? ? 一棵语法树表示了一个句型的种种一棵语法树表示了一个句型的种种可能的可能的( (但未必是所有的但未必是所有的) )不同推导过程不同推导过程. .例例：GE:GE:E iE iE E+EE E+EE EE E* *E EE (E)E (E) E E E + E E + E E E * * E i E i i i i i E E E E * * E E i E + E i E + E i i i i句型句型 i i* *i+i i+i 的两个不同的最左推导：的两个不同的最左推导：推导推导2 2：E E E E* *E E i i* *E E
29、 i i* *E+E E+E i i* *i+E i+E i i* *i+ii+i推导推导1 1：E E E+E E+E E E* *E+E E+E i i* *E+E E+E i i* *i+E i+E i i* *i+ii+i二义文法二义文法 若一个文法存在某个句子对应两棵不若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是同的语法树，则称这个文法是二义二义的或者，若一个文法存在某个句子的或者，若一个文法存在某个句子有两个不同的最左（右）推导，则有两个不同的最左（右）推导，则称这个文法是称这个文法是二义二义的的判定任给的一个上下文无关文法是否判定任给的一个上下文无关文法是否二义，或
30、它是否产生一个先天二义的二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一不可解的，但可以为无二义性寻找一组充分条件组充分条件二义文法改造为无二义文法二义文法改造为无二义文法GE: E i GEGE: E i GE：E T|E+TE T|E+T E E+E T F|T E E+E T F|T* *F F E E E E* *E F E F （E E）|i|i E (E) E (E) 规定优先顺序和结合律规定优先顺序和结合律 如果产生上下文无关语言的每一个文法如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先
31、天二义都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。望对它的每个语句的分析是唯一的。句型的分析句型的分析句型分析句型分析就是就是识别识别一个符号串是否为某一个符号串是否为某文法的文法的句型句型，是某个，是某个推导推导的构造过程。的构造过程。从左到右的分析算法从左到右的分析算法，即，即总是从总是从左左到到右右地地识别输入符号串识别输入符号串，首先识别符号串中，首先识别符号串中的的最左最左符号，进而符号，进而依次识别右边依次识别右边的一个的一个符号，符号
32、，直到分析结束直到分析结束。在语言的编译实现中，把在语言的编译实现中，把完成句型分析完成句型分析的的程序程序称为称为分析程序分析程序或或识别程序识别程序。分析。分析算法又称算法又称识别算法识别算法。句型的句型的分析算法分类分析算法分类分析算法可分为：分析算法可分为：自上而下分析法自上而下分析法：从文法的开始符号出发从文法的开始符号出发，反复使用文，反复使用文法的产生式，法的产生式，寻找寻找与与输入符号串输入符号串匹配匹配的的推导推导。自下而上分析法自下而上分析法：从从输入符号串输入符号串开始开始，逐步进行逐步进行归约归约，直，直至至归约归约到到文法的文法的开始符号开始符号。两种方法反映了两种语
33、法树的构两种方法反映了两种语法树的构造过程造过程。自上而下方法自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上方法自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树自上而下的语法分析自上而下的语法分析例：文法例：文法G G：S S c cA Ad d A A abab A A a a识别输入串识别输入串w=w=cabdcabd是否为该文法的是否为该文法的句子句子SSScAdcAd a b推导过程：推导过程：S cAd cAd cabd自下而上的语法分析自下而上的语法分析例：文法例：文法G G： S S c cA Ad d A A abab A A a a识别输入串识别输入串w=w=cabdcabd是否该文法的是否该文法的句子句子SAA c a b d c a b d c a b d 规约规约过程构造的推导：过程构造的推导： cAd cabd S cAd
