А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 69
Текст из файла (страница 69)
Таким образом, ЬАЬК-анализатор изменит содержимое стека на 0 36 36 89 344 Глава 4. Синтаксический анализ Действие в состоянии 89 для входного символа 3 — свертка С вЂ” сС, после чего содержимое стека приобретает вид 0 36 89 После этого та же свертка выполняется повторно, что приводит к содержимому стека 0 2 Наконец, мы обнаруживаем ошибку в соответствии с записью Асткзн для состо- яния 2 и входного символа 3.
4.7.5 Эффективное построение таблиц ЕАЕК-анализа Имеется несколько изменений, которые можно внести в алгоритм 4.43, чтобы избежать построения полного набора множеств 1.К(1)-пунктов в процессе создания таблицы 1 А1.К (1)-анализа. ° Можно представить любое множество 1.К(0)- или 1.К(1)-пунктов 1 его ядром, т.е, теми пунктами, которые либо являются начальным пунктом (ф' — 5) или [о' — о, 3]), либо содержат точку не в начале тела продукции.
° Можно построить ядра 1.АЬК(1)-пунктов на основе ядер 1.В. (0)-пунктов при помощи процесса распространения и спонтанной генерации символов предпросмотра, который будет описан ниже. ° Если имеются ядра ЬАЬК(1), то можно сгенерировать ЬАЬК(1)-таблицу путем замыкания каждого ядра с использованием функции СЬОЗЫКЕ из рис. 4.40, а затем вычислить записи таблицы при помощи алгоритма 4.40, как если бы ЬАЬК(1)-множества пунктов были каноническими ЬК(1)- множествами пунктов. Пример 4.45.
Используем в качестве примера метода эффективного построения ЬА1.К (1)-таблицы грамматику из примера 4.34, не являющуюся Я.К-грамматикой, которую мы повторим здесь в расширенном виде: У вЂ” Я 3 — Ь=Н(В Ь вЂ” *В) Ы В вЂ” Л Полные множества ЬК(0)-пунктов для этой грамматики были приведены на рис. 4.39. Ядра этих пунктов показаны на рис. 4.44. н 345 4.7.
Более мощные ЕК-анализаторы 15 ° 1' ' н~' 16 ° 17: 19 . В 1,. 1з: 19: 14: Рис. 4.44. Ядра множеств ЬК (О)-пунхтов для грамматики (4.15) Теперь для создания ядер множеств КРАЕК(1)-пунктов требуется назначить корректные предпросматриваемые символы ЕК (О)-пунктам ядер. Есть два способа, которыми предпросматриваемый символ Ь может быть назначен ЕК (О)-пункту  — 7 б из некоторого множества КРАЕК (1)-пунктов,1. 1. Существует множество пунктов 1 с базисным пунктом А - ы )3, а, 1 = = 00тО (1, Х), и построение аото (сьояжн (([А — а,у, аЦ), Х) содержит [ — -~ б,Д безотносительно к а, как показано на рис. 4.40.
Такой символ Ь называется спонтанно (зропгапеопз!у) сгенерированным В 76. 2. В качестве частного случая предпросматриваемый символ 3 спонтанно генерируется для пункта У вЂ” В в начальном множестве пунктов. 3. Как и в случае 1, но а = Ь и, как показано на рис.
4.40, бОтО(О.Очке(([А — ~ а . Д, 6[)), Х) содержит [ — у 6, 6) только потому, что одним из связанных с А — а )3 предпросматриваемых символов является Ь. В этом случае мы говорим о распространении (ргорацаге) символа предпросмотра от А — о )3 в ядре 1 к  — 7 д в ядре 1. Заметим, что распространение не зависит от конкретного символа предпросмотра; либо все символы предпросмотра распространяются от одного пункта к другому, либо ни один из них.
Глава 4. Синтаксический анализ 346 Нам требуется определить спонтанно генерируемые символы предпросмотра для каждого множества 1.К (0)-пунктов, а также определить, для каких пунктов происходит распространение предпросмотров и нз каких именно пунктов. Это достаточно просто. Пусть № — символ, отсутствующий в рассматриваемой грамматике, и пусть А — а Д вЂ” ядро 1.К(0)-пункта в множестве 1.
Для каждого Х вычислим 1 = сото(сьояже(((А — гг )З,№])), Х). Для каждого базисного пункта в 1 проверим его множество символов предпросмотра. Если № является символом предпросмотра, то предпросмотры распространяются к этому пункту ог А — а .
(э. Все прочие предпросмотры генерируются спонтанно. Эти идеи строго изложены в приведенном далее алгоритме, который, кроме того, использует тот факт, что толью в базисных пункгах .1 точка непосредственно следует за Х, так что они должны иметь внд  — уХ . б. Алгоритм 4.46. Определение предпросмотров Вход: ядро К множества 1.К(0)-пунктов 1 и символ грамматики Х. Выход: спонтанно генерируемые пунктами из 1 предпросмотры для базисных пунктов в оото(1,Х), а также пункты из 1, от которых предпросмотры распространяются к базисным пунктам в сото (1, .Х). МЕтод: алгоритм, показанный на рис. 4.45. о аког( каждый пункт А- а 13 из К) ( 1:= свяжи(((А — а.
11,№])) ); И(]В- у Хба]я,Уиа~№) Заключаем, что символ предпросмотра а спонтанно генерируется для пункта  — уХ . б в оото (1, Х); Ы ( [ — -у Хб, №] Е 1 ) Заключаем, что символы предпросмотра распространяются от А — а (3 из 1 к  — уХ . б в сото (1, Х); Рис. 4.45. Выявление спонтанно генерируемых н распространяемых предпросмотров Теперь мы готовы к назначению предпросмотров ядрам множеств ЕК (О)-пунктов для формирования множеств ЕАЕК(1)-пунктов.
Мы знаем, что 3 является символом предпросмотра для У вЂ” 5 в исходном множестве 1.К (О)-пунктов. Алпэритм 4.46 дает нам все спонтанно генерируемые символы предпросмотра. После того как будут перечислены все такие символы предпросмотра, мы должны позволить им распространяться до тех пор, пока не останется ни одного возможного распространения. Существует много различных подходов, которые в определенном смысле отслеживают "новые" символы предпросмотра, которые распространились на некоторый пункт, но пока что не распространились далее. Приведенный 347 4.7, Более мощные ЬК-анализаторы далее алгоритм описывает один из возможных методов распространения символов предпросмотра на все пункты.
Алгоритм 4.47. Эффективное вычисление ядер наборов множеств ЬАЬК(1)- пунктов Вход: расширенная грамматика С'. Выход: ядра наборов множеств ЬА1.К(1)-пунктов для грамматики С'. МБтод: выполним следующие действия. 1. Построим ядра множеств ЬК (О)-пунктов для С. Если количество используемой памяти не является главным, то простейший метод состоит в построении ЬК(0) множеств пунктов, как в разделе 4.6.2, с последующим удалением пунктов, не являющихся базисными. Если же память ограничена, то вместо этого можно сохранять для каждого множества только базисные пункты и вычислять Сото для множества пунктов 1, сначала вычисляя замыкание 1. 2.
Применим алгоритм 4.46 к ядру каждого множества ЬК (О)-пунктов и грамматическому символу Х, чтобы определить, какие символы предпросмотра спонтанно генерируются для базисных пунктов в оото(1, Х) и из каких пунктов 1 символы предпросмотра распространяются на базисные пункты сото(1, Х). 3. Инициализируем таблицу, которая для каждого базисного пункта в каждом множестве пунктов дает связанные с ними предпросмотры. Изначально с каждым пунктом связаны только те предпросмотры, которые в п.
2 определены как сгенерированные спонтанно. 4. Повторим проходы по базисным пунктам во всех множествах. При посещении пункта 1 мы с помощью таблицы, построенной в п. 2, ищем базисные пункты, на которые 1 распространяет свои предпросмотры. Текущее множество предпросмотров для 1 добавляется к множествам, связанным с каждым из пунктов, на которые 1 распространяет свои предпросмотры. Мы продолжаем выполнять такие проходы по базисным пунктам до тех пор, пока не останется новых предпросмотров для распространения. и Пример 4.48. Построим ядра ЬАЬК (1)-пунктов для грамматики из примера 4.45. Ядра ЬК (О)-пунктов были показаны на рис.
4.44. Применяя алгоритм 4.46 к ядру множества пунктов 1ш мы сначала вычисляем сьоя7ке([[У вЂ” ~ 5', ф[)), которое представляет собой 348 Глава 4. Синтаксический анализ Среди пунктов в этом замыкании имеются два, у которых символ предпросмотра = генерируется спонтанно. Первый из них — Ь вЂ” * В. Этот пункт, у которого справа от точки находится *, приводит к ~1 — * 1г, =], т.е. = — спонтанно сгенерированный символ предпросмотра для Ь вЂ” * 1ь, представляющего собой множество пунктов 14.
Аналогично [1, — Ы, =) говорит нам о том, что =— спонтанно сгенерированный символ предпросмотра для Ь вЂ” Ы из 1ь. Поскольку № является символом предпросмотра для всех шести пунктов в замыкании, мы определяем, что пункг У вЂ” Я в 1с распространяет символы пред- просмотра на следующие шесть пунктов: Б'- 5. В11 5- 1 =ЛВ12 — 11 В1з Ь вЂ” ~я ВВ14 Ь вЂ” ~И1 В 15 11 - 1 В 1г Рнс. 4.46. Распространение символов предпросмотра На рис. 4.47 показаны шаги 3 н 4 алгоритма 4.47.
Столбец "Изначально" указывает спонтанно сгенерированные символы предпросмотра для каждого базисного пункта. Здесь только два раза встречается рассмотренный ранее символ = н спонтанно сгенерированный символ предпросмотра 8 для начального пункта У- Я. 349 4.7. Более мошные БК-аналнзаторы Рис. 4.47. Вычисление символов прелпросмотра При первом проходе предпросмотр 5 распространяется от У вЂ” о в 1о к шести пунктам, перечисленным на рис. 4.46. Предпросмотр = распространяется от Ь вЂ” * В в 1з к пунктам Š— *В. в 1т и к  — Ь в 1в. Кроме того, он также распространяется к самому себе и к С вЂ” !й из 1з, но зти предпросмотры уже есть. При втором и третьем проходах единственный распространяемый предпросмотр — 3 (находится для 1г и 14 при втором проходе и для 1е — при третьем).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
