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

3.3. КОММЕНТАРИИ И Т.Д.

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

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

3.4. ПРОБЛЕМЫ, СВЯЗАННЫЕ С КОНКРЕТНЫМИ ЯЗЫКАМИ

Лексический анализатор в основном базирует свои решения на информации, содержащейся в символе, который он обрабатывает. Обычно ожидают, что лексический анализатор примет любую последовательность символов, принадлежащих компилируемому языку. Например, при распознавании целочисленной константы для лексического анализатора не важно, следует ли она за оператором либо за символом begin или находится в объявлении процедуры либо в операторе do. Если способ объединения литер в символы зависит от контекста, может возникнуть затруднение. Например, в Фортране в последовательности

DO 7 1 = 1, 5

«DO» до момента чтения запятой может быть словом языка или же частью идентификатора

DO 71

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

пробелы не имеют значения. В ПЛ/1 слова языка (в основном) не являются зарезервированными, и для разрешения некоторых неоднозначностей может потребоваться предварительный просмотр. В Коболе слова языка (их свыше 100) зарезервированы, поэтому они не используются в качестве идентификаторов. В языках Бейсик и Алгол 68 слова принимают форму, отличную от идентификаторов, и их нельзя спутать. Однако в Алголе 68 возникает другая проблема. Если допустить, что знаки операций являются символами языка, то последовательность литер < = может быть интерпретирована как знак операции (обычно означающий «меньше или равно»). Однако такая же последовательность литер может встретиться и в программе на Алголе 68 в описании знака операции <, например

ор < =

В этом случае «<» есть знак операции, а « = » - символ, отделяющий имя знака операции от определяющей ее процедуры.

От лексического анализатора в такой ситуации ожидается передача «<» и « = » как двух разных символов. Но для того чтобы этот анализатор смог различить сложный символ <= и два символа «<» и « = », следующие друг за другом, ему необходимо иметь некоторую контекстуальную информацию. Очевидно, если ор предшествует «<=», их нужно рассматривать как два различных символа. В приведенном ниже контексте, где у нас имеется последовательность описаний знаков операций

ор > = =

разделенных запятыми, «<» и « = » также представляют собой разные символы. Чтобы справиться с подобными ситуациями, лексическому анализатору Алгола 68 иногда должно быть известно (по крайней мере, во избежание осложнений на последующем этапе) что-либо о контексте, в котором он работает.

Источником затруднений в Алголе 68 служат также форматы. Внутри формата (используемого для ввода-вывода) некоторые буквы, например X, Y, L, в одних местах имеют точно определенное значение, а в других их можно принять за идентификаторы (или части идентификаторов). Каждый формат заключен в пару символов формата (обычно это знаки доллара), так что лексический анализатор всегда знает, находится ли он внутри формата или нет, и может интерпретировать буквы X, Y, L и т. д. соответствующим образом. Осложнение возникает в тех форматах, которые содержат замкнутые предложения (блоки), где для этих литер нужно, конечно, опять вводить нормальную интерпретацию. В

$п(х-1)х, dd$

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

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

соответствующих каждому из тех видов, в которых ему предстоит работать.

М1 уже упоминали о том, что в программе могут содержаться определяемые пользователем выделенные слова, обозначающие виды или знаки операций. Однако лексический анализатор не имеет контекстуальной информации, и выделенные слова просто передаются как таковые. В каждой реализации Алгола 68 есть метод представления выделенных слов (и слов языка) в программе. Приведем два наиболее общих представления слова языка begin:

BEGIN и .BEGIN

Можно построить лексический анализатор таким образом, чтобы он принимал более одного представления выделенных символов, причем будет допускаться одно конкретное представление, если программист не даст другого указания с помощью прагматического замечания. Стандартное представление для Алгола 68 описано в [25].

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

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

Упражнения

3.1. Запишите порождающие правила грамматики типа 3, генерирующей регулярное выражение

(101)* (010)*

3.2.Выведите конечный автомат, соответствующий регулярному выражению в упражнении 3.1.

3.3.Выведите недетерминированный конечный автомат, принимающий регулярное выражение

(101)*(110)*