Главная » Просмотр файлов » Теория синтаксического анализа, перевода и компиляции - Том 1

Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 16

Файл №943928 Теория синтаксического анализа, перевода и компиляции - Том 1 (Теория синтаксического анализа, перевода и компиляции) 16 страницаТеория синтаксического анализа, перевода и компиляции - Том 1 (943928) страница 162013-09-12СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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).

Если да, то лексема, соответствующая новому вхождению этого идентификатора, будет той же, что и у предыдущего вхождения. Например, если в программе, написанной на Фортране, после !.г, овзор процесса компиляции Разбор — одна из наиболее понятных фаз компиляции. По сово° ности синтаксических правил можно автоматически построить синтаксический анализатор, который будет проверять, имеет ли исходная программа синтаксическую структуру, определяемую этими и ими правилами.

Характеристики

Тип файла
DJVU-файл
Размер
4,65 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6553
Авторов
на СтудИзбе
299
Средний доход
с одного платного файла
Обучение Подробнее