|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[6] £ то 7. ДОПОЛНИТЕЛЬНЫЕ КОМБИНАТОРЫ СИНТАКСИЧЕСКОГО АНАЛИЗА Несмотря на то, что в принципе вы можете построить парсеры для любого контекстно-свободного языка используя комбинаторы <*> и <>, на практике проще иметь в распоряжении несколько дополнительных комбинаторов синтаксического анализа. В традиционных грамматических формализмах для описания, например, необязательных или повторяющихся конструкций также используются дополнительные символы. Например рассмотрим формализм БНФ, в котором изначально могли быть использованы только последовательное и параллельное соединения (обозначаемые размещение рядом и вертикальными линиями соответственно), а позже он был расширен таким образом, чтобы учитывать также повторение, обозначаемое звёздочками. Очень просто сделать новые комбинаторы для расширений, подобных этому. В качестве первого примера мы рассмотрим повторение. Для данного парсера структуры, many создает разборщик для 0 или более вхождений этой структуры: many:: Parser s a -> Parser s [a] many p = p <*> many p <@ list <> succeed [] Дополнительная функция list является некаррированной версией конструктора списков: list (x, xs) = x : xs Рекурсивное определение парсера вытекает из рекурсивной структуры списков. Возможно даже лучшим является определение, в котором вместо succeed используется парсер epsilon. many:: Parser s a -> Parser s [a] many p = p <*> many p <@ (\(x, xs) -> x : xs) <> epsilon <@ (\ -> []) Упражнение 9. Чтобы достигнуть симметричности, мы можем также постараться и избежать оператора <@ в обоих альтернативах. Ранее мы определили оператор <* как сокращение применения <@fst к результату, возвращаемому оператором <*>. В функции many результат <*> также подвергается последующей обработке. Определите служебную операцию <:*> для данного случая и используйте её для ещё большего упрощения определения many. Порядок расположения альтернатив влияет только на порядок, в котором решения располагаются в списке благоприятных исходов. Упражнение 10. Предположим, что парсер many (symbola) применён к строке «ааа». В каком порядке появятся четыре возможных разбора в списке благоприятных исходов?
Пример, показывающий как комбинатор many может быть использован для разбора натурального числа: natural :: Parser Char Int natural = many digit <@ foldl f 0 where f a b = a * 10 + b Определенный таким образом, парсер natural принимает пустую входную строку также за число. Если это нежелательно, то лучше использовать комбинатор синтаксического анализа many], который допускает одно или более вхождений структуры. Упражнение 11. Определите комбинатор синтаксического анализа many]. Другой комбинатор, с которым вы возможно знакомы из других формализмов, это комбинатор option. Построенный парсер возвращает список из нуля или одного элемента в зависимости от того, была ли распознана структура или нет. option :: Parser s a -> Parser s [a] option p = p <@ (\x -> [x]) <> epsilon <@ (\x -> []) По эстетическим соображениям мы использовали epsilon в данном определении; вторую альтернативу можно было написать другим способом - succeed []. Комбинаторы many, many] и option являются классическими структурами, входящими в состав компилятора, но нет необходимости оставлять всё как есть. Например, во многих языках, структуры часто заключены между двумя ничего не значащими символами, чаще всего это некоторого рода скобки. Для этого мы создадим комбинатор синтаксического анализа pack. Для заданных парсеров для открывающего символа, основной части и закрывающего символа он строит анализатор для вложенной основной части: pack s1 p s2 = Parser s a -> Parser s b -> Parser s c -> Parser s b s1 *> p <* s2 Особыми случаями данного комбинатора являются следующие: parenthesized p bracketed p compound p pack (symbol () p (symbol )) pack (symbol [) p (symbol ]) pack (token "begin") p (token "end") Другой часто встречающейся конструкцией является повторение некоторой структуры, при котором элементы разделены некоторым символом. Вы можете представить себе список параметров (выражения, разделённые запятыми) или составные операторы (операторы, разделённые точкой с запятой). Для деревьев разбора разделители не представляют никакого интереса. Функция listOf приведённая ниже, создает парсер для списка (возможно пустого) из заданных парсера для элементов и парсера для разделителей:
listOf p s Parser s a -> Parser s b -> Parser s [a] p <:*> many (s *> p) <> succeed [] Полезными частными случаями являются: commaList, semicList commaList p semicList p Parser Char a -> Parser Char [a] listOf p (symbol ,) listOf p (symbol ;) Упражнение 12. В качестве ещё одной вариации на тему «повторение», определите комбинатор синтаксического анализа sequence, преобразующий список парсеров для некоторого типа в парсер, возвращающий список элементов этого типа. Также определите комбинатор choice, выполняющий повторное применение оператора <>. Упражнение 13. В качестве приложения sequence определите функцию token, которая обсуждалась в 3-ей части. Несколько более сложным вариантом функции listOf является случай, когда разделители несут смысловую нагрузку. Например, арифметические выражения, в которых операторы, разделяющие подвыражения должны быть частью дерева разбора. Для этого случая мы разработаем функции chainr и chainl. Эти функции предполагают, что для разделителей парсер вернёт функцию (!); эта функция используется chain для комбинирования деревьев разбора для этих элементов. В случае функции chainr оператор применяется справа налево, в случае chainl - слева направо. Основная структура chainl такая же как у listOf. Но в том случае, когда функция listOf отбрасывает разделители с помощью оператора *>, мы оставим их в результате используя <*>. Более того, последующая обработка теперь более сложная, чем просто применение функции list. chainl chainl p s Parser s a -> Parser s (a->a->a) -> Parser s a p <*> many (s <*> p) <@ f Функция f должна подействовать на элемент и список кортежей, каждый из которых содержит оператор и элемент. Например, функция f (e0, [(Фи, e1), (Ф2, e2), (Ф3, e3)]) должна вернуть ((e0 Фи eu) Ф2 e2) Ф3 e3. Вы можете узнать здесь версию foldl (хотя и некаррированную), в которой кортеж (Ф, y) из списка и промежуточный результат x комбинируются применением x Ф y. Если мы определим ap2 (op, y) x= x "op" y или даже ap2 (op, y) ("op" y) то мы можем определить chainl:: Parser s a -> Parser s (a->a->a) -> Parser s a chainl p s = p <*> many (s <*> p) <@ uncurry (foldl (flip ap2))
|
Среды: 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 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||