基于SML的算术表达式递归下降解析器开发求助（含代码片段）

我帮你把这个SML递归下降算术表达式解析器的需求和代码整理成清晰的Markdown格式，还补全了未完成的部分，确保它能正确处理运算符优先级和括号：

核心需求 #

• 支持加法、减法、乘法、除法四种基础运算
• 自动遵循运算符优先级：乘除（高优先级）> 加减（低优先级）
• 支持通过括号手动改变运算顺序
• 采用递归下降解析的实现方式

完整实现代码 #

exception InvalidExpression

(* 处理加减运算（低优先级） *)
fun parseExpression ([], acc) = (acc, [])
  | parseExpression (token::tokens, acc) =
    case token of
        "+" => let val (termVal, rest) = parseTerm(tokens, 0)
               in parseExpression(rest, acc + termVal) end
      | "-" => let val (termVal, rest) = parseTerm(tokens, 0)
               in parseExpression(rest, acc - termVal) end
      | _ => parseTerm(token::tokens, acc)

(* 处理乘除运算（高优先级） *)
and parseTerm ([], acc) = (acc, [])
  | parseTerm (token::tokens, acc) =
    case token of
        "*" => let val (factorVal, rest) = parseFactor(tokens, 0)
               in parseTerm(rest, acc * factorVal) end
      | "/" => let val (factorVal, rest) = parseFactor(tokens, 0)
               in if factorVal = 0 then raise InvalidExpression else parseTerm(rest, acc div factorVal) end
      | _ => parseFactor(token::tokens, acc)

(* 处理数字和括号（最基础单元） *)
and parseFactor ([], acc) = (acc, [])
  | parseFactor (token::tokens, acc) =
    case token of
        "(" => let val (exprVal, restAfterExpr) = parseExpression(tokens, 0)
               in case restAfterExpr of
                      ")"::rest => (exprVal, rest)
                    | _ => raise InvalidExpression
                  end
      | num => if List.all Char.isDigit (explode num)
               then parseFactor(tokens, valOf (Int.fromString num))
               else raise InvalidExpression

(* 辅助函数：将输入字符串拆分为token列表（处理空格、拆分符号与数字） *)
fun tokenize s =
  let fun helper [] acc = [implode (rev acc)]
        | helper (c::cs) acc =
          if Char.isSpace c
          then if acc = [] then helper cs acc else implode (rev acc) :: helper cs []
          else if c = #"(" orelse c = #")" orelse c = #"+" orelse c = #"-" orelse c = #"*" orelse c = #"/"
          then if acc = [] then str c :: helper cs [] else implode (rev acc) :: str c :: helper cs []
          else helper cs (c::acc)
  in helper (explode s) [] end

(* 顶层解析函数：输入表达式字符串，返回计算结果 *)
fun evaluate expr =
  let val tokens = tokenize expr
      val (result, []) = parseExpression(tokens, 0)
  in result end

(* 测试用例 *)
val test1 = evaluate "3 + 4 * 2"   (* 预期输出：11 *)
val test2 = evaluate "(3 + 4) * 2" (* 预期输出：14 *)
val test3 = evaluate "10 - 6 / 2"  (* 预期输出：7 *)
val test4 = evaluate "8 / (4 - 2)" (* 预期输出：4 *)

代码逻辑说明 #

• parseExpression：负责处理加减这类低优先级运算，递归调用parseTerm获取高优先级运算的结果作为操作数
• parseTerm：负责处理乘除这类高优先级运算，递归调用parseFactor获取最基础的运算单元（数字或括号内表达式）
• parseFactor：处理最基础的运算单元，遇到括号时会递归调用parseExpression解析括号内的完整表达式，遇到数字则转换为整数
• tokenize：把输入的字符串转换成结构化的token列表，自动处理空格并区分数字、运算符和括号
• InvalidExpression异常：用于捕获语法错误（比如不匹配的括号、无效字符、除零操作等）

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