Функции для синтаксического разбора простых языковых конструкций

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

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

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

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

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

Запись этих правил на 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"];

Задание

Сформулируйте формальную постановку задачи, запишите правила вывода и реализуйте программу на SML в соответствии с вариантом исполнения. В качестве целевого типа взять бинарное дерево вида:

tree = Nil | Atom of string |
    Comb of tree * tree;

Варианты заданий

Реализовать функцию на языке программирования SML, которая выполняет синтаксический разбор следующего аппликативного выражения по ассоциации влево с построением бинарного дерева:

Реализовать функцию на языке программирования SML, которая выполняет синтаксический разбор следующего аппликативного выражения по ассоциации вправо с построением бинарного дерева: