我正在将上下文无关的语法转换为Greibach范式(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返回一组规则中的最大变量索引；子rl k j用右手边以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的fold(对于n )。有谁知道我如何在状态monad中构造gnf来实现这种效果？除了最后的计算之外，没有其他东西是“有状态的”，而且我只喜欢将状态monad与“琐碎的”示例一起使用。我很迷路。
最佳答案
为了将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操作。