А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 63
Текст из файла (страница 63)
Следовательно, продукция А — ХУл, дает четыре пункта: А — .ХУЯ А — Х УУ А — ХУ Х А — ХУл,. Продукция А — е генерирует единственный пункт А— Интуитивно, пункт указывает, какую часть продукции мы уже просмотрели в данной точке в процессе синтаксического анализа. Например, пункт А — ХУУ 5 В русскоязычной литературе иногда использовался термин "ситуация". — Прим, лер. 312 Глава 4. Синтаксический анализ указывает, что во входном потоке мы ожидаем встретить строку, порождаемую ХУЯ. Пункт А — Х УЯ указывает, что нами уже просмотрена строка, порожденная Х, и мы ожидаем получить из входного потока строку, порождаемую УЯ. Пункт А — ХУЯ говорит о том, что уже обнаружено тело Хг'Я и что, возможно, пришло время свернуть ХУЯ в А. Один набор множеств 1.К(0)-пунктов, именуемый каноническим набором ЕК(0), обеспечивает основу для построения детерминированного юнечного автомата, который используется для принятия решений в процессе синтаксичесюго анализа.
Такой автомат называется 1.К(0)-автоиатомв. В частности, каждое состояние 1.К (О)-автомата представляет множество пунктов в каноническом наборе 1.К(0). Автомат для грамматики выражений (4.1), показанный на рис. 4.31, будет служить в качестве примера при рассмотрении каноничесюго ЕК (О)-набора грамматики. Для построения канонического 1 К(0)-набора мы определяем расширенную грамматику и две функции, с~.овца и пото. Если С вЂ” грамматика со стартовым символом 5, то расширенная грамманзика С' представляет собой С с новым стартовым символом У и продукцией У вЂ” Я. Назначение этой новой стартовой продукции — указать синтаксическому анализатору, когда следует прекратить анализ и сообщить о принятии входной строки; т.е. принятие осуществляется тогда и только тогда, когда синтаксический анализатор выполняет свертку с использованием продукции У вЂ” Я.
Замыкание множеств пунктов Если 1 — множество пунктов грамматики С, то сьозцкк(1) представляет собой множество пунктов, построенное из 1 согласно двум правилам. 1. Изначально в с~.ояля(1) добавляются все пункты из 1. 2. Если А — о ВД входит в с~ оязке (1), а  — у является продукцией, то в СЬОьпйй (1) добавляется пункт  — у, если его там еще нет. Это правило применяется до тех пор, пока не останется пунктов, которые могут быть добавлены в сьозгзке (1). Интуитивно А — гт В)3 в с~.опаля(1) указывает, что в некоторой точке процесса синтаксического анализа мы полагаем, что далее во входной строке мы можем встретить подстроку, порождаемую из ВД. Подстрока, порождаемая из ВД, будет иметь префикс, порождаемый из В путем применения одной из В- продукций.
Таким образом, мы добавляем пункты для всех В-продукций; т.е. если  — у является продукцией, то мы включаем  — у в сьозцкп (1). 'Технически автомат не является детерминированным по определению из раздела 3.6.4, поскольку не имеет тупикового состояния, соответствующего пустому множеству пунктов. В результате существует некоторое количество пвр "состояние — входной символ", для которых отсутствует следующее состояние.
4.В Ввелсние в ! К-анализ: нрос1ей ~ К 314 Глава 4. Синтаксический анализ Пример 4.26. Рассмотрим следуюшую расширенную грамматику выражений. Е' ŠŠ— Е+Т~Т Т вЂ” Т*г !г Š— (Е) 1Ы Если 1 — множество из одного пункта (1Е' — Е!), то сьозцкн(1) содержит множество пунктов 1о на рис. 4.31. Рассмотрим, как вычисляется замыкание. Е' — Е помещается в сьояян (1) согласно правилу (1). Поскольку непосредственно справа от точки находится Е, мы добавляем Е-продукции с точками на левом конце: Š— Е+ Т н Е- Т.
Теперь справа от точки в последней продукции находится Т, так что следует добавить Т вЂ” Т * Е и Т вЂ” Е. Далее, Е справа от точки заставляет добавить Š— (Е) и Š— Ы, и больше никакие другие пункты не добавляются. о Замыкание может быть вычислено так, как показано на рис. 4.32. Удобный способ реализации функции с)олиге состоит в поддержании булева массива асЫеИ, индексированного нетерминалами Г", так что агЫеЫ (В~ устанавливается равным ггпе, если и когда мы добавляем пункт  — "у для каждой В-продукции В— Яе1ОП[ешз сьозкпн(1) ( ,1 = 1; гереат Гог ( каждый пункт А — о . ВВ из,1 ) Гог ( каждая продукция  — у из С ) 1Г(В- "уневходитв1) Добавить  — 3 в,1; ппт1! больше нет пунктов для добавления в,1 за один проход; гегпгп 1; Рис. 4.32.
Вычисление сьоапкь Заметим, что если одна В-продукция добавляется в замыкание 1 с точкой на левом конце, то в замыкание будут аналогичным образом добавлены все В- продукции. Следовательно, при некоторых условиях нет необходимости в перечислении пунктов  — т, добавленных в 1 при помощи функции сьОЯ!кн; достаточно списка нетерминалов В, продукции которых были добавлены таким образом. Разделим множество интересующих нас пунктов на два класса. ! . Базисные пункты, или пункты ядра (кегле! !!етз): начальный пункт У вЂ” .Я н все пункты, у которых точки расположены не у левого края. 315 4.6.
Введение в 1.К-анализ: простой 1.К 2. Небпзисные (попкегпе1) пункты, у которых точки расположены слева, за исключением У вЂ” Я. Кроме того, каждое множество интересующих нас пунктов формируется как замыкание множества базисных пунктов; добавляемые в замыкание пункты не могут быть базисными. Таким образом, мы можем представить множества интересующих нас пунктов с использованием очень небольшого объема памяти, если отбросим все небазисные пункты, зная, что они могут быть восстановлены процессом замыкания. На рис. 4.31 небазисные пункты размещаются в заштрихованных частях прямоугольников состояний.
Функция СОТО Второй полезной функцией является аото(1,Х), где 1 — множество пунктов, а Х вЂ” грамматический символ. аото(1,Х) определяется как замыкание множества всех пунктов 1А — оХ 13), таких, что 1А — а ХД находится в 1. Интуитивно функция сото используется для определения переходов в 1.й(0)- автомате грамматики. Состояния автомата соответствуют множествам пунктов, и сото (1, Х) указывает переход из состояния 1 при входном символе Х. Пример 4.27. Если 1 — множество из двух пунктов, ~1Е' — Е ~1, 1Š— Е +Т)), то 00то (1, +) содержит пункты Š— Е+ Т т - Т*Е Т вЂ” ŠР— (Е) Š— 1п 00то (1, +) вычисляется путем рассмотрения пунктов 1, в которых + следует непосредственно за точкой.
Е' — Е таким пунктом не является, но таковым является пункт Š— Е +Т. Поэтому мы переносим точку за ~-, получая пункт Š— Е+ Т, а затем находим замыкание этого множества из одного элемента. и Теперь мы готовы к построению канонического набора С множеств 1.К(0)- пунктов для расширенной грамматики С'. Соответствующий алгоритм показан на рис.
4.33. Пример 4.28. Канонический набор множеств 1 К (О)-пунктов для грамматики (4.1) и функция бОТО показаны на рис. 4.31. Значения бОТО представлены на схеме переходами между состояниями. Б 31б Глава 4. Синтаксический анализ то!д Ыевз(С') ( С = (се0яже (([Ь вЂ” ~ . з[))); гереа! !ог ( каждое множество пунктов Г в С ) Гог ( каждый грамматический символ Х ) 1Г ( множество 00т0 (Г, Х) не пустое и не входит в С ) Добавить аото (Г, Х) в С; пп!11 нет новых множеств пунктов для добавления в С за один проход; Рис.
4.33. Вычисление канонического набора множеств 1.К (0)-пунктов Использование ЬК(0)-автомата Основная идея, лежащая в основе "простого ЬК", или БЬК, синтаксического анализа заключается в построении 1.К (0)-автомата для заданной грамматики. Состояниями этого автомата являются множества пунктов из канонического набора 1.К (0), а переходы определяются функцией 00т0. ЬК (0)-автомат для грамматики выражений (4.1) показан на рис.
4.31. Стартовое состояние 1.К (0)-автомата — сьояжн (([Я' — Я[)), где Я' — стартовый символ расширенной грамматики. Все состояния являются принимающими. Под состоянием 1 далее подразумевается состояние, соответствующее множеству пунктов 1 . Каким образом ЬК (О)-автомат помогает в принятии решения "перенос/свертка"? Это решение может быть принято следующим образом. Предположим, что строка у из символов грамматики переводит ЬК (0)-автомат из состояния 0 в некоторое состояние 1. Тогда выполним перенос очередного входного символа а, если состояние з имеет переход для данного символа а.
В противном случае выбирается свертка; пункт в состоянии 3 говорит нам, какую продукцию следует для этого использовать. Алгоритм ЬК-анализа, приведенный в разделе 4.6.3, использует стек для отслеживания как состояний, так и символов грамматики; фактически символы грамматики могут быть восстановлены из состояний, так что стек хранит только состояния. Приведенный далее пример показывает, каким образом 1.К(0)-автомат и стек могут использоваться для принятия решения "перенос/свертка" в процессе синтаксического анализа. Пример 429.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
