А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 65
Текст из файла (страница 65)
4.38. Для ясности показана также последовательность Пример 4.31. На рис. 4.37 показаны функции Астюм и сото из таблицы БК- анализа грамматики выражений (4.1), повторенной ниже с пронумерованными продукциями: Глава 4. Синтаксический анализ 322 Рис. 4.37. Таблица синтаксического анализа для грамматики выражений грамматических символов, соответствующая хранящимся в стеке состояниям. Например, в строке (1) 1.К-анализатор находится в состоянии О, начальном состоянии без грамматических символов, и с Ы в качестве первого входного символа. Действие в строке О и столбце Ы поля АСТ10Х на рис.
4.37 — а5; оно означает перенос и внесение в стек состояния 5. В строке (2) выполняется внесение в стек символа состояния 5 и удаление Ы из входного потока. После этого текущим входным символом становится *; действие для состояния 5 и входного символа * — свертка согласно продукции à — !д. Со стека при этом снимается один символ состояния, и на вершине стека появляется состояние О. Поскольку ООтО [О, г') равно а3, в стек вносится состояние 3. При этом получается конфигурация, показанная в строке (3). Остальные строки на рис.
4.38 получены аналогично. и 4.6.4 Построение таблиц Я.К-анализа Я.К-метод построения таблиц синтаксического анализа — хорошее начало для изучения 1.К-анализа. Далее таблицы синтаксического анализа, построенные этим методом, будут именоваться Я.К-таблицами, а 1,К-анализатор, использующий ВЕК-таблицы, — Я.К-анализатором. Два других метода расширяют Я.К- метод путем информации, получаемой предпросмотром входной строки.
323 4.6. Введение в ЬК-анализ: простой 1.К ДЕЙСТВИЕ Вход СТЕК СИМВОЛЫ Е- и Т вЂ” ~ŠŠ— ~Ы Т вЂ” ~ Т*Е Е- Т Е- Ы Т- Г Е- Е+Т Рис. 4.38. Действия ЕК-анализатора лля строки 14 * Ы -Е Ы Я.К-метод начинается с (.К(0)-пунктов и ЬК(0)-автомата, с которыми вы познакомились в разделе 4.5, т.е. для данной грамматики С мы строим ее расширение С' с новым стартовым символом У. Для С' строится канонический набор С множеств пунктов С' вместе с функцией ОотО.
Затем строятся записи Аст!Ом и оото в таблице синтаксического анализа с использованием следующего алгоритма, который требует от нас знания еоееов (А) для каждого нетерминала А грамматики (см. раздел 4.4). Алгоритм 4.32. Построение таблицы Б(.К-анализа Вход: расширенная грамматика С'. Выход: функции таблицы Я).К-анализа лет!о!ч и Оото для грамматики С'. МЕтОд: выполняем следующие действия. 1. Строим С = (1о, 1ы .,,, 1„) — набор множеств 1.К (0)-пунктов для С'.
2. Из 1; строим состояние!. Действие синтаксического анализа для состояния 1 определяем следующим образом. а) Если (А — о а)3!е1, и оото(1„а) = 1, то устанавливаем Аст!Он (г', а) равным "перенос з". Здесь а должно быть терминалом. (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) (14) 0 05 03 02 027 0275 0 2 7 1О 02 01 016 0165 0163 0169 О1 и Т Тя Тки Т*Е Т Е Е+ е+и Е+Г Е+Т Е и* и+Ы3 ни+ Ы8 *и+ Ы8 *ы+ Ы8 ы+ Ы8 +Ы8 +Ы3 +Ы3 +Ы8 Ы3 3 3 3 8 Перенос Свертка по Свертка по Перенос Перенос Свертка по Свертка по Свертка по Перенос Перенос Свертка по Свертка по Свертка по Принятие 324 Глава 4. Синтаксический анализ б) Если [А — гг ] е 1„то устанавливаем лст~он [1,а] равным "свертка А — гг" для всех а из гоы.оту (А); здесь А не должно быть равно У.
в) Если [У вЂ” о ]е1;,то устанавливаем лст1о1ч[1,8] равным "принятие". Прн наличии любого конфликта между действиями, возникшего в результате применения указанных правил, делается вывод о том, что грамматика не принадлежит классу БЬК (1). В таком случае алгоритм не может построить синтаксический анализатор для данной грамматики. 3.
Переходы для состояния 1 строим для всех нетерминалов А с использованием следующего правила: если оото (1;, А) = 1, то оото [1, А] = 1. 4. Все записи, не определенные правилами 2 и 3, получают значение "ошибка". 5. Начальное состояние синтаксического анализатора строим из множества пунктов, содержащего [У вЂ” о].
о Таблица синтаксического анализа, состоящая из функций АСТ1ОХ и бОТО, определенных при помощи алгоритма 4.32, называется Я.К(1)-табяицейС. 1.К- анализатор с использованием бЬК(1)-таблицы для С называется Я.К(1)-анализатором С, а грамматика, имеющая Я.К(1)-таблицу, называется ВЬК(1)-граиматикой.
Обычно в БЬК(1) опускается (1), идущее после БЬК, поскольку мы не работаем с синтаксическими анализаторами, предпросматривающими более одного символа. Пример 4.33. Построим Я.К-таблицу для расширенной грамматики выражений. Канонический набор множеств 1.К (О)-пунктов для этой грамматики был показан на рис. 4.31.
Сначала рассмотрим множество пунктов 1о. Е' — .ŠŠ— Е + Т Е вЂ” Т Т Т*Г Т вЂ” à à — .(Е) à — Ы Пункт à — (Е) приводит к записи лст1он[0,(] = перенос 4, а пункт à — ~ и1 — к записи лст~он [О,Ы! = перенос 5. Прочие пункты в 1с действий не дают. Теперь рассмотрим пункты 1~. Е' — Е.
Е-Е+Т 325 4.6. Введение в 1.К-анализ: простой ЬК Первый пункт дает Асторы [1, $] = принятие, а второй — Асйом [1, +] = перенос 6. Теперь очередь Тз.' Š— Т. Т вЂ” Т хЕ Поскольку го~.ьоук (Е) = ($, +, ) ), первый пункт приводит к лстю1ч [2, $] = Астюи [2, +] = Астюи [2, )] = свертка Š— Т. Второй пункт дает Астюы [2,*] = перенос 7. Продолжая работу таким образом, мы получим таблицы Астюм и сзото, показанные на рис. 4.31. На этом рисунке номера продукций в свертках те же, что и порядок, в котором они находятся в исходной грамматике (4.1), т.е. продукция Е х Е+ Т имеет номер 1, Š— Т— номер 2 и т.д. и Пример 4.34.
Каждая Я.К(1)-грамматика однозначна, однако имеется множе- ство однозначных грамматик, не принадлежащих классу $1К(1). Рассмотрим грамматику с продукциями Я вЂ” А=В]В Ь вЂ” х *В ]!й  — ~ Ь (4.! 5) в Как и в разделе 2.8.3, Ьзначение описывает ячейку памяти, а т-значение — значение, хранящееся в втой ячейке.
Е н В можно рассматривать как 1- и г-значение соответственно, а * — как оператор "содержимое".8 Канонический набор множеств 1.К (0) пунктов для грамматики (4.15) показан на рис. 4.39. Рассмотрим множество пунктов Тз. Первый пункт в этом множестве приводит к тому, что Аст1ои [2, =] становится равным "перенос б". Поскольку роы.оту (В) содержит = (чтобы увидеть, что это так, рассмотрите порождение Я =а Е =а В =~ хВ = В), второй пункт устанавливает запись Астю1ч [2, =] равной "свертка  — Ь".
Поскольку в записи Астюи [2, =] одновременно оказываются и перенос, и свертка, прн входном символе = в состоянии 2 наблюдается конфликт "перенос!свертка". Грамматика (4.15) не является неоднозначной. Этот конфликт "перенос/свертка" возникает из того факта, что метод построения БЕК-анализатора не достаточно мощный для запоминания достаточного левого контекста для принятия решения о том, какое действие должно быть предпринято синтаксическим анализатором для входного символа = при наличии строки, свертываемой в Ь. Канонический метод и ЬА1.К-метод, которые мы рассмотрим далее, успешно работают с ббльшим З2б Глава 4. Синтаксический анализ 15 ° 1' + гй' 1о: Я- .А=В 16 ° Н- Ь 1з.
У- Я 1т . 1 — *ге. 1в: Л- 12 '  — Ь. 19 ° Рис. 4.39. Канонический 1.К (О)-набор для грамматики (4.15) набором грамматик, включая грамматику (4.15). Заметим, однако, что существуют такие однозначные грамматики, для которых любой метод построения ЕК- анализатора приводит к таблице действий с наличием конфликтов. К счастью, при разработке реальных языков программирования таких грамматик можно избежать. а 4.6.5 Активные префиксы Почему ЕК (О)-автоматы могут использоваться при принятии решений "перенос/свертка" ? 1.К(0)-автомат для грамматики характеризует строки грамматических символов, которые могут находиться в стеке ПС-анализатора грамматики.
Содержимое стека должно быть префиксом правосентенциальной формы. Если в стеке хранится гт, а оставшаяся часть входной строки — х, то последовательность сверток должна привести гтх в Я. В терминах порождений Я =ь сгх. 1 тП Однако в стеке могут находиться не все префиксы правосентенциальных форм, поскольку синтаксический анализатор не должен выполнять перенос после осно- 327 4.6. Введение в 1.К-анализ: простой ЬК вы. Предположим, например, Е =~ Г *!6 =~ (Е) * И Тогда в разные моменты времени в процессе синтаксического анализа в стеке хранятся (, (Е и (Е), но в нем не должно находиться (Е)~, поскольку (Е) является основой, которую синтаксический анализатор должен свернуть в Е до того, как выполнит перенос *.
Префиксы правосентенциальных форм, которые могут находиться в стеке ПС- анализатора, называются активными префиксами (иаЫе ргебхез). Они определяются следующим образом: активный префикс является префиксом правосентенциальной формы, не выходяшим за пределы правого конца крайней справа основы сентенциальной формы. В соответствии с этим определением к концу активного префикса всегда можно добавить терминальные символы для получения правосентенциальной формы. Я.К-анализ основан на том факте, что ЬК(0)-автомат распознает активные префиксы.
Мы говорим, что пункт А — Д . (Зз допустим (ча1Ы) для активного префикса оД, если существует порождение У =~* ггАю =~ аД,Ззш. Вообще гт тт говоря, пункт может быть допустимым для многих активных префиксов. Тот факт, что А — Д~ Дз допустим для аД, многое говорит нам о том, что именно следует выбрать — перенос или свертку — при обнаружении оД в стеке. В частности, если 1)з у'= г, то это предполагает, что основа еше не полностью перенесена в стек и очередное действие анализатора — перенос.
Если Дз = г, то А — ,3~ — основа, и мы должны выполнить свертку в соответствии с этой продукцией. Конечно, два допустимых пункта могут указать на разные действия для одного и того же активного префикса. Одни из этих конфликтов могут быть разрешены путем просмотра очередного входного символа, а другие придется разрешать специальными методами, описанными в разделе 4.8.
Однако не следует считать, что при применении (.й-метода для построения таблицы синтаксического анализа произвольной грамматики могут быть разрешены все конфликты. Можно легко вычислить множество допустимых пунктов для каждого активного префикса, который может появиться в стеке 1.й-анализатора. Основная теорема теории Ьй-анализа гласит, что множество допустимых пунктов для активного префикса 7 в точности равно множеству пунктов, достижимых в (.К (О)-автомате для данной грамматики из начального состояния по пути, помеченному 7. По сути, множество допустимых пунктов содержит в себе всю полезную информацию, которая может быть собрана из стека. Поскольку в этой книге мы не доказываем данную теорему, приведем соответствующий пример.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
