Алгоритм рекурсивного спуска[]
Алгоритм рекурсивного спуска -- это простейший способ разбора текста. При помощи него можно, особо не задумываясь, разобрать, например, арифметическое выражение. Основная идея заключается в том, чтобы разнести разбор разных операций (с разным приоритетом) по разным взаимно-рекурсивным функциям. Тогда, с точки зрения каждой из них, выражение представляет собой набор каких-то левых кусков текста, скреплённых знаками. Содержимое этих кусков функцию не волнует, так как его она разбирать не должна - этим займутся другие, более высокоприоритетные функции. Например, с точки зрения функции, разбирающей операции сложения и вычитания (очевидно, что они имеют равный приоритет), выражение выглядит так:
<expr> := <term>[+<expr>] | <term>[-<expr>]
Это самое простое определение, которое, тем не менее, обладает одним существенным недостатком. Оно неверное. Причина проста: оно утверждает, что операции ( + ) и ( - ) правоассоциативны, однако это верно только по отношению к сложению. Совершенно очевидно, что вычитание следует рассматривать как левоассоциативную операцию. Любой нормальный человек скажет, что
1 - 1 - 1 = (1 - 1) - 1 = -1
Однако, следуя данному выше определению, получаем, что
1 - 1 - 1 = 1 - (1 - 1) = 1
что сомнительно. Таким образом, следует переписать приведённое выше определение как
<expr> := [<expr>+]<term> | [<expr>-]<term>
Грамматика арифметических выражений[]
Итак, с ассоциативностью разобрались. Теперь можно привести полную грамматику, описывающую арифметические выражения. Обозначения операций: ( + ), ( - ), ( * ), ( / ), ( ^ ), - стандартны.
<expr> := [<expr>+]<term> | [<expr>-]<term> // expr = expression - выражение <term> := [<term>*]<powr> | [<term>/]<powr> // term - одночлен <powr> := <atom>[^<powr>] // powr = power - степень; эта операция правоассоциативна <atom> := -<atom> | <int> | (<expr>) // ну а дальше -- просто трюк для представления чисел <int> := <number> | <int><number> <number> := 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
После такого описания грамматики программа, реализующая её разбор, становится весьма очевидной.
Разбор арифметических выражений[]
type tree =
| Num of int
| Minus of tree
| Add of tree * tree
| Mul of tree * tree
| Sub of tree * tree
| Div of tree * tree
| Pow of tree * tree
let parse s =
let int_of_ascii x = int_of_char x - 48
and s = s ^ ";"
and i = ref 0 in
let parse_num () =
let rec pn acc =
match s.[!i] with
|'0'..'9' as x -> incr i; pn (10 * acc + (int_of_ascii x))
|_ -> Num acc in pn 0 in
let rec parse_expr () =
let rec pe acc =
match s.[!i] with
|'+' -> incr i; pe (Add (acc, parse_term ()))
|'-' -> incr i; pe (Sub (acc, parse_term ()))
| _ -> acc in pe (parse_term ())
and parse_term () =
let rec pt acc =
match s.[!i] with
|'*' -> incr i; pt (Mul (acc, parse_powr ()))
|'/' -> incr i; pt (Div (acc, parse_powr ()))
| _ -> acc in pt (parse_powr ())
and parse_powr () =
let atom = parse_atom () in
match s.[!i] with
|'^' -> Pow (atom, parse_powr ())
| _ -> atom in
and parse_atom () =
match s.[!i] with
'0'..'9' -> parse_num i
|'-' -> incr i; Minus (parse_atom ())
|'(' -> incr i; let t = parse_expr () in
if s.[!i] <> ')' then failwith ")"
else incr i; t
|_ -> failwith "?!!" in
let result = parse_expr () in if s.[!i] <> ';' then failwith "?!!" else result
Грамматика лямбды[]
L := [app ] \.L | app app := [app ] term term := (L) | L := \.L | app app := term L | term term := (L) |
Разбор лямбды[]
type lambda =
| Var of string
| App of lambda * lambda
| Abs of string * lambda
let parse s =
let between x a b = (a <= x) && (x <= b) in
let is_char x = (between x 'a' 'z') || (between x '0' '9') || (x = char_of_int 39)
and s = s ^ ";"
and i = ref 0 in
let parse_var () =
let rec pv acc =
match s.[!i] with
|x when is_char x -> incr i; pv (acc ^ (String.make 1 x))
|'.' | ' ' | ')' | ';' -> acc
|_ -> failwith "unexpected symbol" in pv "" in
let rec parse_expr full =
match s.[!i] with
|'\\' -> incr i; let x = parse_var () in Abs (x, parse_expr true)
|'.' -> incr i; parse_expr true
|'(' -> incr i; let t = parse_expr true in
if s.[!i] <> ')' then failwith ")"
else (incr i; if full then parse_app t else t)
|';' -> failwith "end of line reached unexpectedly"
| _ -> let t = parse_var () in if full then parse_app (Var t) else Var t
and parse_app acc =
match s.[!i] with
|' ' -> incr i; let t = parse_expr false in parse_app (App (acc, t))
| _ -> acc in
parse_expr true