吉林大学：《编译原理》课程教学资源（PPT课件讲稿）派生定理

主要内容 识别规约活前缀的LRSM的构造

主要内容  识别规约活前缀的LRSM的构造

派生定理 开始符产生式的右部是归约活前缀。 ◆如果AB是归约活前缀,且A→π是产生式, 则aπ也是归约活前缀。 任何归约活前缀,都可按上述方式被派生。 设文法开始符的产生式是: S→α1|a2|..|an RPS8={a1,…,anJ∪{aπ|aAβ∈RPS;A→T∈P

派生定理 ◆ 开始符产生式的右部是归约活前缀。 ◆ 如果A是归约活前缀，且A→是产生式， 则也是归约活前缀。 ◆ 任何归约活前缀，都可按上述方式被派生。  设文法开始符的产生式是： S →1|2|…|n RPSG={1,…,n}{|ARPSG,A→P}

&例有文法G[s] s→aAc1 A→Abb2 A→b[3] 可归前缀集: aAc aAbb ab

 例有文法G[s]: S → aAc[1] A → Abb[2] A → b[3] 可归前缀集： aAc aAbb ab

LR(0)项目:若A→aβ是产生式, 则称A→a为.LR(o)项目(简称项目),也 写作α●β[]形式。 项目集的投影:假设S是LR(O项目集,则 称下面lS为|S关于X的投影集: S0=[A→aXB|A→0∈|S, X∈(∪V) 项目集的闭包:假设lS是LR()项目集,则 称下面CL0SURE(S)为|S的闭包集 CLOSURE(|S)=|s∪ [A→bπ|Y→β·An∈CL0SURE(|S) A→是产生式

 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→是产生式 }

两个重要的性质 C归约活前缀的性质:若oAn是归约活前 缀,A→π是产生式,则aπ也是归约活 利。 C活前缓状态机性质:若有 a∈ Prefix(|s;),且A→β·n∈lS;,则 αη是归约活前缀

两个重要的性质  归约活前缀的性质：若A是归约活前 缀，A→是产生式，则也是归约活 前缀。  活前缀状态机性质：若有 Prefix(ISi )，且A→•ISi ，则 是归约活前缀

令若有 c∈ PreFIx (|S;),Y→βAn∈|S;,则 根据性质2—(活前缀状态机的性质), αAn是归约活前缀。再根据派生原理,若 A→π是A的产生式,则aπ也是归约活前缀。 令构造LRSM的思想: 如果在状态项目集S1中有项目A→βB, 且B→π是B的产生式,则在IS;中增加项目 B→·π;对于|S:这个过程继续到不可再扩 充为止

❖ 若有 Prefix(ISi )，Y→•AISi ，则 根据性质2—(活前缀状态机的性质）， A是归约活前缀。再根据派生原理，若 A→是A的产生式，则也是归约活前缀。 ❖ 构造LRSM的思想： 如果在状态项目集ISi 中有项目A→•B， 且B→是B的产生式，则在ISi 中增加项目 B→•；对于ISi 这个过程继续到不可再扩 充为止

构造LR(0)活前缀状态机LRSM的算法要点: 构造初始状态lSo:lS=CL0SURE({z→·S}),并给|S标 上No。 从已构造的LRSM部分图选择被标为N0的任一状态|S, 并做 1]对每个符号XeVN,做下面动作: 令|S1=CL0SURE(|S),若非空。 2)若在LRSM部分图中已有s与|S有相同项目 集,则令mk;否则构造|S的状态点|S 并给|S标上NO,同时令mj。 3)在S和S之间画有向X边:1s1Sn。 [2]给lS标上0K。 ◆重复上一步骤,直至没有被标记为N的状态结点为止

构造LR(0)活前缀状态机LRSM的算法要点： ◆ 构造初始状态IS0：IS0=CLOSURE({Z→•S})，并给IS0标 上NO。 ◆ 从已构造的LRSM部分图选择被标为NO的任一状态IS， 并做 [1] 对每个符号XVTVN，做下面动作： 1) 令ISj = CLOSURE( IS(X))，若非空。 2) 若在LRSM部分图中已有ISk与ISj有相同项目 集，则令m=k；否则构造ISj的状态点ISj， 并给ISj标上NO，同时令m=j。 3) 在IS和ISm之间画有向X边：IS ISm 。 [2] 给IS标上OK。 ◆ 重复上一步骤，直至没有被标记为NO的状态结点为止。 x

&例:构造LR(0)状态机 S→E井 E→E+T E→T T→id T→>(E)

 例：构造LR(0)状态机 S → E ＃ E → E + T E → T T → id T→ ( E )

S→·E# E→T● T→(E) E→●E+T E→●E+T E→●T E→●T T→●id 5 T→●id T→●(E) id T→●(E) E s→→E·# E→E+●T 7 E→E+T T→●id T→(E°) T→●(E) E→E●+T 2 8 s→E#● E→E+T● T→(E GE的LRSM

0 S→ • E ＃ E→ • E+T E→ • T T→ • id T→ • ( E ) 1 S→E • ＃ E→E • +T 5 T→id • 3 E→E+ • T T→ • id T→ • (E) 4 E→E+T • 9 E→T • 6 T→( • E) E→ • E+T E→ • T T→ • id T→ • ( E ) 7 T→(E • ) E→E • +T 8 T→(E) • T T ( id E T id )E + id( ( G E 的LRSM + 2 S→E ＃ •＃

LRSM给出了所有的可归活前缀 LRSM中的每个状态将对应一个饱和项目集: (1)其中一部分是由先驱状态分出来 (称为基本项目); (2)一部分则是由基本项目扩展出来的 (称为扩展项目或派生项目)。派生部 分项目的特点是其中的“·”出现在 产 生式右部的最左侧

 LRSM给出了所有的可归活前缀  LRSM中的每个状态将对应一个饱和项目集： （1）其中一部分是由先驱状态分出来 (称为基本项目)； （2）一部分则是由基本项目扩展出来的 (称为扩展项目或派生项目)。派生部 分项目的特点是其中的“ • ”出现在 产 生式右部的最左侧