如何使用alex/haskell执行python样式的缩进/ dedent标记？

我正在用Haskell为Alex写一个小语言词法分析器.

指定语言具有pythonesque显着缩进,每当缩进级别更改时都会发出INDENT标记或DEDENT标记.

在像C这样的传统命令式语言中,你会在词法分析器中保持全局,并使用每行的缩进级别对其进行更新.

这在Alex/Haskell中不起作用,因为我无法在Haskell的任何地方存储任何全局数据,并且我不能将所有的lexing规则放在任何monad或任何东西中.

那么,我该怎么做呢？它甚至可能吗？或者我是否必须编写自己的词法分析器并避免使用alex？

请注意,在其他对空格敏感的语言(如Haskell)中,布局处理确实在词法分析器中完成.GHC实际上实现了Alex的布局处理.这是来源:

https://github.com/ghc/ghc/blob/master/compiler/parser/Lexer.x

正如jrockway指出的那样,你的问题中有一些严重的错误导致你误入歧途."我无法在Haskell的任何地方存储任何全局数据"是在错误的轨道上.首先,你可以拥有全局状态,其次,你不应该在这里使用全局状态,当Alex以安全的方式完全支持规则中的状态转换时.

查看Alex提供的AlexState结构,让您通过词法分析器来处理状态.然后,看看在GHC的布局实现中如何使用状态来实现布局规则的缩进/取消.(在GHC的词法分析器中搜索" - 布局处理",以查看状态是如何被推动和弹出的).

我无法在任何地方使用Haskell存储任何全局数据

这不是真的; 在大多数情况下,像State monad这样的东西就足够了,但也有ST monad.

但是,您不需要全局状态来执行此任务.编写解析器由两部分组成; 词法分析和语法分析.词法分析只是将一串字符转换为有意义的令牌流.语法分析将标记转换为AST; 这是你应该处理缩进的地方.

当你解释缩进时,你会在缩进级别改变时调用处理函数 - 当它增加(嵌套)时,你调用你的处理函数(如果你想跟踪缩进级别,可能会增加一个arg); 当级别降低时,您只需从函数返回相关的AST部分.

(顺便说一下,使用全局变量对我来说也不会出现在命令式语言中 - 如果有的话,它是一个实例变量.状态monad在概念上与此非常相似.)

最后,我认为"我不能将所有的lexing规则放在任何monad中"这一短语表明了对monad的某种误解.如果我需要解析并保持全局状态,我的代码将如下所示:

data AST = ...
type Step = State Int AST

parseFunction :: Stream -> Step
parseFunction s = do
   level <- get
   ...
   if anotherFunction then put (level + 1) >> parseFunction ...
   else parseWhatever
   ...
   return node

parse :: Stream -> Step
parse s = do
   if looksLikeFunction then parseFunction ...

main = runState parse 0 -- initial nesting of 0

而不是将函数应用程序与(.)or ($)组合,而是将它们与(>>=)或组合使用(>>).除此之外,算法是相同的.("monad"没有"内部".)

最后,您可能喜欢应用仿函数:

eval :: Environment -> Node -> Evaluated
eval e (Constant x) = Evaluated x
eval e (Variable x) = Evaluated (lookup e x)
eval e (Function f x y) = (f <$> (`eval` x) <*> (`eval` y)) e

(要么

eval e (Function f x y) = ((`eval` f) <*> (`eval` x) <*> (`eval` y)) e

如果你有像"funcall"这样的东西......但我离题了.)

有很多关于使用applicative functor,monad和arrows进行解析的文献; 所有这些都有可能解决您的问题.阅读这些,看看你得到了什么.