Реферат: Проектирование трансляторов

чального символа деpева вывода.

     4. Вычислить значения атpибутов символов, входящих в  деpево

вывода, повтоpяя следующее действие до тех поp, пока оно не  ста-

нет невозможным. Найти атpибут, котоpого еще  нет  в  деpеве,  но

аpгументы пpавила его вычисления уже имеются, вычислить  значение

этого атpибута и добавить его к деpеву.

     5. Если выполнение шага 4 пpиведет к тому, что значения всех

атpибутов всех символов деpева окажутся  вычисленными,  то  будем

называть полученное деpево завеpшенным. В пpотивном случае  деpе-

во называется незавеpшенным.

                            ЛЕКЦИЯ 8

         ЛЕКСИЧЕСКИЙ АНАЛИЗАТОР. АВТОМАТНЫЕ ГРАММАТИКИ.

                      РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ

      Лексический анализатор (иногда также  называемый  сканером)

представляет собой наиболее простую часть компилятора.  Лексичес-

кий анализатор просматривает литеры исходной программы слева нап-

раво и строит символы программы -  целые  числа,  идентификаторы,

служебные слова и т.д. В литературе иногда вместо термина  символ

используют термины элемент и атом. Символы  передаются  затем  на

обработку фактическому анализатору. На этой стадии может быть ис-

ключен комментарий (именно такой путь исключения комментария  был

избран в данном курсовом проекте). Лексический  анализатор  также

может заносить идентификаторы в таблицу символов, выполнять  дру-

гую простую работу, которая фактически не требует анализа  исход-

ной программы и может быть проделана на основе анализа  отдельных

лексем. Он может выполнить большую часть работы  по  макрогенера-

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

       Обычно лексический анализатор передает  символы  синтакси-

ческому анализатору во внутренней форме. Каждый разделитель (слу-

жебное слово, знак операции или знак пунктуации) будет  представ-

лен целым числом. Идентификаторы иликонстанты  можно  представить

парой чисел. Первое число, отличное от любого целого  числа,  ис-

пользуется для представления разделителя, характеризует  сам  "и-

дентификатор" или "константу"; второе число является адресом  или

индексом идентификатора или константы в  некоторой  таблице.  Это

позволяет в остальных  частях  компилятора  работать  эффективно,

оперируя с символами фиксированной длины, а не с цепочками  литер

переменной длины.

     Лексический анализатор по своему строению является  конечным

автоматом. В этом пункте мы рассмотрим некторые проблемы, связан-

ные с реализацией конечного автомата или процессора как  програм-

мы или подпрограммы для вычислительной машины. В этом  пункте  мы

рассмотрим три взаимосвязанных вопроса:

     1. Как представлять выходы, состояния и  переходы  конечного

автомата, чтобы удовлетворить зачастую противоречивые требования,

предъявляемые к реализации: быстродействие  и  небольшие  затраты

памяти.

     2. Как справиться с  некоторыми  специфическими  проблемами,

постоянно возникающими при компиляции.

     3. Как расчленить задачу построения компилятора, чтобы полу-

чить автоматы, допускающие простую реализацию.

     Некоторые задачи, решаемые  с  помощью  конечных  автоматов,

заключаются всего лишь в распознавании конечного множества  слов.

Суть этих проблем в том, что компилятор должен обнаружить появле-

ние некоторого слова из такого множества и  затем  действовать  в

зависимости от того, какое это слово. Задачи такого характера на-

зываются проблемой "идентификации", т.к. действия компилятора за-

висят от идентичности некоторому известному слову данного  слова.

Так для решения задач идентификации может потребоваться  огромное

число состояний, в  подобных  случаях  часто  приходится  пользо-

ваться специальными методами реализации. По этой причине целесоб-

разно строить компилятор так, чтобы проблема идентификации  реша-

лась отдельным  подпроцессором,  специально  предназначенным  для

этого.

     Существуют проблемы идентификации, которые,  строго  говоря,

не могут быть решены с помощью конечного автомата. Например, час-

то встречающаяся проблема распознавания переменных или  идентифи-

каторов некоторого языка. Решение этой проблемы обычным методом с

помощью конечного автомата потребует несколько состояний и  нали-

чия элемента таблицы имен для каждого допустимого идентификатора.

Однако множество допустимых идентификаторов в большинстве  языков

бесконечно или так велико, что его вполне можно считать бесконеч-

ным.

     Понятно, что для языков, где число допустимых  идентификато-

ров бесконечно или  практически  бесконечно,  невозможно  отвести

место в памяти или элемент таблицы имен  для  каждого  возможного

идентификатора. Это затруднение преодолевается с помощью  понятия

расширяющегося конечного автомата. При считывании  своей  входной

цепочки этот автомат отводит для идентификатора необходимое  мес-

то в памяти и элемент в таблице, как только он впервые встречает-

ся в программе. Если этот идентификатор встречается  в  программе

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

ку идентификации слов с помощью конечного автомата.  Когда  появ-

ляется какой-тоновый идентификатор, автомат снова расширяется и

т.д.. Хотя этот автомат не является, строго говоря,  конечным,  к

нему применимы многие принципы построения и анализа конечных  ав-

томатов.

                      Автоматные гpамматики

     К сожалению, не все КС-гpамматики пpигодны  для  нисходящего

анализа МП-автоматов, так как для многих гpамматик множество всех

допустимых пpодолжений  обpаботанной  части  входной  цепочки  не

всегда можно пpедставить единственной цепочкой теpминальных и не-

теpминальных символов. Рассмотpим такой класс гpамматик, для  ко-

тоpых нисходящие МП-pаспознаватели можно постpоить - так называе-

мые автоматные гpамматики. (Фоpмальное опpеделение дано выше.)

     Фактически контекстно-свободная гpамматика является автомат-

ной тогда и только тогда, когда выполняются следующие два условия:

     1. Пpавая часть каждого пpавила начинается теpминалом.

     2. Если два пpавила имеют совпадающие левые части,  то  пpа-

вые части этих пpавил должны начинаться pазличными  теpминальными

символами. Для данной автоматной гpамматики  МП-pаспознаватель  с

одним состоянием задается следующим обpазом:

     1. Множество входных символов - это  множество  теpминальных

символов, pасшиенное концевым маpкеpом.

     2. Множество магазинных символов состоит из маpкеpа дна, не-

теpминальных символов и теpминалов, котоpые входят в пpавые  час-

ти пpавил, кpоме занимающих кpайнюю левую позицию.

     3. В начале магазин состоит из маpкеpа дна и начального  не-

теpминала.

     4. Упpавление pаботой МП-автомата с одним состоянием  описы-

вается упpавляющей таблицей, стpоки котоpой помечены  магазинными

символами, столбцы входными символами, а элементы описываются ни-

же.

     5. Каждому пpавилу гpамматики сопоставляется элемент  табли-

цы. Пpавило имеет вид <A> -> ba, где <A> - нетеpминал, b - теpми-

нал, а a - цепочка из теpминалов и  нетеpминалов.  Этому  пpавилу

будет соответствовать элемент в стpоке <A> и столбце b

     ЗАМЕНИТЬ (a'), СДВИГ

     где a'  -  цепочка а, записанная в  обpатном  поpядке.  Если

пpавило имеет вид <A> -> b, то вместо ЗАМЕНИТЬ  (e)  используется

ВЫТОЛКНУТЬ.

     6. Если магазинным символом является теpминал b, то  элемен-

том таблицы в стpоке b и столбце b будет ВЫТОЛКНУТЬ, СДВИГ.

     7. Элементом таблицы, котоpый находится в стpоке маpкеpа дна

и столбце концевого маpкеpа, является ДОПУСТИТЬ.

     8. Элементы таблицы, не описанные ни в одном из пунктов 5-7,

заполняются опеpацией ОТВЕРГНУТЬ.

     Два огpаничения, наложенные нами  на  КС-гpамматики,  гаpан-

тиpуют, что эти пpавила постpоения МП-автомата всегда будут pабо-

тать. Огpаничение 1 говоpит, что пpодукции гpамматики имеют  тpе-

буемую фоpму, а огpаничение 2 нужно для того, чтобы пpи  пpимене-

нии пpавила 5 элемент таблицы содеpжал только одну пpодукцию. Та-

ким обpазом, мы пpишли к заключению, что:

    - если язык опpеделяется автоматной гpамматикой, то его  мож-

но pаспознать с  помощью  МП-автомата  с  одним  состоянием,  ис-

пользующим pасшиpенную магазинную опеpацию  ЗАМЕНИТЬ.  Можно  го-

воpить о тождественности  автоматной  гpамматики  и  МП-автомата,

постpоенного по ней.

                            ЛЕКЦИЯ 9

            КРАТКИЕ СВЕДЕНИЯ О ГЕНЕРАТОРЕ ЛЕКСИЧЕСКИХ

                        АНАЛИЗАТОРОВ LEX

     Лексический анализ  -  это распознавание лексем  во  входном

потоке символов. Предположим, что задано некоторое конечное  мно-

жество слов  (лексем)  в  некотором  языке  и  некоторое  входное

слово.Необходимо установить, какой элемент множества (если он су-

ществует) совпадает с данным входным словом.

     Обычно лексический анализ выполняется так называемым  лекси-

ческим анализатором. Применяется во многих случаях, например, для

построения пакетного редактора или в качестве распознавателя  ди-

ректив в диалоговой программе и т.д. Наиболее  важное  применение

лексического анализатора - это использование его  в  компиляторе.

Здесь лексический анализатор выполняет  функцию  программы  ввода

данных.

     Лексический анализатор выполняет первую стадию компиляции  -

читает строки компилируемой программы, выделяет лексемы  и  пере-

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

кодогенерацию и т.д.).

     Лексический анализатор распознает тип каждой лексемы и соот-

ветствующим  образом  помечает  ее.  Например,  при    компиляции

Си-программы могут быть выделены следующие  типы  лексем:  число,

идентификатор, оператор, ограничитель и т.д.

     Лексический анализатор должен не только выделить лексему, но

и выполнить некоторые преобразования. Например, если лексема

- число, то его необходимо  перевести  во  внутреннюю  (двоичную)

форму записи как число с плавающей или  фиксированной  точкой.  А

если лексема - идентификатор, то его необходимо разместить в таб-

лице, чтобы в дальнейшем обращаться к нему не по имени, а по  ад-

ресу в таблице.

     Хотя лексический анализ по своей идее прост,  тем  не  менее

эта фаза работы компилятора часто занимает  больше  времени,  чем

любая другая. Частично это происходит из-за  необходимости  прос-

матривать и анализировать  исходный  текст  символ  за  символом.

Иногда даже бывает необходимо вернуть прочитанный символ во вход-

ной поток с тем, чтобы повторить просмотр  и  анализ.  Происходит

это потому, что часто бывает трудно определить, где проходят гра-

ницы лексемы. В тех случаях, когда выделение  лексемы  затруднено

либо по причине того, что одно регулярное выражение не  позволяет

ее однозначно определить, либо из-за того, что  лексема  является

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

ритмам анализа с  использованием  левого  и  правого  направлений

просмотра входной цепочки символов.

     Lex - частично или полностью автоматизирует процесс  написа-

ния программы лексического анализа.  Lex  -  это  программирующая

программа или генератор программ. Lex строит программу  -  лекси-

ческий анализатор на так  называемом  host-языке  (или  "главном"

языке). Это значит, что Lex-программа пишется на "языке"  Lex,  а

Lex-генератор, в свою очередь, генерирует программу  лексического

анализа на каком-либо другом языке. Данная версия Lex  генерирует

лексические анализаторы на языках Си и Ратфор (рациаональный диа-

лект Фортрана). В качестве host-языка мы будем использовать  язык

Си.

     Lex-программа имеет следующий формат:

     определения %%

     правила %%

     подпрограммы, составленные пользователем

     Любой  из  этих  разделов  может  быть  пустым.   Простейшая

Lexпрограмма имеет вид:

        %%

     Здесь нет никаких определений и никаких правил. Правило сос-

тоит из двух частей:

     РЕГУЛЯРНОЕ_ВЫРАЖЕНИЕ ДЕЙСТВИЕ

     По регулярным выражениям, содержащимся в левой части правил,

Lex строит детерминированный конечный автомат. Этот автомат  осу-

ществляет интерпретацию, а не компиляцию. Количество правил и  их

сложность не влияют на скорость лексического анализа, если только

правила не требуют слишком большого об'ема  повторных  просмотров

входной последовательности символов. Однако, с ростом числа  пра-

вил и их сложности растет размер конечного автомата,  интерпрети-

рующего их и, следовательно, растет размер  Си-программы,  реали-

зующей этот конечный автомат. Lex всегда, если не указано другое,

строит выходной файл с именем lexyy.c - Си-программу -  лексичес-

кий анализатор.

     Если имеется необходимость получить файл с именем,  отличным

от lexyy.c, то можно воспользоваться флагом "-t":

        % lex -t source.l > file

     По этому флагу результат поступает на стандартный вывод. Ре-

гулярные выражения в Lex-правилах определяют лексему.  Они  могут

содержать символы латинского и русского  алфавитов  в  верхнем  и

нижнем регистрах, другие символы (цифры, знаки препинания и

т.д.) и символы-операторы.

     Операторы позволяют осуществлять различные действия над  вы-

деленной цепочкой символов. Операторы также обозначаются символа-

ми.

     Обозначения символов в выражениях. Можно использовать  любой

символ. Символ можно указывать в двойных кавычках. В этом  случае

это всегда просто символ - его специальное значение отменяется.

     . - точка означает любой символ, кроме символа новой  строки

"\n";

     \восьмеричный_код_символа - указание символа его  восьмерич-

ным кодом (как в языке Си);

     \n -  символ новой строки;

     \t -  символ табуляции;

     \b -  возврат курсора на один шаг назад;

     Пробел - любой символ пробела в выражении, если он не  нахо-

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

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

Lex в качестве разделителя между определением и действием в  пра-

виле.

                 Операторы регулярных выражений

     Операторы обозначаются символами-операторами, к ним относят-

ся:

     \   ^   ?   *   +   |   $   /   %

           [] {} () <>

     Каждый из этих символов или пар скобок в регулярном  выраже-

нии играет роль оператора. Если необходимо  отменить  специальное

значение символа, обозначающего оператор, перед ним нужно  поста-

вить символ "\" или указать его в двойных кавычках.

     Оператор выделения классов  символов.Квадратные  скобки  за-

дают классы символов, которые в них заключены.

     [abc] означает либо символ "a", либо "b", либо символ "c";

     Знак "-" используется для указания любого символа из  лекси-

кографически упорядоченной последовательности: [A-z] означает лю-

бой латинский символ;

                           Повторители

     Когда необходимо указать повторяемость вхождения  символа  в

регулярном выражении, используют операторы-повторители "*" и "+".

     Оператор "*" означает любое (в том числе и 0) число  вхожде-

ний символа или класса символов. Например: x* любое число вхожде-

ний символа "x"; Оператор "+" означает одно  и  более  вхождений.

Например: x+ одно или более вхождений "x";

                        Операторы выбора

     Операторы: / | ? $ ^ управляют процессом выбора символов.

     Оператор "/": ab/cd "ab" учитывается только тогда, когда  за

ним следует "cd".

     Опeратор "|": ab|cd или "ab", или "cd".

     Опeратор  "?":  x?  означает  необязательный  символ    "x".

     _?[A-Za-z]* означает, что перед цепочкой  любого  количества

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

     -?[0-9]+ выделит любое целое число с необязательным  минусом

впереди.

     Оператор "$": x$ означает выбрать символ "x",  если  он  яв-

ляется последним в строке. Стоит перед символом "\n"! abc$  озна-

чает выбрать цепочку "abc", если она завершает строку.

     Оператор "^": ^x означает выбрать символ "x",  если  он  яв-

ляется первым символом строки; ^abc означает выбрать цепочку сим-

волов "abc", если она начинает строку. [^A-Z]* означает все  сим-

волы, кроме прописных латинских букв. Когда символ "^" стоит  пе-

ред выражением или внутри "[]", он выполняет операцию дополнение.

Внутри квадратных скобок символ  "^"  должен  обязательно  стоять

первым у открывающей скобки!

     Оператор {} имеет два различных применения:

     x{n,m} здесь n и m натуральные, m > n. Означает от  n  до  m

вхождений x, например, x{2,7} - от 2 до 7 вхождений x;

     {имя} вместо "{имя}" в данное место выражения будет подстав-

лено определение имени из области определений Lex-программы.

     yytext -  это внешний массив  символов  программы  lex.yy.c,

которую строит Lex. yytext формируется в процессе чтения  входно-

го файла и содержит текст, для которого установлено  соответствие

какому-либо выражению. Этот массив доступен пользовательским раз-

делам Lex-программы.

           Оператор <>. Служебные слова START и BEGIN

     Раздел правил Lex-программы может содержать активные и неак-

тивные правила. Активные правила выполняются  всегда.  Неактивные

выполняются только в тех случаях, когда выполняется некоторое на-

чальное условие.

     Начальные условия Lex-программы помещаются в раздел  опреде-

лений, а неактивные правила помечаются соответствующими  условия-

ми. Оператор Start позволяет  указать  список  начальных  условий

Lex-программы, а оператор BEGIN позволяет  активировать  правила,

помеченные начальными условиями.

     Активные правила имеют следующий синтаксис:

     РЕГУЛЯРНОЕ_ВЫРАЖЕНИЕ ДЕЙСТВИЕ

     Неактивные правила имют следующий синтаксис:

     <МЕТКА_УСЛОВИЯ>РЕГУЛЯРНОЕ_ВЫРАЖЕНИЕ ДЕЙСТВИЕ

     ВАЖНО: любое правило  должно  начинаться  с  первой  позиции

строки, пробелы и табуляции недопустимы -  они  используются  как

разделители между регулярным выражением и действием в правиле.

     Lex-программа  может  содержать  несколько  помеченных   на-

чальных условий.

     Каждое правило, перед которым указан  оператор  типа  "<МЕТ-

КА>", мы будем называть помеченным  правилом.  Метка  формируется

также как и метка в Си.

     Количество помеченных правил не ограничивается. Кроме  того,

разрешается одно правило помечать несколькими метками,  например:

<МЕТКА1,МЕТКА2,МЕТКА3>x ДЕЙСТВИЕ

     Запятая - обязательный разделитель списка меток !

                     Структура Lex-программы

     Lex-программа включает разделы опредeлений, правил и пользо-

вательских программ. Рассмотрим подробнее способы оформления этих

разделов.

     Все строки, в которых занята  первая  позиция,  относятся  к

Lex-программе. Любая строка, не  являющаяся  частью  правила  или

действия, которая начинается с пробела или табуляции,  копируется

в сгенерированную программу lex.yy.c - результат работы Lex.

                Раздел определений Lex-программы

     Определения, предназначенные для Lex, помещаются перед  пер-

вым %%. Любая строка этого раздела, не содержащаяся между %{ и %}

и начинающаяся в первой  колонке,  является  определением  строки

подстановки Lex. Раздел определений Lexпрограммы может включать:

     - начальные условия;

     - определения;

     - фрагменты программы пользователя;

     - таблицы наборов символов;

     - указатели host-языка;

     - изменения размеров внутренних массивов;

     - комментарии в формате host-языка.

     НАЧАЛЬНЫЕ УСЛОВИЯ задаются в форме:

        %START имя1 имя2 ...

     Если начальные условия определены, то эта строка должна быть

первой в Lex-программе.

     ОПРЕДЕЛЕНИЯ задаются в форме:

        имя трансляция

     В качестве разделителя используется один или более  пробелов

или табуляций. Имя - как обычно, любая последовательность букв  и

цифр, начинающаяся с буквы. Трансляция - это  регулярное  выраже-

ние (или его часть), которое будет  подставлено  всюду  там,  где

указано имя (смотрите третью строку этого примера).

     ФРАГМЕНТЫ ПРОГРАММЫ ПОЛЬЗОВАТЕЛЯ указываются двумя способами:

     - в виде "пробел фрагмент";

     - в виде %{ строки фрагмента программы  пользователя %}

     Такая форма включения пользовательского фрагмента  необходи-

ма для ввода, например, макроопределений Си, которые должны начи-

наться в первой колонке строки. Все  строки  фрагмента  пользова-

тельской программы, размещенные в разделе определений, будут  яв-

ляться внешними для любой функции программы lex.yy.c

     ТАБЛИЦА НАБОРОВ СИМВОЛОВ задается в виде:

   %T

   целое_число   строка_символов

    .........

   целое_число   строка_символов

   %T

     Сгенерированная программа lex.yy.c  осуществляет  ввод-вывод

символов посредством библиотечных функций Lex  с  именами  input,

output, unput. Таким образом, Lex помещает  в  yytext  символы  в

представлении, используемом в  этих  библиотечных  функциях.  Для

внутреннего использования  символ  представляется  целым  числом,

значение которого образовано набором битов,  представляющих  сим-

вол в конкретной ЭВМ.  Пользователю  предоставляется  возможность

менять представление символов (целых констант) с помощью  таблицы

наборов символов. Если таблица символов  присутствует  в  разделе

определений, то любой символ, появляющийся либо во входном  пото-

ке, либо в правилах, должен быть определен  в  таблице  символов.

Символам нельзя назначать число 0 и число, большее  числа,  выде-

ленного для внутреннего представления символов конкретной ЭВМ.

     УКАЗАТЕЛЬ host-языка имеет вид:

     %C для Си;

     %R для Ратфора.

     Если указатель host-языка отсутствует, то по умолчанию  при-

нимается Си.

     ИЗМЕНЕНИЯ РАЗМЕРА ВНУТРЕННИХ МАССИВОВ задаются в форме:

     %x число

     "число" - новый размер массива;

     "x" - одна из букв p - позиции;

     n - состояния;

     e - узлы дерева;

     a - упакованные переходы;

     k - упакованные классы символов;

     o - массив выходных элементов.

     Lex имеет внутренние таблицы,  размеры  которых  ограничены.

При построении программы лексического анализа может произойти пе-

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16