让国家处于无国界的世界

Question

我正在将无上下文语法转换为Greibach Normal Form(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 -indexed变量开头的规则对k- indexed规则执行替换.执行gnf后,我需要以相反的顺序对语法执行最后一次传递.

问题是noLR,它使用左递归k - indexed规则转换语法.这是一个"状态"功能,因为唯一的变量必须为每个规则(或生成ķ -indexed规则),其noLR被应用.所以我写了一个有状态函数

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作为一个参数.不过,我不知道如何在上面的函数中在step2中执行noLR.我似乎无法在模式中使用let ...因为有状态计算嵌入在几个递归函数中.

我想要做的是有ň是某种类型的全局变量,类似于一个明确的线程ñ,我可以打电话内更新第二步,这就是为什么我原来写的功能与折叠ETA -expansion(为ñ).有谁知道如何在状态monad中构造gnf来实现这种效果？除了折叠中的最后一次计算外,没有别的东西是"有状态的",而我只是习惯使用状态monad和"琐碎"的例子.我很失落.

Answer 1

为了将 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（规则 a），从而可以更有效地实现 newSymbol 操作。