ФЭНДОМ


Алгоритм рекурсивного спускаПравить

Алгоритм рекурсивного спуска -- это простейший способ разбора текста. При помощи него можно, особо не задумываясь, разобрать, например, арифметическое выражение. Основная идея заключается в том, чтобы разнести разбор разных операций (с разным приоритетом) по разным взаимно-рекурсивным функциям. Тогда, с точки зрения каждой из них, выражение представляет собой набор каких-то левых кусков текста, скреплённых знаками. Содержимое этих кусков функцию не волнует, так как его она разбирать не должна - этим займутся другие, более высокоприоритетные функции. Например, с точки зрения функции, разбирающей операции сложения и вычитания (очевидно, что они имеют равный приоритет), выражение выглядит так:

<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 ] \<var>.L | app
app := [app ] term
term := (L) | <var>

L := \<var>.L | app
app := term L | term
term := (L) | <var> 

Разбор лямбдыПравить

 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