Теоретические сведения
Целью синтаксического анализа является разбор строки символов на отдельные составляющие элементы согласно набору синтаксических правил.
Например, простую скобочную запись 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
В аналогичном случае с ассоциацией влево ситуация будет несколько сложнее.
Запишем основные правила для синтаксического разбора:
- f преобразуется в Atom "f"
- f x преобразуется в Comb(Atom "f", Atom "x")
- 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"];
