LR(0) 项目

右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目(简称为项目)

A→ α1·α2

例:S→bBB

项目描述了句柄识别的状态

产生式A→ε 只生成一个项目A→ ·

增广文法 (Augmented Grammar)

如果G 是一个以S为开始符号的文法,则G的增广文法 G' 就是在G中加上新开始符号S' 和产生式S' → S而得到的文法

例:

引入这个新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边,从而使得分析器只有一个接受状态

文法中的项目

后继项目(Successive Item)

  • 同属于一个产生式的项目,但圆点的位置只相差一个符号,
    则称后者是前者的后继项目
  • A→α· Xβ的后继项目是A→αX·β

可以把等价的项目组成一个项目集( I ) ,称为项目集闭包(Closure of Item Sets),每个项目集闭包对应着自动机的一个状态

例:LR(0)自动机

文法
(0) S' → S
(1) S → BB
(2) B → aB
(3) B → b

最后修改日期:2020年6月1日

留言

撰写回覆或留言