如何用Haskell编写Lisp解析器？解析分支错误问题求助

Let's break down why your current parser isn't handling parallel branches correctly, and how to fix it. The core issue is that your original parse function doesn't track remaining tokens after parsing a subexpression—so it can't resume parsing sibling nodes once it hits a closing parenthesis.

First, Clean Up the AST Type #

Your original Ast type has a type parameter x, but since we're working with string tokens, we can simplify it to avoid unnecessary generality:

data Ast = Val String | Node [Ast] deriving (Show)

The Key Fix: Return Remaining Tokens #

To handle parallel branches, our parser functions need to return two things:

1. The parsed AST node(s)
2. The remaining unprocessed tokens (so we can keep parsing sibling expressions)

We'll split parsing into two helper functions:

• parseExpr: Parses a single Lisp expression (either a value or a parenthesized list)
• parseMany: Parses multiple expressions until it hits a closing parenthesis or runs out of tokens

Implementing the Fixed Parser #

data Ast = Val String | Node [Ast] deriving (Show)

-- Parses multiple expressions until a closing parenthesis is found
parseMany :: [String] -> ([Ast], [String])
parseMany [] = ([], [])
parseMany (")":rest) = ([], rest)  -- Stop at closing paren, return remaining tokens
parseMany tokens =
  let (expr, restAfterExpr) = parseExpr tokens
      (remainingExprs, restFinal) = parseMany restAfterExpr
  in (expr : remainingExprs, restFinal)

-- Parses a single Lisp expression
parseExpr :: [String] -> (Ast, [String])
parseExpr [] = error "Unexpected end of input"
parseExpr ("(":rest) =
  let (exprs, restAfterList) = parseMany rest
  in (Node exprs, restAfterList)  -- Wrap the parsed list in a Node
parseExpr (")":_) = error "Unexpected closing parenthesis"
parseExpr (token:rest) = (Val token, rest)  -- Parse a literal value

Testing with Your Example #

Let's use your sample input to verify:

program = "(begin (define r 10) (* pi (* r r)))"
astTokenized = ["(","begin","(","define","r","10",")","(","*","pi","(","*","r","r",")",")",")"]

-- Parse the entire program (it's a single top-level expression)
main = print $ fst $ parseExpr astTokenized

This will output the correct parallel AST:

Node [Val "begin",Node [Val "define",Val "r",Val "10"],Node [Val "*",Val "pi",Node [Val "*",Val "r",Val "r"]]]

Why Your Original Code Failed #

• First version: When it hit a ), it returned [], which stopped parsing entirely—so it never got to the (* pi ...) expression.
• Second version: It ignored ) and kept parsing, which forced all subsequent expressions into the previous Node, creating overly nested structures instead of parallel siblings.

By returning remaining tokens, we let the parser know where to resume after finishing a subexpression, which is critical for building correct sibling branches in the AST.

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