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

1、编译程序的设计原理与实现编译程序的设计原理与实现如何让计算机如何让计算机认识、理解认识、理解 和和 执行执行 高级程序设计语言高级程序设计语言 ？【内容提要】【内容提要】第第 2 2 章章 形式语言基础形式语言基础 (2)(2) 2.1 2.1 形式语言是形式语言是符号串集合符号串集合 2.2 2.2 形式语言是由形式语言是由文法定义文法定义的的 2.3 2.3 主要主要语法成分语法成分的定义的定义 2.4 2.4 两类两类特性文法特性文法 2.5 2.5 文法变换文法变换方法方法 2.6 2.6 关于关于形式语言的分类形式语言的分类问题问题 上节课主要内容回顾：上节课主要内容回顾： 文法文法

2、 是规则集合，四元组：是规则集合，四元组：G(Z)=(VG(Z)=(VN N, V, VT T, Z, P), Z, P) 文法所定义的语言文法所定义的语言： 文法应用示例：文法应用示例： 简单语言的文法构造：简单语言的文法构造： 无符号整数无符号整数文法：文法：G(N): N - dN | d N - dN | d L(G)= x | Z x,xVL(G)= x | Z x,xVT T* * = + +I - A| A| A- A- A|dA| A|dA| 求解文法所定义的语言求解文法所定义的语言(或句子或句子)方法：方法：v 形式语言形式语言是是符号串集合符号串集合且由且由文法文法定义定义

3、！ 正规方程组迭代求语言（如正规方程组迭代求语言（如 标识符文法）标识符文法）直接由定义求解句子直接由定义求解句子(如如 算术表达式文法算术表达式文法)。 标识符标识符文法：文法：G(G(I):):d(d(数字数字), ), ( (字母字母) ) 文法有两种基本运算：文法有两种基本运算：推导推导，归约归约。v 星推导星推导( ): ( ): 2.3 2.3 主要语法成分的定义主要语法成分的定义直接推导直接推导( = ): xAy = x( = ): xAy = x y y 即：指用产生式的右部符号串即：指用产生式的右部符号串替换替换左部非终结符。左部非终结符。 加推导加推导算符算符v 加推导加

4、推导( ): ( ): 设设 x, y(Vx, y(VN N+V+VT T) )* *，A-A- PP = * = *（当且仅当（当且仅当 = 1 1= 2 2=） 即：指一步或一步以上的直接推导运算。即：指一步或一步以上的直接推导运算。 （当且仅当（当且仅当 =或或 = 1 1= 2 2=) 即：指零步或零步以上的直接推导运算。即：指零步或零步以上的直接推导运算。直接推导直接推导算符算符星推导星推导算符算符 = + + = + +2.3.1 2.3.1 文法的运算问题文法的运算问题 实用中最常见的两种运算实用中最常见的两种运算： 最左推导最左推导( )( )每次推导皆每次推导皆最左非终结符最

5、左非终结符优先优先； 最左归约最左归约( )( )每次归约皆每次归约皆最左可归约串最左可归约串优先优先。 =. .+ + =. .+ +v 加归约加归约( ): : 直接归约直接归约( ): x( ): x y xAy y xAy =. . =. .（当且仅当（当且仅当 1 1 2 2 ） =. . =. . =. . =. .v 星归约星归约( )( )： =. .* =. .*（当且仅当（当且仅当 =或或 1 1 2 2 ) ) =. . =. . =. . =. . =+ + =. .+ +即：直接归约是直接推导的即：直接归约是直接推导的逆运算逆运算，用产生式的，用产生式的左部左部非终结

6、符非终结符替换替换右部右部符号串符号串。即：指零步或零步以上的直接归约运算。即：指零步或零步以上的直接归约运算。即：指一步或一步以上的直接归约运算。即：指一步或一步以上的直接归约运算。直接归约直接归约算符算符加归约加归约算符算符星归约星归约算符算符这是相应的这是相应的算符算符i+ii+i* *i i 给定一个符号串给定一个符号串 i+ii+i* *i i ： T-F|T T-F|T* *F|T/FF|T/F F-i |( E ) F-i |( E )G(E):G(E): E-T|E+T|E-T E-T|E+T|E-T文法运算示例：文法运算示例： 【例【例2.82.8】 算数表达式文法：算数表达

7、式文法： =. . =. . =. . =. =. . =. . =. . =. . 最左归约最左归约( (从从符号串出发符号串出发) )过程：过程：E E = E+T= E+T = T+T= T+T= F+T= F+T= i+T= i+T= i+T= i+T* *F F= i+F= i+F* *F F = i+i= i+i* *F F = i+i= i+i* *i i E E =+ +i+ii+i* *i iF+iF+i* *i iT+iT+i* *i iE+iE+i* *i iE+FE+F* *i iE+TE+T* *i iE+TE+T* *F FE+TE+TE i i* *i+ii+i

8、=. .+ +E E1. 1. 最左推导最左推导( (从从开始符号出发开始符号出发) )过程：过程：最左非终结符最左非终结符最左可归约串最左可归约串即：句型是由文法开始符号加推导出的任一符号串。即：句型是由文法开始符号加推导出的任一符号串。2.3 2.3 主要语法成分的定义主要语法成分的定义( (续续1)1) 2.3.2 2.3.2 句型、句子和语法树句型、句子和语法树若有若有 且且 VVT T* * ，则，则 是句子；是句子； Z Z =+ +若有若有 ，则，则 是句型；是句型； Z =+2. 2. 句子句子即：句子是由开始符号加推导出的任一终结符号串。即：句子是由开始符号加推导出的任一终结

9、符号串。 1. 1. 句型句型设有文法设有文法 G(Z)=(VG(Z)=(VN N, V, VT T, Z, P), Z, P)，则：，则：3.3.语法树语法树 句型句型( (句子句子) )产生过程的一种树结构表示；产生过程的一种树结构表示；树根树根-开始符号开始符号；树叶树叶给定的给定的句型句型( (句子句子) )。 A A X X1 1 X X2 2 X Xn n2.3 2.3 主要语法成分的定义主要语法成分的定义( (续续2)2) 重复步骤重复步骤，直到再没有推导产生式为止。，直到再没有推导产生式为止。 置树根为开始符号；置树根为开始符号； 【语法树的构造算法】：【语法树的构造算法】：

10、若采用了若采用了推导产生式推导产生式： A - xA - x1 1x x2 2xxn n，则有则有子树：子树： 如此构造的语法树，其如此构造的语法树，其全体树叶全体树叶（自左（自左至右）恰好是给定的句型。至右）恰好是给定的句型。 E E=T=T =T=T* *F F=F=F* *F F=(E)=(E)* *F F =(E+T)=(E+T)* *F F=(T+T)=(T+T)* *F F=(T/F+T)=(T/F+T)* *F F =(T/F+F)=(T/F+F)* *F F =(T/F+F)=(T/F+F)* *i i 句型、句子和语法树示例：句型、句子和语法树示例：【例【例2.102.10】

11、 算术表达式算术表达式文法：文法： 证明证明 (T/F+F)(T/F+F)* *i i 是一个句型是一个句型( (表达式型表达式型) )； 画出该句型的语法树。画出该句型的语法树。 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 )【证】【证】即：即：E (T/F+F)E (T/F+F)* *i i = + +证闭证闭 句型句型 (T/F+F)(T/F+F)* *i i 的语法树构造：的语法树构造：E ET TT T *

12、 * F FF F( E )( E )E + TE + TT TT / FT / FF Fi i E -T |E+T |E-T E -T |E+T |E-T T -F |T T -F |T* * F |T/FF |T/F F - i | ( E ) F - i | ( E )【注】关于语法树：【注】关于语法树： 子树子树 ：以任何具有：以任何具有分支的结点为根所分支的结点为根所形成的树，称为原形成的树，称为原树的子树。树的子树。 简单子树简单子树 ：仅具有：仅具有单层分支的子树。单层分支的子树。 (他他) (哥哥哥哥)(喜欢喜欢) (看看) 图图2.2 2.2 他哥哥喜欢看书他哥哥喜欢看书的的

13、语法树语法树(书书) 2.3.3 2.3.3 短语、简单短语和句柄短语、简单短语和句柄 【例【例2.112.11】图】图2.22.2为一个为一个中文句型中文句型的语法树：的语法树： 短短 语语 - - 他他哥哥哥哥 ,喜欢看喜欢看 ,书书 ， 喜欢看书喜欢看书 ，他他哥哥喜欢看书哥哥喜欢看书 简单短语简单短语 - - 他他哥哥，喜欢看，书哥哥，喜欢看，书 句句 柄柄 - - 他他哥哥（最左边的简单短语哥哥（最左边的简单短语! !） 句柄句柄 - - 一个句型的一个句型的最左简单短语最左简单短语称为该句型的称为该句型的句柄句柄。2.3 2.3 主要语法成分的定义主要语法成分的定义( (续续3)3

14、)2.3.3 2.3.3 短语、简单短语和句柄短语、简单短语和句柄 设设 文法文法 G(Z) , xG(Z) , x y y 是一个句型，则是一个句型，则: : 则则 是句型是句型 x x y y 关于关于A A的短语的短语(A(A是是 的名字的名字) )； = + + = + + 短语短语 若若 Z xAy xZ xAy x y ,y , Z Z x A y x A y 任一任一子树子树的的树叶全体树叶全体( (具有共同具有共同祖先祖先的叶节点的叶节点符号串符号串) )皆为皆为短语短语； = + + 简单短语简单短语 若若 Z xAy = xZ xAy = x y ,y , 则则 是句型是句

15、型 x x y y 关于关于A A的简单短语的简单短语(A(A是是 的名字的名字) ) ； 任一任一简单子树简单子树的的树叶全体树叶全体( (具有共同具有共同父亲父亲的叶的叶节点符号串节点符号串) )皆为皆为简单短语简单短语； 短语、简单短语和句柄短语、简单短语和句柄示例示例【例【例2.122.12】图】图2.32.3为一个算术表达式为一个算术表达式( (型型) )的语法树：的语法树： 句型：句型： E+F-T/FE+F-T/F* *i i 短语短语: : E+F-T/FE+F-T/F* *i i，E+FE+F，F F，T/FT/F* *i i，T/FT/F，i i 简单短语简单短语: F:

16、F，T/FT/F，i i 句柄句柄: F: F E E - T E + T T * F F T / F i 图图2.3 E+F-T/F2.3 E+F-T/F* *i i 的语法树的语法树 一类典型的综合例题：一类典型的综合例题：【例【例2.132.13】G(S): S-aAcBe ; A-Ab|b ; B-dG(S): S-aAcBe ; A-Ab|b ; B-d 给定符号串给定符号串 ： aAbcdeaAbcde 证明证明 = aAbcde 是一个句型；是一个句型； 画出句型画出句型 的语法树；的语法树； 指出指出 中的短语、简单短语和句柄。中的短语、简单短语和句柄。【题解】【题解】 S=a

17、AcBe=aAbcBe= aAbcde S=aAcBe=aAbcBe= aAbcde 语法树如右图：语法树如右图： 短语、简单短语和句柄短语、简单短语和句柄: : S S a A c B e a A c B e A b d A b d 短语短语: aAbcde ,Ab , d: aAbcde ,Ab , d 简单短语简单短语: Ab , d: Ab , d 句柄：句柄：AbAbG2(S): S - b S | a - G2(S): S - b S | a - 直接右递归直接右递归文法。文法。2.4 2.4 两种特性文法两种特性文法1 1 2.4.1 2.4.1 递归文法递归文法 设有文法：设有

18、文法：G(Z)=(VG(Z)=(VN N,V,VT T,Z,P),Z,P)【定义】【定义】 设设 AVAVN N，x, y(Vx, y(VN N+V+VT T) )* *，则，则; ; 若若 A xAyA xAy，：称文法具有，：称文法具有递归性递归性; ; = + +特别特别： 若若 A -A - A A ，称文法具有，称文法具有直接左递归性直接左递归性； A A - - A A ，称文法具有，称文法具有直接右递归性直接右递归性。 递归文法是定义无限语言的工具（递归文法递归文法是定义无限语言的工具（递归文法定义的语言有无限个句子）！定义的语言有无限个句子）！如：如：G1(S): S - S

19、b | a - G1(S): S - S b | a - 直接左递归直接左递归文法；文法； 2.4 2.4 两种特性文法两种特性文法2 22.4.2 2.4.2 二义性文法二义性文法【定义】【定义】 若文法中存在这样的句型，它具有若文法中存在这样的句型，它具有两棵两棵不同的语法树不同的语法树，则称该文法是，则称该文法是二义性二义性文法。文法。【例【例2.142.14】 算术表达式的另一种文法：算术表达式的另一种文法： 句型句型 i+ii+i* *i i 有两棵有两棵不同的语法树不同的语法树( (右图右图) )： G(E) 是二义性文法。是二义性文法。G G (E)(E)：E - E+E|E-E|EE - E+E|E-E|E* *E|E/E|(E)|i ;E|E/E|(E)|i ;i(i(变量或常数变量或常数) ) E E E E E + E E E + E E * * E E i E i E * * E E + E i E E + E i i i i i i i i i 二义性文法会引起歧义，二义性文法会引起歧义，应尽量避免之！应尽量避免之！练习题练习题【