Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 58
Текст из файла (страница 58)
Существенно контекстно-сво одн языка анализируются на этапе сиитаксиче г р пр р око о азбо а, го авдо более сложном, чем лексическая фаза. Определение. Последов тельностью регулярных определении в алфавите Х назовем список определенн1 А„=- „, где А„ ..., Аь — азличные символы, не принадлежа- щие Х, и Е(, — расширейное регулярное выражение в алфавите 20(А, ... А.
) (1 =Е 'и). Для 1. 1 и определим расши- Ренное регулярное выражение Ес,' в алфавит (1) й;=П„ (2) Ес'; получается нз Ес, заменой каждого вхождения у д, и ля (1 вырюкеннем Ес,'. Множество, обозначаемое символом А,, это ь . это множество, обозна- чаемое выражением я;. Должно быть ясно, что множества, обозначаемые расширенрегуляриыми выражениями и последовательностями ре2вз гл. з.
теория переводя 3 3 лексический лнллиз гулярных определений, регулярны. Доказательство оставляем в качестве упражнения. Пример 3.18. Идентификаторы Фортрана задаются последовательностью регулярных определений <буква>=А)В!... )2 <цифра> =0)1!...!9 <идентификатор> = <буква> (<буква> ! <цифра>)*1 Если мы не хотим допустить, чтобы в качестве идентификаторов использовались ключевые слова Фортрана, то нам придется пересмотреть определение <идентификаторов>, чтобы исключить соответствующие цепочки. Тогда оио должно читаться так: <идентификатор> = (<буква> (<буква> ! <цифра >)") — (1>О )1Р ! ...) Е) Пример 3.19. Общепринятый вид записи вещественных констант (например, 3.14159, — 882, б.бŠ— 29 и т.
д.) задается следующей последовательностью регулярных определений'): <цифра>=-0(1! ... (9 <знак>=+ ! — (е <целое> = <знак> <цифра>+ <десятичное> = <знак> (<цифра>'. <цифра>+ ! <цифра>+. <цифра>*) <константа> = <целое> ! <десятичное> ! <десятичное> Е <целое> Г 3.3.2. Непрямой еекснческнй ананнз При непрямом лексическом анализе требуется, прочитав цепочку знаков, определить, появилась лн подцепочка, образующая некоторую конкретную лексему.
Если множество возможных цепочек, которые могут образовывать эту лексему, обозначается, как это обычно бывает, регулярным выражением, то проблему построения непрямого лексического анализатора для данной лексемы можно представлять себе как проблему реализации конечного преобразователя.
Конечный преобразователь — это почти конечный автомат (распознаватель) в том смысле, что он читает вход, не производя выхода, пока не обнаружит присутствие лексемы данного типа (т. е. достигнет заключительного состоя. ния). Тогда оп сигнализирует о том, что эта лексема появилась, и выдает на выходе пеночку символов, образующих эту лексему. Сигналом, очевидно, служит само заключительное состояние. Однако лексическому анализатору, возможно, требуется иссле- ') Конкретная реализация лемке оеычяа налагает ограниченая ка длин! н величину констант.
а ь один нли более символов, стоящих после правого конца довать о лексемы. семы, Простой пример: мы ие можем определить правый конец нд идентификатора Алгола, пока не встретим символ, который ие явл е является ни буквой, ни цифрой, т. е. обычно не считается частью идентификатоРа.
Прн непрямом лексическом анализе можно получить выход ксического анализатора, говорящий о появлении некоторой лексеззы, а если позднее обнаружится, что лексема на самом деле отсутствует, то алгоритм синтаксического анализа осуществляет возврат к данной цепочке, обеспечивающий в конце концов работу анализатора для подходящей лексемы. Используя непряой лексический анализ, нужно заботиться о том, чтобы с таб. лицами имен не выполнялись ошибочные операции. Обычно идентификатор не помещают в таблицу, пока не убедятся в том, что он действительно встречается.
(В противном случае надо обеспечить механизм, удаляющий нз таблиц ненужные элементы.) Проблема непрямого лексического анализа является, таким образом, по существу проблемой построения детерминированного конечного автомата по заданному регулярному выражению и его программной реализации. Результаты гл. 2 убеждают нас в том, что такое построение возможно, хотя и требует немало работы. Нетрудно, оказывается, прямо перейти от регулярного выражения к педетерминироваиному конечному автомату. Затем по теореме 2.3 можно превратить этот автомат в детерминированный либо моделировать его работу, прослеживая параллельно всевозлюжные последовательности тактов, При прямом лексическом анализе тоже удобно начинать построение прямого лексического анализатора с компактного недетерминированного конечного автомата для каждой из лексем.
Недетермииированный автомат можно строить с помощью алгоритма, подобного тому, который в равд. 2.2 применялся для построения праволинейной грамматики по регулярному выражению. Распространить эту процедуру на все расширенные регулярные выражения ие так-то просто, особенно потому, что опеРация пересечения и вычитания множеств требуют конструкций, связанных с детерминированными автоматами.
(Очень тРУдно доказать, что )с, () Рз и зс,— )сз РегУлЯРны, если РегУ- л"Рны 1с, и 1<„не обращаясь так или иначе к детерминированным автоматам. С другой стороны, для доказательства замкнутости относительно операций (1, . и ч детерминированные автоматы "е тРебуются.) Однако операции, '" н *" обрабатываются естественным образом. Гл. 3. ТеОРия пеРенодд З.З. ЛЕКСИЧЕСКИЙ АНАЛИЗ Алгоритм 3 2. Построен ие иедетер ми пир он а нного конечного автомата по расширенному регуляр. ному выражению. Вход.
Расширенное регулярное выражение В в алфавите Х, не содержащее символа Я и операций П и —. Выход. Недетерминированный конечный автомат М, для ко. торого Т. (М) = тсР. Метод. (1) Выполнять шаг (2) рекурсивно, начиная с выражения !<, Пусть М вЂ” автомат, построенный в результате данного обраще- ния к шагу (2). (2) Пусть Вв — расширенное регулярное выражение, к кото- рому применяется этот шаг. Строится педетерминированный ко.
нечный автомат М,. Возможны следующие случаи: (а) Вв=в. Тогда М,—... ((Ч), Х, йу, д, (г))), где д — новое состояние, (б) др„=-а, где або. Тогда М„=((д„д,), Х, б„ды (д,)), где 6,(йы а)=(р)в); в остальных случаях 6, не определена, уг и с1,— новые состояния. (в) гсв — !с,~ )св. Тогда можно применить шаг (2) к йрт и !<, и получить соответственно М,=(()ы Х, б„г)„Р,) и М,— =--(1!„Х, б„дю Рв), где !г, и 1;!, Ие пересекаются, а затем построить М,— (сг, 0!г,0 (д,), л.', б„ор, Р„), где (!) др — новый символ, (П) 6, включает 6, и бю и 6,(фю а)= 6, (йы а) 06,(Р)м а), (П!) Р„=Р,0Р„если д,(Р, и д,(Р„и Р, Р,0Р,0(с)) в противном случае.
(г) (с,=-(<,1<,. Применить шаг (2) к АР„И )<в и получить М! н М„как в случае (в). Построить М,=-(Я,0!<вр Хр б„игр Р,), где (!) 6, включает 6,; 6,(д, а)=6,(д, а) для всех д~тг' н а~2, если г) (Ры й бв(р), а)=-6,(д, а) 06,(д„а) в против. ном случае, (П) Р, = Р„если дв ( Р„и Р, = Р, 0 Р, в противном слу. чае. (д) );рв=-)!р;. Применить шаг (2) к )!рг и получить М, =(сг! Х, б„д„Р ). Построить М„=(!),0(дрр), Х, бв йр Рд0(р)в)) где р)в — новый символ и 6, определяется соотношениями (!)'6р(йю а) =6,(9„а), ' (!1) если т1(Р„то 6,(с1, а) = 6,(д, а), (10) если д С Р, то 6, (д, а) = 6, (д, а) 0 6, (ды а).
(е) гсРв:==Р<+. ПРименить шаг (2) к !с, и полУчить М„как в (д). Построить М, = (! !„Х, б„ды Рр), где 6, (д, а) =6, (Ч, а если д(Р„И 6„(с1, а)=6,(г), а) 06,(г)„а), если дЕР,. «ж) р —.др,*в. Применить шаг (2) к )ср, и получить М„как в (д). Построить Мв (!сгХ(1 а), Хр бв, [р)„11,Р,),где (В если д(Р, или г=-л, то 6,([р1, г1, а)=([р, г|( 6, (р), а) содеРжит Р), (11) если д б Р, и 1 < и, то 6, ([г), !1, а) = ([р, 11( 6, (д, а) содержит р) 0([р, !+1)(6,(с)„а) содержит р), (!П) Р,=-([9, '1!йЕР„1~!~а)0([ды Ц).
(з) Ар,=Д,'". Делать то же, что и на шаге (ж), но пункт (!!!) заменить на (!!1') Р,=-([д, г(/д~Р„1(!(и). Теорема 3.9. Алгоритм 3.2 дает такой недетержиниро- ванный конечный автомшп М, что Т-(М) = )с. д о к а з а т с л ь с т в о. Упражнение на индукцию. Заметим, что в пунктах (ж) и (з) алгоритма 3.2 вторую ком- поненту состояния автомата М, часто можно эффективно реали- зовать при программировании в виде счетчика (в том числе и при переходе к детерминированному автомату). Зго возможно потому, что во многих случаях !с, обладает префиксным свой- ством и цепочку из !<р+" можно тривиально разбить на цепочки нз г(р.
Например, 1<, может быть <цифрой>, как в примере 3,18, а длина каждого элемента множества <цифра> равна 1. Пример 3.20. Сконструнруем недетерминироваппый автомат для идентификаторов, определенных в примере 3.18 Чтобы при- менить шаг (2) алгоритма 3.2 к выражению, названному <иден- тификатором>, надо применить его к выражениям <буква> н (<буква> (<цифра>)"'.
Построение автомата для первого из этих выражений фактически содержит 26 применений шага (2б) и 25 применений шага (2в). Однако заметим, что после очевидного ОтожДествлениа состоЯний ') полУчитсЯ автомат ((д„ с)в)„ Х, бзэ р)г (ру,)), где Х=(А,..., Х, О, ..., 9) и 6, (ды А)=6,(йы В) = " =-б*(Ч.
К)=И.). Чтобы получить автомат для выражения (<буква> (<цифра>)*', нужен еще один автомат для <буквы>, скажем ((((„дв), Х, 6, Х, (Чр)), и аналогичный автомат для <цифры>, скажем ((с)„р)в~, р)„(о,)). Изготавливая автомат для объединения двух последних выражений, мы добавляем новое начальное состояние ар " "бнаруживаем, что из него нельзя достичь состояний д, и р)„. ВР „„,.„',.р, ° р, ° р„° ° - р ° . В рь г дссчн ! два состпяння нсдетсрмнннрозанного конечного автомата можно отож- сстннть, вслн онн обз либо заключнтвльныс, либо незаключнтсльные, н кажзхсд пврсподнт нх з одно н то же множестно состпяннй. Зто асе, что Рсбустся здесь, но состояния нсдетсрмнпнрозанного конечною автомата можно жд стзлять н прн некоторых другах уюзннх.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
