Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 36
Текст из файла (страница 36)
Проблема недетерминированности состоит в том, что существует несколько одинаково помеченных дуг, исходящих из одного состояния. Такилт образом, в недетерминированном автомате появляется возможность выбора между различными переходами. Цифра Цифра Рис. 3.7. КА, распознающий целые числа с необязательным знаком Итак, недептерлтпттирооаттный конечный автомат определяется как конечный автомат, обладающий: 1) множеством состояний (узлы графа); 2) начальным состоянием (один из узлов); 3) множеством конечных состояний (подмножество узлов); 4) входным алфавитом (символы для маркировки дуг, определяющих перехо- ды между состояниями); 5) множеством маркированных символами входного алфавита дуг, соединяю- щих узлы и определяющих переходы между состояниями.
В таком недетерминированном автомате из любого узла может выходить несколько дуг (или не выходить вовсе), причем одну и ту же маркировку могут иметь несколько дуг. Такие переходы недетерминированы, поскольку для одного введенного символа может быть несколько разных вариантов дальнейшего пути (см. пример на рис. 3,9). В таком случае считается, что некоторая цепочка допускается конечным автоматом, если существует хотя бы один путь от начального к какому- либо из конечных узлов, даже если другие пути, соответствующие той же цепочке, не приводят к конечному состоянию. В детерминированном случае автомат всегда будет находиться в определенном состоянии, которое однозначно зависит от вводимых символов. Дополнительные сведения о конечных автоматах вы можете найти в задаче 12 в конце атой главы.
Регулярные грамматики Частным случаем ИФБ-грамматик являются регулярные грамматики. Можно показатьч что язык, определяемый некоторой регулярной грамматикой, зквивалентен языку, определяемому некоторым конечным автоматом. Правила рет улярных грамматик записываются в следующей форме; <нетернинагьный синвол> :.= <тернинагьный сиивог> <не|ернинагьный синвол> ! <териинальныи сиивол> 126 Глава 3.
Вопросы трансляции языка Каждое правило состоит из терминального символа, за которым может следовать нетерминальный. Грамлгатика, генерирующая битовые цепочки, которые оканчиваются нулем, задается следующим образом: А -ч ОА ) 1А ) О Первых два варианта используются для генерации произвольных битовых цепочек, а третий — для топь чтобы создать битовую цепочку, оканчивающуюся пулем. Между КА и ре1.улярными грамматиками существует тесная связь; можно показать, что они генерируют одни и те же языки (см. задачи и упражнения в конце этой славы). Регулярные выражения Регулярные пьсражения представляют собой третий способ описания языка, эквивалентный описаникг с помощью регулярных грамматик и конечных автоматов.
Регулярное выражение определяется рекурсивно следующим образом: 1) отдельные терминальпые сиьгволы являются регулярными выражениями; 2) если а и Ь вЂ” регулярные выражения, то змЬ, аЬ, (а) и а* также являются регулярными выражениями; 3) ничто другое не является регулярным выражением. вЬ вЂ” это результат конкатенации, или объединения, в последовательность регулярных выражений з и Ь, амЬ обозначает выбор одного из выражений, з или Ь, и наконец, з* называется замыканием Клини регулярного выражения а и представляет собой ноль или более повторений регулярного выражения з (например, сюда относится пустая строка, часто обозначаемая как е, а, аа, ааа,„.)'.
Замыкание Клини: а* Альтврнвция(выбор) а ч р Конкатенация: а)) Рис. 3.8. Преобразование регулярных выражений в КА Регулярные выражения можно использовать для представления любого языка, определенного регулярной грамматикой или конечным автоматом, хотя преобразование конечного автомата в регулярное выражение не всегда очевидно. Следующая небольшая таблица иллюстрирует использование регулярных выражений. Язык Регулярное выражение Идентификаторы Битовые цепочки, кратные 2 Битовые цепочки, содержащие 01 буква(буквах цифра)* (Оч!)*0 (Оч1)*01(оч1)* Операция заключения регулярного выраже~щя а круглые скобки, о коз арой авторы пичего пе сказа- ли, означает создание группы, к которой можно применить другие операции, например аамыкание Клинц. — Пуичеч.
науч. ред. 3.3. Формальные модели трансляции 127 Преобразование любого регулярного выражения в КА достаточно просто. С)перация ж представляет альтернативные варианты перехода от состояния А к состоянию В, конкатенация означает последовательность состояний, а замыкание Клини соответствует циклам (рис. 3.8). На рис.
З.9 представлен конечньгй автомат для третьего регулярного выражения из таблицы. Заметим, что в результате мы получаем недетерминированный КА, который, однако, может быть преобразован в эквивалентный детерминировашняй КА (см. задачу 12). Как будет показано в раз- деле 3.З.З, несмотря на их сложность, регулярные выражения н конечные автоматы достаточно легки для понимания, а для упрощения обработки регулярных выражений был разработан такой инструмент, как язык программирования Рег!. Рис. 3.9.
Преобразование регулярного выражения (Ож1)*01(ож1)* в КА Вычислительные возможности КА Конечный автомат способен содержать конечное количество информации — ограниченное множество состояний. Следовательно, количество распознаваемых им цепочек ограничено. Папример, КА не способен распознать множество цепочек типа а Ь". Лля доказательства допустим, что а Ь распознается некоторым КА с числом состояний 1. 'Тогда для любого л э г при считывании символа а автомат должен будет войти в то же самое состояние по крайней мере дважды. Следовательно, какое-то подмножество этой цепочки вызывает цикл внутри КА. Это означает, что а" = иху, где подцепочка х вызывает циклический возврат КА в то жс самое состояние.
Легко видеть, что цепочка их"уЬ' будет принята конечным автоматом. Принятыми цепочками будут цепочки вида а"'"'Ь", где и и р — целые числа, а 1 — произвольное число; но это отнюдь не то же саиое, что цепочка э"Ь". 3.3.3. Обзор языка Рег! Рег! — это язык программирования, хорошо приспособленный для работы с регулярными выражениями. Как сказано в разделе 1А2, операционная система (1!ч!Х ввела в практику системного программирования сценарий на языке командного интерпретатора зЬеН, который можно рассматривать как язык программируемых процессов для управления выполнением программ на компьютере, Даиггыыи, обрабатываемыми этими сценариями, были программы и файлы, входящие в систему компьютера.
В качестве вспомогательных средств для программирования на 128 Глава 3. Вопросы трансляции языка языке командного интерпретатора айеП были разработаны разнообразные языки лля обработки строковых данных. Одними из первых были АЪЪ'К, появившийся в 1977 г. (назван в честь своих авторов — Альфреда В. Ахо (А!(гег) Ч. АЬо), Питера Дж. Вейнбергера (Ресег.
1. ЪЧе!вЬегйег) и Брайана В. Кернигана (Впап ЪЧ. Кеги!ВЬап)), и БЕП, потоковый редактор (зггеаш ег!!Сот), созданный по образцу одного из первых редакторов 13!ч! Х егь Поскольку АЪЧК был предназначен для работы с файлами определенной регулярной структуры, его можно было использовать, например, следующим образом: взять файл, состоящий из имен и соответствуюших им адресов электронной почты, и, используя АЪЧК, разослать по всем этим адресам письма.
Для этого нужно было написать зЬей-сценарий, содержащий цикл, на каждом шаге которого вызывался бы АЪЧК для извлечения очередного алреса электронной почты из файла, после чего сообщение могло быть отправлено соответствующему адресату. Зная язык командного интерпретатора ейеП и возможности сопоставления с образцами АЪЧК, программист достаточно легко мог созлать подобный процесс обработки списка рассылки. История.
Для облегчения вйеП-программирования в (Пх!1Х было разработано много новых языков управления процессами типа АЪЧК. Язык Рег! (РгасПса! Ехггасйоп апг! Керогг Еапйпайе) был создан в 1986 г. Ларри Уоллом (Еаггу ЪЧаП) для решения задач управления конфигурацией сети, состоящей из нескольких компьютеров. Вначале Уолл использовал механизм под названием В-пеюв, но он неадекватно выполнял задачу создания и обработки необходимых отчетов. АЪЧК не мог одновременно открывать и закрывать множество файлов.
В результате появился новый язык Рег!, который унаследовал некоторые черты предшественников — языков АЪЧК и 8Е1), но более подхолил для данного применения. Сначала язгяк назывался РЕАКЕ (жемчуг), но поскольку так назывался существующий графический язык, бьшо решено сократить название. В языке были предусмотрены скалярные данные, возможность сопоставления с образцом, управление и обработка файлов, Со временем появились новые версии этого языка„ последняя включает возможность объектно-ориентированного программирования. Широкое распространение ЪЧЪЧЪЧ привело к открытию, что Рег! является одним из наиболее подходящих языков для программирования задач интерактивного взаимодействия в ЪЧеЬ вЂ” задач обработки на сервере ицформапии, введенной пользователем на я еЬ-странице.
Краткий обзор языка. Рег! — это интерпретируемый язык, предназначенный для эффективной обработки текстов. Синтаксис языка Рег! построен по образцу языка С, так как исходно Рог! развивался как командный язык в операционной системе П)ч1Х, где С являлся основным языком программирования. Ввиду сходства с С Рег! столь же удобен (или неудобен — в зависимости от того, считаете ли вы С удобным для чтения) для пения, как и С. Переменные в языке Рег! начинаются с символа $ и могут солержать как целые числа, так и строки. Также в Рег! имеются массивы скаляров и ассоциативные массивы.
Ассоциативные массивы называются также массивами с адресацией по содержанию, поскольку для доступа к информации можно пользоваться не только индексами массива, но и содержанием элемента. Например, в большнн- 3.3, Формальные модели трансляции 129 стве современных операционных систем с программой ассоциирована некоторая среда или окружение, содержащее переменные с определенными значениями.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
