Парсер рекурсивного спуска для арифметических выражений в smlnj - PullRequest
Новая
       34

Парсер рекурсивного спуска для арифметических выражений в smlnj

0 голосов
/ 03 мая 2018

Мне нужно написать синтаксический анализатор рекурсивного спуска в 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
функция работает нормально, но для больших выражений, включая скобки, она вызывает bind и недопустимые исключения.

Любая помощь с кодом приветствуется.

Я думаю, что я не реализовал for конструкции, подобные этой - 

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

функция eat и оценка parenthesis правильно. Я немного запутался, что делать, когда вижу закрывающую скобку.

...