Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[2]

2. ТИП «PARSER»

Задачей синтаксического анализа является построение дерева, описывающего структуру заданной строки. В функциональном языке мы можем определить тип данных Tree (дерево). Парсер может быть реализован посредством функции следующего типа:

type Parser = String -> Tree

Для разбора подструктур парсер может вызвать другие парсеры или рекурсивно самого себя. Этим вызовам необходимо обмениваться не только своими результатами, но и информацией о том, какая часть входной строки осталась необработанной. Поскольку это не может быть сделано при помощи глобальной переменной, необработанная часть входной строки должна быть частью результата работы анализатора. Два результата могут быть сгруппированы в кортеж. Более удачным определением для типа Parser является следующее:

type Parser = String -> (String, Tree)

Тип String определён в стандартной вводной части как список символов. Однако, тип Tree ещё не определён. Тип возвращаемого дерева зависит от приложения. Поэтому лучше превратить тип анализатора в полиморфный тип, параметризируя его типом дерева разбора. Таким образом мы абстрагируемся от типа поступающего дерева разбора, заменяя его переменным типом а:

type Parser a = String -> (String, a)

Например, анализатор, возвращающий структуру типа Oak теперь имеет тип Parser Oak. Для деревьев разбора, представляющих структуру Expression (выражение) мы можем определить тип Expr, делая возможным разработку анализатора, возвращающего выражение: Parser Expr. Другим примером анализатора является функция, распознающая строку цифр и возвращающая число, представленное этой строкой, в качестве «дерева разбора». В этом случае данная функция имеет тип Parser Int.

До сих пор мы предполагали, что каждая строка может быть разобрана ровно одним способом. В общем случае это предположение не обязательно верно: одна строка может быть разобрана различными способами или может не существовать ни одного способа разбора строки. В качестве ещё одного усовершенствования определения типа мы допустим, что вместо одного дерева разбора (и связанной с ним необработанной частью строки) парсер возвращает список деревьев. Каждый элемент результата является списком, состоящим из дерева и части строки, оставшейся необработанной после разбора. Следовательно, более подходящим является следующее определение типа Parser:

type Parser a = String -> [(String, a)]

ФП 02005-06 01

№ докум.


Если существует единственный разбор, то результатом работы функции-анализатора будет список, состоящий из одного элемента. Если разбор провести невозможно, то результатом будет пустой список. В случае неоднозначной грамматики элементами результирующего списка будут альтернативные варианты разбора.

Этот метод называется «список благоприятных исходов»», его описал Вадлер (Wadler) [5]. Он может быть использован в тех случаях, когда возможно применение поиска с возвратом. В учебнике Бёрда (Bird) и Вадлера (Wadler) он используется для решения комбинаторных задач, таких как задача о восьми ферзях [1]. Если необходимо получить только одно решение, а не все возможные, то вы можете взять голову списка благоприятных исходов. Благодаря отложенному вычислению, если требуется только первое значение, то не все элементы списка будут определены, так что потери эффективности не произойдет. Отложенные вычисления позволяют использовать поиск с возвратом для получения первого решения.

Парсеры имеющий тип, описываемый нами до сих пор, работают со строками, которые являются списками символов. Однако, это не мешает допустить разбор строк, состоящих из элементов, отличных от символов. Можно предположить ситуацию, когда препроцессор подготавливает список лексем, который затем разбирается. Чтобы учесть этот случай, в качестве последнего усовершенствования типа парсера, мы снова абстрагируемся от типа - от типа элементов входной строки. Обозначив его а, а тип результата b, можно определить тип парсера следующим образом:

type Parser a b = [a] -> [([a], b)]

или так, если вы предпочитаете кратким идентификаторам более выразительные: type Parser symbol result = [symbol] -> [([symbol], result)]

Мы будем использовать это определение типа в оставшейся части данной статьи.

ФП 02005-06 01


£ то

св а: =з

3. ПРОСТЕЙШИЕ ПАРСЕРЫ

Мы начнём с довольно простого, дав определение функции разбора, которая распознаёт символ «а». В этом случае типом символов входной строки будет Char и в качестве «дерева разбора» мы также просто используем Char:

symbola:: Parser Char Char

symbola []= []

symbola (x:xs) x == a= [(xs, a)]

otherwise = []

Сразу же становится очевидным преимущество списка благоприятных исходов, потому что теперь мы можем вернуть пустой список в том случае, когда разбор невозможен (так как входная строка пуста или не начинается с символа «а»).

Таким же образом мы можем написать парсеры, распознающие другие символы. Как всегда вместо того, чтобы определять много тесно связанных функций, лучше абстрагироваться от распознаваемого символа, сделав его дополнительным параметром функции. Также функция может оперировать со строками, состоящими из элементов, отличных от символов, таким образом, она может быть применена в приложениях, ориентированных на обработку не только символьных данных. Единственным необходимым условием является то, что символы, которые нужно разобрать могут пройти проверку на равенство. В языке Gofer это обозначается предикатом Eq в типе функции:

symbol:: Eq s => s -> Parser s s

symbol a []= []

symbol a (x:xs) a == x= [(xs, x)]

otherwise = []

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

symbol a [] symbol a (x:xs)

= [(xs, a) a == x]

В языке Gofer список без генераторов, лишь с условием, определён как пустой или состоящий из одного элемента, в зависимости от условия.

Функция symbol - это функция, которая возвращает парсер для заданного символа. Парсер, в свою очередь также является функцией. Вот почему в определении функции symbol появилось два параметра.

Теперь мы определим некоторые простейшие парсеры, которые могут выполнять работу, традиционно выполняемую лексическими анализаторами. Например, полезным является парсер, распознающий фиксированную строку символов, такую как «begin» или «end». Мы назовем эту функцию token.

ФП 02005-06 01



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13]