Файл: Отчеты оформляются в виде файлов формата Microsoft Word (файлы других форматов не принимаются), размер шрифта 1214.docx

11. 
    LALR(1)-грамматики и автоматы
    

Рассмотренный в предыдущем разделе метод построения восходящего синтаксического акцептора можно модифицировать, используя вместо канонических так называемые расширенные конфигурации. Расширенной называется конфигурация, с которой связано некоторое множество символов ожидаемого правого контекста:

N :  ▼  , {t₁, t₂, … t_k}.

В отличие от канонических две расширенные конфигурации, имеющие одинаковое маркированное правило и разные множества символов ожидаемого правого контекста, могут быть объединены в одну конфигурацию путем слияния ОПК:

N :  ▼  , {t₁} и N :  ▼  , {t₂} эквивалентны N :  ▼  , {t₁, t₂}.

1. 
   Сформулируем две разных технологии построения таблицы расширенных конфигураций. Согласно одной технологии должно быть выполнено следующее. Строится таблица канонических конфигураций как в разделе 3.3.9.
   
2. 
   Просматриваются множества конфигураций каждого состояния. Если в них обнаруживаются пары конфигураций с одинаковым маркированным правилом, то каждая такая пара заменяется одной расширенной конфигурацией с объединенным ожидаемым правым контекстом. Если одна из конфигураций пары являлась базовой, то базовой должна быть и конфигурация, полученная в результате объединения пары конфигураций. Если изменилось множество символов ОПК какой-либо базовой конфигурации (обозначим ее К_исх), то пересчитываются ожидаемые правые контексты всех ее дочерних конфигураций, т.е. таких, для которых К_исх является родительской либо при выполнении замыкании, либо при образовании другой базы. Процедура пересчета должна продолжаться рекурсивно до тех пор, пока фиксируются изменения ожидаемого правого контекста дочерних конфигураций.
   
3. 
   Просматриваются все возможные пары состояний. Если два состояния имеют одинаковые (по маркированным правилам) наборы базовых расширенных конфигураций, то эти состояния сливаются, ожидаемые правые контексты пар всех конфигураций с одинаковым маркированным правилом объединяются. При слиянии состояний одно из них удаляется, но в оставшемся состоянии должна быть сохранена информация о том, откуда образовалось удаляемое состояние, т. е. содержимое колонок «Из» и «Через». Затем, если изменилось множество символов ОПК какой-либо базовой конфигурации (обозначим ее К_исх), то пересчитываются ожидаемые правые контексты всех ее дочерних конфигураций, т. е. таких, для которых К_исх является родительской либо при выполнении замыкания, либо при образовании другой базы. Процедура пересчета должна продолжаться рекурсивно до тех пор, пока фиксируются изменения ожидаемого правого контекста дочерних конфигураций.
   

---

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

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

Вторая технология заключается в следующем:

1. 
   Базой нулевого состояния является конфигурация вида
   

Z : ▼S ► , {►},

где S – начальный нетерминал грамматики; ► – псевдотерминал «конец файла».

2. 
   При формировании замыкания каждая вновь построенная расширенная конфигурация добавляется к множеству конфигураций данного состояния, если в этом множестве еще нет конфигурации с точно таким же маркированным правилом. Если же в множестве конфигураций состояния уже есть конфигурация с точно таким же маркированным правилом (обозначим ее К_исх), то ее множество символов ожидаемого правого контекста объединяется с ОПК новой конфигурации. Если ожидаемый правый контекст конфигурации К_исх изменился в результате объединения, то пересчитываются ожидаемые правые контексты всех тех конфигураций, для которых конфигурация К_исх является родительской как при формировании новой базы, так и при замыкании множеств конфигураций. Процедура пересчета должна продолжаться рекурсивно до тех пор, пока не перестанут изменяться ожидаемые правые контексты дочерних конфигураций.
   
3. 
   При формировании базы новое состояние образуется, если нет ни одного состояния с точно таким же (по маркированным правилам) базовым набором расширенных конфигураций. Если же существует такое состояние то новое состояние не формируется. Вместо этого объединяются множества ОПК одинаковых по маркированным правилам базовых конфигураций. Если при этом изменился ожидаемый правый контекст какой-либо базовой конфигурации, то должны быть пересчитаны ОПК всех ее дочерних конфигураций. Процедуру пересчета следует продолжать рекурсивно до тех пор, пока не перестанут изменяться ожидаемые правые контексты дочерних конфигураций.
   

---

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

При использовании расширенных конфигураций для предупреждения конфликтов используется тот же самый способ формирования базовых конфигураций состояний автомата, что и в случае формирования таблицы простых конфигураций. Поэтому размеры управляющей таблицы для любой грамматики будут одинаковы как при использовании расширенных конфигураций, так и без вычисления ожидаемого правого контекста. Грамматики, для которых удается построить детерминированный восходящий синтаксический акцептор с использованием расширенных конфигураций, называются LALR(1)-грам­матиками.

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

4. 
   Порядок выполнения работы (рекомендуется использовать в качестве примера систему правил Samples/Sample5):
   

1. 
   Завершить разработку грамматику языка, заданного на курсовую работу. Грамматика должна определять программы, включающие несколько функций.
   
2. 
   Используя пакет ВебТрансБилдер и полную грамматику своего языка:
   

• 
  построить табличную реализацию восходящего синтаксического анализатора, найти в программном коде парсера управляющую таблицу автомата, и его программную модель, описать в отчете эти фрагменты кода парсера;
  
• 
  построить процедурную реализацию восходящего синтаксического анализатора, сравнить текст построенного программного модуля с кодом табличного парсера, описать результаты сравнения в отчете;
  
• 
  изучить структуру таблицы канонических и таблицы расширенных конфигураций (пункты меню «Показать/Канонические конфигурации» и «Показать/Расширенные конфигурации»), описать на примерах операций Go, Shift и Reduce (по одной, взятой произвольным образом из управляющей таблицы) связь этих таблиц с управляющей таблицей восходящего парсера;
  
• 
  выявить конфликты типов «сдвиг–свертка» и «свертка–свертка», разрешенные и, возможно, не разрешенные преобразователем, описать способы разрешения конфликтов.
  

---

1. 
   Выполнить трассировку процессов нисходящего синтаксического акцепта, включая флажок показа истории работы при запуске транслятора на тестирование. Изучить по историям работы поведение всех построенных синтаксических акцепторов при разборе как правильных предложений, так и предложений с намеренно внесенными синтаксическими ошибками. Описать фрагменты этих историй, включающие не менее, чем по одной операции Go, Shift и Reduce.
   
2. 
   Проанализировать и сравнить между собой все полученные тексты программ и результаты выполнения пункта 4.2. Оценить степень пригодности изученных вариантов реализации нисходящих синтаксических акцепторов для выполнения курсовой работы. Отразить в заключении к отчету результат анализа и оценки.
   
3. 
   Подготовить, сдать и защитить отчет к лабораторной работе.
   

5. 
   Требования к содержанию отчета.
   

Отчет должен содержать:

• 
  цель работы;
  
• 
  фрагменты кода процедурной реализации восходящего и управляющей таблицы автоматной реализации восходящего синтаксического акцептора, описание структур данных и алгоритмов работы этих реализаций;
  
• 
  фрагменты историй работы процедурной и автоматной реализаций восходящего синтаксического акцептора для правильного и ошибочного тестовых примеров с объяснением принципов работы акцепторов;
  
• 
  выводы и заключение.
  

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

1. 
   Что хранится в стеке восходящего парсера?
   
2. 
   Что такое операция перехода восходящего парсера?
   
3. 
   Если грамматика относится к классу SLR(1), то можно ли по ней построить нисходящий синтаксический акцептор?
   
4. 
   Перечислите все знаки операций восходящего синтаксического акцептора, объясните назначение их полей (параметров).
   
5. 
   Постройте историю работы восходящего синтаксического акцептора при разборе цепочки: (((x)))
   
6. 
   Что такое конфигурация?
   
7. 
   Напишите LR-грамматику для условного оператора С-подобного языка, имеющего и полную и сокращенную форму.
   
8. 
   Какие грамматики относятся к классу LALR(1)?
   
9. 
   Что такое конфликт «сдвиг/свертка»?
   
10. 
    Как таблица конфигураций преобразуется в управляющую таблицу восходящего синтаксического акцептора?
    
11. 
    Что такое ожидаемый правый контекст?
    
12. 
    Что делает восходящий автомат при выполнении операции свертки?
    
13. 
    Что такое детерминированное (безвозвратное) восстановление дерева грамматического разбора?
    
14. 
    Как вычисляется ожидаемый правый контекст конфигурации?
    
15. 
    Опишите технологию разработки процедурной реализации восходящего синтаксического акцептора.
    
16. 
    Как выполняется операция сдвига?
    
17. 
    Что такое LR(1)-грамматика?
    
18. 
    Что такое конфликт «свертка/свертка»?
    
19. 
    Перечислите все операции восходящего синтаксического акцептора.
    
20. 
    Чем различаются понятия расширенной и канонической расширенной конфигурации?
    
21. 
    Как используются множества последователей нетерминалов для предупреждения конфликтов при построении управляющей таблицы восходящего синтаксического акцептора по SLR(1)-грамматике?
    
22. 
    Разработайте LR-грамматику для оператора переключателя (switch) С-подобного языка.
    

---

---