Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 16
Текст из файла (страница 16)
и., также считаются лексическими единицами языка программирования. Работа лексического анализатора состоит в том, чтобы сгруппировать определенные терминальные символы в единые синтаксические объекты, называемые лексемами. Какие объекты считать лексемами, зависит от определения языка программирования. Лексема — это цепочка терминальных символов, с которой мы связываем лексическую структуру, состоящую из пары вида (типлексемы, некоторые данные).
Первой компонентой пары является синтаксическая категория, такая, как „константа" или „идентификатор", а вторая — указатель: в ней указывается адрес ячейки, хранящей информацию об этой конкретной лексеме. Для данного языка число типов лексем предполагается конечным. Пару (тип лексемы, указатель) тоже будем называть лексемой, когда это не будет вызывать недоразумений. Таким образом, лексический анализатор — это транслятор, входом которого с ого служит цепочка символов, представляющая ть лексем.
исходную пи ю программу, а выходом — последовательность л Этот выход образует вход синтаксического анализатора. Пример 1Л. Рассмотрим следующий оператор присваивания из языка, подобного Фортрану: СОБТ=(РИСЕ+ТАХ) . 0.98 На этапе лексического анализа будет обнаружено, что о СС6Т, РИСЕ и ТАХ вЂ” лексемы типа идентификатора, а 0.98 — лексема типа константы.
н Знаки = (+ ) в сами являются лексемами. н жно отоб а- Допустим, что все константы и идентификаторы нужно ото разить в лексемы типа <ид>. Мы предполагаем, что вторая компонента лексемы представляет собой указатель элемента таблицы, содержащего фактическое имя идентификатора вместе с другими собранными нами данными об этом конкретном идентификаторе, Первая компонента используется синтаксическим анализатором для разбора.
Вторая компонента используется на этапе генерации кода для изготовления подходящего машинного кода. Таким образом, выходом лексического анализатора, работающего на нашей входной цепочке, будет последовательность лексем 4идУт = ((ид)в +4нд)„) а (идр, 3 орая компонента лексемы (указатель данных) показана десь втор в виде нижнего индекса. Символы = (+) а тр ту лексемы, тип которых представлен ими самими. Оии нс имеют связанных с ними данных и, значит, не имеют указателей. [~ Лексический анализ провести легко, если лексемы, состоящие более чем нз одного знака, изолированы с помощью знаков, к~~ор~~ сам" являю'Гся лекс ' р р емами. В п име е 1.1 знаки = ( + )н 1 не могут быть частью идентификатора, так что н ТАХ легко выделяются как лексемы.
Однако в общем случае лексический анализ может оказаться не таким легким. Например, рассмотрим следующие правильные операторы Фортрана: (!) !)О 1О ? =1.!5 (2) 1)О 10 1=1, 15 (1) епочка Т!О 10 1 — переменная т), а цепочка 1.15 — константа. В операторе (2) 00 — ключевое слово, 10 — а тта, 1 — переменная, 1 и 15 — константы. — коистат т, к соп оЕсли бы лексический анализатор был реализован ка рграмма (Джентльмен, !971; Мак-Илрой, !9681 и должен был на- т) Напомним, что в Фортрана пробелм нгнорнруютсв.
ГЛ.1.ВВЕДЕНИЙ Б КОМПИЛЯЦИЮ 1.2, ОБЗОР ПРОЦЕССА КОМПИЛЯЦИИ чать работу, находясь в начале одного из этих операторов, с выполнения такой команды, как „найти очередную лексему", то он до тех пор не мог бы определить, является этой лексемой ПО или 1)0 10 1, попа не дошел бы до запятой или точки. Таким образом, лексический анализатор иногда должен заглядывать вперед за интересующую его в данный момент лексему. Еще худший пример встречается в ПЛ!1, где ключепые слова могут быть переменными. Глядя на входную цепочку вида ПЕС(.АП Е (Х 1, Х2, ..., Хп) упомянутый выше лексический анализатор не знал бы, что ему сказать: то ли (лЕС).АКŠ— идентификатор функции и Х1, Х2,... ..., Хп — аргументы этой функции, то ли ПЕС(.А!(Š— ключевое слово, требующее, чтобы у идентификаторов Х!, Х2, ..., Хп был атрибут (или атрибуты), расположенный непосредственно справа от правой скобки.
Здесь различение лексем должно Осуществляться с помощью части текста, которая идет после правой скобки. Но так как число и может быть сколь угодно большим '), то, работая с языком ПЛу1, этот лексический анализатор должен заглядывать вперед сколь угодно далеко. Однако существует другой подход к лексическому анализу, менее удобный, но позволяющий избежать проблемы произвольно далекого заглядывания вперед. Мы определим два крайних подхода к лексическому анализу.
Большинство известных способов основано на том или другом пз этих подходов, а некоторые на нх комбинации. (1) Говорят, что лексический анализатор работает прямо, если для данного входного текста (цепочки) и положения указателя в этом тексте анализатор определяет лексему, расположенную непосредственно справа от указываемого места, и сдвигает указатель вправо от части текста, образующей эту лексему. (2) Говорят, что лексический анализатор работает не прямо, если для данного текста, положения указателя в этом тексте и типа лексемы он определяет, образуют лц знаки, расположенные непосредственно справа от указателя, лексему этого типа.
Если да, то указатель передвигается вправо от части текста, образующей эту лексему. Пример !.2. Рассмотрим текст из Фортрана ПО 10 1 — -1, !5 с указателем, расположенным на левом конце. Непрямой лексический анализатор ответит,да", если его спросят о лексеме т) В определении языка верхана граннца для п не указывается, однако в каждом конкретном номпнляторс с языка П11'1 она, нонечно, существует. типа ПО или о лексеме типа <идентификатор>. Но в первом случае указатель передвинется на два символа вправо, а в последнем †пять символов.. Прямой лексический анализатор обследует текст вплоть до запятой и сделает заключение, что очередная лексема должна быть типа (лО. Указатель при этом передвинется только на два символа вправо, хотя было просмотрено гораздо больше символов. Ед Вообще мы будем описывать алгоритмы синтаксического анализа в предположении, что лексический анализ прямой.
В случае непрямого лексического анализа можно использовать „недетерминированные*' алгоритмы или алгоритмы с возвратами. Синтаксический анализ этого типа мы обсудим в гл. 4 и 6. 4.2.3. Работа с табпмцами После того как в результате лексического анализа лексемы распознаны, информация о некоторых из них собирается и за- пасается в одной или нескольких таблицах. Какова эта инфор- мация, зависит от языка.
В случае Фортрана, например, мы хотели бы знать, что СОЗТ, РЕ!СЕ и ТАХ вЂ” переменные с пла- вающей точкой, а 0.98 — константа с плавающей точкой. Допустим, что СОЗТ, РВ1СЕ и ТАХ не описаны оператором описанйя типа. Тогда необходимую информацию об этих пере- менных можно извлечь из того, что СОЗТ, РИСЕ и ТАХ на- чинаются с букв, отличных от 1, 3, К, 1., М, )ч), В качестве другого примера на сбор информации о перемен- ных рассмотрим оператор Фортрана (л1МЕ)ч)810)ч) вида 1)1МЕ)ЦЫОР( А(10 20) Встретив этот оператор, мы должны запасти информацию о том, что А — идентификатор, являющийся именем двумерного массива с размерами 10 и 20.
В сложных языках, таких, как ПЛ!1, объем сведений, которые надо запомнить о данной переменной, может быть очень велик. Рассмотрим несколько упрощенный пример таблицы, в кото- рой хранится информация об идентификаторах. Такую таблицу часто называют таблицей имен (а также таблицей идентафихо.- таблицей символов). В ней перечислены, в частности, й. все идентификаторы вместе с относящейся к ним информациет.
Допустим, что в тексте встречается Оператор СОЗТ = (РВ1СЕ-. 'ТАХ) в 0.98 После просмотра этого оператора таблица может иметь видтабл. 1,, ,1, Если позднее во входной цепочке попадется ндентифииатор, надо справиться в этой таблице, не появлялся ли он раньше. ту гл. !.
введение в компиляцию Таблица А1 Номер аиеиента Идентификатор Информации Переменная с плвввющей точкой Переменная с плавающей точкой Переменная с плавающей точкой Константа с плавающей точкой 005Т РЦ!ПЕ ТАХ 0.98 указанного выше оператора следует оператор, содержащий переменную СОЯТ, то лексемой для второговхождеция СОЯТдолжна быть <ид>,— та же, что и для первого вхождения. Таким образом, эта таблица должна обеспечивать (1) быстрое добавление новых идентификаторов и новых сведений о них, (2) быстрый поиск информации, относящейся к данному идентификатору. Обычно применяют метод хранения данных с помощью таблиц расстановки; оци будут обсуждаться в гл. !О (том 2).
Если да, то лексема, соответствующая новому вхождению этого идентификатора, будет той же, что и у предыдущего вхождения. Например, если в программе, написанной на Фортране, после !.г, овзор процесса компиляции Разбор — одна из наиболее понятных фаз компиляции. По сово° ности синтаксических правил можно автоматически построить синтаксический анализатор, который будет проверять, имеет ли исходная программа синтаксическую структуру, определяемую этими и ими правилами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
