将字符串解析为 Ast

Question

我需要一些关于我做一些解析的函数的指导。

这是我的语法（我无法更改）：

Expr -> Int | - Expr | + Expr Expr | * Expr Expr
Int -> Digit | Digit Int
Digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

我的数据类型（我应该填写 Min 和 Mult，我想我是对的）：

data Ast = Num Int | Sum Ast Ast | Mult Ast Ast | Min Ast | Var String  deriving (Eq, Show)

所以首先我创建了一个分词器方法，将字符串拆分为字符列表：

tokenize :: String -> [String]
tokenize [] = []
tokenize xs @ (x : xs')
    | x `elem` t = [x] : tokenize xs'
    | isDigit x = [y | y <- takeWhile isDigit xs] : (tokenize (dropWhile isDigit xs))
    | otherwise = tokenize xs'
        where t = ['+', '-', '*']

这可以正常工作。

接下来我做了 parseExpr :: [String] -> (Ast, [String])。它正在做的是通过 tokenize :: String -> [String] 制作的列表并递归地生成 Ast（我认为至少）

parseExpr :: [String] -> (Ast,[String])
parseExpr [] = error "Error!"
parseExpr (s:ss) | all isDigit s = (Num (read s),ss)
             | s == "-" = let (e,ss') = parseExpr ss in (Min e,ss')
             | s == "*" = (Mult e e',ss'')
             | s == "+" = (Sum e e',ss'') where
                          (e,ss') = parseExpr ss
                          (e',ss'') = parseExpr ss'

我现在苦恼的是如何将这些组合到函数中 parse :: String -> Ast。我这样做的尝试（可能还有很长的路要走）是这样的。 parseExpr 产生形式为 (Ast, [String]):

的输出

parse :: String -> Ast
parse [] = error "Empty string"
parse str = parseExpr x
  where x = tokenize str

我的问题是：

假设我有简单的字符串str = "+ 1 4"。

tokenize str = ["+", "1", "4"]

运行 parseExpr 递归地遍历来自 tokenize 的列表并产生这个输出：

(Sum (Num 1) (Num 4),[])

它输出 Ast 和一个空的字符串列表。

现在是手头的问题。我需要做到 parse "+ 1 4" returns (Sum (Num 1) (Num 4)) 我可以通过哪些方式做到这一点？我是否将 parseExpr 的输出视为列表并从第 0 个索引中获取 Ast，或者这是不可能的？我是否必须更改我的 parseExpr 浏览列表的方式？任何帮助是极大的赞赏！顺便说一句，我不能更改函数的任何定义，也不能更改 Ast 的语法或数据类型。

Answer 1

(Sum (Num 1) (Num 4),[]) 是一个元组，您需要第一个元素。

您可以使用函数 fst.

从元组中获取第一个元素

parse :: String -> Ast
parse [] = error "Empty string"
parse str = fst $ parseExpr x
  where x = tokenize str

将字符串解析为 Ast

Parse String to Ast

tree

parsing

haskell

abstract-syntax-tree