上下文无关课件

1、第四章文法与语法分析本章主要内容(Chapter 4)4.1 语法分析程序概述4.2 上下文无关文法4.3 递归下降法自顶向下分析4.4 LL分析方法自顶向下分析4.5 LR方法自底向上分析4.6 LR分析分析器的生成器4.7 语法错误处理4.1 语法分析程序概述1） 语法分析器的功能 根据文法规则，从源程序单词符号串中识别出语法成分，并进行语法检查。 基本任务：识别符号串S是否为某语法成分4.1 语法分析程序概述2） 语法分析器的输入语法分析器的输入是语法分析器的输出，即Token序列或者称Token流。4.1 语法分析程序概述3） 语法错误类别及关键性错误a. 程序的开始单词错，表达式的开

2、始单词错，语句的开始单词错，表达式的后继单词错，语句的后继单词错b. 标识符和常量单词错c. 括号类错误d. 分隔符错（最关键性错误）4.1 语法分析程序概述4） 语法错误处理语法错误纠正语法错误信息输出a. 插入b. 删除c. 修改4.2 上下文无关文法当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。1） 上下文无关文法的概念（谈谈什么是文法）以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则来说明句子的组成结构，比如汉语句子可以描述为：由主语后接谓语构成，构

3、成谓语的是动词和直接宾语我们采用BNF来表示这种句子的构成规则：句子=主语谓语主语=代词名词代词=我你他名词=王明大学生工人英语谓语=动词直接宾语动词=是学习直接宾语=代词名词 4.2 上下文无关文法1）上下文无关文法的概念（谈谈什么是文法）有了一组规则以后，按照如下方式导出句子：开始去规则中找=左端的带有句子的规则并把它由=右端的符号串代替，那么这个过程一种可能为在页底所示：句子=主语谓语主语=代词名词代词=我你他名词=王明大学生工人英语谓语=动词直接宾语动词=是学习直接宾语=代词名词 句子 主语谓语 代词谓语我谓语我动词直接宾语 我是直接宾语我是名词我是大学生结论：文法是一组规则，用以定义

4、语言的语法结构4.2 上下文无关文法1）上下文无关文法的概念（上下文无关文法数学定义） 上下文无关文法G定义为四元组(VN，VT，P，S )其中：VN为非终结符号(或语法实体，或变量)集；VT为终结符号集；P为产生式(也称规则)的集合； 具有如下形式： AX1X2Xn，A为VN ，Xi为（VN VT） 。 S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。VN和VT不含公共的元素，即VN VT = 4.2 上下文无关文法1）上下文无关文法的概念（举例1）例1 文法G=（VN，VT，P，S）VN = S , VT = 0, 1 P=S0S1, S01 S为开始符号注：

5、 1.产生式左部相同时可以进行合并：如：S, S， S 可以写作S 例1中的P可以写成如下形式：P= S0S1014.2 上下文无关文法1）上下文无关文法的概念（举例2）例2 文法G=（VN，VT，P，S）VN =I，T，DVT =a,b,c,x,y,z,0,1,9P=IT IT ID， Tab|z|A|B|Z， D09， S=I2.习惯表示 大写字母：非终结符小写字母：终结符 开始符号和文法的名字写在一起：如GS注： 4.2 上下文无关文法1）上下文无关文法的概念（简写的例子）例3GS： SaSb Aab |aAb |例4GS：S ABA Ax | yB z4.2 上下文无关文法1） 上下文

6、无关文法的概念（推导的定义）直接推导“”的定义: A是文法G的产生式， 则有A , 读作A 直接推导到 也称直接归约到A 推导的定义(直接推导的定义)例5：G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S14.2 上下文无关文法1）上下文无关文法的概念（推导的定义） 推导的定义(多步推导的定义) 若存在v w0 w1 . wn=w,(n0) 则记为v =+ w，v推导出w，或w归约到v 若有v =+ w，或v=w，则记为v =* w例6：G：S0S1， S01 0S1 00S11 00S11 000S111 000S111 0

7、0001111 S 0S1 00S11 000S111 00001111 S =+ 00001111 S =* S 00S11 =* 00S114.2 上下文无关文法 推导的定义(最左和最右推导)最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型。1）上下文无关文法的概念（推导的定义）4.2 上下文无关文法1）上下文无关文法的概念（句型、句子的定义） 句型、句子的定义句型有文法G，若S =* x，则称x是文法G的句型。句子有文法G，若S =* x，且xVT*，则称x是文法G的句子。例7：G： S0S1，

8、 S01 S 0S1 00S11 000S11100001111 G的句型S,0S1 ,00S11 ,000S111,00001111 G的句子00001111, 014.2 上下文无关文法1）上下文无关文法的概念（文法生成的语言）由文法G生成的语言记为L(G),它是文法G的一切句子的集合: L(G)=x|S =* x，其中S为文法的开始符号，且x VT* 文法生成的语言例8：G： S0S1， S01L(G)=0n1n|n14.2 上下文无关文法1）上下文无关文法的概念（文法的等价） 文法的等价若L（G1）=L（G2），则称文法G1和G2是等价的。例9如文法G1A：A0R A01 RA1 与G

9、2S：S0S1 S01表达的语言是相同的，所以有G1与G2是等价的4.2 上下文无关文法2） 文法的类型（四种类型的定义）对产生式施加不同的限制，Chomsky将文法分为四种类型：0型文法：对任一产生式，都有(VNVT)+， (VNVT)*1型文法：对任一产生式，都有|， 仅仅 S除外2型文法：对任一产生式，都有VN ， (VNVT)*3型文法：任一产生式的形式都为AaB或Aa，其中AVN ，BVN ，aVT4.2 上下文无关文法1型文法（上下文有关文法）：产生式的形式为1A212，即只有A出现在1和2的上下文中时，才允许取代A。其识别系统是线性界限自动机。 2型文法（上下文无关文法CFG）：

10、产生式的形式为A，取代A时与A的上下文无关。其识别系统是不确定的下推自动机。 3型文法（正规文法RG）：产生的语言是有穷自动机（FA）所接受的集合2） 文法的类型（四种文法产生式的形式）4.2 上下文无关文法0型文法1型文法2型文法3型文法四种文法之间的关系是：包含关系.（原因：将产生式做进一步限制而定义的。）2） 文法的类型（四种类型文法包含关系）4.2 上下文无关文法例10：1型（上下文有关）文法 文法GS： SCDAbbA CaCABaaB CbCBBbbB ADaDC BDbDD AabD2） 文法的类型（1型文法举例）4.2 上下文无关文法例11：2型（上下文无关）文法 文法GS：S

11、ABABS|0BSA|1例12：3型(正则（或正规）文法)文法 文法GS：S0A|1B|0 A0A|1B|0S B1B|1|02） 文法的类型（2型和3型文法举例）4.2 上下文无关文法 a. 0型文法产生的语言称为0型语言 b. 1型文法或上下文有关文法（ CSG ）产生的语言称为1型语言或上下文有关语言（CSL） c. 2型文法或上下文无关文法（ CFG ）产生的语言称为2型语言或上下文无关语言（ CF L ） d. 3型文法或正则（正规）文法（ RG ）产生的语言称为3型语言正则（正规）语言（ RL ） 2） 文法的类型（四种类型文法产生的语言）4.2 上下文无关文法 0型文法（短语结构

12、文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的 带 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an 控制器磁头任何能用图灵机描述的计算都能机械实现，任何能在现代计算机上实现的计算都能用图灵机描述2） 文法的类型（0型文法和图灵机）4.2 上下文无关文法3） 正规语言、正规式与有限自动机的表达能力 正规语言、正规式与有限自动机FA的表达能力是相同的。即: a. 如果存在一个正规语言、其表达的语言为L（G），则一定存在表达能力相同的正规式和有限自动机FA。 b. 如果存在一个正规式、其表达的语言为L（r），则一定存在表达能力相同的正规语言

13、和有限自动机FA。 c. 如果存在一个有限自动机、其表达的语言为L（M），则一定存在表达能力相同的正规语言和正规式。且L(G)=L(r)=L(M)且L(G)=L(r)=L(M)且L(G)=L(r)=L(M)4.2 上下文无关文法有穷自动机NFA M 这样构造： = VT K= VN N, N为一个新状态,它不在VN中 A=S Z=N 对G中的形如 DtB的产生式,t为终结符或,有f(D,t)=B； 对G中形如Dt的产生式， t为终结符或,有f(D,t)=N; 对VT中的每一个a ,有f(N,a)=设G=（VN，VT，P，S）是正规文法，则存在一个有穷自动机 M=(K, , f, A, Z)，使

14、得L(M)=L(G)3） 正规语言、正规式与有限自动机的表达能力(续)4.2 上下文无关文法G 的构造： VT = VN= K S = A 若 f(D,t)=B ，则DtB在P中 若 f(D,t)=B ，且B在Z中，则Dt在P中已知一有穷自动机M= (K, , f, A, Z),存在有一个3型文法G = （VN，VT，P，S）,使得L(G)=L(M)3） 正规语言、正规式与有限自动机的表达能力(续)4.2 上下文无关文法对上的正规式r ,存在一个RG=(VN,VT,P,S)：L(G)=L(r) VT= ,S VN ，生成正规产生式 Sr (R 1) 对形如 Ar1r2的正规产生式：Ar1B B

15、r2 BVN (R 2)对形如Arr1的正规产生式： ArB Ar1 BrB Br1 BVN (R 3)对形如Ar1r2的正规产生式: Ar1 A r2 不断应用R做变换，直到每个产生式右端至多有一个VN3） 正规语言、正规式与有限自动机的表达能力(续)4.2 上下文无关文法4）上下文无关文法的语法树 上下文无关文法产生式形式为：A ，它表示不管A的前后是 什么，都可以把A用替换。 语法树-句型推导的直观表示 上下文无关文法有足够的能力描述程序设计语言的语法结构， 所以我们在本章研究上下文无关文法。4.2 上下文无关文法4）上下文无关文法的语法树（续）设G=( VN,VT,P,S)为一cfg，

16、若一棵树满足下列4个条件，则此树称作G的语法树(推导树)(派生树）：1. 每个结点都有一个标记，此标记是V的一个符号2. 根的标记是S3. 若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定AVN4. 如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式语法树的结果：从左到右读出叶子的标记而构成的行谓之语法树的结果。 语法树的定义 4.2 上下文无关文法 语法树的例子 4）上下文无关文法的语法树（续） 例13: GS:SaASASbAASSSaAba句子aabbaa的语法树（推导树） S a A S

17、 S b A a a b a句子aabbaa推导过程：S aAS aSbAS aabAS aabbaS aabbaa4.2 上下文无关文法 语法树的有关结论 给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树(推导树)。若G为上下文无关文法，对于，有S =* ，当且仅当文法G有以为结果的一棵语法树(推导树)。4）上下文无关文法的语法树（续） S a A S S b A a a b a4.2 上下文无关文法推导过程中施用产生式的顺序4）上下文无关文法的语法树（续） 例14: GS:SaASASbAASSSaAbaSaASaAaaSbAaaSbbaaaabbaaSaASa

18、SbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。最左（右）推导：4.2 上下文无关文法二义文法的定义5）二义文法二义文法的定义 a. 若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的 b. 或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的 4.2 上下文无关文法5）二义文法（二义文法的例子）例15GE:E E + E | E * E | (E ) | E | idE E * E E E + E id * E E * E

19、 +E id * E + E id * E + E id * id + E id * id + E id * id + id id * id + id二义文法的例子EEE*+EEidididEEidE*+EEidid4.2 上下文无关文法5）二义文法（二义文法的相关结论）判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题都是递归不可解的，但可以为无二义性寻找一组充分条件。二义文法的相关结论文法的二义性和语言的二义性是不同的概念可能有两个不同的文法G和G，这两个文法所产生的语言是相同的，但G为二义的，而G 是无二义的。4.2 上下文无关文法5）二义文法（二

20、义文法改造为无二义文法）GE: E i GE：E T|E+TE E+E T F|T*FE E*E F （E）|iE (E) 规定优先顺序和结合律二义文法改造为无二义文法 如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。4.2 上下文无关文法6）文法分析算法1) 令S_Lambda=Aj|Aj ；确定可推导出空串的非终极符对每个产生式p:Ap X1Xn,若X1Xn S_Lambda,则Ap并入S_Lambda；重复第2）步，直到S_Lambda收敛，此时的S_Lambda即为可推导出

21、空串的非终极符集。问题：哪些非终极符可以推导出空串？A + 例16：文法GS：SAa|bB|c AAa|bB| BAB|b|c S_Lambda=A4.2 上下文无关文法6）文法分析算法（续）First()=a VT| *a (if * then else )First集注：表示符号串，可以为非终极符和终极符组成的任意串，即 （VN VT） *。例17：文法GS：SaA|Bb|c AAa|bB| |B BaB|b|c First(S)=a, c, b, First(A)=b,a,c,First(B)=a,b,c4.2 上下文无关文法6）文法分析算法（续）Follow(A)=a VT|S *Aa

22、 (if S*A then # else )注：A为非终极符，即A VN 。Follow集例18：文法GS：SaA|Bb|c AAa|bB| |B BaB|b|c Follow(A)=#,a, Follow(B)=b,#4.2 上下文无关文法6）文法分析算法（续）Predict(A )=First() ，当First()不含时First()- Follow(A),当First()包含时注：A 为产生式。Predict集例19：文法GS：SaA|Bb|c AAa|bB| |B BaB|b|c Predict(BaB)=a, 因为First(aB)=a Predict(AAa)=#, b,a,c,

23、 因为First(Aa )=b,a,c, Follow(A)=#,a4.2 上下文无关文法7）语法分析方法（概述）语法分析的含义识别一个符号串是否为某文法的句型，是语法树的构造过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。从左到右的分析算法：即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。例20：文法G：S cAd A ab A a识别输入串w=cabd是否为该文法的句子4.2 上下文无关文法7）语法分析方法（分类）自顶向下分析法：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配

24、的推导。分析算法分类自底向上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。4.2 上下文无关文法自顶向下的分析方法语法树的构造过程例21：文法G：S cAd A ab A a识别输入串w=cabd是否为该文法的句子S S S c A d c A d a b推导过程：S cAd cAd cabd 7）语法分析方法（自顶向下分析方法）要点：由根向下构造语法树构造最左推导推导出的终结符是否与当前输入符匹配 S ABA aA | B b | bBaaab.S AB S AB aAB A aA aaAB A aA aaaAB A aA aaa B A aaab B b4.2 上下文无

25、关文法7）语法分析方法（自顶向下分析方法要点） S aaab A B a A b a A a4.2 上下文无关文法例22：文法G： S cAd A ab A a识别输入串w=cabd是否该文法的句子自底向上的分析方法语法树的构造过程SAA c a b d c a b d c a b d 规约过程构造的推导： cAd cabd S cAd7）语法分析方法（自底向上分析方法）4.2 上下文无关文法两种方法反映了两种语法树的构造过程自顶而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串。自底而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上地构

26、造语法树。7）语法分析方法（可能遇到的问题）4.2 上下文无关文法自顶向下的分析方法可能遇到的问题若S cAd 后选择(3)，则得到S cAd cad那将会？ w的第二个符号可以与叶子结点a得以匹配，但第三个符号却不能与下一叶子结点d匹配？宣告分析失败（其意味着，识别程序不能为串cad构造语法树，即cad不是句子）-显然是错误的结论。导致失败的原因是在分析中对A的选择不是正确的。 S c A d a7）语法分析方法（续）4.2 上下文无关文法对串cabd的分析中，如果不是选择ab用产生式(2),而是选择a用产生式(3)将a归约到了A，那么最终就达不到归约到S的结果，因而也无从知道cabd是一个

27、句子。自底向上的分析方法可能遇到的问题c a b dc A b d a7）语法分析方法（可能遇到的问题）4.3 递归下降法自顶向下分析1）递归下降法分析原理递归下降法的优缺点优点：简单，易于实现，可自动生成。缺点：1）频繁调用子程序，降低分析速度。2）对文法限制较严格。递归下降法的原理对非终极符，按其产生式结构产生相应的语法子程序，对其中的终极符：产生匹配命令，对其中的非终极符，产生调用命令。子程序结构与文法的产生式结构几乎是一致的，文法递归则子程序也递归，所以称该方法为递归下降法。4.3 递归下降法自顶向下分析1）递归下降法分析原理(续)递归下降法示例一例23：文法G： VN =Stm,Ex

28、p VT =while,do P=Stm while Exp do Stm S=Stm对应语法分析程序可如下：begin Match(#while); Exp; Match(#do); Stm end4.3 递归下降法自顶向下分析1）递归下降法分析原理（续）递归下降法示例二例24：文法G： VN =Z，B VT =a,b,c P=Z aBa, B bB|c S= Z对应语法分析程序可如下： procedure Z;begin Match(a) end procedure B;begin case token of b:begin Match(b);B end; c:begin Match(c)

29、; end; -:Error() end; begin ReadToken; Z end 4.3 递归下降法自顶向下分析1）递归下降法分析原理（续）递归下降法要考虑的主要问题1.当一非终极符有多个产生式时，如何保证唯一地确定其中一个产生式？2.如果非终极符有空产生式（ A ），怎么办？例25：文法G： S cAd A ab A a A 识别输入串w=cabd是否该文法的句子4.3 递归下降法自顶向下分析1）递归下降法分析原理（续）解决办法1.对文法进行限制，使得对每一个输入符，文法最多有一个产生式被选择。此时每个非终极符全部产生式满足条件：Predict(Ak) Predict(Aj) 2.对

30、于当前输入符a，选择产生式A k的条件是：a Predict(Ak) 例26：文法G： S cAd A ab A a A 识别输入串w=cabd是否该文法的句子例27：文法G： S cAd A ab A b A 识别输入串w=cabd是否该文法的句子4.3 递归下降法自顶向下分析1）递归下降法分析原理（续）递归下降分析法的条件递归下降法对文法有一定要求，即，每个非终极符全部产生式满足条件：Predict(Ak) Predict(Aj) 其中Ak与A j是A的任意两条产生式实际程序设计语言中，文法不满足上述条件的主要有两种情形：1.某个非终极符A有如下产生式： A ，A 即有公共前缀。2.某个非

31、终极符A有如下产生式： A A，即有直接左递归。怎么办？消除公共前缀，消除左递归。4.3 递归下降法自顶向下分析2）消除公共前缀消除公共前缀的步骤A ，A A （）A AA 4.3 递归下降法自顶向下分析2）消除公共前缀消除公共前缀例子例28：文法GStm： Stm id:=Exp Stm id(ExpL) ExpL Exp ExpL Exp,ExpL消除公共前缀后为： Stm id Stm Stm :=Exp Stm (ExpL) ExpL Exp ExpL ExpL ,ExpL ExpL 4.3 递归下降法自顶向下分析3）消除左递归消除直接左递归的步骤A A，非，不以P打头A A，A A|

32、 4.3 递归下降法自顶向下分析2）消除左递归（续）消除直接左递归的例子例29 已知GE： E T*F | T/F | F T F | T*F | T/F 解：左递归改为右递归得： E T*F | T/F | F T FT T *FT | /FT | 4.3 递归下降法自顶向下分析2）消除左递归（续）1.把G的非终结符整理成某种顺序A1，A2，An ，使得： A1 1|2|k A2 A1 r A3 A2u | A1v. . 2. For i:=1 to n do begin for j :=1 to i-1 do 把每个形如AiAjr的规则替换成 Ai (1|2|k) r 其中Aj 1|2|k

33、是当前全部Aj 的规则 消除Ai规则中的直接左递归 end 3.化简由2得到的文法即可。间接左递归直接左递归消除直接左递归消除一般左递归步骤4.4 LL分析方法自顶向下分析1）概述 LL（k）分析方法是自顶向下分析方法LL（k）是一类分析方法，其中的k表示向前看k个符号的意思。我们重点学习LL（1）分析方法。 LL（1）方法是递归下降法的区别1.递归下降法对每个非终极符产生子程序，而LL（1）方法产生LL分析表。2.递归下降法能判断每个产生式的结束，而LL（1）方法不能。3.递归下降法不用符号栈，而LL（1）方法用符号栈。4.4 LL分析方法自顶向下分析2）LL（1）文法 LL（1）分析方法的

34、焦点问题在LL（1）分析方法中，每当在符号栈的栈顶出现非终极符时，要决定用哪个产生式的右部进行该非终极符的替换。 LL（1）文法对文法G，如果G中任意非终极符A，其任意两个产生式都满足如下条件：Predict(Ak) Predict(Aj) 则称文法G为LL（1）文法。如果文法G中没有空产生式，则要求G中任意非终极符A，其任意两个产生式的右部都满足条件：First(k) First(j) 4.4 LL分析方法自顶向下分析3）LL（1）分析表 LL（1）分析表构造方法1.对文法G的每个产生式 执行第二步和第三步；2.对每个终结符aFIRST()，把 加至A,a中；3.若 FIRST()，则对任何bFOLLOW(A)把 加至A,b中；4.把所有无定义的A,a标上“出错标志”。注：可以证明，一个文法G