А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 67
Текст из файла (страница 67)
Подытоживая обе воз1т можности, мы говорим, что Ь может быть любым терминалом в ршзт (Дах), где "Возможны прсдпросмотры длиной более 1, однако здесь мы ик нс рассматриваем. 4.7. Более мощные ЬК-анализаторы БесОйсешз сьОЯ7ке (1) ( гереас Гог ( каждый пункт [А — о В)З,а] из 1) Гог ( каждая продукция  — у из С' ) !ог ( каждый терминал Ь Е Р!Квт (С)сс) ) Добавить [ — 'у, Ь] в множество 1; ппС!! нет больше пунктов для добавления в 1; геспгп 1; БесОПсешз аото(1, Х) ( Инициализировать 1 пустым множеством; Гог ( каждый пункт [А — сг Х)3,а] из 1) Добавить пункт [А — оХ - )3, а] в множество 1; гетпгп СЬОяЛси (1); то!с! Дели (С') ( Инициализировать С множеством (сьоЯжЕ(([У вЂ” .В, 3]))); гереас Гог ( каждое множество пунктов 1 в С ) Гог ( каждый символ грамматики Х ) !Г ( бото (1, Х) не пустое множество и не входит в С ) Добавить оото (1, Х) в С; ппс!! нет новых множеств пунктов для добавления в С; Рис.
4,40. Построение множеств 1.К (1)-пунктов лля грамматики С' йкзт — функция из раздела 4.4. Заметим, что х не может содержать первый терминал нз Ьу, так что Рскзт ()Зах) = Рскзт (Да). Приведем теперь метод построения множеств ЬК (1)-пунктов. Алгоритм 4.38. Построение множеств 1.К (1)-пунктов Вход: расширенная грамматика С'. Выход: множества ЬК (1)-пунктов, которые представляют собой множество пунктов, допустимых для одного или нескольких активных префиксов С'.
МБтОд: процедуры СЬОЗС7КБ и СОто и основная подпрограмма йенса для построения множеств пунктов были приведены на рис. 4.40. о 334 Глава 4. Синтаксический анализ Пример 4.39. Рассмотрим следующую расширенную грамматику: У вЂ” 5 Я вЂ” СС С вЂ” с С[й (4.16) то: В-" В,З Я- СС3 С вЂ” ~ сС, с/д С вЂ” й, с/д Для удобства записи здесь опущены квадратные скобки, а запись [С вЂ” сС, сЯ представляет собой сокращенную запись двух пунктов — [С вЂ” сС, с] и [С вЂ” сС,И).
Теперь вычислим сото(То, Х) для различных значений Х. Для Х = Я мы должны вычислить замыкание пункта [У вЂ” 5, 3]. Никакие дополнительные замыкания невозможны, поскольку точка располагается крайней справа. Таким образом, мы получаем следующее множество пунктов; 11: У вЂ” "Я 3 Для Х = С вычисляем замыкание ф — С С,З]. Добавляем С-продукции со вторым компонентом 3, после чего не можем добавить ничего более и, таким образом, получаем Тз: В С СЗ С вЂ” .сС,З С вЂ” .0,3 Начнем с вычисления замыкания ([У вЂ” .Я,З)).
В процедуре СЬОЗОКЕ мы сопоставляем пункт [У вЂ” 5,3) с пунктом [А — а Вд,а), т.е. А = 5', о = г, В = 5, (1 = г и а = 8. Функция сюзикн говорит нам, что следует добавить пункт [ — у, Ь] для каждой продукции  — т и терминала Ь из нкзт (13а). В терминах рассматриваемой грамматики  — г должно быть Я вЂ” С С, а поскольку (3 равно е, а а равно 3, Ь может быть толью 3.
Таким образом, мы добавляем [Я вЂ” .СС, 8). Продолжим вычисление замыкания путем добавления всех пунктов [С вЂ” т, Ь] для Ь из нкзт(СЗ), т.е. сопоставляя [Я вЂ” СС,З] с [А — а В13,а) и получая А = Я, о = г, В = С, (3 = С и и = 8. Поскольку С не порождает пустой строки, нкзт(СЗ) = нкзт(С), а поскольку нкзт(С) содержит терминалы с и с~, мы добавляем пункты [С- сС,с), [С- сС,д], [С- 0,с) и [С- с~,д]. Ни один из новых пунктов не имеет нетерминала непосредственно справа от точки, так что первое множество 1.К (1)-пунктов завершено.
Начальное множество пунктов представляет собой 335 4.7. Более мощные ЬК-анализаторы Далее положим Х = с. Теперь надо выполнить замыкание ([С вЂ” с С,сЯ). Добавляем С-продукции со вторым компонентом с/й, что дает 1з. С- с С,с/й С вЂ” сС, с/д С вЂ” д, с/О Наконец, полагая Х = г~, получаем множество пунктов Этим завершается рассмотрение сото для 1д.
Из 1~ новые множества не получа- ются, но зато 1з имеет переходы для С, с и г~. Для сото (1з, С) получаем Для него не требуется замыкания. Чтобы вычислить сото(1з, с), берем замыкание ([С вЂ” с С,З[) и получаем 1а. С- с С,8 С сС8 С- .Ы,3 Заметим, что 1а отличается от 1з только вторыми компонентами. Мы увидим, что это достаточно распространенное явление, когда несколько различных множеств ЕК (1)-пунктов грамматики имеют одни и те же первые компоненты и отличаются друг от друга своими вторыми компонентами.
При построении наборов множеств ЕК (О)-пунктов для той же самой грамматики каждое множество ЕК (О)-пунктов совпадает с множеством первых компонентов одного или нескольких множеств ЕК(1)-пунктов. На этом явлении мы более подробно остановимся позже, при рассмотрении 1.А1.К-анализа. Продолжая вычисление функции сото для 1з, получаем, что сото (1з, Н) имеет вид Перейдем теперь к 1з. Значениями функции 0070 для 1з при входных символах с и д являются соответственно 1з и 14, а сото (1з, С) равна 1з .
С вЂ” сС, с/д 14 и 1з не имеют функций бото, поскольку все пункты в них содержат точки в крайнем положении справа. Значения йото для 1а при входных символах с и й равны соответственно 1а и 17, а СОТО (1а, С) равна 336 Глава 4. Синтаксический анализ Остальные множества пунктов не дают значений ООТО, так что наша работа завершена. На рис. 4.41 показаны найденные десять множеств пунктов и их переходы. а Рис.
4.41. Граф бОТО лля грамматики (4.16) 4.7.3 Канонические таблицы 1.К(1)-анализа Теперь приведем правила построения 1.К(1)-функций АСТ10Х и 00ТО из множеств ).К(1)-пунктов. Эти функции, как и ранее, представлены таблицей. Единственное отличие — в значениях записей таблицы. Алгоритм 4.40. Построение таблиц канонического 1.К-анализа Вход: расширенная грамматика С'. Выход: таблица канонического 1.К-анализа с функциями АСТ10М и ООТО для грамматики С'. 337 4.7. Более мощные ЬК-анализаторы МвтОд: выполнить следующие действия. 1.
Построить С' = (1е,1ы,,., 1„) — набор множеств ЬК(1)-пунктов для С'. 2. Состояние синтаксического анализатора строится из 1,. Действие синтаксического анализа для состояния 1 определяется следующим образом. а) Если [А — а а,З,Ь] входит в 1; и оото(1;,а) = 1, установить ястыком [1, а] равным "перенос 7". Здесь а должно быть терминалом. б) Если [А - она] входит в 1; и А Ф У, то установить яством [в,а] равным "свертка А — о".
в) Если [У вЂ” Я, 8] входит в 1„установить яств [1, Э] равным "приня- тие". Если при применении указанных правил обнаруживаются конфликтующие действия, грамматика не принадлежит классу ЬК (1). 3. Переходы для состояния 1 строятся для всех нетерминалов А с использо- ванием следующего правила: если сото (1„А) = 1, то сото [1, А] = ~'. 4. Все записи, не определенные правилами (2) и (3), считаются записями "ошибка".
5. Начальное состояние синтаксического анализатора — состояние, построенное из множества пунктов, содержащего [У вЂ” Я, Э]. и Таблица, образованная функциями действий и переходов, полученными при помощи алгоритма 4.40, называется канонической таблицей ЬК (1)-анализа. ЬК- анализатор, использующий эту таблицу, называется каноническим ЬК (1)-синтаксическим анализатором.
Если функция действий синтаксического анализа не имеет многократно определенных записей, то соответствующая грамматика называется 1.К (1)-граммагликой. Как и ранее, (1) опускается везде, где оно очевидно из контекста. Пример 4.41. Каноническая таблица синтаксического анализа для грамматики (4.16) показана на рис. 4.42. Продукциями 1, 2 и 3 являются соответственно продукции Я - С С, С - с С и С - 0. и Каждая БЬК(1)-грамматика является ЬК(1)-грамматикой, но канонический 1.К-анализатор для БЬК(1)-грамматики может иметь большее количество состояний, чем БЬК-анализатор для той же грамматики. Грамматика из предыдущего примера является БЬК-грамматикой и имеет Я.К-анализатор с семью состояниями (сравните с десятью состояниями на рис.
4.42). 338 Глава 4. Синтаксический анализ Рис. 4.42. Каноническая таблица синтаксического анализа для грамматики (4.16) 4.7.4 Построение ЕА1.К-таблиц синтаксического анализа Перейдем к последнему из рассматриваемых нами методов построения синтаксических анализаторов, а именно — к методу !.АЬК (ЬЯ с предпросмотром— !соха!1еаг) !.К).
Этот метод часто используется на практике из-за того, что получаемые при его использовании таблицы получаются сравнительно небольшими по сравнению с каноническими ЕК-таблицами, а также поскольку большинство распространенных синтаксических конструкций языков программирования могут быть легко выражены ).А).К-грамматикой. Практически то же самое можно сказать и о Я.К-грамматиках, но в этом случае имеется несколько конструкций, которые не могут быть легко обработаны при помощи метода Б).К (см., в частности, пример 4.34).
Сравнивая размеры синтаксических анализаторов, можно сказать, что Я.К- и ).А).К-таблицы для грамматики почти всегда имеют одно и то же количество состояний, и это количество обычно составляет несколько сотен состояний для 339 4.7. Более мощные ЕК-анализаторы языков наподобие С'о. Каноническая ЕК-таблица для языка такого типа обычно содержит несколько тысяч состояний. Таким образом, построить БЕК- или ЕАИ.- таблицы существенно проще и экономичнее, чем канонические ЕК-таблицы. В качестве введения обратимся вновь к грамматике (4.16), множества ЕК (1)- пунктов которой были приведены на рис.
4.41. Возьмем пару похожих состояний, таких как 14 и 17. Эти состояния содержат только пункты с первым компонентом С вЂ” и . В 14 предпросматриваемыми символами могут быть с и с(, а в 17— только 3. Чтобы увидеть разницу между 14 и 17 в синтаксическом анализаторе, обратите внимание, что грамматика (4.16) порождает регулярный язык с*г)с*п. При считывании входного потока сс . с!(сс ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
