Министерство образования Российской Федерации

Саратовский государственный технический университет

             
 Построение детерминированного синтаксического

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

        работы по курсу «Теория вычислительных процессов

            структур» для студентов специальности  ПВС
                            Составил доцент кафедры ПВС

                                      Сайкин А.И.
                                Саратов, 2001 г.
                                     1. Введение.

Данная лабораторная работа рассчитана на 4 аудиторных часа и ещё 4 часа самостоятельной работы для изучения литературы и оформление отчёта.

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

Метод построения синтаксического анализатора основывается на применении грамматик типа LL(1), что позволяет решить задачу, используя  детерминированный алгоритм.

Лабораторная работа выполняется в дисплейном классе. Результат представляет собой работающую программу, которая может анализировать любые тексты и сообщать об ошибках программирования.
                           2. Содержание работы.

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

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

Одним из способов описания алгоритма распознавания языка является задание его в виде некоторого распознающего устройства. Для КС-языков такими устройствами являются магазинные автоматы - автоматы с магазинной памятью.

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

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

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

Две буквы L означают, что цепочка символов разбирается слева направо, и используются самые левые продукции. Цифра 1 означает, что варианты порождающих продукций выбираются с помощью одного предварительно просмотренного символа. Эта терминология была впервые предложена Кнутом. Если КС-грамматика не является грамматикой  типа LL(1), то её нужно привести к этому типу.

LL(1) грамматика допускает детерминированный разбор предложений языка, описываемого этой грамматикой. Если эта грамматика задана, то магазинный автомат строится по известному правилу [1], а построенный автомат позволяет запрограммировать процесс синтаксического анализа, действуя формально, что и предопределяет решение задачи.
                  3. Задание по работе.

1. Вариант задания к данной лабораторной работе совпадает с вариантом задания к 1 лабораторной работе.

2. Построить КС-грамматику и проверить является ли она грамматикой типа LL(1).

3. Привести грамматику к типу LL(1).

4. По правилу [1] построить магазинный распознаватель, реализующий детерминированный разбор. Составить управляющую таблицу автомата.

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

6. Запрограммировать работу синтаксического анализатора.

7. Представить два контрольных примера.

8. Составить отчёт по работе.
                         4. Методические указания.

Язык программирования описывается КС-грамматикой. Детерминированный синтаксический анализ требует, чтобы КС-грамматика отвечала определённым требованиям. Во-первых, необходимо привести её, т.е. грамматика не должна содержать циклы, e-продукции, бесполезные и недостижимые символы, левые рекурсии.

Недостижимые нетерминальные символы никогда не появятся ни в одной из выводимых цепочек. Бесполезные символы не играют никакой роли в построении правильных терминальных цепочек. Такие символы могут появиться в КС-грамматике в основном не из-за ошибок разработчика языка- они могут быть введены в грамматику алгоритмами, предназначенными для модификации грамматик.

КС-грамматика называется грамматикой без e-продукций (e-свободной), если множество продукций Р не содержит e-продукций, либо есть только одна продукция S®e и S не встречается в правых частях остальных продукций.

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

                          А®А , для А Ì N.

         

         АЛГОРИТМ УСТРАНЕНИЯ НЕДОСТИЖИМЫХ.
Пусть дана КС-грамматика G={N,T,P,S}. Построим КС-грамматику  G’={N’, T’, P’, S} без недостижимых символов. Метод состоит в следующем:

1. Положим множество V={S} и  i=1.

2. Положим множество V_i = V_i-1È{A®aCb Î P  и   A Î V_i-1 }.

3. Если V_i  ¹ V_i-1,  то i=i=1 и перейти к шагу 2. В противном случае

    N’= N Ç V_i , T’=TÇV_i. Искомое множество продукций Р’ состоит

   из множества продукций Р, содержащих символы из множества V_i



       АЛГОРИТМ УСТРАНЕНИЯ БЕСПОЛЕЗНЫХ СИМВОЛОВ.
Пусть дана КС-грамматика G={N,T,P,S}. Построим эквивалентную грамматику G’={N’, T’, P’, S} без бесполезных символов. Метод состоит в следующем:

1. Положим N₀=Æ, i=1.

2. Положим множество N_i=N_i-1È{A | A®aÎR,  aÎ(N_i-1ÈT)*}.

3. Если N_i¹N_i-1, положим i=i+1 и перейти к шагу 2. В противном случае положим N₀=N_i.

4. Положим G₁={N₀Ç N,T,P’,S}, где P’ÍP состоит из продукций множества Р, содержащих символы из N₀ÎN.

5. Применив к G₁ алгоритм устранения в грамматике недостижимых символов, получим G’={N’, T’, P’, S}.
           АЛГОРИТМ ПРЕОБРАЗОВАНИЯ ГРАММАТИКИ В

                    ГРАММАТИКУ БЕЗ e-ПРОДУКЦИЙ.
Пусть дана КС-грамматика G={N,T,P,S}. Построим e-свободную грамматику G’, эквивалентную грамматике G. Метод состоит в следующем.

1. Применяем шаги 1-3 алгоритма устранения бесполезных символов, определяем множество N₀={ A | AÎN, A®e}.

2. Множество P’ строим следующим образом. Если продукция A®a₀B₁a₁B₂a₂...B_ka_k ÎR, где k ³ 0 и B_i ÎN₀, но ни один символ в цепочках a_j (0£ j £ k) не принадлежит N₀, добавим к Р’ продукции вида A®a₀C₁a₁C₂a₂...C_ka_k, где X_i есть или B_i  или  e, не включая в P’ продукцию A®e.

 Если SÎN₀, то включим в P’ продукцию вида S’®e | S, где S’ новый нетерминальный символ и положим N’=NÈS’, в противном случае N’=N, S’=S.

3. Положим G’={N’,T’, P’, S’}.
         АЛГОРИТМ УСТРАНЕНИЯ ЦЕПНЫХ ПРОДУКЦИЙ.
Пусть нам дана e-свободная КС-грамматика G={N,T,P,S}. Получим эквивалентную КС-грамматику G’={N’, T’, P’, S’} свободную от цепных и e-продукций.

Метод состоит в следующем.

1. Для каждого AÎN построим множество N_A={B | A®BÎR} нетерминальных символов, выводимых из А следующим образом:

1.1. Положим N₀={A} и i=1;

1.2. Положим N_i={C | B®CÎR и ВÎN_i-1} È N_i-1;

1.3. Если N_i ¹ N_i-1, то положим i=i+1 и повторим шаг 1.2. В противном случае положим N_A=N.

2. Построим множество P’: если (В®a)ÎR и не является цепной продукцией, то включим в P’ продукцию A®a, для всех таких А, что ВÎN_А.

3. Положим G={N, T, P’,S}.

Данный алгоритм позволяет устранить из грамматики и циклы, т.е. выводы А®A*, где АÎN.
  УСТРАНЕНИЕ В КС-ГРАММАТИКЕ ЛЕВОЙ РЕКУРСИИ.
Алгоритмы синтаксического анализа легче строить тогда, когда КС-грамматика G  не обладает свойствами леворекурсивности, т.е. в ней нет продукций вида X®Ca. Это особенно важно при использовании методов разбора сверху вниз и слева направо. Выбор продукции из множества альтернативных в этих методах базируется на сравнении порождённого крайнего левого символа промежуточной цепочки с текущим символом входной терминальной цепочки. При появлении же в выводе левой рекурсии произойдёт зацикливание. Поэтому при использовании алгоритмов нисходящего разбора левую рекурсию необходимо удалить.

В общем случае левая рекурсия в КС-грамматике может быть явной, когда есть продукции вида A®Aa или неявной- когда в грамматике есть взаимно рекурсивные продукции вида:
                         A®Ba|...
                         B®Ab|...
Устранение леворекурсивных правил. Пусть G КС-грамматика, в которой есть леворекурсивные правила. Эквивалентная грамматика G’ получается путём замены множества леворекурсивных правил грамматики G на множество правил вида:
                     A®b₁A’|b₂A’| ... |b_nA’
                      A’®a₁A’|a₂A’| ... |a_nA|e
Здесь А’- новый вспомогательный нетерминальный символ.
             ДЕТЕРМИНИРОВАННЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ

                                            СВЕРХУ ВНИЗ
В данном синтаксическом анализе  используются LL(1) грамматики, которые являются обобщением S-грамматик.

КС-грамматика называется S-грамматикой, если выполняются условия:

-правая часть каждой продукции начинается терминальным символом;

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

Для заданной S-грамматики магазинный автомат  ( МП-распознаватель) с одним состоянием задаётся следующим образом:

1. А=ТÈ{|-}

2. Г=NÈ{t | tÎT и (А®ta)ÏR}È{#}.

3. Q={q}.

4. z₀={#S | S- аксиома}.

5. q₀=q.

6. Каждой продукции КС-грамматики сопоставляется элемент управляющей таблицы МП-распознавателя. Если продукция имеет вид A®ta, где AÎN и tÎT, а aÎ{NÈT}*, то этому правилу в строке А и в столбце t будут соответствовать операции

                     

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

где a^r - цепочка a, записанная в обратном порядке для того, чтобы удовлетворить соглашения «верхний символ справа».

Если продукция имеет вид А®t, то строке А и столбцу t соответствуют операции
               ЧТЕНИЕ, СДВИГ.
Если магазинным символом является терминал b, то элементом таблицы в строке b будет
                  ЧТЕНИЕ, СДВИГ.
Элементом таблицы, который находится в строке маркера дна магазина # и концевого маркера |-, является
                    ДОПУСТИТЬ.
Все остальные элементы таблицы заполняются операцией
                   ОТВЕРГНУТЬ.
где: А- символы, записанные на входной ленте;

        Г- символы, записанные в магазинную память;

        Q- множество состояний автомата;

         z₀- начальная запись в магазин;

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

Определим  ПЕРВ(a) как множество терминальных символов, которые являются первыми символами цепочек, выводимых из a.

Цепочка a называется аннулирующей, если a®

e.

Продукция грамматики вида А®e также называется аннулирующим.
                        ВЫБОР (А®a)= ПЕРВ(a),
если a - не аннулирующая, и
    ВЫБОР(А®a)=ПЕРВ(a)ÈСЛЕД(А),

если a- аннулирующая цепочка. При этом СЛЕД(А) - множество следующих за А терминалов в промежуточной цепочке, выводимой из S|-, где S-аксиома грамматики.

Для того, чтобы КС-грамматика была типа LL(1), необходимо, чтобы множества выбора для правил с одинаковыми левыми частями не пересекались, т.е.  не имели общих терминальных символов.

Если  для вашей грамматики это так, то она будет относится к типу LL(1) и для неё автомат строится по следующему правилу.
   ПРАВИЛА ОПРЕДЕЛЕНИЯ ДЕТЕРМИНИРОВАННОГО

      МП-РАСПОЗНАВАТЕЛЯ ПО LL(1) ГРАММАТИКЕ.
Для заданной LL(1) грамматики МП-распознаватель задаётся следующим образом:

1. А=ТÈ{|-};

2. Г=NÈ{t | tÎT и (А®ta)ÏR, AÎN, aÎ{NÈT}*}È{#};

3. Q={q};

4. z₀={#S};

5. q₀=q;

6. Управление описывается управляющей таблицей с одним состоянием, строки помечены магазинными символами из Г, столбцы - входными символами из А. Элемент таблицы создаётся для каждой продукции. Если продукция имеет вид А®ta, то этому правилу в строке А и столбце t будут соответствовать операции
                   ЗАМЕНИТЬ(a^r), СДВИГ,
где  a^r - цепочка a, записанная в обратном порядке для того, чтобы удовлетворить соглашению «верхний символ справа»

Если продукция имеет вид А®a, где a=Хb и ХÎN, bÎ{NÈT}*, то ему в строке А и во всех столбцах, принадлежащих множеству ВЫБОР (А®a), будет соответствовать переход
                        ЗАМЕНИТЬ (a^r), ДЕРЖАТЬ.
Когда a=e, вместо ЗАМЕНИТЬ(e) можно использовать ЧТЕНИЕ.

Если продукция имеет вид А®t, то ей в строке А и в столбце t соответствует операция
                            ЧТЕНИЕ. СДВИГ.

7. Если магазинным символом является терминал b, то элементом таблицы в строке b будет

                             ЧТЕНИЕ. СДВИГ.

8. Элементом таблицы, который находится в строке маркера дна # и столбце концевого маркера |-, является
                               ДОПУСТИТЬ.

9. Все остальные элементы таблицы заполняются операцией
                                ОТВЕРГНУТЬ.      
              5. Содержание отчёта.

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

1. Как определяется КС-грамматика?

2. Как определяется нормальная форма Хомского?

3. Как задаётся нормальная форма Грейбах?

4. Как исключить e-продукции?

5. Как устранить недосигаемые символы?

6. Как устранить бесполезные символы?

7. Как устраняются циклические связи в продукциях?

8. Как устранить левые рекурсии в грамматике?

9. Как определяется магазинный автомат?

10. Как определяется LL(1) грамматика?

11. Как определяется S-грамматика?
                  Литература.

1. Компаниец Р.И., Маньков Е.В., Филатов Н.Е. Основы построения трансляторов. -СПб.: КОРОНА принт, 2000. -256 с.

2. Хантер Р. Проектирование и конструирование компиляторов. М.: Финансы и статистика. 1984 г.

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