sml - smlnj 中算术表达式的递归下降解析器

Question

我必须在 SML 中编写一个递归下降解析器，类似于这个SO Post。我只需要为加法、减法、乘法和除法运算编写它。

解析器应该能够处理运算符的优先级和括号。

这是我到现在为止写的——

    exception invalid

fun parseExpression ([], x2) = (x2, [])
|   parseExpression (h2::t2, x2) =
    let
        fun parseTerm ([], x1) = (x1, [])
        |   parseTerm (h1::t1, x1) =
            let
                fun parseFactor ([], x) = (x, [])
                |   parseFactor (h::t, x) =
                    if(h = "~") then 
                        let val (a, b) = parseFactor(t, x) in (~1 * a, b) end
                    else if(h = "(") then parseExpression (t, x)
                    else if(h = ")") then (x, t)
                    else
                        let
                            val v1 = Int.fromString(h)
                        in
                            case v1 of
                            SOME v => (v, t)
                            | NONE => raise invalid
                        end
                val (y1, yl1::ys1) = parseFactor (h1::t1, x1)
            in
                if(yl1 = "/") then
                    let val (elm1, exp1) = parseFactor (ys1, x1) in parseTerm(exp1, y1 div elm1) end
                else if(yl1 = "*") then
                    let val (elm1, exp1) = parseFactor (ys1, x1) in parseTerm(exp1, y1 * elm1) end
                else (y1, yl1::ys1)
            end
        val (y, yl::ys) = parseTerm (h2::t2, x2)
    in
        if(yl = "+") then
            let val (elm, exp) = parseTerm (ys, x2) in parseExpression(exp, y + elm) end
        else if(yl = "-") then
            let val (elm, exp) = parseTerm (ys, x2) in parseExpression(exp, y - elm) end
        else (y, yl::ys)
    end

fun parse L =
    let
        val (x, L1) = parseExpression (L, 0)
    in
        if(L1 = []) then x
        else raise invalid
    end
fun takeinput () =
    let
        val inp = TextIO.inputLine TextIO.stdIn
        val exp = case inp of
                    SOME s => s
                  | NONE => raise invalid
        val tkns = String.tokens Char.isSpace exp
    in
        parse tkns
    end
end

函数的输入parse是表达式的字符串标记列表。

对于普通的三个操作数表达式，例如 -
45 + 52 * 6
，该函数运行良好，但对于包括括号在内的较大表达式，它会引发绑定和无效异常。

感谢您对代码的任何帮助。

我认为我还没有实现这样的for结构 -

for (;;) {
                if      (eat('+')) x += parseTerm(); // addition
                else if (eat('-')) x -= parseTerm(); // subtraction
                else return x;
            }

功能和eat评价parenthesis得当。当我看到右括号时，我有点困惑该怎么做。

标签： smlsmlnjrecursive-descent