第四章节7-LR(1)文法.ppt

* * * * * * * * * * * * * * * * * * * * * 主要内容： LR(1)分析方法 Z ? E E ? (L,E) E ? S L ? L,E L ? E S ? id S ? (S) Z ? ?E E??(L,E) E??S S??id S? ?(S) 0 E?(?L,E) S?(?S) L??L,E L??E E??(L,E) E??S S??id S??(S) 1 E?S? S?(S?) 2 ( S ?1(S2, ) ) = {Shift, Reduce3} 即| ?1(S2,) ) | ≤ 1 不成立(Follow(E)={#,),,}) 非SLR(1)文法 LR(0)方法不依赖输入流，直接判定归约，容易出现冲突。 SLR(1)方法简单地把非终极符的follow集做为可归约的依据，并不精确。 一个非终极符在不同的位置上出现，它所允许的后继符是不同的，而SLR(1)没有加以区分。LR(1)针对不同产生式上的非终极符，分别定义其后继符集（展望符集Reducelookup），减少了移入/归约冲突。 任何SLR(1)都一定是LR(1)文法。 1、构造文法的LR(1)自动机 2、由LR(1)自动机构造LR(1)分析表（Action表和 Goto表） 3、根据当前状态和输入符号查分析表确定要执行的操作，进行相应的语法分析 LR(1)分析步骤 LR(1)分析方法 LR(1)方法研究的对象是二元组：(? , b)，其中?是活前缀，而b是一个输入符号。我们称上述(?，b)为LR1前缀模式。 活前缀？ 规范活前缀：若规范前缀?不含句柄或含一个句柄并且具有形式?=???(?是句柄)，则称规范前缀?为规范活前缀(简称活前缀）。 　（前缀中若有句柄，则句柄在前缀的最右端） 物理含义：在归约过程中，若符号栈中的内容为活前缀，则表示到目前为止，语法正确。可以继续进行移入或归约操作。 LR(1)分析方法 LR(1)方法研究的对象是二元组：(? , b)，其中?是活前缀，而b是一个输入符号。我们称上述(?，b)为LR1前缀模式。 如果?是文法的归约活前缀，b是?的合法后继续符，则称(?，b)为LR1归约前缀模式。 归约活前缀？ 移入活前缀：如果活前缀不中不包含简单短语（句柄），则称为移入型活前缀。 　因为此时只能进行移入操作，不能进行归约操作。 归约活前缀：若活前缀?是含句柄的活前缀，即有?=???，且?是句柄，则称活前缀?为归约规范活前缀。 （即含有句柄的规范活前缀。是可以归约的） 不确定活前缀：如果一个活前缀既是移入型的又是归约型的，则称为不确定活前缀。 例： S ? abc S ?ab 则ab既是移入型活前缀，又是归约型活前缀。 LR(1)分析方法 LR(1)方法研究的对象是二元组：(? , b)，其中?是活前缀，而b是一个输入符号。我们称上述(?，b)为LR1前缀模式。 如果?是文法的归约活前缀，b是?的合法后继续符，则称(?，b)为LR1归约前缀模式。 LR1归约前缀的派生定理 假设?0是拓广产生式的右部，#是输入流的结束符，则有： ( ?0[p], # )是LR1归约前缀模式。 设( ?A?[p], b )是LR1归约前缀模式，且A→?是q产生式，则(??[q] , a)也是LR1归约前缀模式，其中a?First(?b)。 派生定理的目的是要求得项目集合的闭包CLOSURE ( IS ) LR(1)项目：[A→???, a ]。LR(0)项目及一个VT?{#}的展望符（输入符）集合。 IS:LR(1)项目集 IS(X):　（目的：产生下一个状态） IS(X) = {[A→?X??,a] |[A→??X?,a]?IS } CLOSURE ( IS ) = IS∪ {[B→??,b] |[A→??B?,a]? CLOSURE(IS), B→?是产生式 , b?First(?a)} 目的：产生派生项目 LRSM1的构造算法 初始项目集： ISS=CLOSURE({ [Z→ ?S,{ # } ]}) 若所有状态都处理完，则结束 选一未处理完状态IS，对所有语法符号 X?（VT?VN?{#}),求ISX,令 IS’ = CLOSURE(ISX)，若IS’不为空： 若IS’为新状态，则增加IS IS’,把IS’加 入LRSM1中；否则为图中某个状态ISj，则在IS 和ISj之间增加一条转换边：IS ISj 转到步骤2 X X 非SLR(1)文法： Z → S S → L=