Карпов - Основы построения трансляторов (2005), страница 37

б.13). По дереву (рис. 6.10) видно, что при восходящем синтаксическом анализе при первой свертке А1 <.== г в соответствии с продукцией 2 грамматики нам еще неизвестно значение атрибута А|.~уре, поэтому мы не можем выполнить действие Адд(г, Е~.~уре) добавления в таблицу имен типа переменной. Далее, Восходящие алгоритмы синтаксического анализа 245 Построить матрицы отношений предшествования для грамматик ббпр и С~б.4 Для грамматики: 5" — +ФЯ~ Я-+а556~аЬ а) построить матрицу отношений предшествования; б) восстановить с помощью матрицы предшествования правый вывод цепочки ЫааЬааоаЬЬЬЯ; в) построить 1 К(0)-анализатор и восстановить правый вывод той же цепочки.

Построить матрицу отношений предшествования для грамматики арифме- тических выражений. Построить матрицу отношений предшествования для грамматики: Я' — ~ФЯФ Я-+аЯ~А ~ Ьс А-+пЯЬ | Ы и провести синтаксический анализ цепочки Ф ааосоаЬсЬЫ Ф Построить для грамматики бб~ Е.К(1)-анализатор, и из него отбрасывани- ем несущественных контекстов и последующим объединением эквива- лентных состояний построить 1 А1 К(1)-анализатор.

Для грамматики: Я-+Аа ~ дАЬ ~ ВЬ ~ ИВи а) построить 1 К(0)-анализатор; б) выделить конфликты и разрешить их нахождением контекстов длины 1 с построением 1.А1.К(1)-анализатора; в) построить 1 К.(1)-анализатор и затем свести его к 1.А1..К(1)-анализатору, минимизировав его. объединяя эквивалентные состояния. (т. е. 6б1 не является 1 К(0)-грамматикой). Построить Я К(1)- и ЕА1.К(1)- анализаторы для этой грамматики. Восстановить правый вывод цепочек Ф[аоо1Ф, Ф[[аЫЫДФ, д[аЬа61Ф, используя 1 А1 К(1)-анализатор этой грам- матики. Глава 6 9. Проверить, что грамматика: А-+а  — СП~ аЕ является Я.Й.(2)-грамматикой.

10. Для грамматики: У-+4Я 5-+ЯВЬ ! е а) построить матрицу предшествования и 1.8.-анализатор; б) провести синтаксический анализ произвольной цепочки языка, порождаемого этой грамматикой. 11. Для грамматик: У-+Я ::': У-+Е: У-+Е 5 — +Е: ::Š— ьТ+Е .: :'Š— ~Е+Т Е вЂ” '~Е+Т: :Š— +Т::: Š— ~Т+Е Е-+Т: ::Т вЂ” '~~:: Š— +Т Т вЂ” «~ построить 1 К-распознаватель. 12. Построить таблицу предшествования и 1 К-распознаватель для грамматики регулярных выражений: Е- Е+Т~ Т Т вЂ” РТЕ~ Р Е- (Е~!Е*!~ 13. При каком 1 грамматика условных операторов: 5-+И'Ь 1Ьеп Яе!ее Я~!И 1'пеп Я~я является 1 К(1)-грамматикой? 14. При каком А. грамматика условных операторов: Я-+ЫЬ 1пеп ЯеЬе Яй ~ ИЬ Феп Ей ~ л является 1.К(1)-грамматикой? 248 22.

~АСУ01~ Покажите, что следующая грамматика является 1 А1.К(1), но не Я.К(1): В Ьа~ЬАс~ис~Ыа ~АСУ01~ Покажите, что следующая грамматика является 1,К(1), но не 1 А1.К(1): Я-+Аа~ЬАс~Вс~ЬВа Рассмотрите следующие грамматики языка, порождающие цепочки языка описания переменных вида г', г, г: геаг или г, г, г, г: т1едег' О. Х) — +Х, г': Т 1.Х, Х,г 2.

А-+е 3. Т вЂ” ип~еуег 4. Т вЂ” и'еаза 4. Т вЂ” ииг~едег 5. Т вЂ” и"еаза 4. Т вЂ” ип1еуег. 5. Т вЂ” ьтеа1 Для этих грамматик: а) определите семантические атрибуты; б) постройте Я.К ( 1)-распознаватель; в) выполните синтаксический анализ с одновременной генерацией семантических действий для цепочек г, г, г: ген и г, г, г, г: нг$едег. Рассмотрите следующие грамматики языка, порождающие двоичные ве- щественные числа: О. Я-+ВЯ : '1.5 — +.

Я 2. А-+АВ 3. Я вЂ” +В 4.  — +О 5.  — +1 :': 5. В-+О 6.  — +1 О. Я вЂ” +Х,.А 1. Х,-+ВХ, 2. Х,— +я 3. А-+ВЯ 4. Я-+е 5. В-+О 6.  — +1 : О.Π— +Е: Т 1. Х,— +Х,1 г 2. Х,1 — + Х,1, г' ::: 3. Х,1-+е : 0.5 — эХ.Я 1. Х вЂ” + Х,В . 2.Х,— +я 4. Я вЂ” + е : О. Х)-+Х,: Т : :"1.Х,— и Е1 2.

Х,1 — >, гХ,1 3. Х,1-+е Восходящие алгоритмы синтаксического анализа Для этих грамматик: а) определите семантические атрибуты для вычисления числового значения цепочек языка; б) постройте Я.К(1)-распознаватель; в) выполните синтаксический анализ с одновременной генерацией семантических действий для цепочек 100.01 и .0110. 26. Построить |.А1.К(2)-грамматику, не являющуюся 1 А1 К(1)-грамматикой.

27. Построить 1 К(2)-грамматику, не являющуюся 1.К(1)-грамматикой. 28. Покажите, что грамматика Я вЂ” эата ~ я не является 1.К(1)-грамматикой при любом к, и в то же время эта грамматика не является двусмысленной. 29. Покажите, что грамматика: Я-+А = Р ~ А А — +*А~ а А — +1. является 1.А1.К(1)-, но не Я К(1)-грамматикой.

30. Определите, к каким классам ~1.К(0), Я К(1), 1А1.К(1) или 1 К(1)~ принадлежат следующие грамматики построением соответствующих распознавателей: Я +Аа ~сИЬ ~ сЬ ~ Дса:: Я вЂ” +Аа ~ с1АЬ ~ ВЬ ~ ИВп.:: .5 — +Аа ! с1АЬ ~ ВЬ ~ ~Иа ~ с А-+с : А — >с А-+с В-+с :  — +с Универсальные методы синтаксического анализа 253 ПРИМЕР?.1. Пусть дана простая грамматика арифметических выражений: ~7.1 ° '~ +~Е~ к- ь~т~т т- т Р~р Р— +а Построим множества ситуаций для алгоритма Зрли на примере анализа це- почки Ф а+а Ф (рис.

7.1). Рис. 7.1. Множества ситуаций для алгоритма Эрли успешно применено, и из нетерминала А, начиная с шага д, выведена цепочка, совпадающая с подцепочкой а, а„~ а„,2 ... а;. в соответствии с правилом А — +а, т. е. формально, А ==> а ==>* а а,~ ... а,. Поэтому в множестве ситуаций Мч завер~иатель ищет ситуацию <А — +еа; д>, и для каждой ситуации < — +уеАр; ю>, которая является родительской для <А — +еа; а>, в М он добавляет новую ситуацию <В-+уАер; 5>. Это свидетельство того, что во входной цепочке подстрока а,. а,, ~ ... а, может быть выведена из начальной части правила для нетерминала В„а именно В ==> уАр ==* а, а,+~ ...

а,р. С каждым множеством ситуаций М, все три оператора работают до тех пор, пока в М и в М ~ не могут появиться новые ситуации. Очевидно, что входная цепочка будет распознана (т. е. она является цепочкой языка, порождаемой данной грамматикой), если в заключительном множестве ситуаций (после последнего символа входной строки) встретится ситуация вида <У вЂ” +Фее; 0>.

Покажем построение множеств ситуаций на примере. Глава 7 Рассмотрим, как строятся множества ситуаций. П Мо. Начальное множество ситуаций включает только ситуацию <5" — +еФБ~'„ 0>, которая говорит о том, что до прихода первого символа в нулевой позиции мы ожидаем цепочку, порожденную из цепочки ФЕЮ из начального символа У.

Применим все возможные операции, которые выполняются считывателелг, ггредсказапгелем и завергиагггелем, к Мо. Считыватель добавляет в следующее множество М| ситуацию <У-+ФРЕЮ; 0>. Больше ни одного из трех операторов к множеству Мо применить нельзя. П Мг.

Это множество ситуаций вначале будет включать ситуацию <У вЂ” +ФеЕФ; 0>, полученную из Мо. Иредсказагггель добавит сюда еще пять ситуаций следующим очевидным образом. Поскольку в ситуации <У-+ФЛЕР; 0> указатель оказался перед нетерминалом Е, сюда добавляются ситуации <Š— +еЕ+Т; 1> и <Е-+еТ; 1>, которые говорят о том, что с первой позиции (после первого терминала входной строки) мы ожидаем цепочку, порожденную из Е по правилу Š— +Е+Т либо по правилу Š— +Т.

Остальные три ситуации добавляются повторным применением ггредсказателя. Считыватель добавляет в следующее множество М2 ситуацию <Р-+ае; 1>. На этом построение и обработка множества М~ завершается. П М~, Множество М2 будет включать ситуацию <Р— +ае; 1>, полученную из М1 счигггывателем со сдвигом метки положения за встреченный терминал а, поскольку а — очередной входной символ. Теперь операция завершения заставляет добавить в М2 ситуацию <Т вЂ” +Ре; 1>.

Дальнейшее рекурсивное применение этой операции заставляет добавить в М. .еще четыре ситуации <Š— ~Та; 1>, <Т вЂ” +Те*Р; 1>, <Š— +Ее+Т; 1> и <5' — +ФЕед; О>. Ни в одной ситуации в М2 метка не стоит перед нетерминалом, поэтому ггредсказатель не работает. Считыватель добавляет в следую|цее множество Мз ситуацию <Š— +Е+еТ; 1>. На этом построение и обработка множества М2 завершается. Множества Мз — М5 строятся аналогично. На рис. 7.1 все ситуации связаны указателями.

Указатель от ситуации Кг к ситуации К~ проводится в случае, если К~ порождена из Кг любым из указанных трех операторов: либо ггредсказапгелел~, либо считывате.гем, либо завершагггелем из Кг. Очевидно, что часть ситуаций в построенных множествах несущественные — например, в множестве М4 это <Š— +Ее+Т; 1> и <Т вЂ” ьа Т'"Р; 3>, которые не приводят к завершающимся ситуациям вида <А — +ае; к>. Последовательное выбрасывание таких ситуаций приводит к связному списку существенных ситуаций рис. 7.2. Восстановление дерева вывода входной цепочки выполняется в алгоритме Эрли после построения всех множеств ситуаций, если последнее множество содержит ситуацию <У-+Фее; О». Дерево вывода легко восстанавливается Универсальные методы синтаксического анализа 255 по списку существенных ситуаций. На рис. 7.3 мы строим такое дерево для примера 7.1.