文法与语法分析(中).ppt

《文法与语法分析(中).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第04章文法与语法分析主要内容：语法分析概述文法进行语法分析的几种方法语法错误处理4.5自底向上分析－LR分析概述自底向上分析的思想和主要问题几种LR分析方法：LR(0)SLR(1)LR(1)LALR(1)主要内容：LR的几个基本概念识别归约活前缀的识别器LR(0)分析算法SLR(1)分析算法4.5.1LR的几个基本概念短语：设S是文法的开始符，是句型(即有S*），如果满足条件：S*AA+则称是句型的一个短语。直接短语（简单短语）：如果满足条件：S*AA则称是句型的一个简单短语。句柄：一个句型可能有多个简单短语，其中最

2、左的简单短语称之为句柄。EE+TTT*FiF(E)F句型:(E)*i+F短语:1.(E)*i+F2.(E)*i3.(E)4.i5.F简单短语：(E),i,F句柄：(E)例：作业：书Page129习题7、8文法G[E]:ET

3、E+TTF

4、T*FF(E)

5、ii(1)*i(2)+i(3)是G的一个句子，（1）画出该句子的语法分析树（2）给出该句子的所有短语，简单短语，句柄4.5.2活前缀规范推导：即最右推导。规范归约：即最左归约。规范句型：用最右推导导出的句型(也称右句型）。规范前缀：若存在规范句型，且是终极符串或空串，则称为规范前缀。活前缀：对个规范前缀，

6、如果：[1]不含简单短语（移入型活前缀）或[2]含一个简单短语，但其后没有符号（归约型活前缀）则称规范前缀为活前缀；它表示符号栈中的内容，即输入串中已被分析过的部分。例：SaAcBe[1]Ab[2]AAb[3]Bd[4]输入流：abbcde。规范推导过程为：逆过程:(分析栈，输入流)(-,abbcde)(a,bbcde)//a为移入活前缀(ab,bcde)//ab为归约活前缀(aA,bcde)//aA为移入活前缀(aAb,cde)//aAb为归约活前缀(aA,cde)//aA为移入活前缀(aAc,de)//aAc为移入活前缀(aAcd,e)//

7、aAcd为归约活前缀(aAcB,e)//aAcB为移入活前缀(aAcBe,-)//aAcBe为归约活前缀(S,-)//S为规范前缀SaAcBe[1]aAcd[4]e[1]aAb[3]cd[4]e[1]ab[2]b[3]cd[4]e[1]4.5.3归约活前缀识别器---LR(0)自动机LR(0)归约活前缀定理：简称派生定理，设增广产生式为[0]S→S，则定理内容如下：[1]S[0]是LR(0)归约活前缀。[2]若αAβ[p]是LR(0)归约活前缀，且[q]Aπ是产生式，则απ[q]也是LR(0)归约活前缀。例，设文法G[S]:[1]S→aAc[2]A→

8、Abb[3]A→b求归约活前缀集如下：aAc[1]aAbb[2]//因为SaAc[1]aAbb[2]c[1]ab[3]//因为SaAc[1]ab[3]c[1]以上结果见上图。123[1]4[3][2]aAbbbcPA自动机：假设产生式[1]Z→A，则可构造如下Z产生式自动机，并记为PA(Z)。GA自动机：假设给定文法G的一组PA自动机：PA(A1),,PA(An)，则按如下方法构造的自动机称为G文法自动机，记为GA(G).[1]将PA(S)的初始状态作为GA(G)的初始状态；[2]连接各PA自动机；[3]把原所有PA(Ai)的终止状态作为GA(G)的终止状态

9、。1.0A1.1例，设文法G[S]:[1]Z→A[2]A→aAa[3]A→b解：PA自动机见右上图；GA自动机见左下图，其确定化后见右下图：1.0A1.12.0aAa2.12.22.33.0b3.11.0A1.12.0aAa2.12.22.33.0b3.1A21aAa345b6baLR(0)项目：若A→是产生式，则称A→为LR(0)项目(简称项目），也写作[p]形式。项目集的投影：假设SS是LR(0)项目集，则称下面nextstates(SS,X)为SS关于X的投影集：nextstates(SS,X)={A→X

10、A→XSS,X(

11、VTVN)}项目集的闭包：假设IS是LR(0)项目集，则称下面CLOSURE(IS)为IS的闭包集：CLOSURE(IS)=IS{A→

12、B→αACLOSURE(IS)A→G}例：假设G[S]:S,DaA,AaB,ABa,Bb，求close({Da·A})。解：close({Da·A})={Da·A,A·aB,A·Ba,B·b}Da·AAA·aBaA·BaBB·bbaDa·AA·aBA·BaB·baAaBaLR(0)项目表示法：有三种模式：A→·（产生式模式）、·[p]（归约号模式