Введение в теорию программирования. Функциональный подход



   Гостиница Волхов 2            

Теоретические сведения


Целью синтаксического анализа является разбор строки символов на отдельные составляющие элементы согласно набору синтаксических правил.

Например, простую скобочную запись a(bc) можно представить как в виде аппликации a -> (b -> c), так и в виде двоичного дерева.

Рассмотрим простой случай разбора аппликативного выражения, записанного в виде бесскобочного выражения.

Создадим рекурсивный тип – бинарное дерево:

datatype tree = Atom of string | Comb of tree * tree

Примем за минимальную синтаксическую единицу один символ и будем считать, что строка представляет из себя последовательную аппликацию с ассоциацией влево (f xyz):

fun Parse [next] = Atom next | Parse (next::rest) = Comb(Atom next, Parse rest);

В результате выполнения процедуры синтаксического анализа

Parse["f", "x", "y", "z"]

получим

val it = Comb (Atom "f",Comb (Atom "x", Comb (Atom "y",Atom "z"))) : tree

В аналогичном случае с ассоциацией влево ситуация будет несколько сложнее.

Запишем основные правила для синтаксического разбора:

  1. f преобразуется в Atom "f"
  2. f x преобразуется в Comb(Atom "f", Atom "x")
  3. f xy преобразуется в Comb(Comb(Atom "f", Atom "x"), Atom "y")

Запись этих правил на SML будет выглядеть следующим образом:

fun Parser t[] = t | Parser t (next::rest) = Parser (Comb(t, Atom next)) rest; fun Parse [next] = Atom next| Parse (next::rest) = Parser (Atom next) rest; Parse["f", "x", "y", "z"];




Содержание    Вперед