如何用Haskell Happy解析器同步构建AST与LeBlanc-Cook符号表

我正好在Haskell的Happy解析器里做过类似的单遍解析结合符号表的实现，你的需求（构建AST同时填充LeBlanc-Cook风格符号表，不事后遍历AST）完全可以通过自定义Monad栈来实现，核心是把Happy的解析过程和状态管理、错误处理结合起来。下面一步步给你讲清楚：

1. 先定义核心数据结构和Monad栈 #

首先得明确符号表的结构——LeBlanc-Cook是分层作用域，所以我们用栈结构来存储作用域，栈的每个元素是当前作用域的符号映射（比如用Data.Map存名字到符号项的映射）。同时，解析过程中可能出现错误（比如重复声明），所以我们用StateT包裹符号表，再套一层Either String来处理错误：

import Control.Monad.State
import qualified Data.Map as Map

-- 符号表项：包含名字、类型、作用域层级
data SymEntry = SymEntry
  { symName  :: String
  , symType  :: Type
  , symLevel :: Int  -- 作用域层级，全局是0，嵌套一层+1
  } deriving (Show)

-- 支持的类型（根据你的语言扩展）
data Type = IntType | BoolType | UserDefinedType String deriving (Eq, Show)

-- LeBlanc-Cook符号表：栈结构，头部是当前作用域
type SymTable = [Map String SymEntry]

-- 自定义解析Monad：状态+错误处理
type MyParser a = StateT SymTable (Either String) a

然后写几个辅助函数来操作符号表：

-- 在当前作用域添加符号（检查重复声明）
addSymbol :: String -> Type -> MyParser ()
addSymbol name typ = do
  st <- get
  case st of
    [] -> lift $ Left "Internal error: empty symbol table stack"
    currentScope:rest ->
      if Map.member name currentScope
        then lift $ Left $ "Duplicate declaration: " ++ name
        else do
          let level = length st  -- 当前作用域层级（栈长度就是层级数）
              entry = SymEntry name typ level
          put $ Map.insert name entry currentScope : rest

-- 压入新作用域（比如进入代码块{）
pushScope :: MyParser ()
pushScope = modify (Map.empty :)

-- 弹出当前作用域（比如离开代码块}）
popScope :: MyParser ()
popScope = modify tail

-- 查找符号（从当前作用域往上遍历，符合LeBlanc-Cook的规则）
lookupSymbol :: String -> MyParser SymEntry
lookupSymbol name = do
  st <- get
  case find (Map.member name) st of
    Just scope -> case Map.lookup name scope of
      Just entry -> return entry
      Nothing -> lift $ Left $ "Symbol not found: " ++ name
    Nothing -> lift $ Left $ "Symbol not found: " ++ name

2. 配置Happy使用自定义Monad #

在Happy的语法文件里，你需要指定使用我们定义的MyParser作为monad，同时指定return和bind操作，还要处理错误：

%name parseProgram  -- 生成的解析函数名
%monad {MyParser} {return} {(>>=)}  -- 告诉Happy用我们的Monad
%error {parseError}  -- 自定义错误处理函数

-- 定义你的token（根据你的语言调整）
%token
  LET     "let"
  INT     "Int"
  IDENT   "identifier"
  NUM     "number"
  LBRACE  "{"
  RBRACE  "}"
  ASSIGN  "="
  COLON   ":"
  -- 其他token...

%%

3. 调整语法规则，结合状态操作 #

现在你可以在每个语法规则里直接调用状态操作，同时构建AST。核心思路是：

• 声明类的规则（比如VARDEF的纯声明形式）只修改符号表，返回不影响AST的空节点（或者Maybe类型，后续过滤）
• 带初始化的声明/执行类规则，既修改符号表，又生成对应的AST节点
• 代码块规则要处理作用域的压入和弹出

举个具体的规则示例：

-- AST节点定义（只保留必要的执行相关节点）
data AST = AST_Root [ASTStmt]
         deriving (Show)

data ASTStmt = AST_Assign String ASTExpr
             | AST_Nop  -- 空语句，用于纯声明的情况
             -- 其他语句类型...
             deriving (Show)

data ASTExpr = AST_LitInt Int
             -- 其他表达式类型...
             deriving (Show)

对应的Happy规则：

START : BLOCK { AST_Root $1 }

-- 代码块：处理作用域的进入和退出
BLOCK : LBRACE pushScope INSTRUCTIONS popScope RBRACE { $3 }
      | INSTRUCTION { [$1] }

-- 指令列表：过滤掉空语句（纯声明）
INSTRUCTIONS : INSTRUCTIONS INSTRUCTION { case $2 of AST_Nop -> $1; stmt -> stmt : $1 }
             | { [] }

-- 单个指令：处理变量定义、修改等
INSTRUCTION : VARDEF { $1 }
            | VARMOD { $1 }
            -- 其他指令类型...

-- 变量定义：两种情况
VARDEF : LET IDENT COLON INT
           { addSymbol $2 IntType >> return AST_Nop }  -- 纯声明，只修改符号表，返回空语句
       | LET IDENT COLON INT ASSIGN NUM
           { addSymbol $2 IntType >> return (AST_Assign $2 (AST_LitInt (read $6))) }  -- 带初始化，生成赋值节点

-- 变量修改（示例：需要查找符号验证存在性）
VARMOD : IDENT ASSIGN NUM
           { do
               _ <- lookupSymbol $1  -- 检查变量是否已声明
               return (AST_Assign $1 (AST_LitInt (read $3)))
           }

注意这里的pushScope和popScope是我们定义的辅助函数，直接写在规则里就行——Happy允许在规则中插入Monad动作，只要它们的类型匹配。

4. 解析入口函数 #

最后，写一个入口函数来运行解析器，得到AST和最终的符号表：

-- 错误处理函数（Happy会调用这个处理语法错误）
parseError :: [Token] -> MyParser a
parseError tokens = lift $ Left $ "Syntax error at tokens: " ++ show tokens

-- 解析入口：输入字符串，返回Either错误信息，或者(AST, 最终符号表)
runMyParser :: String -> Either String (AST, SymTable)
runMyParser input = do
  parserAction <- parseProgram input  -- Happy生成的parseProgram返回MyParser AST
  runStateT parserAction [Map.empty]  -- 初始符号表：一个空的全局作用域

关键要点总结 #

• 单遍解析：所有符号表的修改和验证都在解析过程中完成，AST只保留执行逻辑相关的节点，避免了事后遍历AST的开销。
• 作用域管理：通过pushScope和popScope维护符号表的栈结构，完美契合LeBlanc-Cook的分层作用域规则。
• 错误处理：结合Either可以在解析阶段直接捕获重复声明、未定义符号等错误，不需要等到后续阶段。
• 灵活扩展：如果需要支持类型定义（TYPEDEF），只需要扩展符号表结构（比如添加类型映射的栈），或者单独维护一个类型状态即可。

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