А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 40
Текст из файла (страница 40)
Например, если наибольший префикс входной строки, соответствующий какому-либо из шаблонов — с)зеп, и при этом шаблон с)теп в программе предваряет шаблон ( 1с(), как на рис. 3.23, то лексический анализатор возвращает токен ТНЕ(ч, а не токен 1Р. 197 3.5. Генератор лексических анализаторов Ьех 3.5.4 Прогностический оператор Ьех автоматически считывает один дополнительный символ за последним символом, образующим лексему, а затем выполняет возврат его во входной поток с тем, чтобы из потока была изъята только распознанная лексема. Однако иногда требуется, чтобы входная строка соответствовала определенному шаблону только тогда, когда за ней следуют некоторые (предопределенные) другие символы.
В этом случае в шаблоне можно использовать символ косой черты, который указывает конец той части шаблона, которой должна соответствовать лексема. Все, что следует за /, представляет собой дополнительный шаблон, которому должен соответствовать остаток входной строки после найденной лексемы, чтобы было принято решение о том, что найденная лексема соответствует рассматриваемому токену. Однако часть входной строки, соответствующая второй части шаблона, не входит в найденную лексему н остается во входном потоке для последующей обработки. Пример 3.13.
В Рогпап и некоторых других языках ключевые слова не являются зарезервированными. Это создает много проблем. Так, например, в инструкции 1Р(1, У) = 3 1Р представляет собой имя массива, а не ключевое слово. В противоположность этому в инструкции вида 1Р ( попс(ЬП1оп ) ТНЕУ 1я представляет собой ключевое слово.
К счастью, за ключевым словом 1Р всегда следуют левая скобка, некоторый текст (условне), который может содержать скобки, правая скобка и буква. Таким образом, правило Ьех для ключевого слова 1Р можно записать как 1Г / ~( .* ~) (1ет~ек) Это правило гласит, что лексема, соответствующая шаблону, состоит из двух букв 1Р. Косая черта указывает, что имеется и дополнительный шаблон, не соответствующий лексеме. Первым символом этого шаблона является левая скобка. Поскольку скобка является мегаснмволом языка Ьех, она должна быть предварена обратной косой чертой, указывающей, что имеется в виду буквальное значение данного символа. Точка со звездочкой означает "любая строка без символа начала новой строки".
Точка в языке Ьех представляет собой метасимвол, который означает "любой символ, кроме символа начала новой строки", Далее следует правая скобка, предваренная обратной косой чертой, обозначающей буквальное значение следующего за ней метаснмвола. Наконец, за правой скобкой следует символ (епег, который является регулярным определением, представляющим класс символов, состоящий из всех букв. 198 Глава 3. Лексический анализ Для надежной работы этого шаблона из входного потока предварительно должны быть удалены пробельные символы.
В шаблоне не приняты меры ни на случай наличия пробельных символов, ни на случай, когда условие не содержится целиком в одной строке, поскольку точка не соответствует символу новой строки. Предположим, например, что выясняется соответствие этого шаблона следующему префиксу входной строки: 1Е(А<(В+С)*Р)ТНЕМ.. Первые два символа соответствуют 1Р, следующий — комбинации 1(, девять символов после левой скобки — шаблону .*, а идущие за ними два символа соответствуют 1) и (еиег. Обратите внимание на то, что первая правая скобка (после С) не рассматривается, поскольку за ней следует символ, не являющийся буквой. В результате мы делаем вывод, что буквы 1Р составляют лексему, являющуюся экземпляром токена И'. о 3.5.5 Упражнения к разделу 3.5 Упражнение 3.5.1. Опишите, какие изменения надо внести в программу Еех на рис.
3.23 для того, чтобы а) добавить ключевое слово и)з11е; б) заменить множество операторов сравнения операторами сравнения языка программирования С; в) позволить использовать в именах символ подчеркивания ( ); ! г) добавить новый шаблон с токеном ЯТН1МС.
Этот шаблон состоит из двойных кавычек ("), произвольной строки символов и завершающих двойных кавычек. Если символ двойных кавычек содержится в строке, он должен быть предварен обратной косой чертой ((); соответственно, сама обратная косая черта в строке должна быть представлена двумя обратными косыми чертами. Лексическое значение представляет собой строку без охватывающих ее двойных кавычек и без символов обратной косой черты, использованных для изменения смысла символов двойных кавычек и обратной косой черты в строке на буквальный.
Строки вносятся в отдельную таблицу строк. Упражнение 3.5.2. Напишите программу Ьех, которая копирует файл, заменяя все непустые последовательности пробельных символов одним пробелом. Упражнение 3.5.3. Напишите программу Вех, которая копирует программу иа языке программирования С, заменяя все вхождения ключевого слова й1оаг.
на с(оиЬ1е. 3.6. Конечные автоматы ! Упражнение 3.5.4. Напишите программу Еех, которая преобразует текстовый файл в "поросячью латынь".з В частности, считаем, что файл представляет собой последовательность слов (групп символов), разделенных пробельными символами. Всякий раз, когда встречается слово, выполняются следующие действия. !. Если первая буква согласная, она перемещается в конец слова и за ней добавляются буквы ау.
2. Если первая буква гласная, к концу слова просто добавляется ау. Все небуквенные символы копируются без изменений. ! Упражнение 3.5.5. В Я~Е ключевые слова и идентификаторы нечувствительны к регистру. Напишите программу на языке Ьех, которая распознает ключевые слова ЯЕЬЕСТ, ГЕОМ и !ЯНЕВЕ (с любыми сочетаниями верхних и нижних регистров) и токен 1Р, который в данном упражнении может быть любой последовательностью букв и цифр, начинающейся с буквы. Вносить идентификаторы в таблицу символов не требуется, но следует указать, чем именно функция для внесения в таблицу символов отличается от таковой для идентификаторов, чувствительных к регистру, как на рис. 3.23.
3.6 Конечные автоматы Сейчас мы рассмотрим, как Еех преобразует входную программу в лексический анализатор. Ключевым моментом этого преобразования является формализм, известный как конечный автомат (Йп)!е ацюша!а). Конечные автоматы, по сути, представляют собой графы, подобные диаграммам переходов, но с небольшими отличиями. !. Конечные автоматы являются распознавателями (гесойл)хег); они просто говорят "да" или "нет" для каждой возможной входной строки. 2.
Конечные автоматы разделяются на два класса. а) Недетерминированные конечные автоматы (попс)ейепп)п)зйс Бпйе ацсошага — ХЕА) не имеют ограничений на свои дуги. Символ может быть меткой нескольких дуг, исходящих из одного и того же состояния; кроме того, одна из возможных меток — пустая строка е. 5 Из англо-русскою словаря: р!я !.анп — дегиск, жара "поросячья латынь" (манера коверкать слова, переставляя первый согласный звук в конец слова и добавляя слог "ау", например Оодйау опйпйгпау = Овод пзопппя). — Прим. иер. 2ОО Глава 3.
Лексический анализ б) Детерминированные конечные автоматы (де!егппщзбс бпйе ац!оща!а — 0гА) для каждого состояния и каждого символа входного алфавита имеют ровно одну дугу с указанным символом, покидающим это состояние. Как детерминированные, так и недетерминированные конечные автоматы способны распознавать одни и те же языки. По сути, зто те же языки, именуемые регулярными языками (геяп!аг!апяцаяе), которые могут быть описаны регулярными выражениями.в 3.6.1 Недетерминированные конечные автоматы Недетерминированньзй конечный автомат (НКА) состоит нз !) множества состояний Я; 2) множества входных символов Е (входиого алфавита); считаелн что символ е, обозначающий пустую строку, не является членом Е; 3) функции переходов, которая для каждого состояния н каждого символа нз Е 0 (е) дает множество последующих состояний (пех! з!а!е); 4) состояния ло из Я, известного как стартовое (кача гьное); 5) множества состояний Е, являющегося подмножеством 5', известных как допускающие (ко ечные).
Как недетерминированный, так и детерминированный конечныс автоматы можно представить в виде графа переходов, узлы которого представляют состояния, а помеченные дуги представляют функцию переходов. Дуга из состояния в в состояние !., помеченная как а, существует тогда и только тогда, когда ! — одно из последующих состояний для состояния в и входного символа а. Этот граф очень похож на диаграмму переходов, за исключением того, что а) один и тот же символ может помечать дуги, исходящие нз одного состояния в несколько разных других; б) дуга может быть помечена пустой строкой е вместо символа входного алфавита (или вместе с ним).
"Здесь имеется небольшое упущение: в том виде, в котором мы их определили, регулярные выражения не могут описывать пустой язык, поскольку мы никогда не используем зтот шаблон ня првктике. Однвко конечный автомат мозкслг определять пустой язык. Теоретически Я рвссмягриввегся как дополнительное регулярное выражение для единственной цели — определения пустого языка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
