4

所以我有这个语法（如下），我需要建立一个解析表。我需要使它适合预测解析器。我知道第一个想法是让它明确，但对我来说它已经明确（因为我找不到可以为其绘制 2 个不同解析树的字符串）。其次，我需要将其考虑在内。我把我的猜测放在原来的语法下面，我觉得我错过了一些东西，如果我错过了一些东西，有人可以指出。

S -> m G | m K p
G -> n G | n
K -> q K r | m n

我猜：

S -> m A
A -> G | K p 
G -> n G'
G' -> n G' | emptyString
K -> q K r | m n
4

1 回答 1

0

你所拥有的看起来是正确的！以下是了解如何实现目标的分步方法，以及为什么每次转换都是必要的。

首先，让我们看看我们的 S 非终结符。这个非终结符有两个以 开头的产生式m，这意味着我们在这些产生式之间存在 FIRST/FIRST 冲突。左分解产生式 S → mG 和 S → mKp 给我们

小号 → 毫安

A → G

A → Kp

现在，这样做是否暴露了以前不存在的任何问题？幸运的是，没有。非终结符 G 只能生成以 开头的字符串n，非终结符 K 只能生成以qor开头的字符串m。这意味着我们在这里没有引入任何 FIRST/FIRST 冲突，所以没有必要进一步触及任何东西——至少现在还没有。

接下来，让我们看看 G 非终结符，它有产生式 G → nG 和 G → n。换句话说，这会产生一个包含一个或多个 letter 副本的字符串n。正如目前所写的那样，存在 FIRST/FIRST 冲突。我们有很多方法可以重写它。n您提出的一个本质上是将其分成两部分 - 一个生成单个n. 我将在这里跟随你的领导，它引入了一个新的非终结符，我将调用 H 以将其与 G 区分开来：

G → nH

H → nH | ε

现在，我们不得不问 - 这个 ε 产生式是否会引入任何 FIRST/FOLLOW 冲突？要回答这个问题，我们需要确定 FOLLOW(H) 是什么。我们看到 H 只出现在产生式 H → nH（它没有给我们任何新东西）和 G → nH 的末尾，它告诉我们 FOLLOW(G) 中的所有内容也将出现在 FOLLOW(H) 中. FOLLOW(G) 中有什么？G 出现在产生式 A → G 的末尾，它告诉我们 FOLLOW(A) 中的所有内容都将在 FOLLOW(H) 中。并且 A 只出现在 S → mA 中，这意味着 FOLLOW(A) 中唯一的记号是输入结束标记 $。呸！所以跟随（H）= { $ }。这是个好消息，因为这不会与 H → nH 产生冲突。

这留下了 K 的生产规则，幸运的是它们没有任何问题。

把这一切放在一起，我们得到网络转换的语法是

S &rarr mA

A → G | Kp

G → nH

H → nH | ε

K → qKr | 锰

这恰好是 LL(1)。这是解析表：

     m      n       q     r      $
  +------+------+------+------+------+
S |  mA  |      |      |      |      |
  +------+------+------+------+------+
A |  Kp     G      Kp  |      |      |
  +------+------+------+------+------+
G |      |  nH  |      |      |      |
  +------+------+------+------+------+
H |      |  nH  |      |      | eps  |
  +------+------+------+------+------+
K |  mn  |      | qKr  |      |      |
  +------+------+------+------+------+

看妈！没有冲突！

于 2018-12-16T04:28:55.343 回答