|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[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)]
Если существует единственный разбор, то результатом работы функции-анализатора будет список, состоящий из одного элемента. Если разбор провести невозможно, то результатом будет пустой список. В случае неоднозначной грамматики элементами результирующего списка будут альтернативные варианты разбора. Этот метод называется «список благоприятных исходов»», его описал Вадлер (Wadler) [5]. Он может быть использован в тех случаях, когда возможно применение поиска с возвратом. В учебнике Бёрда (Bird) и Вадлера (Wadler) он используется для решения комбинаторных задач, таких как задача о восьми ферзях [1]. Если необходимо получить только одно решение, а не все возможные, то вы можете взять голову списка благоприятных исходов. Благодаря отложенному вычислению, если требуется только первое значение, то не все элементы списка будут определены, так что потери эффективности не произойдет. Отложенные вычисления позволяют использовать поиск с возвратом для получения первого решения. Парсеры имеющий тип, описываемый нами до сих пор, работают со строками, которые являются списками символов. Однако, это не мешает допустить разбор строк, состоящих из элементов, отличных от символов. Можно предположить ситуацию, когда препроцессор подготавливает список лексем, который затем разбирается. Чтобы учесть этот случай, в качестве последнего усовершенствования типа парсера, мы снова абстрагируемся от типа - от типа элементов входной строки. Обозначив его а, а тип результата b, можно определить тип парсера следующим образом: type Parser a b = [a] -> [([a], b)] или так, если вы предпочитаете кратким идентификаторам более выразительные: type Parser symbol result = [symbol] -> [([symbol], result)] Мы будем использовать это определение типа в оставшейся части данной статьи.
£ то св а: =з 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.
|
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||