编译原理第二章形式语言基础(1)

1、编译程序的设计原理与实现编译程序的设计原理与实现如何让计算机如何让计算机认识、理解认识、理解 和和 执行执行 高级程序设计语言高级程序设计语言 ？ 第第 2 2 章章 形式语言基础形式语言基础 计算机处理语言，首先应考虑语言的形式化、规计算机处理语言，首先应考虑语言的形式化、规范化，使其具有可计算性和可操作性；这就是形式语范化，使其具有可计算性和可操作性；这就是形式语言理论研究的问题。言理论研究的问题。 形式语言诞生于形式语言诞生于19561956年，由年，由chomskychomsky创立。通常，创立。通常，语言研究至少涉及三个方面：语言研究至少涉及三个方面：语法语法、语义语义和和语用语用；

2、 这里仅侧重于这里仅侧重于语法的研究语法的研究。 形式语言的形式语言的基本观点基本观点是是 ： 语言是符号串之集合！语言是符号串之集合！ 形式语言理论研究的形式语言理论研究的基本问题基本问题是：是： 研究符号串集合的表示方法、结构特性研究符号串集合的表示方法、结构特性 以及运算规律。以及运算规律。【前【前 言】言】【内容提要】【内容提要】第第 2 2 章章 形式语言基础形式语言基础 2.1 2.1 形式语言是形式语言是符号串集合符号串集合 2.22.2 形式语言是由形式语言是由文法定义文法定义的的 2.32.3 主要主要语法成分语法成分的定义的定义 2.42.4 两类两类特性文法特性文法 2.

3、5 2.5 文法变换文法变换方法方法 2.6 2.6 关于关于形式语言的分类形式语言的分类问题问题 字母表字母表 - - 元素元素( (符号符号) )的非空有限集合；的非空有限集合； 符符号串号串 - - 符号的有限序列；符号的有限序列； 符号串集合符号串集合 - - 有限个或者无限个符号串组成有限个或者无限个符号串组成的集合；的集合； 规规 则则 - - 以以某种形式表达的在一定范围内共某种形式表达的在一定范围内共同遵守的章程和制度；这里，指符号串的组成同遵守的章程和制度；这里，指符号串的组成规则。规则。2.1 2.1 形式语言是符号串集合形式语言是符号串集合 【形式语言】【形式语言】是是字

4、母表字母表上的符号，按一定的上的符号，按一定的规则规则组成的所有组成的所有符号串集合符号串集合；其中的每个符号串；其中的每个符号串称为称为句子句子。【名词解释】：【名词解释】：三要素！三要素！【例【例2.12.1】 L L1 1= 00,01,10,11 ;= 00,01,10,11 ; 字母表字母表1 1= 0,1,= 0,1, 句子有：句子有：00,01,10,1100,01,10,11【注】【注】 b b0 0= = （空符号串）（空符号串）,b,b1 1=b,b=b,b2 2=bb,b=bb,b3 3=bbb,=bbb, L L1 1 为有限语言为有限语言; L; L2 2 为无限语言

5、。为无限语言。 形式语言概念示例：形式语言概念示例：【例【例2.22.2】 L L2 2= ab= abm mc,bc,bn n | m0,n0 | m0,n0 字母表字母表2 2= a,b,c,= a,b,c,句型句型1: ab1: abm mc ,c ,有句子：有句子： abc, abbc, abbbc, abc, abbc, abbbc, 句型句型2: b2: bn n ; ;有句子：有句子： , b, bb, bbb, , b, bb, bbb, 两个语言！两个语言！1. 1. 连接连接： . . = = 如如 a.b=aba.b=ab 2.1.1 2.1.1 符号串符号串( (集合集

6、合) )的运算的运算3.3. 方幂方幂： n n = = = = n-1n-1 = = n-1n-1 4.4. 闭包：闭包：n n个个. . 符号串的运算符号串的运算 设设 , , 为两个符号串，则为两个符号串，则： 的正闭包：的正闭包： + + = = 1 1| | 2 2| n n| 的星闭包：的星闭包： * * = = 0 0| | 1 1| | 2 2| n n| 0 0 = = ( (空符号串空符号串) ) 什麽符号也没有的符号串什麽符号也没有的符号串 ！ 1 1= = ； 2 2 = = ；2.2. 或或： | | = = ( (或者或者 ）这是一种这是一种泛指泛指！2.1.1 2

7、.1.1 符号串符号串( (集合集合) )的运算的运算( (续续1)1)【例】：【例】： ab|cd = ab ab|cd = ab（或者或者 cd cd ） abc.de= abcde abc.de= abcde (a|b) (a|b)1 1 =(a|b)= a|b =(a|b)= a|b (a|b) (a|b)* * =(a|b)=(a|b)0 0 |(a|b)|(a|b)1 1 |(a|b)|(a|b)2 2 |(a|b)(a|b)2 2 =(a|b)(a|b)=aa|ab|ba|bb=(a|b)(a|b)=aa|ab|ba|bb 即：即：(a|b)(a|b)* * = (a|b)= (

8、a|b)n n ，n0n0同理：同理： (a|b)(a|b)+ + = (a|b)= (a|b)n n ，n n0 0 符号串运算示例符号串运算示例泛指：泛指：由由a，b组成的组成的任意符号串！任意符号串！（包括空串）（包括空串）1.1.乘积：乘积： AB=xy |xAB=xy |x A A 且且 y y BB 2.1.1 2.1.1 符号串符号串( (集合集合) )的运算的运算( (续续2)2)4.4.闭包：闭包：A A 的正闭包的正闭包： A A+ + = A= A1 1AA2 2AAn nA A 的星闭包的星闭包： A A* * = A= A0 0AA1 1AA2 2AAn n设设 A

9、A 和和 B B 为两个符号串集合，则：为两个符号串集合，则：2. 2. 和：和： AB=A+B=x| xAB=A+B=x| x A A 或或 x x BB 3.3.方幂：方幂： A An n = AAA = AA= AAA = AAn-1n-1 = A = An-1n-1A An n个个 A A0 0 = ; A A1 1 =A =A ; ; A A2 2 =AA ; A=AA ; A3 3 =AAA ; =AAA ; . . 符号串集合的运算符号串集合的运算 符号串集合运算示例：符号串集合运算示例：【例【例2.32.3】 设设 A=a,b,B=c,dA=a,b,B=c,d 则则 A+B=a

10、,b,c,d A+B=a,b,c,d 则则 AB=xy|xAB=xy|x A,yA,y B=B=ac,ad,bc,bdac,ad,bc,bd【例【例2.42.4】 设设 A=aA=a 则则 A A* * = A= A0 0AA1 1AA2 2AAn n = = +a+aa+aaa+a+aa+aaa+ = = ,a,aa,aaa,a,aa,aaa, =a =an n|n0 |n0 【例【例2.52.5】 设设 A=aA=a，bb， A A* * = ? = ? A A* * = A = A0 0AA1 1AA2 2AAn n A A0 0 = = ; A A1 1 = A =a = A =a，b

11、;b; A A2 2 = A.A=a = A.A=a，b.ab.a，b=aa,ab,ba,bb;b=aa,ab,ba,bb; A A3 3 = A.A = A.A2 2=a=a，b.aa,ab,ba,bbb.aa,ab,ba,bb =aaa,aab,aba,abb,baa,bab,bba,bbb; =aaa,aab,aba,abb,baa,bab,bba,bbb; A A* * = x | x=(a|b) = x | x=(a|b)n n ，n0 n0 符号串集合运算示例符号串集合运算示例( (续续) )： 推论推论：若：若 A A为任一字母表为任一字母表, ,则则 A A* * 就是该字母就

12、是该字母表上表上的所有符号串的所有符号串( (包括空串包括空串) )的集合。的集合。 S,A S,A 定义的对象定义的对象(S (S 句子句子, ,最大的定义对象，又最大的定义对象，又 称为开始符号称为开始符号; A; A为句型为句型aAcaAc的的短语短语），）， a,b,c - a,b,c - 为为字母表字母表中的符号中的符号;- ;- 空符号串。空符号串。 - ,| - - ,| - 为为描述符号描述符号( - ( - 定义为定义为; | ; | 或者是）或者是） 2.1.2 2.1.2 符号串集合的文法描述符号串集合的文法描述【例【例2.52.5】 L = abL = abn nc |

13、 n0 c | n0 ， 字母表字母表：= a,b,c= a,b,c； 展开展开：L =ac,abc,abbc,abbbc, L =ac,abc,abbc,abbbc, 右图给出的表示右图给出的表示 S -S - aAcaAc A - bA | A - bA | 长久以来，探讨符号串集合长久以来，探讨符号串集合(即形式语言即形式语言)的各种的各种描述方法，一直是语言计算机处理的重要任务之一。描述方法，一直是语言计算机处理的重要任务之一。方法方法 -文法规则文法规则 ；其中：其中： 从开始符号开始符号出发，对符号串中的定义对象，采用推导推导的方法（用其规则右部替换左部）产生新的符号串，如此进行，

14、直到新符号串中不再出现定义的对象为止，则最终的符号串就是一个句子句子。 S - S - aAc aAc A - bA | A - bA | 规则应用说明示例：规则应用说明示例： 【句子产生过程句子产生过程】(= = 推导算符推导算符):): 怎样利用上述怎样利用上述文法规则文法规则表示语言表示语言L?L? S S= = aAcaAc = ac= ac = ac= ac S S= aAc= aAc = abAc= abAc = abc= abc = abc= abc S S = aAc= aAc = abAc= abAc= abbAc= abbAc = abbc= abbc 一个句子一个句子!

15、!又一个句子又一个句子! ! S abS abn nc , n0 c , n0 = + +再一个句子再一个句子! ! 【定义】【定义】 文法文法(grammar)(grammar)是规则的有限集是规则的有限集, ,其中的上下文无关文法可定义为四元组：其中的上下文无关文法可定义为四元组： G(Z)=(VG(Z)=(VN N, V, VT T, Z, P), Z, P) V VN N : : 非终结符集（定义的对象集，如：语法成分等非终结符集（定义的对象集，如：语法成分等) )； V VT T : : 终结符集（字母表）；终结符集（字母表）； Z : Z : 开始符号（研究范畴中，最大的定义对象）

16、；开始符号（研究范畴中，最大的定义对象）； P : P : 规则集（又称产生式集）；规则集（又称产生式集）； A - A - 或者或者 A - A - | | 其中其中, , 描述符号描述符号 ： -(-(定义为定义为) )，|(|(或者是或者是) ) 文法符号文法符号 ： Z,AVZ,AVN N， , , (V(VN N+V+VT T) )* * 2.2 2.2 形式语言是由文法定义的形式语言是由文法定义的每个元素每个元素每个规则每个规则2.2.1 2.2.1 什麽是文法什麽是文法 ？2.2 2.2 形式语言是由文法定义的（续形式语言是由文法定义的（续3 3）【注意】【注意】 提供了规则集，

17、就相当给出了一个文法：提供了规则集，就相当给出了一个文法： S - S - aAc aAc A - bA | A - bA | G(S):2.2.2 2.2.2 文法是怎样定义语言的？文法是怎样定义语言的？ 则则 L(G)= x | Z x,xVL(G)= x | Z x,xVT T* * 即：一个文法所定义的即：一个文法所定义的语言语言，就是由该文法，就是由该文法开始开始设设 有文法有文法 G(Z), L(G)G(Z), L(G)为为G G所定义的语言；所定义的语言；V VT T= a,b,c ; = a,b,c ; Z Z = S ; = S ; P P : :V VN N= S,A =

18、S,A ；G(Z)=(VG(Z)=(VN N, V, VT T, Z, P), Z, P)利用利用 = = 进行连续推导之意！进行连续推导之意！符号推导出符号推导出的所有的所有仅含终结符仅含终结符的的符号串符号串之集合之集合。其中的每个符号串皆称为其中的每个符号串皆称为句子句子。 = + +2.1【例【例2.62.6】标识符标识符的文法的文法 【标识符标识符】 指字母开头的字母、数字序列。指字母开头的字母、数字序列。令令 G(Z)= (VG(Z)= (VN N, V, VT T, Z, P), Z, P)则则 V VN N =I( =I(标识符标识符),A(),A(标识符尾标识符尾)； V V

19、T T = = ( (字母字母),d),d( (数字）数字） ； Z = I ; Z = I ; P : P : I - - A | A | A - A - A | d A | A | d A | 同理，同理，【无符号整数无符号整数】文法】文法 可写成：可写成：G(N):G(N):N - d N | dN - d N | d其其四元组四元组也可写成：也可写成：G(N)=( N, d, N, P ) 得：得： I = (|d|d)n , n0 令：令： I = = A | A | A = A = A | d A | A | d A | 标识符文法标识符文法所定义的语言求解：所定义的语言求解： 上

20、面构造的上面构造的标识符文法标识符文法属于属于正规文法正规文法( (定义在后定义在后) )类，类，正确性检验较容易；下面给出一个正确性检验较容易；下面给出一个算法算法：I - - A | A | A - A - A | d A | A | d A | 求解求解 I 值步骤：值步骤：先求解先求解 A: A=(|d|d) A , A=(|d|d)2 A , , A=(|d|d)n A 代入代入 A= A= 得：得： A= A= (|d|d)n , n0 I= A | A | 代入代入 A= A= (|d|d)n , n0正规方程式正规方程式标识符标识符：字母开头的字母、数字序列；：字母开头的字母、

21、数字序列；则则 V VN N = E( = E(算术表达式算术表达式),T(),T(项项) )，F(F(因式因式)； V VT T = i( = i(变量或常数变量或常数),),+,-,+,-,* *,/,(,/,(,） ； Z = E ; Z = E ; P : P : 【例【例2.72.7】简单算术表达式文法】简单算术表达式文法【注】此文法定义了算术表达式的层次嵌套结【注】此文法定义了算术表达式的层次嵌套结构构: : E - T | E + E - T | E + T | E -T | E - T T T - F | T T - F | T * * F | T /F | T / F F F - i | ( E ) F - i | ( E )令令 G(Z)= (VG(Z)= (VN N, V, VT T, Z, P), Z