基于Alex与Happy实现eval()函数的原理疑问及优化咨询

需求背景 #

使用Alex词法分析器与Happy语法分析器，实现仅支持整数加减的算术表达式语法，目标是实现eval()函数，将传入的字符串参数解析为Expr类型。预期运行结果：

$ stack run
1 + eval("3-2") 
Plus (ConstInt 1) (Minus (ConstInt 3) (ConstInt 2))

当前实现可正确解析，但对运行逻辑存在疑惑，同时希望了解更优实现方式。

现有代码 #

Lexer代码（Lexer.hs） #

{
module Lexer where

import Control.Monad (when)
}

%wrapper "monadUserState"

$digit = 0-9

tokens :-

<0> $white+     { skip }

<0> "("       { tok TokLParen }
<0> ")"       { tok TokRParen }
<0> "+"       { tok TokPlus }
<0> "-"       { tok TokMinus }

<0> "eval"    { tok TokBuiltinEvalExpr }

<0> $digit+                                             { tokInt }

<0> \"        { enterString `andBegin` string }
<string> \"   { exitString `andBegin` 0 }
<string> \\   { emit '\\' }
<string> \\\" { emit '"' }
<string> \\n  { emit '\n' }
<string> \\t  { emit '\t' }
<string> .    { emitCurrent }

{
data Token =
    TokLParen
  | TokRParen
  | TokPlus
  | TokMinus
  | TokBuiltinEvalExpr
  | TokConstInt Int
  | TokConstStr String
  | EOF
  deriving (Eq, Show)

data AlexUserState = AlexUserState {
    nestLevel :: Int
  , strStart :: AlexPosn
  , strBuffer :: String
} deriving (Show)

alexInitUserState :: AlexUserState
alexInitUserState = AlexUserState
  { nestLevel = 0
  , strStart = AlexPn 0 0 0
  , strBuffer = []
  }

alexModifyUserState :: (AlexUserState -> AlexUserState) -> Alex ()
alexModifyUserState f = f <$> alexGetUserState >>= alexSetUserState

alexEOF :: Alex Token
alexEOF = do
  (AlexPn _ line column, _, _, _) <- alexGetInput
  startCode <- alexGetStartCode
  when (startCode == string) $
    alexError $ "Error: unclosed string at line " <> show line <> ", column " <> show column
  pure EOF

tok :: Token -> AlexAction Token
tok ctor _ _ = pure ctor

tokInt :: AlexAction Token
tokInt (_, _, _, str) len =
  pure $ TokConstInt $ read $ take len str

enterString, exitString :: AlexAction Token
enterString inp@(pos, _, _, _) len = do
  alexModifyUserState $ \s -> s{strStart = pos, strBuffer = strBuffer s}
  skip inp len
exitString _ _ = do
  s <- alexGetUserState
  alexSetUserState s{strStart = AlexPn 0 0 0, strBuffer = []}
  pure $ TokConstStr $ reverse $ strBuffer s

emit :: Char -> AlexAction Token
emit c inp len = do
  alexModifyUserState $ \s -> s{strBuffer = c : strBuffer s}
  skip inp len

emitCurrent :: AlexAction Token
emitCurrent inp@(_, _, _, str) len = do
  alexModifyUserState $ \s -> s{strBuffer = head str : strBuffer s}
  skip inp len
}

Parser代码（Parser.hs） #

{
module Parser where

import qualified Lexer as L
}

%name parser expr
%tokentype { L.Token }
%error { parseError }
%monad { L.Alex } { >>= } { pure }
%lexer { lexer } { L.EOF }

%token

'('     { L.TokLParen }
')'     { L.TokRParen }
'+'     { L.TokPlus }
'-'     { L.TokMinus }
'eval'  { L.TokBuiltinEvalExpr }

int   { L.TokConstInt $$ }
str   { L.TokConstStr $$ }

%left '+' '-'

%%

expr :: { Expr }
  : op_expr { $1 }
  | int { ConstInt $1 }
  | eval_expr { $1 }

inject_string :: { () }
  : str {% injectString $1 }

eval_expr :: { Expr }
  : 'eval' '(' inject_string ')' expr { $5 }

op_expr :: { Expr }
  : expr '+' expr { Plus $1 $3 }
  | expr '-' expr { Minus $1 $3 }


{
data Expr =
    ConstInt Int
  | Plus Expr Expr
  | Minus Expr Expr
  deriving (Show)

injectString :: String -> L.Alex ()
injectString s = do
  (a, b, c, t) <- L.alexGetInput
  L.alexSetInput (a, b, c, s ++ t)

parseError :: L.Token -> L.Alex a
parseError tok = do
  (L.AlexPn _ line column, _, _, _) <- L.alexGetInput
  L.alexError $ "Parse error. Unexpected token " ++ show tok ++ " at line " ++ show line <> ", column " <> show column

lexer :: (L.Token -> L.Alex a) -> L.Alex a
lexer = (=<< L.alexMonadScan)
}

实现思路与疑惑 #

实现思路 #

1. 通过空单子式生成式inject_string将字符串内容添加到Alex输入缓冲区的前缀；
2. 解析修改后的输入得到Expr。

核心矛盾 #

以输入1 + eval("3-2")为例：

• 处理inject_string前，Alex输入为"3-2")；
• 调用injectString后，输入变为3-2)，即表达式后接右括号。

但原规则eval_expr定义为：

eval_expr :: { Expr }
  : 'eval' '(' inject_string ')' expr { $5 }

按逻辑，规则要求)后接表达式，但修改后的输入是3-2)，应该匹配失败，但实际却能正常运行。

如果调整为更符合直觉的规则：

eval_expr :: { Expr }
  : 'eval' '(' inject_string expr ')' { $4 }

反而会出现解析错误：

1 + eval("3-2") 
Parse error. Unexpected token TokRParen at line 1, column 16

疑问 #

1. 为何原规则能正常运行？
2. 是否有更优的eval()实现方式？

补充思考：推测右括号可能已作为前瞻token被消费，处理inject_string后输入仅为3-2，但疑惑为何规则中的)不会匹配失败。此前认为前瞻token仅为解决歧义临时匹配，仍需在inject_string处理后再次匹配，是否此理解有误？

解答 #

1. 原规则能运行的原因 #

Happy的词法器交互逻辑是预读取前瞻token，且一旦读取就不会回退。具体到你的场景：

• 当解析到eval(后，词法器会预读取下一个token，也就是TokConstStr "3-2"，之后继续预读取下一个token——TokRParen（右括号）；
• 执行inject_string时，你修改了输入缓冲区，但此时Happy已经把TokRParen作为已读取的前瞻token缓存起来了；
• 原规则中的)直接匹配了这个已缓存的前瞻token，而不需要从修改后的输入中重新读取；
• 匹配完)后，接下来解析expr时，词法器会从修改后的输入3-2中读取token，正好解析出Minus (ConstInt 3) (ConstInt 2)，最后整个输入处理完毕。

而调整规则后，inject_string之后要解析expr，此时Happy缓存的前瞻token是TokRParen，和expr的预期token（int/eval等）不匹配，直接触发解析错误。

2. 更优的实现方式 #

直接修改输入缓冲区的方式依赖Happy的内部token缓存逻辑，可读性差且容易出问题。更合理的方式是递归调用解析器，把字符串内容单独解析为Expr，而不是修改全局输入。

修改方案如下：

步骤1：修改Parser，添加单独解析字符串的入口

在Parser.hs的顶层添加一个新的解析函数：

%name parseExprFromString expr

然后在代码部分实现一个辅助函数，用于解析字符串：

evalStringExpr :: String -> L.Alex Expr
evalStringExpr s = do
  -- 保存当前输入状态
  oldInput <- L.alexGetInput
  -- 设置新输入为字符串内容
  L.alexSetInput (L.AlexPn 0 1 1, 1, 1, s)
  -- 调用解析器
  result <- parseExprFromString
  -- 恢复原输入状态
  L.alexSetInput oldInput
  pure result

步骤2：修改eval_expr规则

去掉inject_string，直接在规则中调用evalStringExpr：

eval_expr :: { Expr }
  : 'eval' '(' str ')' {% evalStringExpr $3 }

完整修改后的Parser核心部分

{
module Parser where

import qualified Lexer as L
}

%name parser expr
%name parseExprFromString expr  -- 新增的解析入口
%tokentype { L.Token }
%error { parseError }
%monad { L.Alex } { >>= } { pure }
%lexer { lexer } { L.EOF }

%token

'('     { L.TokLParen }
')'     { L.TokRParen }
'+'     { L.TokPlus }
'-'     { L.TokMinus }
'eval'  { L.TokBuiltinEvalExpr }

int   { L.TokConstInt $$ }
str   { L.TokConstStr $$ }

%left '+' '-'

%%

expr :: { Expr }
  : op_expr { $1 }
  | int { ConstInt $1 }
  | eval_expr { $1 }

eval_expr :: { Expr }
  : 'eval' '(' str ')' {% evalStringExpr $3 }  -- 修改后的规则

op_expr :: { Expr }
  : expr '+' expr { Plus $1 $3 }
  | expr '-' expr { Minus $1 $3 }


{
data Expr =
    ConstInt Int
  | Plus Expr Expr
  | Minus Expr Expr
  deriving (Show)

-- 新增的字符串解析辅助函数
evalStringExpr :: String -> L.Alex Expr
evalStringExpr s = do
  oldInput <- L.alexGetInput
  L.alexSetInput (L.AlexPn 0 1 1, 1, 1, s)
  result <- parseExprFromString
  L.alexSetInput oldInput
  pure result

parseError :: L.Token -> L.Alex a
parseError tok = do
  (L.AlexPn _ line column, _, _, _) <- L.alexGetInput
  L.alexError $ "Parse error. Unexpected token " ++ show tok ++ " at line " ++ show line <> ", column " <> show column

lexer :: (L.Token -> L.Alex a) -> L.Alex a
lexer = (=<< L.alexMonadScan)
}

方案优势 #

• 逻辑清晰：直接明确地将字符串内容作为独立输入解析，不依赖Happy的内部token缓存；
• 可维护性高：避免了修改全局输入带来的副作用，后续扩展更安全；
• 错误处理友好：如果字符串内容解析失败，错误信息会对应到字符串内部的位置，而不是原输入的位置（可进一步优化错误提示）。

内容的提问来源于stack exchange，提问作者swingbit