haskell - 如何在 Happy 中使用 Alex monadic 词法分析器？

我正在尝试学习使用 Alex + Happy 来构建解析器，特别是我对学习使用 Alex 的 monad 包装器很感兴趣。我已经看过 Alex 和 Happy 的文档，但对我来说，他们都缺乏关于将它们一起使用的任何有用信息。我设法让它们与 basic 和 posn 包装器一起工作，但我对 monad 感到茫然。

我已经看过关于亚历克斯、快乐和一元词法分析器的不同问题(包括:Are there any tutorials on building a simple interpreter using Alex + Happy?，但没有一个能够提供一个简单的例子，其中使用了 monad。

大多数在线代码使用带有自定义词法分析器函数的 Happy，或者使用 basic 或 posn Alex 包装器。

这是一个类似 ini 的语法的简单词法分析器:

{
module IniLexer where
}

%wrapper "monad"



$spaces = [\ \t]
$alpha = [a-zA-Z]
$digits = [0-9]
$alnum = [$alpha$digits]


@identifier = $alpha $alnum*

@comment = \#.*

@integer = $digits+

@boolean = (true) | (false)

@string = \"[^\"]*\"


:-

@integer    { mkL LInteger }
@boolean    { mkL LBoolean }
@string     { mkL LString }

@identifier  { mkL LIdentifier }

\[@identifier\] { mkL LSection }

=           { mkL LAssign }

\;          { mkL LEndAssign }
@comment    ;
[\ \t \n]+  ;


{

data LexemeClass = LInteger | LBoolean | LString | LIdentifier | LSection | LAssign | LEndAssign | LEOF
    deriving (Eq, Show)


mkL :: LexemeClass -> AlexInput -> Int -> Alex Token
mkL c (p, _, _, str) len = let t = take len str
                           in case c of
                                LInteger -> return (IntegerNum ((read t) :: Integer) p)
                                LBoolean -> return (BooleanVal (if t == "true"
                                                                   then True
                                                                   else False
                                                               ) p)
                                LString -> return (StringTxt (take (length t - 2) (drop 1 t)) p)
                                LIdentifier -> return (Identifier t p)
                                LSection -> return (SectionHeader (take (length t - 2) (drop 1 t)) p)
                                LAssign -> return (Assignment p)
                                LEndAssign -> return (EndAssignment p)


-- No idea why I have to write this myself. Documentation doesn't mention it.
alexEOF :: Alex Token
alexEOF = return Eof



data Token = SectionHeader {identifier :: String, position :: AlexPosn} |
             Identifier {name :: String, position :: AlexPosn}          |
             Assignment {position :: AlexPosn}                          |
             EndAssignment {position :: AlexPosn}                       |
             IntegerNum {value :: Integer, position :: AlexPosn}        |
             BooleanVal {istrue :: Bool, position :: AlexPosn}          |
             StringTxt  {text :: String, position :: AlexPosn}          |
             Eof
    deriving (Eq, Show)


}

这是相对的 Happy 解析器:

{
module Main where

import IniLexer

}



%name parseIniFile
%error {parseError}
%lexer  {alexMonadScan} {AlexEOF}
%monad {Alex}
%tokentype {Token}
%token
    SECTION     {SectionHeader name _ }
    IDENT       {Identifier name _ }
    '='         {Assignment _ }
    INT         {IntegerNum value _ }
    BOOL        {BooleanVal istrue _ }
    STRING      {StringTxt text _ }
    ';'         {EndAssignment _ }


%%


ConfigFile : SequenceOfSections                    {reverse $1}

SequenceOfSections : {- empty -}                   {   []  }
                   | SequenceOfSections Section    {$2 : $1}


Section : SECTION SectionBody                      {Section (identifier $1) (reverse $2)}


SectionBody : {- empty -}        {[]}
            | SectionBody AssignmentLine ';' {$2 : $1}


AssignmentLine : IDENT '=' Value      {(name $1, $3)}

Value : INT         {IntV (value $1)}
      | BOOL        {BoolV (istrue $1)}
      | STRING      {StringV (text $1)}


{

data Value = IntV Integer | BoolV Bool | StringV String
    deriving (Eq, Show)

data Section = Section String [(String, Value)]
    deriving (Eq, Show)

data IniFile = IniFile [Section]
    deriving (Eq, Show)


parseError :: [Token] -> Alex a
parseError t = fail "a"

main = do
    s <- getContents
    print $ parseIniFile $ runAlex s alexMonadScan

}

这引发了很多编译器错误:

[...]
Couldn't match expected type `(AlexReturn t1 -> Alex a0) -> t0'
                with actual type `Alex Token'
    The function `alexMonadScan' is applied to one argument,
    but its type `Alex Token' has none
[...]

我应该如何修改解析器以使用 alexMonadScan ？
Happy 文档根本不清楚，并努力不使用任何澄清的例子(或者从我的角度来看，提供的例子没有澄清)。

如果需要，我可以发布我的 posn 版本的同一个词法分析器+解析器。

最佳答案

据我所知，您的词法分析器的定义完全没问题。假设那里没有错误，您需要修复的唯一问题是解析器的配置。第一件事是您使用的词法分析器是错误的。虽然该函数是 Alex 词法分析器的接口(interface)，但它的类型为

alexMonadScan :: Alex result

但是快乐想要的词法分析器是类型

lexer :: (Token -> P a) -> P a

其中 P 是我们正在使用的 monad。这就是说，词法分析器在给出延续时应该为我们提供 Alex a。我们需要一个简单的包装器:

lexwrap :: (Token -> Alex a) -> Alex a
lexwrap cont = do
    token <- alexMonadScan
    cont token

或等效地

lexwrap = (alexMonadScan >>=)

其次，在 alexEOF 指令中使用 %lexer 会导致解析器在每次输入时都失败。您在那里提供的名称插入到生成代码中 case 语句的分支中，因此您必须使用数据构造函数的名称而不是值 --- 特别是，您需要使用 Alex 将发出的数据构造函数信号EOF。

这使得我们在解析器中的词法分析器行有点不同。

%lexer {lexwrap} {Eof}

(作为旁注，这就是您需要自己编写 alexEOF = return Eof 的原因。您在 alexEOF 中返回的数据构造函数需要与您将 Happy 标识为结束文件的数据构造函数进行模式匹配。Alex 没有办法知道你想发出什么，而Happy 无法知道你选择通过Alex 发出什么。)

现在下一个问题是您的 parseError 类型不正确。仅使用 monad 时，这确实是您需要的类型，但是当您将词法分析器添加到组合中时，您的 parseError 必须具有不同的类型。此外，可能不建议使用 fail，所以这里有一个稍微好一点的定义:

parseError :: Token -> Alex a
parseError _ = alexError "Why is using happy and alex so hard"

最后，这里的main函数定义有点奇怪。我们想要调用解析器是用 runAlex 调用它。所以这里是它的一个快速包装。传入的字符串是您要解析的字符串。

parse :: String -> Either String [Section]
parse s = runAlex s parseIniFile

函数 parse 的类型由 parseIniFile 的定义决定。这里，它是一个 Alex [Section]，所以返回一个 Either String [Section]。

我认为这就是一切。

关于haskell - 如何在 Happy 中使用 Alex monadic 词法分析器？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20315739/