7

我正在将上下文无关语法转换为格雷巴赫范式 (GNF)。主要的转换（来自 Hopcroft & Ullman）是对语法的索引变量的一系列迭代。它本质上是“无状态的”。我已经将它实现为适当索引上的一系列折叠（实现相当简单）：

gnf :: Ord a => Set (Rule a) -> Set (Rule a)
gnf rl = foldl step1 rl [1..maxIndex rl]
 where step1 rl' k = foldl step2 rl' [1..k - 1]
        where step2 rl'' j = noLR k (subst rl'' k j)

maxIndex rl返回一组规则中的最大变量索引；subst rl kj用右手边以j索引变量开始的规则对k索引规则执行替换。执行完 gnf后，我需要以相反的顺序对语法进行最后一次传递。

问题是noLR，它用左递归k索引规则转换语法。这是一个“有状态”函数，因为必须为每个应用 noLR 的规则（或 k 索引规则）生成一个唯一变量。所以我写了一个有状态的函数

noLR :: Ord a => Int -> Set (Rule a) -> State [Sym a] (Set (Rule a))
noLR rl = do (n:ns) <- get; put ns;
             let rl' = ... remove left recursion rl n ...
              in return rl'

我可以对noLR进行排序，以更新noLR作为参数的n 。不过，我不确定如何在上述函数的step2中执行noLR 。我似乎无法在模式中使用 let ...，因为有状态计算嵌入在几个递归函数中。

我想要做的是让n成为某种类型的全局变量，类似于n的显式线程，我可以在step2中调用和更新它，这就是为什么我最初将函数编写为带有eta -expansion 的折叠（对于n）。有谁知道我如何在 state monad 中构造gnf来实现这种效果？除了折叠中的最后一次计算，没有其他东西是“有状态的”，我只喜欢使用带有“琐碎”示例的状态单子。我比较迷茫。

4

2 回答 2

4

为了使用您给定的类型的 noLR，您必须按照以下几行重写您的 gnf 函数：

gnf :: Ord a => Set (Rule a) -> Set (Rule a)
gnf rl = evalState (foldM step1 rl [1..maxIndex rl]) ( ... generate the initial state [Sym a] here ...)
 where step1 rl' k = foldM step2 rl' [1..k - 1]
        where step2 rl'' j = noLR k (subst rl'' k j)

您的状态变量存在于整个计算过程中，并且必须在代码中明确说明这一事实。

如果您所需要的只是新生成的变量名称不会相互冲突，那么您可以通过从索引 k 和 j 生成新符号名称来使 noLR 纯 - 类似于 k == 42 的 "foo_42_16" 和j == 16. 如果输入文法已经包含那种符号名称，那么你可能会遇到麻烦。

如果你需要你的符号在语法中是唯一的，那为什么不这么说呢？

newSymbol :: Set (Rule a) -> Sym a
newSymbol rl = ... find a symbol name not used in rl ...

但是，这绝对不是有效的，除非您将 Set (Rule a) 替换为允许您更有效地实现 newSymbol 操作的不同类型。

于 2010-11-23T22:48:59.983 回答
3

我会尝试将 noLR 重写为纯粹的。你确定你不能重写它来生成一个只依赖于规则名称及其索引（或类似的东西）的符号吗？

noLR k j = noLR' k j $ newSymbol k j
    where newSymbol k j = ... -- some concatenation of k and j
          noLR' k j sym = ... -- your now pure function
于 2010-11-23T20:51:44.843 回答