第五章语法分析-自底向上分析方法详解.ppt

第五章 自底向上分析方法;基本思想 从待分析的符号串开始，自左向右进行扫描，自下而上进行分析，通过反复查找当前句型的句柄，并使用产生式规则将找到的句柄归约为相应产生式的左部非终极符，直到将输入串归约为文法的开始符。(移入-归约分析) 两种分析方法 简单优先和LR类分析方法;例：S ? aAcBe [1] A ? b [2] A ? Ab [3] B ? d [4] 输入流：abbcde。 规范推导过程为： ;5.2 简单优先分析;简单优先分析中的三种关系;文法优先关系的确定; 例： Z ? bMb M ? a M ? (L L ? Ma);定理： 设X1…XiXi+1…Xj…Xn是一个句型，若有 Xi ?Xi+1 ?Xi+2 ?… ?Xj-1 ?Xj ?Xj+1 则Xi+1Xi+2…Xj-1Xj一定是该句型的简单短语。 结论： ?用来确定句柄的头； ?用来确定句柄的内部； ?用来确定句柄的结束。 ;简单优先分析算法要点;简单优先分析实例;规范句型：用最右推导导出的句型(也称右句型）。 规范前缀：若存在规范句型??，且?是终极符串或空串，则称?为规范前缀。 规范活前缀：若规范前缀?不含句柄或含一个句柄并且具有形式?=???(?是句柄)，则称规范前缀?为规范活前缀(简称活前缀）。 归约规范活前缀：若活前缀?是含句柄的活前缀，即有?=???，且?是句柄，则称活前缀?为归约规范活前缀（简称归约活前缀）。;活前缀的描述性定义：形成可归前缀之前，包括可归前缀在内所有规范句型的前缀都称为活前缀。 活前缀 为一个或若干规范句型的前缀。 在规范归约过程中的任何时刻已分析过的部分，即在分析栈（符号栈）中的符号串均为规范句型的活前缀，表明输入串的已被分析过的部分是该文法某规范句型的一个正确部分。;线性正则式状态机－LRSM;项目：假设??[P]是一个正则式，则我们称形如???[P]的表示为项目，其中P是正则式编号。其中黑点可出现于任何位置上。 项目集：用IS表示 IS(X) ： SubItems(IS,X)= {?X??[P]|??X?[P]?IS,X?SymbSet} 简记为IS(X) ;假设有线性正则项集: IS = {?abd[1],?abc[2],?bc[3],de?[4], de?c[5]}, 则有 ：;线性正则式到LRSM的构造;a;LRSM的性质;派生定理; 例有文法G[S]: S → aAc[1] A → Abb[2] A → b[3] ; LR(0)项目：若A→??是产生式， 则称A→???为LR(0)项目(简称项目），也 写作???[p]形式。 项目集的投影：假设IS是LR(0)项目集，则 称下面IS(X) 为IS关于X的投影集： IS(X) = {A→?X?? |A→??X??IS, X?(VT?VN)}. 项目集的闭包：假设IS是LR(0)项目集，则 称下面CLOSURE(IS)为IS的闭包集： CLOSURE(IS)= IS ? {A→?? | Y→??A??CLOSURE(IS) A→?是产生式 } ;两个重要的性质; 若有 ??Prefix(ISi )，Y→??A??ISi ，则 根据性质2—(活前缀状态机的性质）， ?A?是归约活前缀。再根据派生原理，若 A→?是A的产生式，则??也是归约活前缀。 构造LRSM的思想： 如果在状态项目集ISi 中有项目A→??B?， 且B→?是B的产生式，则在ISi 中增加项目 B→??；对于ISi 这个过程继续到不可再扩 充为止。 ;构造LR(0)活前缀状态机LRSM的算法要点 ; 例：构造LR(0)状态机 S ? E $ E ? E + T E ? T T ? id T? ( E );0; LRSM给出了所有的可归活前缀 LRSM中的每个状态将对应一个饱和项目集： （1）其中一部分是由先驱状态分出来 (称为基本项目)； （2）一部分则是由基本项目扩展出来的 (称为扩展项目或派生项目)。派生部 分项目的特点是其中的“?”出现在产 生式右部的最