Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 59
Текст из файла (страница 59)
!ОА Азв. дзр. ульмза. я. ! 289 Гл. 3, теОРия пеРеВОдА В.В, ЛЕКСИЧЕСКИЙ АНАЛИЗ зультате получаем автомат ((д„ д„), Х, 6„ д„ (д,)), где 6, (д„ А) = ... =- 64(д~ Е) = 6, (дс О) — ... = 6,(де, 9) = (д,). Чтобы пРименить шаг (2ж), введем состоЯниЯ [Ч„() и [ле, 1) для 1~1(5. Заключительными состояниями будут [Ри !) дли 1(! 5 и [д„!!. Последнее состояние является также началь. ным. Получаем автомат (Я„Х, 6„[д„11, Р,), где Р, то же, что н выше, а 6([ие !) а)=([ч !П 6([че 1) а) — ([ч4 1+ !!) для всех аЕ2 н !6(1 2, 3, 4). Таким образом состояния [д, 2] недостижимы и не должны быть в Я,.
Следовательно, Як=Ты Рис. 3.7. Недетермииироваивый коиекиый автомат дли идентификаторов. Чтобы построить окончательный автомат для с'идентифика. тора>, применим шаг (2г). В результате получим М=(И Ч [С., 11 ",[Ч. 5!) ~,6,Ч,(Ч [Ч.,11," [РИ51)) где 6 определяется соотношениями (1) 6(Ч„а)=. (че) для всех ачба, которые являются буквами, (2) 6(Ч„а)=. ([д4, 1)) для всех аЕХ, (3) 6([ч„(), а)=([су„1+1)) для всех а~1 и 1(! < 5. Заметим, что состояние [ло !1 недостижимо и его можно устранить из М.
Кроме того, автомат М оказался здесь петер. минированным, хотя в общем случае этого может и не быть. Диаграмма автомата М показана на рис. 3.7. 3.3.3. Прямей пекснческнй анапнз При прямом лексическом аначизе требуется найти одну из многих лексем. Наиболее эффективный способ заключается, ео обще говоря, в том, чтобы вести поиск параллельно, так квх он при этом часто довольно быстро сужается. Таким образом 290 модел ,опалые прямого лексического анализатора служит множество аботающих параллельно конечных автоматов, или, точнее, один „вечный преобразователь, моделирующий много конечных автоОв и выдающий сигнал о том, какой из них распознал цепочку. Вели нужно моделировать параллельно несколько иедетерминнрованиых автоматов, пРичем множества их состояний ие пересекаются, то можно объединить эти множества состояний и функции переходов, построив один недетерминированный конечный автомат, который можно превратить в детерминированный по теореме 2.3.
(Начальным состояниемдетерминированного автомата будет при этом множество всех начальных состояний составляющих автоматов.) Таким образом, удобнее объединить множества состояний до перехода к детерминированному автомату, а не после. Объединенный детерминированный автомат можно рассматривать как конечный преобразователь простого типа. Рн выдает имя лексемы и, возможно, информацию, локализующую вхождение этой лексемы. В каждом состоянии объединенного автомата представлены состояния всех составляющих автоматов. Понятно, что когда объединенный автомат попадает в состояние, содержащее заключительное состояние одного составляющего автомата и ие содержащее никаких других состояний, он должен остановиться и выдать имя лексемы, соответствующей этому составляющему автомату.
Однако часто дело обстоит не так просто. Например, если идентификатором может быть любая цепочка, за исключением ключевых слов, то на практике нецелесообразно определять идентификатор в точности как это регулярное множество, поскольку такое определение сложно и требует много состояний.
Вместо этого пользуются простым определением идентификатора (одно из таких дано в примере 3.13) и предоставляют объединенному автомату принять правильное решение. В этом случае, если объединенный автомат попадает в состоя Оянне, которое содержит заключительное состояние одного из автома Оматов, соответствующих ключевым словам, и состояние автомата, нон снм та, соответствующего идентификаторам, а следующий вход- указыва символ (это может быть пробел или специальный знак) чевом сл ывает на окончание лексемы, то предпочтение отдается клюну ~лову н выдается указание о том, что обнаружено клю- ЧЕВОЕ СЛОВО.
П име РимеР 3.21. Рассмотрим нескогько абстрактный пример. Доставленные ИУстим, что идентификаторы представляют собой цепочки соЖен сле ов ные нз четырех символов !), Р, 1 и О, за которыми лопать пробел (Ь), причем 00 и 1Р— ключевые слова, 10 ° 291 З.З. ЛЕКСИЧЕСКИЙ АНАЛИЗ Гл. 3. ТеоРия пеРВВОдА которые ие являются идентификаторами и за которыми может не следовать пробел и не должны следовать (непосредственно) буквы0, Р,1ио.
Упрощенное множество идентификаторов (включагощее РО и 1Р) распознается конечным автоматом, изображенным на рис. 3.8,а, цепочка 00 — автоматом на рис. 3.8,б, а !Р— автоматоаг на рнс. 3.8,в. (Здесь все автоматы детерминированные, хотя е общем случае это, разумеется, не обязательно.) л Рис. 3.3. Лвтоматы для леясн ~есиого анализа: а — идентификаторы; б — 00; в — 1Г. Объединенный автомат показан на рис. 3.9').
Состояние г1, указывает, что обнаружен идентификатор. Однако состояния (г)ы г)а) и (г)„г),) нельзя истолковать однозначно. Они могут указывать иа 1Р или )лО соответственно, а могут только нато, что появи.чся начальный отрезок какого-то идентификатора, вроде ОООР. Чтобы разрешить возникпгий конфликт, лексический анализатор должен взглянуть на следующий символ.
Если зто 1), О, 1 илн Р, то перед нами префикс идентификатора. Если что-то другое, в том числе н пробел (допустим, что букв больше, чем упомянутых пять), то автомат переходит в новое состониие да или г)те и вьщает сигнал о том, что обнаРУжено ключевое слово 1)0 нли 1Р соответственно и оно окончилось на один символ раньше. Если автомат попадает в г)„то он вгн дает сигнал о том, что обнаружен идентификатор, оканчиваю щнйся одним символом раньше. ') В прогивополоигность автомату рис. 3.3 данный автомат не допускает в качестве идентификатора пробел.
Рис. Зтй Объединеннъ1й леисичесинй аналнаатор. Важно отметить, что так как указанное различие проявляется " выходе описанного устройства, а не в состоянии, то состоя"ия г)„г)а и г)га можно отождествить, и на самом деле опи вообп1е не будут представлены в программной реализации. П з 3 4 Програаамное модепнрованне конечных преобразоватепей Известно несколько подходов к программному моделированию конечных автоматов и преобразователей. Медленный, ио з"ономный с точки зрения расхода памяти способ заключается том что кодируется функция переходов соответствующего Так у тройства и работа с ней реализуется в режиме интерпретации. как лексический анализ составляет значительную долю но ме роцесса трансляции, такой метод часто оказывается слишком лапиным, чтобы его можно было принять.
Однако некоторые Гл. 3. теория пеРеВОдА замечания по литепдттпе вычислительные машины имеют команды, распознающие те или иные виды лексем, н хотя этими командами нельзя промодели ровать произвольный конечный автомат, они очень хорошо раба. тают, когда лексемами служат ключевые слова или идентификаторы. Другой подход состоит в том, чтобы завести кусок про граммы для каждого состояния. В функции программы входит определение очередной буквы (для локализации буквы можно использовать подпрограмму), выдача требуемого выхода и пере ход к тому месту программы, которое соответствует следующему состоянию. Важную проблему представляет выбор подходящего метода определения очередной буквы. Если для данного текущего состояния функция переходов такова, что большинство различных очередных букв приводят к различным следующим состояниям, то, по-видимому, нет ничего лучше, чем передавать управление косвенно через таблицу, основанную на очередной букве.
Этот метод по скорости не уступает любому другому, но для него нужна таблица, объем которой пропорционален числу различных букв. В типичном лексическом анализаторе много состояний, для которых почти все очередные буквы приводят к одному и тому же состоянию. Размещение в памяти полной таблицы для каж. дого такого состояния привело бы к слишком большому расходу памяти. Для многих состояний разумным компромиссом между соображениями, связанными с затратами времени и памяти, был бы двоичный поиск для выбора тех немногих букв, которые вызывают переход в необычное состояние. УПРАЖНЕНИЯ 3.3.1.
Напишите регулярные выражения, эквивалентные еле. дующим расширенпылз регулярнылл выражениям: (а) (а+з(тчз)ьз (б) (а / Ь)' — (аЬ)', (в) (аа / ЬЬ)" П а (аЬ / Ьа)+Ь. 3.3.2. Напашите последовательность регулярных определе- ний, приводящую к определению (а) идентификаторов Алгола, (б) идентификаторов ПЛ(1, (в) комплексных констант вида (а, (5), где а и ~3 — веществен- ные константы Фортрана, (г) комментариев в ПЛ1!.
3.3.3. Докажите теорему З.З. 3.3.4. Постройте непрямые лексические анализаторы для трех регулярных множеств из упр. 3.3.2. 3 З.б, Постройте прямой лексический анализатор, различащий следующие лексемы: (Н идентификаторы, представляющие собой любые последо- вательности букв и цифр содержащие хотя бы одну букву (исключения оговорены в пункте (3)), (2) константы, как в примере 3.19, (3) ключевые слова !Р, 1)л) и 1ХГЕСзЕК (которые не счита- ются идентификаторами). З.З.З. Расширьте понятие неразличимых состояний (равд. 2.3), чтобы ПРименпть его к недетеРминиРованным конечным автома- там, Если склеить все неразличимые состояния, обязательно лн получится недетерминированный автомат с минимальным числом состояний? еез.3.7. Будет ли более легким прямой лексический анализ для Фортрана, если исходная программа считывается в обрат- ном направлении? Проблема для исследования 3.3.8.
Дайте алгоритм выбора реализации для прямых лексических анализаторов. Ваш алгоритм должен допускать задание желательного соотношения между затратами времени н памяти. Возможно, Вы пе захотитс реализовать работу конеююго автомата символ за символом, а предпочтете использовать и другие операции. Например, если бы многие лексемы были арифметическими знаками, которые должны отделяться пробелами, как в Сноболе, то было бы разумно в качестве первого шага лексического анализа отделить эти лексемы от других, проверяя, является ли вторая буква пробелом. ттпраяснения на програлемирование 3.3,9.
П ... Постройте лексический анализатор для одного из языков программирования, данных в приложении. Приведите сообРажения относительно того, как этот анализатор будет обнару- жива ать лексические ошибки, в частности описки. 3.3.10. . Придумайте язык программирования, основанный на расши енп Р пых регулярных выражениях. Постройте компилятор для этого я зыка. Программа в объектном языке должна быть Реализа ией ц й лексического анализатора, описываемого исходной программой. Замечания по литературе лнз „° озой системой, н которой прн построеннн лекснческнх анаПеРвой бол, йлоО о ьзоаалась техннка конечных автоматов, была система АПО роа нсполь (йеай а р? а нрОЙО). Обзор атой системы дан джонсоном н др.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
