А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 68
Текст из файла (страница 68)
сс( синтаксический анализатор переносит первую группу символов с и следующий за ними с( в стек, попадая после считывания символа г( в состояние 4. Затем синтаксический анализатор вызывает свертку по продукции С вЂ” г(, обусловленную следующим входным символом с или с!. Требование, чтобы следующим входным символом был с или г(, имеет смысл, поскольку это символы, с которых может начинаться строка с*44. Если после первого г( следует 3, то получается входной поток наподобие ссг(, который не принадлежит рассматриваемому языку, и состояние 4 совершенно справедливо обнаруживает ошибку при очередном входном символе Б.
В состояние 7 синтаксический анализатор попадает после чтения второго г(. Соответственно, синтаксический анализатор должен обнаружить во входном по- "Вот некоторые сравнительные характеристики реальных языков программирования. КоличестВо Токены ПРодукций (непустъъх) Язык ТЕРМИНАЛЪ| КЛЮЧЕВЫЕ СЛОВА Для ознакомления со сравнительным анализом различных языков программирования можно обра- титься к книге Свердлов С.З.Языки программирования и методы трансляции: Учебное пособие.
СПбз Питер, 2007. — 638 с. — Прим. ред. А18о1-60 Рааса! Моди!а-2 Ада 95 ТпгЬо Рааса! 6.0 Ое!рЬ! 7.0 С (Кбга) С99 С-н-(Страуструп, 1990) С-н- (180ЛЕС 14882-1998) 1ача С№ 890 1004 887 2999 1479 2041 913 1413 1654 2292 1813 3036 102(90) 109(85) 70(69) 327(258) 141(117) 186(165) 52(49) 110(106) 124(117) 176(166) 172(158) 295(268) 88 84 88 98 89 92 122 133 131 136 121 115 24 35 39 69 55 107 27 37 48 63 48 88 340 Глава 4. Синтаксический анализ токе символ 3, иначе входная строка не соответствует регулярному выражению с'пс*п.
Таким образом, состояние 7 должно приводить к свертке С вЂ” о при входном символе 3 и к ошибке при входном символе с или и'. Заменим теперь состояния 1» и 1т состоянием 1»7 которое представляет собой объединение 1» и 1т, состоящее из трех пунктов — [С вЂ” и'., с/и/3]. Все переходы по г) в 1» или 1т из 1ш 1з, 1з и 1а ведут теперь в 1»т. Действие в состоянии 47— свертка при любом входном символе. Такой синтаксический анализатор в целом ведет себя так же, как исходный, хотя и может свернуть д в С в условиях, когда исходный синтаксический анализатор объявил бы об ошибке, например при входной строке со~1 или сдоб.
В конце концов ошибка будет обнаружена — перед тем как мы получим любой символ, вызывающий перенос. Обобщая, мы можем рассмотреть множества ЕК (1)-пунктов, имеющих одно и то же ядро (соте), т.е. множество первых компонентов, и объединить эти множества с общими ядрами в одно множество пунктов. Например, на рис. 4.41 такую пару с ядром (С вЂ” д ) образуют состояния 1» и 1т. Аналогично множества 1з и 1а образуют другую пару — с ядром (С вЂ” с С, С вЂ” сС, С вЂ” д).
Имеется и еше одна пара — 1а и 1я — с общим ядром (С вЂ” сС ). Заметим, что, вообще говоря, ядро является множеством ЕК (0)-пунктов рассматриваемой грамматики и что ЬК (1)-грамматика может давать более двух множеств пунктов с одним и тем же ядром. Поскольку ядро множества сото(1, Х) зависит только от ядра множества 1, значения функции ПОТО объединяемых множеств также могут быть объединены. Таким образом, проблем вычисления функции бОТО при слиянии множеств не возникает. Функция же АСТ10Н должна быть изменена, чтобы отражать не ошибочные действия всех объединяемых множеств пунктов. Предположим, имеется ЕК (1)-грамматика, т.е.
грамматика, множества ЕК (1)- пунктов которой не вызывают конфликтов действий синтаксического анализа. Если заменить все состояния, имеющие одно и то же ядро, их объединениями, возможно, полученное в результате состояние будет иметь конфликт, хотя зто маловероятно по следующей причине. Предположим, что в объединении возникает конфликт при просмотре входного символа а, поскольку существует пункт [А — а, а], вызывающий свертку по продукции А — а, а также другой пункт, [ — ~3 ау, б], приводящий к переносу.
Тогда некоторое множество пунктов, из которого было сформировано объединение, имело пункт [А — а,а]. Поскольку ядра объединяемых множеств совпадают, зто множество должно также иметь пункт [ —,'3 а;у,с] для некоторого с. Но в таком случае это состояние имело бы конфликт переноса/свертки для символа а и вопреки нашему предположению грамматика не была бы ЕК (1)-грамматикой.
Следовательно, объединение состояний с одинаковыми ядрами не может привести к конфликту переноса/свертки, если такой конфликт не присутствовал ни в одном из исходных состояний (поскольку переносы зависят только от ядра, но не от предпросмотра). 341 4.7, Более мощные 1.К-анализаторы Тем не менее при объединении возможно появление конфликта "свертка'свертка", как показано в следующем примере. Пример 4.42.
Рассмотрим грамматику Я вЂ” ~ аАс1(ЬВс((аВе(ЬАе А — ~ с  — с Она генерирует четыре строки — асс(, асе, Ьсс( и Ьсе. Читатель может убедиться, что грамматика является ЬК(1), построив множества пунктов. Сделав это, мы обнаружим множество пунктов ((А — с., с((, ( — с, е(), допустимых для активного префикса ас, и ((А — с.,е], [В - с,с1() — для префикса Ьс. Ни одно из этих множеств не вызывает конфликта; ядра их одинаковы. Однако их объединение А — с, с(/е  — с с1ссе вызывает конфликт "сверткагсвертка", поскольку при входных символах с( и е вызываются две свертки: А — с и  — с.
и Теперь мы готовы рассмотреть первый из двух алгоритмов построения ЬАЬК- таблиц. Основная идея состоит в создании множеств 1.К (1)-пунктов и, если это не вызывает конфликтов, объединении множеств с одинаковыми ядрами. Затем на базе набора множеств пунктов строим таблицу синтаксического анализа. Описываемый метод служит, в первую очередь, определением ЬАЬК(1)-грамматик. Построение полного набора множеств ЬК(1)-пунктов требует слишком много памяти и времени, чтобы использоваться на практике. Алгоритм 4.43.
Простое построение ЬАЬК-таблицы (с большими затратами памяти) Вход: расширенная грамматика С'. Выход: таблица функций ЬАЬК-анализа лстюгг и сото для грамматики С'. МЕТОД: выполняем следующие действия. 1. Строим набор множеств 1.К(1)-пунктов С = (1о, 1ы..., 1„1 для грамматики СЬ 2. Для каждого ядра, имеющегося среди множества ЬК (1)-пунктов, находим все множества, имеющие это ядро, и заменяем эти множества их объединением.
342 Глава 4. Синтаксический анализ 3. Пусть С' = (,1о, 1ы..., 1 ) — полученные в результате множества ЬК (1)- пунктов. Функцию лстюн для состояния г строим из 1, так же, как и в алгоритме 4.40. Если при зтом обнаруживается конфликт, алгоритм не в состоянии построить синтаксический анализатор, а грамматика не является ЬАЬ.К (1)-грамматикой. 4. Таблица бОТО строим следующим образом. Если,7 — обьединение одного или нескольких множеств ЬК(1)-пунктов, т.е..7 = 1~ 0 1д 0 о 1ы то ядра множеств аото (1ы Х), 0ото (1з, Х),..., пото (1ь, Х) одни и те же, поскольку 1ы 1з,..., 1ь имеют одно и то же ядро. Обозначим через К объединение всех множеств пунктов, имеющих то же ядро, что и сото (1ы Х).
Тогда сото(.1,Х) = К. а Таблица, полученная при помощи алгоритма 4.43, называется таблицей ЕАьР- анализа для грамматики С. Если конфликты действий отсутствуют, то данная грамматика называется ЬАЬК(1)-грамматикой. Набор множеств пунктов, построенный на шаге 3, называется ЬАЬК (1)-набором. Пример 4.44. Вновь обратимся к грамматике (4.1б), граф бОТО которой показан на рис. 4.4Ь Как уже упоминалось, имеется три пары множеств пунктов, которые могут быть объединены. 1з и 1д заменяются их объединением 1зв: С вЂ” с С,с1г118 С вЂ” сС, с/п18 С вЂ” ~ д,с/ф8 14 и 1т заменяются их объединением 1зт '.
С вЂ” ~ д, с/ф8 1в и 1д заменяются их объединением 1зд . 'С вЂ” ~ сС, с/ф8 Функции действий и переходов ЬАЬК для объединенных множеств пунктов показаны на рис. 4.43. Чтобы увидеть, каким образом вычисляется функция бОТО, рассмотрим сото(1зд, С). В исходном множестве ЬК (1)-пунктов сото(1з, С) = 1з, а 1з теперь является частью 1зд, так что мы определяем, что сото(1зд, С) = 1зд. Тот же вывод моно сделать, рассматривая 1д — вторую часть 1зд.
.сото(1д, С) = 1д, а 1д теперь также является частью 1зд. В качестве другого примера рассмотрим бото(1з,с), переход, выполняемый после переноса состояния 1з прн входном символе с. В исходных множествах ЬК (1)-пунктов сото(1з, с) = 1в. Поскольку 343 4.7. Более мощные ЬК-ааализаторы Рис.
4.43. Таблица ЬАЬК-анализа лля грамматики нз примера 4.39 теперь Та является частью Тзе сото(1з,с) становится равным Тзе, таким образом, запись на рис. 4.43 для состояния 2 и входного символа с — а36, что означает перенос и помещение в стек состояния 36. При входной строке из языка с*ос'и как ЬК-анализатор на рнс. 4.42, так и ЬАЬК-анализатор на рис. 4.43 выполняют одну и ту же последовательность переносов и сверток, хотя имена состояний в стеке могут отличаться. Так, если ЬК-анализатор помещает в стек Тз или 1е, ЬАЬК-анализатор помешает в стек Тзе. Это верно и в общем случае 1.А1.К-грамматики.
1.К- и 1.А1.К-анализаторы имитируют друг друга при корректной входной строке. Однако при строке с ошибками ЬАЬК-анализатор может выполнить несколько сверток после того, как 1.К-анализатор уже обьявит об ошибке. Однако 1.А1.К- анализатор никогда не перенесет символ после того, как ошибка распознана 1.К.- анализатором. Например, для входной строки сей 1.К-анализатор на рис.
4.42 поместит в стек 0334 и в состоянии 4 обнаружит ошибку, поскольку следующий входной символ — 8, а для состояния 4 соответствующая запись таблицы АСТ1ОХ вЂ” "ошибка". В протнвогюложность этому ЬАЬК-анализатор, показанный на рис. 4.43, выполняет соответствующие действия, помещая в стек 0 36 36 47 Однако состояние 47 при входном символе 8 приводит к свертке С вЂ” д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
