А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 70
Текст из файла (страница 70)
При четвертом проходе распространения не происходит, и окончательное множество предпросмотров показано в последнем столбце на рис. 4.47. Обратите внимание, что конфликт "перенос1свертка", обнаруженный в примере 4.34 при использовании БЕК-метода, исчезает при использовании ЕАг.К- технологии. Причина в том, что с Л вЂ” 1,. в 1з связан только предпросмотр 5, так что нег конфликта с переносом =, генерируемым пунктом о — 1. = Л из 1з. о 4.7.6 Уплотнение таблиц ЕК-анализа Грамматика типичного языка программирования с 50-100 терминалами и 100 продукциями может иметь таблицу ЬАЕК-анализа с несколькими сотнями состояний. Функция АСТ10Х может легко иметь 20 000 записей, каждая из которых требует минимум 8 бит.
Очевидно, что немаловажной задачей является поиск более эффективного, по сравнению с двумерной таблицей, представления информации. В этом разделе будут вкратце рассмотрены некоторые технологии, используемые для сжатия полей АСТ1ОХ и ООТО таблицы ВК-анализа, збо Глава 4. Синтаксический анализ Одна из таких технологий уплотнения части АСТ)ОН таблицы основана на том, что обычно в таблице многие строки идентичны. Так, на рис.
4.42 состояния О и 3 имеют одинаковые записи действий; то же самое можно сказать и о состояниях 2 и 6. Следовательно, память можно сэкономить (ценой небольшого повышения времени работы), создавая указатель в одномерный массив для каждого состояния. Указатели для состояний с одними и теми же действиями указывают на одно и то же место. Для получения информации из этого массива присвоим каждому терминалу номер — от нуля до числа, на единицу меньшего количества терминалов, и используем затем это целое число как смещение от значения указателя для каждого состояния.
Для данного состояния действие синтаксического анализа для г-го терминала представляет собой ю'-ю запись после той, на которую указывает упомянутый указатель для данного состояния. Дальнейшее повышение эффективности использования памяти достигается путем создания списка действий для каждого состояния. Список состоит из пар (терминальный символ, действие). Наиболее часто встречающиеся действия для данного состояния могут быть размещены в конце списка; в списке можно использовать специальный терминал "любой", который означает, что если в списке не найден текущий входной символ, то действие синтаксического анализатора выполняется независимо от входного символа.
Кроме того, записи ошибок можно для единообразия заменить записями сверток — это не повлияет на выявление ошибок, а просто отложит его до использования переноса. Пример 4.49. Рассмотрим таблицу синтаксического анализа на рис. 4.37. Начнем с того, что заметим, что действия для состояний О, 4, 6 и 7 совпадают. Мы можем представить их в виде списка: СимВОл Дййствик любой ошибка Состояние 1 имеет похожий список: асс любой ошибка В состоянии 2 мы можем заменить записи ошибок действием г2, так что для любого символа, кроме *, будет выполняться свертка по продукции 2.
г2 любой 351 4.7. Более мощные ЕЕ-анализаторы Состояние 3 имеет только записи ошибок и свертки г4, поэтому можем заменить первые записи последними, и список для состояния 3 будет содержать только одну пару — (любой, г4). Состояния 5, 10 и ! 1 могут рассматриваться аналогично. Список для состояния 8 представляет собой ошибка любой а список для состояния 9— любой г1 Мы можем закодировать в список и таблицу оото, но более эффективный путь состоит в создании списка пар для каждого нетерминала А. Каждая пара в списке для А имеет вид (текущее состояние, следующее состояние), указывающий, что ООТО !текущее состояние, А~ = следующее состояние Такой способ предпочтительнее по той причине, что обычно в одном столбце таблицы оото имеется только небольшое количество состояний.
Это связано с тем, что сото для нетерминала А может быть только состоянием, порождаемым из множества пунктов, в котором у некоторых пунктов символ А расположен непосредственно слева от точки. Ни одно множество не имеет пунктов с Х и 3' непосредственно слева от точки, если Х ~ 'г'. Следовательно, каждое состояние появляется не более чем в одном столбце таблицы переходов. Для еше большей экономии памяти заметим, что к записям ошибок в таблице сото никогда не производится обращений. Такую запись можно заменить наиболее часто встречающейся неошибочной записью в том же столбце.
Эта запись становится записью по умолчанию и представляется в списке одной парой со специальным текущим сосгоянием "любое". Пример 4.50. Вновь рассмотрим рис. 4.37. Столбец Р имеет запись 10 для состояния 7, а все остальные записи — либо 3, либо "ошибка". Мы можем заменить ошибку третьим состоянием и создать для столбца г следующий список: ТЕКУЩЕЕ СОСТОЯНИЕ СЛЕДУЮЩЕЕ СОСТОЯНИЕ 1О любое 352 Глава 4. Синтаксический анализ Аналогично список для столбца Т представляет собой любое Для столбца Е можно выбрать в качестве значения по умолчанию либо 1, либо 8; в любом случае необходимы две записи. Например, можно создать для столбца Е следующий список: любое Экономия памяти в этих маленьких примерах слишком мала.
Если читатель подсчитает число записей в списках, созданных в этом и предыдущем примерах, а затем добавит указатели от состояний в списки действий и указатели от нетерминалов в списки следующих состояний, то экономия памяти по сравнению с матричной реализацией на рис. 4.37 не произведет на него особого впечатления.
В реальных же грамматиках память, необходимая для представления в виде списков, обычно составляет менее !ОУо от памяти, требуемой для матричного представления. Следует также отметить, что методы сжатия таблиц конечных автоматов, рассмотренные в разделе 3.9.8, могут использоваться н для представления таблиц 1.К-анализа. 4.7.7 Упражнения к разделу 4.7 Упражнение 4.7.1. Постройте для грамматики Я вЂ” Я 5+ ~ Я Я* ~ а из упражнения 4.2.1 следующие множества пунктов: а) каноническое 1.К.; б) 1.А1.К. Упражнение 4.7.2. Повторите упражнение 4.7.
! для каждой из (расширенных) грамматик из упражнений 4.2.2, а — ж. ! Упражнение 4.7.3. Воспользуйтесь алгоритмом 4.47 для вычисления набора ЬАЬК-множеств пунктов на основе ядер ЬК(0)-множеств пунктов для грамматики из упражнения 4.7.!. ! Упражнение 4.7.4. Покажите, что грамматика Я вЂ” ~ Аа)ЬАс)дс(Ьда А — д принадлежит классу 1.А1.К(1), но не 8ЬК(1). 353 4.8. Использование неоднозначных грамматик ! Упражнение 4.7.5. Покажите, что грамматика Я вЂ” ~ Аа)ЬАс(Вс)6Ва А принадлежит классу 1.К (1), но не 1.А1.К (1). 4.8 Использование неоднозначных грамматик Тот факт, что каждая неоднозначная грамматика не может быть 1.К-грамматикой и, следовательно, не может относиться ни к одному из рассмотренных ранее классов грамматик, является доказанной теоремой.
Ряд типов неоднозначных грамматик, однако, вполне пригоден для определения и реализации языков, как мы увидим в этом разделе. Для языковых конструкций наподобие арифметических выражений неоднозначные грамматики обеспечивают более краткую и естественную спецификацию по сравнению с эквивалентными однозначными грамматиками. Другое использование неоднозначных грамматик состоит в выделении распространенных синтаксических конструкций для специализированной оптимизации. Имея неоднозначную грамматику, можно определить специализированные конструкции путем аккуратного добавления в грамматику новых продукций. Следует особо отметить, что, хотя используемые грамматики являются неоднозначными, во всех случаях задаются специальные правила разрешения неоднозначности, обеспечивающие для каждого предложения только одно дерево разбора.
В этом смысле полное описание языка остается однозначным, так что иногда оказывается возможной разработка 1 К-анализатора, который следует тем же правилам разрешения неоднозначности. Подчеркнем также, что неоднозначные конструкции должны использоваться как можно реже и предельно аккуратно; в противном случае нет никакой гарантии, что синтаксический анализатор распознает соответствующий язык. 4.8.1 Использование приоритетов и ассоциативности для разрешения конфликтов Рассмотрим неоднозначную грамматику (4.3) для выражений с операторами + и * (здесь она повторена для удобства читателя): Š— Е+ Е ~ Е* Е ! (Е) ~ Ы Данная грамматика неоднозначна, поскольку не определяет ассоциативность нлн приоритет операторов ~- и ~. Однозначная грамматика (4.1), включающая продукции Š— Е + Т и Т вЂ” Т * Е, генерирует тот же язык, но придает оператору ~ 354 Глава 4. Синтаксический анализ низший приоритет по сравнению с оператором * и делает оба оператора левоассоциативными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
