Понимание этого реализованного парсера рекурсивного спуска в Haskell - PullRequest
Новая
       51

Понимание этого реализованного парсера рекурсивного спуска в Haskell

1 голос
/ 11 октября 2019

У меня была проблема с назначением, когда мне приходилось анализировать нотацию префиксного калькулятора в предварительно определенном AST. Нам дали довольно полный алгоритм разбора (нам пришлось добавить кое-что).

Алгоритм и AST, который я представил, выглядит следующим образом: 

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

parseExpr :: [String] -> (Ast, [String])
parseExpr [] = error "Empty!"
parseExpr ("+":rs) = let (e1, r1) = parseExpr rs ;(e2, r2) = parseExpr r1 in (Sum e1 e2, r2)
parseExpr ("*":rs) = let (e1, r1) = parseExpr rs ;(e2, r2) = parseExpr r1 in (Mult e1 e2, r2)
parseExpr ("-":rs) = let (e1, r1) = parseExpr rs in (Min e1, r1)
parseExpr (x:rs)
        | all isDigit x = (Tall (read x), rs)
        | all isAlpha x = (Var x, rs)
        | otherwise = error ("Syntax errors "++x)

Пример ввода / вывода: 

parseExpr ["+","4","*","8","-","5"] =
 (Sum (Tall 4) (Mult (Tall 8) (Min (Tall 5))),[])

В продолжении моего задания мне была нужна первая часть кортежа. Это правильно, назначение передается, и все хорошо для целей назначения.

Сказав это, я не знаю, что происходит в рекурсивной функции. Особенно в этих трех строках: 

parseExpr ("+":rs) = let (e1, r1) = parseExpr rs ;(e2, r2) = parseExpr r1 in (Sum e1 e2, r2)
parseExpr ("*":rs) = let (e1, r1) = parseExpr rs ;(e2, r2) = parseExpr r1 in (Mult e1 e2, r2)
parseExpr ("-":rs) = let (e1, r1) = parseExpr rs in (Min e1, r1)

Конечно, я получаю обозначение ("+": rs). Что мне трудно понять, так это «let (e1, r1) = .....» и т. Д.

И в охранниках в конце я не вижу никаких рекурсивных вызовов. Тем не менее, рекурсия происходит, верно? Как это работает?

1 Ответ

0 голосов
/ 11 октября 2019

Давайте напишем одно из определений более традиционным способом: 

parseExpr ("+":rs) = let (e1, r1) = parseExpr rs -- recursive call #1
                         (e2, r2) = parseExpr r1 -- recursive call #2
                     in (Sum e1 e2, r2)

Учитывая список, который начинается с "+", мы сначала рекурсивно анализируем токены, следующие за "+";полученному выражению присваивается имя e1, а неиспользованному суффиксу rs присваивается имя r1. Мы повторяем процесс, анализируя r1, чтобы получить выражение e2 и оставшиеся входные данные r2. Таким образом, мы можем построить значение Sum, используя два подвыражения e1 и e2, и передать обратно r2, чтобы наш вызывающий мог выполнить синтаксический анализ.

Используя ваш пример, 

-- Step 1
parseExpr ["+","4","*","8","-","5"] 
  = let (e1, r1) = parseExpr ["4","*","8","-","5"]
        (e2, r2) = parseExpr r1
    in (Sum e1 e2, r2)

Прежде чем мы сможем сделать что-то еще, мы должны оценить первый рекурсивный вызов 

-- Step 2
parseExpr ["4","*","8","-","5"] = (Tall 4, ["*","8","-","5"])

Теперь мы можем подключить этот результат обратно к шагу 1 

-- Step 3
parseExpr ["+","4","*","8","-","5"] 
  = let (e1, r1) = (Tall 4, ["*","8","-","5"])
        (e2, r2) = parseExpr r1
    in (Sum e1 e2, r2)

-- Step 4
parseExpr ["+","4","*","8","-","5"] 
  = let (e2, r2) = parseExpr ["*","8","-","5"]
    in (Sum (Tall 4) e2, r2)

И так далее. ...

...