时间戳

首页 > 解决方案 > 将字符串解析为 Ast

parsing - 将字符串解析为 Ast

问题描述

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

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

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"返回(Sum (Num 1) (Num 4))，我有什么方法可以做到这一点？我是否将输出parseExpr视为列表并从第 0 个索引中获取 Ast，或者这不可能？我是否必须改变我parseExpr通过列表的方式？任何帮助是极大的赞赏！顺便说一句，我无法更改函数的任何定义，也无法更改 Ast 的语法或数据类型。

标签： parsinghaskelltreeabstract-syntax-tree

解决方案

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

您可以使用函数从元组中获取第一个元素fst。

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

推荐阅读