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

第五章 自底向上分析方法 主要内容 自底向上分析的基本思想 简单优先分析方法 LR类分析方法 例：S ? aAcBe [1] A ? b [2] A ? Ab [3] B ? d [4] 输入流：abbcde。 规范推导过程为： 5.2 简单优先分析 一种shift-reduce分析方法 根据文法符号的优先关系确定句柄 文法符号的优先关系的确定 文法优先关系的确定 FIRST(W) ={S | W ?+ S…，S?(VN?VT)} LAST(W) ={S | W ?+ …S，S?(VN ?VT)} 若有U?…SiSj…: 则有Si ? Sj ; 若有U?…SiW…:任Sj?FIRST(W),有Si ? Sj 若有U?…VW…:任Si?LAST(V), Sj?(FIRST(W) ?{W})则有Si ? Sj 输入流的开始和结束标志 ‘＃’，文法的开始符为Z， S?FIRST(Z),有# ? S，; 且＃ ? Z S?LAST(Z)，有S ? #，; 且Z ? ＃ 优先关系矩阵 一个文法的全部优先关系可以用矩阵来表示，称作优先关系矩阵。 例： 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一定是该句型的简单短语。 结论： ?用来确定句柄的头； ?用来确定句柄的内部； ?用来确定句柄的结束。 简单优先分析算法要点 找第一个使Sj?Sj+1的Sj。 从Sj开始往前(左)找第一个使Si-1?Si的Si。 用SiSi+1…Sj去查产生式的右部，并用相应的左部符号代替句柄SiSi+1…Sj (归约) 。 重复上述过程，直至输入符结束。如果归约出文法的开始符号则成功。否则失败。 简单优先分析实例 活前缀的描述性定义：形成可归前缀之前，包括可归前缀在内所有规范句型的前缀都称为活前缀。 活前缀 为一个或若干规范句型的前缀。 在规范归约过程中的任何时刻已分析过的部分，即在分析栈（符号栈）中的符号串均为规范句型的活前缀，表明输入串的已被分析过的部分是该文法某规范句型的一个正确部分。 线性正则式状态机－LRSM 线性正则式：不含*符号的正则表达式 LRSM：(Linear Regular States Machine) (1)从LRSM可构造出恰好接受给定所有正 则式的确定自动机DA； (2)从LRSM的终止状态可判定接受的是哪 个正则式； (3)从LRSM的状态可判定一个正则式是不 是另一正则式的前缀。 项目：假设??[P]是一个正则式，则我们称形如???[P]的表示为项目，其中P是正则式编号。其中黑点可出现于任何位置上。 项目集：用IS表示 IS(X) ： SubItems(IS,X)= {?X??[P]|??X?[P]?IS,X?SymbSet} 简记为IS(X) 线性正则式到LRSM的构造 给定正则式集{?1,?2,…?n}： ■构造初始项目集IS0={??1[1],...,??n[n]}，并给IS0标上NO(表示未处理）。 ■从已构造的LRSM部分图选择被标为NO的任一项目集ISi，并做下面动作： [1] 对每个符号X?SymbSet： 若ISiX非空，给ISiX标上NO，并在ISi和ISiX之间 画有向X边:ISi → ISiX。 [2] 给ISi标上OK。 ■ 重复上述步骤二，直至在LRSM中没有被标记为NO的 状态（项目集）节点为止。 LRSM的性质 展望符：Lookup(S) 有效前缀集 Prefix(S) 状态Si中的项目???[P]表示?部分已被输入，而且是Si的前缀的后缀，?表示待输入部分。 可构造接受给定正则式集合的DA 严格前缀：某状态中既含有定位点在尾处的项目又含有定位点不在尾处的项目，则一个正则式是另一个正则式的严格前缀。 派生定理 开始符产生式的右部是归约活前缀。 如果?A?是归约活前缀，且A→?是产生式， 则??也是归约活前缀。 任何归约活前缀，都可按上述方式被派生。 设文法开始符的产生式是： S →?1|?2|…|?n RPSG={?1,…,?n}?{??|?A??RPSG,A→??P} 例有文法G[S]: S → aAc[1] A → Abb[2] A → b[3] LR(0)项目：若A→??