-
LALR(1)-грамматики и автоматы
Рассмотренный в предыдущем разделе метод построения восходящего синтаксического акцептора можно модифицировать, используя вместо канонических так называемые расширенные конфигурации. Расширенной называется конфигурация, с которой связано некоторое множество символов ожидаемого правого контекста:
N : ▼ , {
t1,
t2, …
tk}.
В отличие от канонических две расширенные конфигурации, имеющие одинаковое маркированное правило и разные множества символов ожидаемого правого контекста, могут быть объединены в одну конфигурацию путем слияния ОПК:
N : ▼ , {
t1} и
N : ▼ , {
t2} эквивалентны
N : ▼ , {
t1,
t2}.
-
Сформулируем две разных технологии построения таблицы расширенных конфигураций. Согласно одной технологии должно быть выполнено следующее. Строится таблица канонических конфигураций как в разделе 3.3.9.
-
Просматриваются множества конфигураций каждого состояния. Если в них обнаруживаются пары конфигураций с одинаковым маркированным правилом, то каждая такая пара заменяется одной расширенной конфигурацией с объединенным ожидаемым правым контекстом. Если одна из конфигураций пары являлась базовой, то базовой должна быть и конфигурация, полученная в результате объединения пары конфигураций. Если изменилось множество символов ОПК какой-либо базовой конфигурации (обозначим ее Кисх), то пересчитываются ожидаемые правые контексты всех ее дочерних конфигураций, т.е. таких, для которых Кисх является родительской либо при выполнении замыкании, либо при образовании другой базы. Процедура пересчета должна продолжаться рекурсивно до тех пор, пока фиксируются изменения ожидаемого правого контекста дочерних конфигураций.
-
Просматриваются все возможные пары состояний. Если два состояния имеют одинаковые (по маркированным правилам) наборы базовых расширенных конфигураций, то эти состояния сливаются, ожидаемые правые контексты пар всех конфигураций с одинаковым маркированным правилом объединяются. При слиянии состояний одно из них удаляется, но в оставшемся состоянии должна быть сохранена информация о том, откуда образовалось удаляемое состояние, т. е. содержимое колонок «Из» и «Через». Затем, если изменилось множество символов ОПК какой-либо базовой конфигурации (обозначим ее Кисх), то пересчитываются ожидаемые правые контексты всех ее дочерних конфигураций, т. е. таких, для которых Кисх является родительской либо при выполнении замыкания, либо при образовании другой базы. Процедура пересчета должна продолжаться рекурсивно до тех пор, пока фиксируются изменения ожидаемого правого контекста дочерних конфигураций.
Перед слиянием каждой пары состояний можно проверять, не приведет ли это слияние к конфликту, которого не было в исходной таблице канонических конфигураций. Просматриваются пересечения множеств символов ОПК всех возможных пар конфигураций, первая из которых принадлежит одному состоянию, а вторая – другому. Если пересечение не пусто, и конфигурации требуют свертки по разным правилам, то состояния слиянию не подлежат. Далее, если одна из конфигураций требует сдвига по терминалу, принадлежащему ожидаемому правому контексту другой конфигурации, то выполнять слияние состояний не следует.
Согласно такой технологии строятся восходящие синтаксические акцепторы в учебном пакете автоматизации проектирования трансляторов ВебTрансБилдер.Вторая технология заключается в следующем:
-
Базой нулевого состояния является конфигурация вида
Z : ▼
S ► , {►},
где S – начальный нетерминал грамматики; ► – псевдотерминал «конец файла». -
При формировании замыкания каждая вновь построенная расширенная конфигурация добавляется к множеству конфигураций данного состояния, если в этом множестве еще нет конфигурации с точно таким же маркированным правилом. Если же в множестве конфигураций состояния уже есть конфигурация с точно таким же маркированным правилом (обозначим ее Кисх), то ее множество символов ожидаемого правого контекста объединяется с ОПК новой конфигурации. Если ожидаемый правый контекст конфигурации Кисх изменился в результате объединения, то пересчитываются ожидаемые правые контексты всех тех конфигураций, для которых конфигурация Кисх является родительской как при формировании новой базы, так и при замыкании множеств конфигураций. Процедура пересчета должна продолжаться рекурсивно до тех пор, пока не перестанут изменяться ожидаемые правые контексты дочерних конфигураций.
-
При формировании базы новое состояние образуется, если нет ни одного состояния с точно таким же (по маркированным правилам) базовым набором расширенных конфигураций. Если же существует такое состояние то новое состояние не формируется. Вместо этого объединяются множества ОПК одинаковых по маркированным правилам базовых конфигураций. Если при этом изменился ожидаемый правый контекст какой-либо базовой конфигурации, то должны быть пересчитаны ОПК всех ее дочерних конфигураций. Процедуру пересчета следует продолжать рекурсивно до тех пор, пока не перестанут изменяться ожидаемые правые контексты дочерних конфигураций.
Обе технологии требуют выполнения большого объема вычислений при пересчете ожидаемых правых контекстов.
При использовании расширенных конфигураций для предупреждения конфликтов используется тот же самый способ формирования базовых конфигураций состояний автомата, что и в случае формирования таблицы простых конфигураций. Поэтому размеры управляющей таблицы для любой грамматики будут одинаковы как при использовании расширенных конфигураций, так и без вычисления ожидаемого правого контекста. Грамматики, для которых удается построить детерминированный восходящий синтаксический акцептор с использованием расширенных конфигураций, называются LALR(1)-грамматиками.Класс
LALR(1)-грамматик более широк, чем класс
SLR(1), однако существуют языки (в том числе практически все известные языки программирования), для которых не может быть найдена порождающая
LALR(1)-грамматика. В то же время доказано, что для любого детерминированного контекстно-свободного языка существует хотя бы одна порождающая
LR(1)-грамматика. Тем не менее задача нахождения грамматики требуемого класса, даже если известно, что она должна существовать для данного языка, алгоритмически неразрешима.
-
Порядок выполнения работы (рекомендуется использовать в качестве примера систему правил Samples/Sample5):
-
Завершить разработку грамматику языка, заданного на курсовую работу. Грамматика должна определять программы, включающие несколько функций.
-
Используя пакет ВебТрансБилдер и полную грамматику своего языка:
-
построить табличную реализацию восходящего синтаксического анализатора, найти в программном коде парсера управляющую таблицу автомата, и его программную модель, описать в отчете эти фрагменты кода парсера;
-
построить процедурную реализацию восходящего синтаксического анализатора, сравнить текст построенного программного модуля с кодом табличного парсера, описать результаты сравнения в отчете;
-
изучить структуру таблицы канонических и таблицы расширенных конфигураций (пункты меню «Показать/Канонические конфигурации» и «Показать/Расширенные конфигурации»), описать на примерах операций Go, Shift и Reduce (по одной, взятой произвольным образом из управляющей таблицы) связь этих таблиц с управляющей таблицей восходящего парсера;
-
выявить конфликты типов «сдвиг–свертка» и «свертка–свертка», разрешенные и, возможно, не разрешенные преобразователем, описать способы разрешения конфликтов.