Главная страница
Навигация по странице:

  • Рис. 1. Заполнение рабочего стека при интерпретации ариф. выражения

  • Общий подход к интерпретации

  • Рис. 2. Таблица переходов и выходов МП-автомата

  • Использование «Учебного компилятора» в л/р №3 Войти в Режим ввода действий. Используя теоретический материал, Режим помощи

  • Ввода действий

  • Ввод действий в грамматику и построение синтаксического анализатора. Ввод действий в грамматику и построение синтаксического анализат. Лабораторная работа 3 Ввод действий в грамматику и построение синтаксического анализатора


    НазваниеЛабораторная работа 3 Ввод действий в грамматику и построение синтаксического анализатора
    АнкорВвод действий в грамматику и построение синтаксического анализатора.doc
    Дата04.10.2018
    Размер74 Kb.
    Формат файлаdoc
    Имя файлаВвод действий в грамматику и построение синтаксического анализат.doc
    ТипЛабораторная работа
    #24717
    КатегорияИнформатика. Вычислительная техника




    ЛАБОРАТОРНАЯ РАБОТА № 3
    Ввод действий в грамматику и построение синтаксического анализатора

    Цель работы – анализ построения МИ операторов языка программирования и создания синтаксического компилятора.


    1. Основные сведения



    Задачи синтаксического анализа



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

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

    • распознавание синтаксических единиц программы и проверка их правильности;

    • интерпретация конструкций языка – перевод в промежуточную форму в виде матрицы интерпретации ( МИ).

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

    Решение второй задачи часто называют семантическим или контекстным анализом. Как правило, он входит в состав синтаксического анализа, но может выделяться и в самостоятельную часть в некоторых случаях ( при однопроходных компиляторов ).

    Интерпретация конструкций языка программирования



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

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

    Как было указано выше, код в виде строки МИ должен порождаться сразу, как только символ за символом была проанализирована конструкция языка при нисходящем анализе.

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

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

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

    Проект интерпретации арифметического выражения.


    Пусть существует арифметическое выражение (- a + b )  ( c + d ) и грамматика для него:

    +







     -



     ()

     a | b | c | d | e

    Матрица интерпретации такого выражения может выглядеть следующим образом :

    Определим действия, необходимые для выполнения такого выражения.

    Прежде, чем выполнить любую операцию, необходимо в памяти ЭВМ иметь данные для ее выполнения. Поскольку для временного хранения данных при компиляции используется стек, то действие [1] – положить на стек переменную. В рассматриваемом примере четыре переменных. Значит, каждую из них необходимо разместить в стеке. После этого можно производить операции арифметики: [2] – сформировать операцию «+», использовав два верхних операнда из стека и внутреннюю переменную для результата, # Pi сохранить в стеке; [3] – сформировать операцию «», аналогично [2];

    [4] – сформировать операцию «-», использовав верхний операнд из стека.

    Теперь необходимо эти действия поместить в саму грамматику арифметического выражения:

    + [2]



    [3]



     - [4]

    [1]

     ( )

     a | b | c | d | e

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

    Как провести проверку правильности простановки действий? Нужно вновь построить выводы операторов, грамматики в целом и рассмотреть матрицы интерпретации для каждого из этих выводов.

    Выведем заданное арифметическое выражение, основываясь на грамматике с действиями:

         [3]    [3]  ()  [3]  ( + [2] )  [3]  ( + [2] )  [3]  ( + [2] )  [3]  ( -  [4] + [2] )  [3]  ( -  [1][4] + [2] )  [3]  ( - a [1] [4] +  [2] )  [3]  ( - a [1] [4] +  [2] )  [3]  ( - a [1] [4] +  [2] )  [3]  ( - a [1] [4] +  [1] [2] )  [3]  ( - a [1] [4] + b [1] [2] )   [3]  ( - a [1] [4] + b [1] [2] )  (  ) [3]  ( - a [1] [4] + b [1] [2] )  ( + [2] ) [3]  ( - a [1] [4] + b [1] [2] )  ( + [2] ) [3]  ( - a [1] [4] + b [1] [2] )  ( + [2] ) [3]  ( - a [1] [4] + b [1] [2] )  ( [1] + [2] ) [3]  ( - a [1] [4] + b [1] [2] )   ( c [1] +  [2] ) [3]  ( - a [1] [4] + b [1] [2] )  ( c [1] +  [2] ) [3]  ( - a [1] [4] + b [1] [2] )  ( c [1] +  [1] [2] ) [3]  ( - a [1] [4] + b [1] [2] )  ( c [1] + d [1] [2] ) [3] .

    Порядок действий полностью совпадает с МИ :

    - - - > Рабочий стек

    Рис. 1.
    Заполнение рабочего стека при интерпретации ариф. выражения

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

    Общий подход к интерпретации:

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

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

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

    • выполнить проверку грамматики с действиями построением выводов конструкций частного вида ( операторов, блоков операторов ) и мысленной их интерпретацией.

    Чем более сложные конструкции приходится интерпретировать, тем большее количество действий требуется включить в грамматику. Так, любой условный оператор требует генерации различного количества меток, необходимых для осуществления переходов, перед своим выполнением. Подробное описание действий, описывающих семантическую часть компилятора, содержится в справочнике “HELP” “Учебного компилятора”.


    Построение синтаксического анализатора



    Моделью, обеспечивающей распознавание цепочек символов, порождаемых КС- грамматиками, является автомат с магазинной (стековой ) памятью – расширение и обобщение конечного автомата.

    Автомат с магазинной памятью (МП-автомат ) – это устройство управления, имеющее конечное множество состояний (S0,S1,...) и магазинную память неограниченной длины, для которого определены входной алфавит (Х1,Х2,...), магазинный алфавит (Y1,Y2,...) и множество переходов и выходов, задающих ( в виде таблицы ) реакцию автомата на комбинацию текущего состояния, входного символа и символа в вершине магазина (переход).

    Переход состоит в операции:

    • над входным символом (“Принять”, т.е. перейти к следующему символу входной строки, или “Оставить без изменения”);

    • над магазинным символом (“Втолкнуть(Yi) ”, “Вытолкнуть”, “Оставить без изменения”);

    • над состоянием (“Перейти в состояние Si”, “Перейти в заключительное состояние Fj”(“Выход j”)).

    Распознающимназывается МП-автомат, имеющий два выхода “допустить” (Fd) “Отвергнуть” (Fo).

    Задать МП-автомат означает определить его начальное состояние и задать для каждого состояния таблицу переходов и выходов (). Чтобы определить начальное состояние автомата, необходимо установить начальное состояние устройства управления (S0), начальное состояние магазина ( обычно “магазин пуст” ) и текущий символ входной строки ( обычно первый ).
    Si (i=1,...k)

    Вх.с.

    М.с.

    Х1

    Х2

    ...

    Хn


    Y1

    Втолкнуть (Y3)

    Si принять

    ____

    Sk принять


    ...

    Вытолкнуть

    Sj ____

    ...

    - - -

    - - -

    ...

    - - -


    Ym

    Вытолкнуть

    Si принять

    Вытолкнуть

    Si ____


    ...

    ____

    Fd принять

    Рис. 2. Таблица переходов и выходов МП-автомата

    Доказано, что если грамматика принадлежит к классу КС-грамматик, то может быть определен МП-автомат, такой, что множество входных строк, допустимых этим автоматом, совпадает с множеством предложений, генерируемых данной грамматикой.

    На МП-автомате легко смоделировать последовательность шагов L-вывода предложения. Формализация этого алгоритма требует построения таблицы переходов и выходов распознающего МП-автомата по заданной LL(1)-грамматике, для чего нужно определить алфавиты входных и магазинных символов. Во входной алфавит должны быть включены все Т-символы и концевой символ (обозначающий конец входной строки), а в магазинный – все НТ- и Т-символы, символы действий и символ дна магазина (обозначает состояние «магазин пуст»). Но размер таблицы в этом случае будет слишком велик, поэтому чаще используется модифицированный алгоритм работы автомата, показанный на рис. 3. Магазинными символами в таблице переходов и выходов такого автомата будут только НТ-символы, а входными – направляющие символы правил. Шаг по таблице переходов и выходов представляет собой либо выход в указанное состояние («допустить» или «отвергнуть»), либо выталкивание НТ-символа из магазина и запись вместо него правой части заменяющего правила (символ за символом,

    начиная с последнего).

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

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

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

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

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

    В “Учебном компиляторе” окончательный формат управляющей таблицы имеет вид:


    Метка

    КОпА

    Прием

    Допустимый


    Действ.

    Воз

    врат

    Ошиб ка

    Недопуст.


    Мет.

    №со-

    -ст.

    Мет.

    №со--ст.



    Поле “Метка”, где указывается имя узла и номер альтернативы, используется для наглядности и упрощения построения таблицы, т.к. заранее неизвестно, на какой строке будет располагаться то или иное правило.

    В поле “КОпА” заполняется символическими командами анализатора:

    • “???” – проверить пригодность правила Р для продолжения анализа (проверка на совпадение очередного входного символа с направляющими символами правила Р);

    • => - переход к анализу внутреннего НТ-символа с возвратом (выполняет действие D с возвратом и переход в состояние S, в стеке возврата запоминается номер следующего состояния команды; действие выполняется до перехода);

    • <<= - возврат для продолжения анализа по правилу (выполняет переход в состояние , извлекаемое из стека возврата, действие выполняется до перехода);

    • `s` - проверить символ `s` во входной строке;

    • *** - конец анализа.


    2. ПОРЯ ДОК ВЫПОЛНЕНИЯ РАБОТЫ


    1. Отлаженную в л/р №1,2 грамматику открыть в Режиме построения выводов. Нажав на кнопку Действия войти в Режим ввода действий.

    2. Ввести номера действий в необходимых точках.

    3. Построить выводы грамматики с действиями.

    4. Проверить МИ конструкций.

    5. Построить СА.



    1. Использование «Учебного компилятора» в л/р №3




    1. Войти в Режим ввода действий.

    2. Используя теоретический материал, Режим помощи “Учебного компилятора” ввести номера необходимых действий в нужные точки грамматики.

    3. При успешном прохождении этапа Ввода действий, войти в Режим построения СА.

    4. Обозначить классы используемых в грамматике символов.

    5. Проверить построенный СА.




    1. Содержание отчета

    Отчет по лабораторной работе должен содержать следующие сведения:

    1. цель работы;

    2. вариант задания;

    3. листинг грамматики с включенными действиями;

    4. выводы конструкций с действиями и их МИ.




    1. Контрольные вопросы




    1. Поясните цели и задачи этапа синтаксического анализа.

    2. Что такое интерпретация конструкций языка программирования?

    3. Как используется стек на этапе синтаксического анализа?

    4. Поясните смысл вводимых грамматику действий.

    5. На основе какой теории строится синтаксический анализатор?

    6. Каков принцип работы синтаксического анализатора?



    ЛИТЕРАТУРА


    1. Грис Д. Конструирование компиляторов для цифровых вычислительных машин.:Пер. с англ.-М.:Мир,1975.-544с.

    2. Хантер Р. Проектирование и конструирование компиляторов.:Пер. с англ.-М.: Финансы и статистика, 1984. – 232с.
    написать администратору сайта