第3章上形式语言简介.ppt

《第3章上形式语言简介.ppt》由会员分享，可在线阅读，更多相关《第3章上形式语言简介.ppt（74页珍藏版）》请在三一文库上搜索。

1、第3章上 形式语言简介,3.1 文法和语言 3.2 推导与语法树,3.1 文法和语言,文法是程序语言的生成系统，而自动机则是程序语言的识别系统；用文法可以精确地定义一个语言，并依据该文法构造出识别这个语言的自动机。因此，文法对程序语言和编译程序的构造具有重要意义，如程序语言的词法可用正规文法描述，语法可用上下文无关文法描述，而语义则要借助于上下文有关文法描述。,3.1.1 文法和语言的概念 1语言 通常我们用表示字母表，字母表中的每个元素称为字符或符号。不同语言的字母表可能是不同的，程序语言的字母表通常是ASCII字符集。由字母表中的字符所组成的有穷系列称为上的字符串或字，字母表上的所有字符串

2、(包括空串)组成的集合用*表示。那么，对字母表来说，*上的任意一个子集都称为上的一个语言，记为L(L*)，该语言的每一个字符串称为语言L的一个语句或句子。,每一个形式语言都是某字母表上符号串的一个集合，反之字母表上符号串的一个集合可定义为一个形式语言。例如，C语言是其基本符号字母表上符号串的集合，而每个C语言程序是基本符号的符号串。再如，假定=a,b,c，则 L1=a,b,c L2=a,aa,ab L3=c,cc 均可表示字母表=a,b,c上的一个形式语言。,当一语言是有穷集合时，可用上述枚举方法来表示语言。但如果语言是无穷集合，那就无法用这种枚举方法。我们要设计出表示无穷集合的强有力的工具。

3、文法就是这样一种工具。 设=a,b，则根据定义+表示a和b的所有可能的符号串的集合。下面用A表示+则A可表示成： A a A b A Aa A Ab 其中，符号“”读作“生成”。,显然，由A生成的符号串都属于+，另一方面，可用归纳法证明+ A，因此有A= +。 考虑=a上的符号串集合：A=a2n|n1 显然aa A；如果yaa A，因此，A可按下法构造： A aa A Aaa 考虑=a,b上的符号串集合：A=abna|n 1 显然A可表示为 A=aBa B=bn|n 1 其中B是我们会构造的，于是可以写出：, A aBa B b B Bb 在这里A是所要构造的，B是辅助集合。这样A aBa可理

4、解为A可生成aBa。若用“ ”表示“推出”，则我们有 A aBa aBa aBba aBba aBbba aBbba abbba 于是得出：A推出符号串abbba，即abbba A。,2文法 文法通常表示成四元组G=(VT，VN，S，)，其中： (1)VT为终结符号集，这是一个非空有限集，它的每个元素称为终结符号； (2)VN为非终结符集，它也是一个非空有限集，其每个元素称为非终结符号，且有VTVN=； (3)S为一文法开始符，是一个特殊的非终结符号，即SVN；,(4)是产生式的非空有限集，其中每个产生式(或称规则)是一序偶(，)，通常写作 或:= 读作“是”或“定义为”。在此，为产生式的左部

5、，而为产生式的右部，、是由终结符和非终结符组成的符号串，(VTVN)+且至少有一个非终结符，而(VTVN)*。,终结符号是指语言不可再分的基本符号，通常是一个语言的字母表；终结符代表了语法的最小元素，是一种个体记号。非终结符号也称语法变量，它代表语法实体或语法范畴；非终结符代表一个一定的语法概念，因此，一个非终结符是一个类、一个集合。例如，在程序语言中，可以把变量、常数、“+”、“*”等看作是终结符，而像“算术表达式”这个非终结符则代表着一定算术式组成的类，如i*(i+i)、i+i+i等；也即每个非终结符代表着由一些终结符和非终结符且满足一定规则的符号串组成的集合。,文法开始符号是一个特殊的非

6、终结符，它代表文法所定义的语言中我们最终感兴趣的语法实体，即语言的目标，而其它语法实体只是构造语言目标的中间变量；如表达式文法的语言目标是表达式，而程序语言的目标通常为程序。 产生式(也称产生规则或规则)是定义语法实体的一种书写规则。一个语法实体的相关规则可能不止一个。例如，有： P1 P2 Pn,为书写方便，可将这些有相同左部的产生式合并为一个，即缩写成 P12n 其中，每个i(i=1,2,n)称为P的一个候选式，直竖“”读为“或”，它与“”一样是用来描述文法的元语言符号(即不属于的字符),例3.1试构造产生标识符的文法。 解答首先，标识符是以字母开头的字母数字串，我们用L表示“字母”类非终

7、结符，用D表示“数字”类非终结符，而用T表示“字母或数字”类非终结符，则有： Labz D019 TLD 其次，如果用S表示“字母数字串”类，则T是一字母或数字，ST也是字母数字串，即有 STST 其中，产生式STST是一种左递归形式，由它可以产生一串T。,最后，作为“标识符”的非终结符I，它或者是一单个字母，或者为一字母后跟字母数字串，即 ILLS 因此，产生标识符的文法GI为： G=(a,b,z,0,9,I,S,T,L,D,I,) :ILLS STST TLD Labz D019,例3.2写一文法，使其语言是奇数集合，但不允许出现以0打头的奇数。 解答根据题意，我们可以将奇数划分为如图31

8、所示的三个部分，即最高位允许出现19，用非终结符B表示；中间部分可以出现任意多位数字09，每一位用非终结符D表示；最低位只允许出现1、3、5、7、9等奇数，用A表示。,图31奇数划分示意,由于中间部分可出现任意位，所以另引入了一个非终结符M，它包括最高位和中间位部分。假定开始符为N，则可得到文法GN为： G=(0,1,9,N,A,M,B,D,N,) :NAMA /*一位数字多位数字*/ MBMD /*仅两位数字(无中间位)多于两位数字*/ A13579 B123456789 D0B,3文法产生的语言 设文法G=(VT,VN,S,)且、(VTVN)*，如果存在产生式A(VTVN)*)，则称A可直

9、接推出，即 A 其中“ ”表示直接推导出，是应用产生规则进行推导的记号。注意“ ”与“”不同，“”是产生式中的定义记号。直接推导是对文法符号串A中的非终结符A用相应的产生式A的右部来替换，从而得到。我们给出推导的说明如下：,(1)如果1可直接推出2，2可直接推出3，n-1可直接推出n，即存在一个自1至n的推导序列：1 2 3 n(n0)，则我们称1可推导出n，记为1 n，它表示从1出发经过一步或若干步可推导出n。 (2)如果记1 1，则1 n表示从1出发，经过0步或若干步可推导出n；也即1 n意味着或者1=n，或者1 n。,例如，对下面的文法GE： EE+EE*E(E)i (3.1) 其中，惟

10、一的非终结符E可以看成是代表一类算术表达式。我们可以从E出发进行一系列的推导，如表达式i+i*i的推导如下： E E+E E+E*E E+E*i E+i*i i+i*i,假定GS是一个文法，S是它的开始符号，如果S ，(VTVN)*，则称是文法GS的一个句型；如果VT*，则称是文法GS的一个句子。仅含终结符的句型是一个句子。 由定义可知，开始符S本身只能是文法的一个句型而不可能是一个句子；此外，上面推导出的i+i*i是文法GE的一个句子(当然也是一个句型)，而E+E、E+E*E、E+E*i和E+i*i都是文法GE的句型。 对于文法GS，它所产生的句子的全体称为由文法GS产生的语言，记为LG，即

11、有 L(G)=S且VT*,3.1.2形式语言分类 语言学家Noam Chomsky于1956年首先建立了形式语言的描述，定义了四类文法及相应的形式语言，并分别与相应的识别系统相联系，它对程序语言的设计、编译方法、计算复杂性等方面都产生了重大影响。 在四类文法中，我们主要用到2型和3型文法。,10型文法与0型语言(对应图灵机) 如果文法G的每一个产生式具有下列形式： 其中，V*VNV*(注：V=VNVT)，即至少含有一个非终结符；V*；则称文法G为0型文法或短语文法，记为PSG。0型文法相应的语言称为0型语言或称递归可枚举集，它的识别系统是图灵(Turing)机，0型语言是不可判定的。 换句话说

12、， 和都是符号串，对它们没有任何限制。这种文法，对计算机语言来说，太一般化了。,21型文法与1型语言(对应线性界限自动机,自然语言) 文法G的每一个产生式，均在0型文法的基础上增加了字符长度上满足的限制，则称文法G为1型文法或上下文有关文法，记为CSG。1型文法相应的语言称为1型语言或上下文有关语言，它的识别系统是线性界限自动机。 1型语言是可以判定的，但是现在还没有找到有效的方法。 1型文法的另一种定义方法是文法G的每一个产生式具有下列形式： A 其中，、V*，AVN，V+（ 是非空串）；显然|A| ，但它更明确地表达了上下文有关的特性，即A必须在、的上下文环境中才能被所替换。,32型文法与

13、2型语言(对应下推自动机,程序设计语言) 文法G的每一个产生式具有下列形式： A 其中，AVN，V*，则称文法G为2型文法或上下文无关文法，记为CFG。2型文法相应的语言称为2型语言或上下文无关语言，它的识别系统是下推自动机。2型文法是可判定的，而且有有效的判定方法。 大部分程序设计语言的文法近似于2型文法，因此2型文法是我们的主要研究对象。,43型文法与3型语言(对应有限自动机) 文法G的每个产生式具有下列形式： Aa或AaB 其中，A、BVN，aVT*，则文法G称为3型文法、正规文法或右线性文法，记为RG。3型文法相应的语言为3型语言或正规语言，它的识别系统是有限自动机。 程序设计语言的单

14、词通常都可写成3型文法的形式，因此3型文法（或自动机）与词法分析有密切关系。 3型文法还可以呈左线性形式： Aa或ABa,5四类文法的关系与区别 由四类文法的定义可知，从0型文法到3型文法逐渐增加限制。13型文法都属于0型文法，2、3型文法均属于1型文法，3型文法属于2型文法。四类文法的区别如下： (1)1型文法中不允许有形如“A”的产生式存在，而2、3型文法则允许形如“A”的产生式存在； (2)0、1型文法的产生式左部存在含有终结符号的符号串或两个以上的非终结符，而2型和3型文法的产生式左部只允许是单个的非终结符号。,给定一个文法，如何判断其属于何种文法？通常我们判断是按照3型文法、2型文法

15、、1型文法、0型文法从高到低的顺序来判断。 例如：一旦判断给定文法属于3型文法之后，就没有必要再判断是否属于2型文法了，因为它必定属于2型文法。我们应该以最高规则来判定一个文法属于的文法类型，其他情况依次类推。只有当我们不属于3型文法时，我们才向下判断，它是否属于2型文法，若不属于2型文法，则依次类推向下判断。最终的结果如果不属于3型文法、 2型文法以及1型文法，那就只有属于0型文法了。,例3.3试判断下列产生式集所对应的文法和产生的语言： (1)SACaB (2)SaSBC (3)SAc (4) SaS CaaaC SaBC SSc SaA CBDB CBDB Aab AbA CBE DBD

16、C AaAb AbB aDDa DCBC BcB ADAC aBab Bc aEEa bBbb AE bCbc cCcc,解答 由四类文法的定义与区别可知，14分别为03型文法。 (1) 该0型文法产生的0型语言为L0(G)=a2nn0。例如：当n=2时，句子a22= aaaa是通过下列推导得到的：,(2) 该1型文法产生的1型语言为 L1(G)=anbncnn1。 例如，当n=2时，句子a2b2c2=aabbcc是通过下列推导得到的：,(3) 该2型文法产生的2型语言为 L2(G)=anbncmm、n1。 例如当n=2、m=3时，句子a2 b2 c3=aabbccc是通过下列推导得到的：,(

17、4) 该3型文法产生的3型语言为 L3(G)=ambnckm、n、k1。 例如当m=2、n=3、k=4时，句子a2b3c4=aabbbcccc是通过下列推导得到的：,由例3.3可知：anbncnn1 anbncmm、n1 ambnckm、n、k1，这说明对文法规则定义形式的限制虽然加强了，但相应的语言反而更大了。因此，不能主观认定文法限制越大则语言越小，也即下述结论是不成立的： 3型语言 2型语言 1型语言 0型语言 在编译方法中，通常用3型文法来描述高级程序语言的词法部分，然后用有限自动机FA来识别高级语言的单词；利用2型文法来描述高级语言的语法部分，然后用下推自动机PDA来识别高级语言的各

18、种语法成分。,例3.4 给出字母表=a,b上的同时只有奇数个a和奇数个b的所有字符串集合的正规文法。 解答 为了构造字母表=a,b上同时只有奇数个a和奇数个b的所有字符串的正规表达式，我们画出如图32所示的DFA，即由开始符S出发，经过奇数个a到达状态A，或经过奇数个b到达状态B。再由状态A出发，经过奇数个b到达状态C(终态)；同样，由状态B出发，经过奇数个a到达终态C。,图32 例3.4的DFA,由图32可直接得到正规文法GS如下： GS: SaAbB AaSbCb BbSaCa CbAaB,3.1.3 正规表达式与上下文无关文法 1正规表达式到上下文无关文法的转换 正规表达式所描述的语言结

19、构均可以用上下文无关文法描述，反之则不一定。由正规表达式构造上下文无关文法的一种方法如下： (1) 构造正规表达式的NFA； (2) 若0为初始状态，则A0为开始符号； (3) 如果存在映射关系f(i, a)= j，则定义产生式 Ai aAj； (4) 如果存在映射关系f(i, )= j，则定义产生式 Ai Aj； (5) 若i为终态，则定义产生式 Ai 。,例3.5 用上下文无关文法描述正规表达式(ab)*abb。 解答 首先构造识别正规表达式(ab)*abb的NFA M如图33所示。 由构造上下文无关文法的方法得到上下文无关文法GA0如下： GA0: A0aA0bA0aA1 A1bA2 A

20、2bA3 A3,事实上，由正规表达式构造上下文无关文法还可以采用另一种方法，即通过分析正规表达式的特性凭经验直接构造。如可把(ab)*abb看作由(ab)*和abb两部分组成，第一部分是由0个或若干个a和b组成的字符串，而第二部分则仅由abb字符串组成，由此得到上下文无关文法GA0如下： GA0: AHT HaHbH Tabb,图33 例3.5的NFA M,2正规表达式与上下文无关文法描述的对象 上下文无关文法既可以描述程序语言的语法，又可以描述程序语言的词法，但基于下述原因，应采用正规表达式描述词法： (1) 词法规则简单，采用正规表达式已足以描述； (2) 正规表达式的表示比上下文无关文法

21、更加简洁、直观和易于理解； (3) 有限自动机的构造比下推自动机简单且分析效率高。,贯穿词法分析和语法分析始终如一的思想是：语言的描述和语言的识别是表示一个语言的两个不同的侧面，二者缺一不可。用正规表达式和上下文无关文法描述语言时的识别方法(即自动机)不同。通常，正规表达式适合于描述线性结构，如标识符、关键字和注释等；而上下文无关文法则适合于描述具有嵌套(层次)性质的非线性结构，如不同结构的语句if-else、while等。,3.2 推导与语法树,3.2.1 推导与短语 1规范推导 在3.1.1节中，所给句子i+i*i推导序列中的每一步推导都是对句型中的最右非终结符用相应产生式的右部进行替换，

22、这样的推导称为最右推导。如果每一步推导都是对句型中的最左非终结符用相应产生式的右部进行替换，则称为最左推导。,从一个句型到另一个句型的推导过程并不是惟一的，为了对句子的结构进行确定性分析，我们往往只考虑最左推导或最右推导，并且称最右推导为规范推导。规范推导的逆过程便是规范归约。,例如句子i+i*i按文法(3.1)的最左推导是,例如,假定有文法 G:N D|ND D 0|1|2 则下面的推导都是规范推导: N D N ND N ND N2 D2 22 而下面的推导都不是规范推导: N ND NDD N ND DD D2 22,每个句子都有规范推导，而且通常是唯一的。例如，对上例来说，33这个句子

23、只有下面一种规范推导： N ND N3 D3 33 但对句型来说，也可能没有规范推导。例如，对上例的句型2D和2DD，我们只有下面一种推导，但它们都不是规范的： N ND DD 2D N ND NDD DDD 2DD 我们所感兴趣的是句子，而每个句子都有规范推导，因此可以只考虑规范推导。,2短语 设是文法GS的一个句型，如果有： S A 且 A 则称是句型关于非终结符A的一个短语，或称是的一个短语。特别是有A产生式时，为句型的一个直接短语或简单短语。 短语的两个条件缺一不可。仅有A 未必意味着就是句型的一个短语，还需要有S A这一条件加以限制；也即短语属于该句型的组成部分，不能破坏这种句型结构

24、的限制。,3句柄 一个句型的最左直接短语称为该句型的句柄。注意，一个句型的直接短语可能不只一个，但最左直接短语则是惟一的。如对S A 来说，将句型中的句柄用产生式的左部符号代替便得到新句型A，这是一次规范归约，恰好与规范推导相反。,4素短语 含有终结符的短语，如果它不存在也具有同样性质的真子串，则该短语为素短语。 例如，在E E+E*i中，i、E*i和E+E*i是句型E+E*i的三个短语；其中，i为素短语；E*i虽为短语且含有终结符，但它的真子串i是素短语，故E*i不是素短语；同样E+E*i也不是素短语。,下面考虑定义表达式的一个文法。 G:E E+T | E-T | T T T*F | T/

25、F | F F i | (E) 符号串(T+i)*i-F是文法G的一个句型。对此我们有： 短语8个： 1. (T+i)*i-F 2. (T+i)*i 3. (T+i) 4. T+i 5. T 6. 第一个i 7. 第二个i 8. F,下面考虑定义表达式的一个文法。 G:E E+T | E-T | T T T*F | T/F | F F i | (E) 符号串(T+i)*i-F是文法G的一个句型。对此我们有： 简单短语4个： 1. T 2. 第一个i 3. 第二个i 4. F 句柄1个： T,3.2.2 语法树与二义性 1语法树 对程序语言来说，有两个问题需要解决：其一是判别程序在语法上是否正确

26、；其二是句子的识别或分析。在编译方法中，为了便于识别或分析句子而引入了语法树这一重要的辅助工具。语法树以图示化的形式把句子分解成各个组成部分来描述或分析句子的语法结构，这种图示化的表示与所定义的文法规则完全一致，但更为直观和完整。,对文法G=(VT,VN,S,) ，满足下列条件的树称为GS的语法树： (1) 每个结点用GS的一个终结符或非终结符标记； (2) 根结点用文法开始符S标记； (3) 内部结点(指非树叶结点)一定是非终结符，如果某内部结点A有n个分支，它的所有子结点从左至右依次标记为x1、x2、xn，则Ax1x2xn一定是文法GS的一条产生式； (4) 如果某结点标记为，则它必为叶结

27、点且是其父结点的惟一子结点。,相应于一个句型的语法树是以文法的开始符S作为根结点的，并随着推导逐步展开；当某个非终结符被它对应的产生式右部的某个候选式所替换时，这个非终结符所对应的结点就产生出下一代新结点，即候选式中从左至右的每一个符号都依次顺序对应一个新结点，且每个新结点与其父结点之间都有一条连线(树枝)。在一棵语法树生长过程中的任何时刻，所有那些没有后代的树叶结点自左至右排列起来就是一个句型。,图3-4 句子i+i*i的语法树 例如，对下面的文法GE： EE+EE*E(E)i (3.1) 与文法(3.1)的句子i+i*i相应的语法树如图34所示。,在构造语法树时可以发现，一个句型的最左推导

28、及最右推导只是决定先生长左子树还是先生长右子树，句型推导结束时相应的语法树也随之完成，这时已不能看出是先生长左子树还是先生长右子树，所呈现的只是已经长成的这个句子或句型的语法树，这与使用文法规则进行推导是有差异的，即使用文法规则的推导过程是有先后之分的。,因此，一棵语法树表示了一个句型种种可能的(但未必是所有的见下面文法的二义性)不同推导过程，包括最左(最右)推导。如果我们坚持使用最左(或最右)推导，那么一棵语法树就完全等价于一个最左(或最右)推导，这种等价性也包括语法树的每一步生长和推导的每一步展开的这种完全一致性。,2子树和短语 语法树的某个结点连同它的所有后代组成了一棵子树，只含有单层分

29、枝的子树称为简单子树。 子树与短语的关系十分密切，根据子树的概念，句型的短语、直接短语、句柄和素短语的直观解释如下： (1) 短语：子树的末端结点(即树叶)组成的符号串是相对于子树根的短语； (2) 直接短语：简单子树的末端结点组成的符号串是相对于简单子树根的直接短语；,(3) 句柄：最左简单子树的末端结点组成的符号串为句柄； (4) 素短语：子树的末端结点组成的符号串含终结符，且在该子树中不再有包含含有终结符的更小子树。显然，从语法树出发寻找短语、直接短语、句柄和素短语要直观得多。此外，要注意的是子树末端结点组成的符号串是指由该子树根开始向下生长的所有末端结点(即树叶)，该子树的部分末端结点

30、并不是该子树的短语。,图35 E+E*i的语法树,对图35所示的关于句型E+E*i的语法树来说，它有3棵子树，即3个短语，分别为i、E*i和E+E*i；而直接短语、句柄和素短语均为i。 3文法的二义性 文法GS的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。 例如，对文法(3.1)，句子i+i*i存在着两种最左推导或最右推导，所形成的两棵不同的语法树如图36所示。,图36 句子i+i*i的两棵不同语法树,再如，条件语句的文法GS为： GS: Sif B S Sif B

31、S else S SA /*A指其它语句*/ 其中，VN = B,S,A，VT = if , else，则句型 if B if B S else S 所对应的两棵不同语法树见图37。 因此，文法GS是二义性文法。,图37 句型 if B if B S else S 的两棵不同语法树,4文法二义性的消除 一个文法是二义性的，并不说明该文法所描述的语言也是二义性的。也即，对于一个二义性文法GS，如果能找到一个非二义性文法GS，使得L(G)=L(G)，则该二义性文法的二义性是可以消除的。如果找不到这样的GS，则二义性文法描述的语言为先天二义性的。,文法二义性消除的方法如下： (1) 不改变文法中原有

32、的语法规则，仅加进一些语法的非形式规定。如对文法(3.1)，不改变已有的四条规则(即四个产生式)，仅加进运算符的优先顺序和结合规则，即*优先于+，且*、+都服从左结合。这样，对文法(3.1)中的句子i+i*i就只有如图36(a)的惟一一棵语法树。,(2) 构造一个等价的无二义性文法，即把排除二义性的规则合并到原有文法中，改写原有的文法。 例如，我们可以将文法(3.1)改写为无二义性的文法G E如下： GE: EE+TT TT*FF F(E)i 此时，句子i+i*i就只有如图38所示的惟一一棵语法树。,图38 句子i+i*i的语法树,例3.6 试将如下的二义性文法GS的二义性消除: GS: Si

33、f b Sif b S else SA 解答 消除GS的二义性可采用如下两种方法： (1) 不改变已有规则，仅加进一项非形式的语法规定：else与离它最近的if匹配(即最近匹配原则)，这样，文法GS的句子if b if b A else A只对应惟一的一棵语法树(见图39)。,(2) 改写文法GS为GS: SS1S2 S1if b S1 else S1A S2if b Sif b S1 else S2 这是因为引起二义性的原因是if-else语句的if后可以是任意if型语句，所以改写文法时规定if和else之间只能是if-else语句或其它语句。这样，改写后文法GS的句子if b if b A else A只对应惟一的一棵语法树(如图310所示)。,图39 复合if语句的语法树,图310 GS的复合if语句的语法树,我们总希望一个文法是无二义性的，这样，句子的分析可以按惟一确定的方式进行。但是，文法的二义性是不可判定的，即不存在一种算法，能够在有限步内判定一个文法是否为二义性的。有时候，二义性文法也可带来一定的好处，如语法分析中二义性文法的应用。,