什么是 SLR (1) 解析器?

SLR代表“简单 LR 解析器”。执行起来非常简单和经济。但是它没有为某些语法类制作解析表,即为什么使用CLR和LALR,它们主要实现所有类或类型的语法。它构造解析表,有助于执行输入字符串的解析。

SLR(1) - 具有 SLR 解析表的语法被称为 SLR (1)。

SLR解析器的工作

如果给出上下文无关语法,则可以进行 SLR 解析。在 LR (0) 中,0 表示没有 Look Ahead 符号。

LR (0) 项的规范集合

语法 G 的 LR (0) 项目由一个产生式组成,其中符号点 (.) 插入到产生式 RHS 的某个位置。

例如- 对于生产 S → ABC,生成的 LR (0) 项目将是 -

S →∙ ABC

S → A ∙ BC

S → AB ∙ C

S → ABC ∙

产生式 S → ε 只产生一项,即 S →∙

规范 LR (0) 集合有助于构建称为简单 LR (SLR) 解析器的 LR 解析器。

要为语法创建 Canonical LR (0) 集合,需要做 3 件事 -

  • 增强语法

  • 闭包函数

  • 转到函数

增强语法- 如果语法 G 具有起始符号 S,则增强语法是具有新起始符号 S' 的新语法 G'。此外,它将包含产生式 S′ → S。

闭包- 对于上下文无关文法 G,如果 I 是文法 G 的项目或状态集,则 -

  • I 中的每个项目都在闭包 (I) 中。

  • 如果规则 A → α。B β 是闭包 (I) 中的一条规则,B 有另一个规则,例如 B → γ,那么闭包 (I) 将由 A → α 组成。Bβ 和 B → 。γ

goto (I, X) - 如果在 I 中存在产生式 A → α ∙ X β,则 goto (I, X) 定义为 A → α X ∙ β 的项集的闭包,其中 I 是项集,并且X 是语法符号(非终结符)。

SLR解析表的构建

SLR Parsing table 基本上有两部分

  • 行动

可以使用以下算法填充操作和转到表 -

算法

输入- 增强语法 G'

输出- SLR 解析表

方法

  • 最初构建项目集

C = {I 0 , I 1 , I 2 ... ... I n } 其中 C 是语法的一组 LR (0) 项。

  • 解析动作基于每个项目或状态 I 1

各种行动是 -

  • 如果 A → α ∙ a β 在 I i中并且 goto (I i , a) = I j则设置 Action [i, a] = shift j"。

  • 如果 A → α ∙ 在 I i中,则对所有符号 a 设置 Action [i, a] 以“减少 A → α”,其中 a ∈ FOLLOW (A)。

  • 如果 S′ → S ∙ 在 I i中,则动作表 Action [i, $] = accept" 中的条目。

  • SLR 表的 goto 部分可以填充为 - 状态 i 的 goto 转换仅考虑非终端。如果 goto (I i , A) = I j那么 goto [i, A] = j

  • 规则 2 和 3 未定义的所有条目都被视为“错误”。

以上是 什么是 SLR (1) 解析器? 的全部内容, 来源链接: utcz.com/z/363380.html

回到顶部