Главная Промышленная автоматика.

которые ие являются идентификаторами и за которыми может не следовать пробел и не должны следовать (непосредственно) буквы D, F, I и О.

Упрощенное множество идентификаторов (включающее DO и IF) распознается конечным автоматом, изображенным на рис. 3.8,(2, цепочка DO - автоматом на рис. 3.8,6, а IF - автоматом на рис. 3.8,6. (Здесь все автоматы детерминированные, хотя в общем случае это, разумеется, не обязательно.)

мчало <



тчало

шало


Рис. 3.8. Автоматы для лексического анализа: а -идентификаторы; б -DO; e~IF.

Объединенный автомат показан на рис. 3.9 ). Состояние указывает, что обнаружен идентификатор. Однако состояния {и Qs) и ii й} нельзя истолковать однозначно. Они могут указывать иа IF или DO соответственно, а могут только на то, что появился начальный отрезок какого-то идентификатора, вроде DOOF. Чтобы разрешить возникший конфликт, лексический анализатор должен взглянуть на следующий символ. Если это D, О, I или F, то перед нами префикс идентификатора. Если что-то другое, в том числе н пробел (допустим, что букв больше, чем упомянутых пять), то автомат переходит в новое состояние q или q±fj и выдает сигнал о том, что обнаружено ключевое слово DO или IF соответственно и оно окончилось на один символ раньше. Если автомат попадает в q, то он выдает сигнал о том, что обнаружен идентификатор, оканчивающийся одним символом раньше.

) В противоноложность автомату рис. 3.8 данный автомат не допускает в качестве идентификатора пробел.


Рис. 3.9. Объединенный лексический анализатор.

Важно отметить, что так как указанное различие проявляется в выходе описанного устройства, а не в состоянии, то состояния q И q можно отождествить, и на самом деле они вообще не будут представлены в программной реализации. □

•3.4, Программное моделирование конечных преобразователей

Известно несколько подходов к программному моделированию конечных автоматов и преобразователей. Медленный, ио экономный с точки зрения расхода памяти способ заключается , J кодируется функция переходов соответствующего устройства и работа с ней реализуется в режиме интерпретации.

ак как лексический анализ составляет значительную долю Процесса трансляции, такой метод часто оказывается слишком

ЗДеиным, чтобы его можно было принять. Однако некоторые



гл. 3. ТЕОРИЯ ПЕРЕВОДА

ЗАМЕЧАНИЯ по ЛИТЕРАТУРЕ

вычислительные машины имеют команды, распознающие те или иные виды лексем, и хотя этими командами нельзя промоделировать произвольный конечный автомат, они очень хорошо работают, когда лексемами служат ключевые слова или идентификаторы. Другой подход состоит в том, чтобы завести кусок программы для каждого состояния. В функции программы входит определение очередной буквы (для локализации буквы можно использовать подпрограмму), выдача требуемого выхода и переход к тому месту программы, которое соответствует следующему состоянию.

Важную проблему представляет выбор подходящего метода определения очередной буквы. Если для данного текущего состояния функция переходов такова, что большинство различных очередных букв приводят к различным следующим состояниям, то, по-видимому, нет ничего лучше, чем передавать управление косвенно через таблицу, основанную на очередной букве. Этот метод по скорости не уступает любому другому, ио для него нужна таблица, объем которой пропорционален числу различных букв.

В типичном лексическом анализаторе много состояний, для которых почти все очередные буквы приводят к одному и тому же состоянию. Размещение в памяти полной таблицы для каждого такого состояния привело бы к слишком большому расходу памяти. Для многих состояний разумным компромиссом между соображениями, связанными с затратами времени и памяти, был бы двоичный поиск для выбора тех немногих букв, которые вызывают переход в необычное состояние.

УПРАЖНЕНИЯ

3.3.1. Напишите регулярные выражения, эквивалентные следующим расширенным регулярным выражениям;

(а) {а+.ЬУ\

(б) (a\b)*-{ab)*,

(в) (аа\ЬЬу r\a{ab\bayb.

3.3.2. Напишите последовательность регулярных определений, приводящую к определению

(а) идентификаторов Алгола,

(б) идентификаторов ПЛ/1,

(в) комплексных констант вида (а, р), где а и р-вещественные константы Фортрана,

(г) комментариев в ПЛ/1.

3.3.3. Докажите теорему 3.3.

3.3.4. Постройте непрямые лексические анализаторы для трех регулярных множеств из упр. 3.3.2.

3 3.5. Постройте прямой лексический анализатор, различающий следующие лексемы:

(1) идентификаторы, представляющие собой любые последовательности букв и цифр, содержащие хотя бы одну букву (исключения оговорены в пункте (3)),

(2) константы, как в примере 3.19,

(3) ключевые слова IF, IN и INTEGER (которые не считаются идентификаторами).

3.3.6. Расширьте понятие неразличимых состояний (разд. 2.3), чтобы применить его к недетерминированным конечным автоматам. Если склеить все неразличимые состояния, обязательно ли получится недетерминированный автомат с минимальным числом состояний?

**3.3.7. Будет ли более легким прямой лексический анализ для Фортрана, если исходная программа считывается в обратном направлении?

Проблема для исследования

3.3.8. Дайте алгоритм выбора реализации для прямых лексических анализаторов. Ваш алгоритм должен допускать задание желательного соотношения между затратами времени н памяти. Возможно, Вы ие за.хотите реализовать работу конечного автомата символ за символом, а предпочтете использовать и другие операции. Например, если бы многие лексемы были арифметическими знаками, которые должны отделяться пробелами, как в Сноболе, то было бы разумно в качестве первого шага лексического анализа отделить эти лексемы от других, проверяя, является ли вторая буква пробелом-

Упражнения на программирование

3.3.9. Постройте лексический анализатор для одного из языков программирования, данных в приложении. Приведите соображения относительно того, как этот анализатор будет обнаруживать лексические ошибки, в частности описки.

3.3.10. Придумайте язык программирования, основанный на расширенных регулярных выражениях. Постройте компилятор

я этого языка. Программа в объектном языке должна быть Р ализацией лексического анализатора, описываемого исходной "Рограммой.

Замечания по литературе

лнза?оппТ" "ьшой системой, в которой при построении лексически.х ана-RVlORD/р"!!°*и техника конечных автомагов, была система AED (КШ а WORD), Обзор этой системы дан Джонсоном и др. [1938].



3.4. СИНТАКСИЧЕСКИЙ АНАЛИЗ

Томпсон [1968] приводит алгоритм, который по регулярному выражению строит программу в машинном языке, моделирующую соответствующий иеде-термииированный конечный автомат. Этот ал1-орнтм применялся для сравнения образцов в мощном языке QED, предназначенном для редактирования текстов.

Лексический анализатор целесообразно проектировать так, чтобы ил справлялся с лексическими ошибками. К ним относятся, в частности,

(1) замена в лексеме правильного символа неправильным,

(2) вставка в лексему лишнего символа,

(3) пропуск символа в лексеме,

(4) перестановка двух смежных символов лексемы.

Техника, позволяющая обнаруживать и исправлять ошибки такого рода, описана Фримэном [1964] и Морганом [1970]. Дополнительная литература по обнаружению и исправлению оигибок прн компиляции указана в замечаниях по литературе в конце разд. 1.2.

3.4. СИНТАКСИЧЕСКИЙ АНАЛИЗ

Второй фазой процесса компиляции обычно является фаза синтаксического анализа, или разбора. В данном разделе мы дадим формальные определения двух распространенных типов разбора и кратко сопоставим их возможности. Займемся также вопросом о том, что значит: одна грамматика „покрывает" другую.

3.4.1, Определение разбора

Мы говорим, что для некоторой КС-грамматики G цепочка wL{G) разобрана, или проанализирована, если известно одно (или, быть может, все) из ее деревьев выводов. При трансляции такое дерево можно „физически" построить в памяти машины, но вероятнее, что будет использован какой-нибудь более искусный способ представления. Прослеживая шаг за шагом работу синтаксического анализатора, можно получить дерево разбора, хотя связь между этими процессами едва ли сразу очевидна.

К счастью, большинство компиляторов осуществляют разбор моделированием МП-автомата, анализирующего входные цепочки либо сверху вниз, либо снизу вверх (см, разд. 2.5). Мы увидим, что способность МП-автомата проводить нисходящий анализ связана со способностью МП-преобразователя отображать входные цепочки в соответствующие левые выводы. Аналогично восходящий анализ связан с отображением входных цепочек в их обращенные правые выводы. Таким образом, мы буде трактовать проблему разбора как проблему отображения цепочек в их левые или правые выводы. Хотя известно много ДРУ гих стратегий разбора, мы будем опираться на эти две.

В разных частях книги упоминаются другие стратегии разбора. В упражнениях, помещенных в конце разд. 3.4, 4.1 и 5 1, рассматривается анализ по левому участку-метод разбора, который по своему характеру является и восходящим, и нисходящим- В разд. 6.2.1 мы обсудим методы обобщенного нисходящего и восходящего разбора.

Определение. Пусть G = (N, 2, Р, S) -КС-грамматика, правила которой занумерованы 1,2.....р. Пусть ae(Nu2)*. Тогда

(1) левым разбором цепочки а называется последовательность правил, примененных при левом выводе цепочки а из S,

(2) правым разбором цепочки к называется обращение последовательности правил, примененных при правом выводе цепочки сс из S.

Эти разборы можно представить в виде последовательпостн номеров из множества {1,2, ..., р).

Пример 3.22. Рассмотрим грамматику G с такой нумерацией правил:

Е--Т

-Tx-F

Левый разбор цепочки а»(а + а) -это последовательность 23465124646, а правый разбор -64642641532. П

Для описания левых и правых разборов введем дополнительные обозначения.

Соглашение. Пусть G = (N, S, Л 5)-КС-грамматика, правила которой занумерованы числами от 1 до р. Будем писать i->p, если а=>р и применено i-e правило. Аналогично будем нсать ау. если а=>р и применено i-e правило. Расширим гн обозначения, положив

0) щяу, если и ря.Т»

"f >я,яЛ, если а=>л, р и р=>я, у.

3-4.2. Нисходящий разбор

лнза Разделе мы хотим исследовать проблему левого ана-

OHKHwlrrl " я-ц.../„-левый разбор це-"ttU), где G -КС-грамматика. Зная я, можно построить





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 [48] 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.0019