|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[5] £ сс 6. СОГЛАСОВАНИЕ СКОБОК Используя комбинаторы синтаксического анализа и преобразователи, создаваемые до сих пор, мы можем сконструировать парсер, распознающий согласующиеся пары скобок. Первой попыткой, не представляющей однако корректный тип, является следующее: parens :: Parser Char ??? parens = (symbol ( <*> parens <*> symbol ) <*> parens) <> epsilon На это определение оказала сильное влияние хорошо известная грамматика для вложенных скобок. Тем не менее вызывает затруднения тип дерева разбора. Если этим типом будет а, то типом соединения четырех поддеревьев в первой альтернативе будет (Char, (a, (Char, a))), что не является тем же самым или унифицирующимся с а. Также вторая альтернатива (epsilon) должна возвращать дерево разбора того же типа. Поэтому для построения дерева нужного типа необходимо сначала определить тип дерева разбора, и использовать оператор <@ в обоих альтернативах. Например, тип дерева разбора может быть следующим: data Tree= Nil Bin (Tree, Tree) Теперь мы можем добавить «семантические функции» к парсеру: parens :: Parser Char Tree parens = (symbol ( <*> parens <*> symbol ) <*> parens) <@ (\( , (x, ( , y))) -> Bin (x, y)) <> epsilon <@ const Nil Довольно непонятный текст \( , (x, ( , y))) является лямбда образцом, описывающим функцию с первым параметром, являющимся кортежём, содержащим четыре части первой альтернативы, из которых лишь вторая и четвертая имеют значение. Упражнение 4. Почему в лямбда образце вместо кортежа, у которого второй элемент является кортежём, у которого второй элемент является кортежём, мы не используем кортеж, состоящий из четырех элементов? Упражнение 5. Почему нужна функция const., которая определена в стандартном модуле Prelude как const x y = x? Вы можете написать вторую альтернативу более лаконично без использования const и <@? В лямбда образце символы подчеркивания используются в качестве «заполнителя»
результате. Для того, чтобы не пришлось использовать эти сложные кортежи, возможно было бы легче отсеять деревья разбора для символов на более раннем этапе. Для этого мы вводим два вспомогательных комбинатора синтаксического разбора, которые пригодятся во многих ситуациях. Эти операторы ведут себя также как и <*>, за исключением того, что они отсеивают результат одного из двух парсеров, являющихся их аргументами: (<*) p <* q (*>) p *> q Parser s a -> Parser s b -> Parser s a p <*> q <@ fst Parser s a -> Parser s b -> Parser s b p <*> q <@ snd Мы можем использовать эти новые комбинаторы синтаксического анализа для улучшения удобочитаемости парсера parens: open close parens parens symbol ( symbol ) Parser Char Tree (open *> parens <* close) <*> parens <@ Bin <> succeed Nil Путём благоразумного выбора приоритетов используемых операторов: infixr 6 <*>, <*, *> infixl 5 <@ infixr 4 <> мы сводим к минимуму число необходимых скобок. Упражнение 6. Скобки вокруг open >parens <* close в первой альтернативе необходимы несмотря на наши продуманные приоритеты. Что случится если мы опустим их? Изменяя функцию, используемую после <@ («семантическую функцию»), мы можем получить нечто отличающееся от деревьев разбора. В качестве примера мы напишем парсер, подсчитывающий глубину вложенности скобок: nesting :: Parser Char Int nesting = (open *> nesting <* close) <*> nesting <@ f <> succeed 0 where f (x, y) = (1 + x) "max" y Если интерес представляют дополнительные варианты, то, возможно, стоит превратить семантическую функцию и величину, возвращаемую в «пустом» случае в два дополнительных параметра. Функция высшего порядка foldparens производит разбор вложенных скобок, используя данную семантическую функцию и константу соответственно, после разбора одной из двух альтернатив: foldparens foldparens f e ((a, a) -> a) -> a -> Parser Char a p = (open *> p <* close) <*> p <@ f <>
succeed e Упражнение 7. Функция foldparens является обобщением функций parens и nesting. Напишите последние две как частный случай первой. Пример использования nesting может выглядеть следующим образом: ? just nesting "()(())()" [(2, [])] ? just nesting "())" В самом деле nesting лишь распознает корректно построенные вложенные скобки и вычисляет глубину вложенности в процессе разбора. Упражнение 8. Что случится, если мы опустим преобразователь just в этих примерах?
|
Среды: 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 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||