代码之家 › 专栏 › 技术社区 › emi

使国家处于无国籍的世界

context-free-grammar monads state haskell

7

emi · 技术社区 · 15 年前

我正在将上下文无关语法转换为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)

最大索引 返回一组规则中的最大变量索引; 子项rl k j 对执行替换千 -由右侧以 j型 -索引变量。演出结束后 国民生产总值 ,我需要按相反的顺序完成语法的最后一关。

问题是诺尔 ,它用左递归转换语法千 -索引规则。这是一个“有状态”函数,因为必须为每个规则(或千 -索引规则) 诺尔已应用。所以我写了一个状态函数

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'

我可以把诺尔为了更新 n个哪一个诺尔作为参数。我是不一定要表演诺尔里面 第二步 不过,在上面的函数中。我似乎无法使用 让。。。在里面 模式,因为有状态计算嵌入在几个递归函数中。

我想做的是 n个是某种类型的全局变量,类似于 n个 ,我可以在内部调用和更新 第二步 ,这就是为什么我最初将函数编写为 预计到达时间 -扩展(用于 n个 ). 有人知道我如何组织 国民生产总值 在州内单子达到这种效果?除了折叠中的最后一个计算之外,没有什么是“有状态的”,我只喜欢使用状态monad和“琐碎的”示例。我迷路了。

2 回复 | 直到 15 年前

1

4

wolfgang 15 年前

要将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和j==16的“foo_42_16”。如果输入语法已经包含这种类型的符号名,那么您可能会遇到麻烦。

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

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

不过,除非用另一种类型替换Set(规则a),使您能够更有效地实现newSymbol操作,否则这绝对是不有效的。

2

3

luispedro 15 年前

我试着把诺尔改写成纯粹的。您确定不能重写它以生成仅依赖于规则名称及其索引(或类似内容)的符号吗?

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