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

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

Например, простую скобочную запись 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"];

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

---

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий

---

---

---