А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 57
Текст из файла (страница 57)
Во-первых, невозможно выбрать единственную А-продукцию в строке 1, так что требуется испытывать каждую из нескольких продукций в некотором порядке. Во-вторых, ошибка в строке 7 не является окончательной и предполагает возврат к строке 1 и испытание другой А-продукции. Объявлять о найденной во входной строке ошибке можно только в том случае, если больше не имеется непроверенных А-продукций. Чтобы быть в состоянии проверить новую А- продукцию, нужно иметь возможность сбросить указатель входного потока в состояние, в котором он находился при первом достижении строки 1.
Таким образом, для хранения этого указателя входного потока требуется локальная переменная. 285 4.4. Нисходящий синтаксический анализ Н„и сравниваем его с очередным листом б. Поскольку Ь не соответствуег д, мы сообщаем об ошибке и возвращаемся к А, чтобы выяснить, нет ли альтернативной продукции, которая не была проверена до этого момента.
Вернувшись к А, мы должны сбросить указатель входного потока так, чтобы он указывал на позицию 2, в которой мы находились, когда впервые столкнулись с А. Это означает, что процедура для А должна хранить указатель на входной поток в локальной переменной. Вторая альтернатива для А дает дерево разбора, показанное на рис. 4.14, в. Лист а соответствует второму символу ш, а лист д — третьему символу.
Поскольку нами построено дерево разбора для входной строки зо, мы завершаем работу и сообщаем об успешном выполнении синтаксического анализа и построении дерева разбора. и Леворекурсивная грамматика может привести синтаксический анализатор, работающий методом рекурсивного спуска, к бесконечному циклу, т.е. когда мы попытаемся развернуть нетерминал А, то в конечном счете можем найти этот же нетерминал и прийти к попытке развернуть А, так и не взяв ни одного символа из входного потока. 4.4.2 ИКОТ и РОЕЬОЖ При построении как нисходящего, так и восходящего синтаксического анализатора нам помогут две функции — НКЯТ и ЕОЬЬ0%, — связанные с грамматикой С.
В процессе нисходящего синтаксического анализа НКЗТ и ЕОЬЬ0% позволяют выбрать применяемую продукцию на основании очередного символа входного потока. Множества токенов, порождаемые функцией ЕОЬЬ0%, могут также использоваться как синхронизируюшие токены в процессе восстановления после ошибки в "режиме паники". Определим НКЯТ(а), где су — произвольная строка символов грамматики, как множество терминалов, с которых начинаются строки, порождаемые су. Если а =у е, то е е НКБТ (су). Например, на рис. 4.15 А =~ с ~, так что с е НКБТ (А).
Рис. 4.15. Терминал с Е НК5Т (А), а терминал а и РОЬЬ0% (А) Чтобы понять, как НКЗТ может использоваться в процессе предиктивного синтаксического анализа, рассмотрим две А-продукции А — су ~ )3, где НКБТ (су) гйб Глава 4. Синтаксический анализ и НКЯТ(33) представляют собой непересекающиеся множества. Выбрать необходимую А-продукцию можно путем просмотра очередного входного символа а, поскольку а может находиться не более чем в одном из множеств ЯКУТ(а) и НКЗТ(33), но ни в коем случае не в обоих одновременно.
Например, если а Е НКЯТ (33), то следует выбрать продукцию А — 33. Эта идея будет использоваться в разделе 4.4.3 для Щ1)-грамматик. Определим Е01Л.0%(А) для нетерминала А как множество терминалов а, которые могут располагаться непосредственно справа от А в некоторой сентенциальной форме, т.е. множество терминалов а, таких, что существует порождение вида Я =~ аАа13 для некоторых а и 33, как на рис. 4.15. Заметим, что в процессе порождения между А и о могут появиться символы, но если это так, то они порождают е н исчезают. Кроме того, если А может оказаться крайним справа символом некоторой сентенциальной формы, то 3 Е гО!Е0%(А) (вспомните, что 3 — это специальный символ "маркера конца", который не является символом грамматики). Чтобы вычислить ЯКУТ (Х) для всех символов грамматики Х, будем применять следующие правила до тех пор, пока ни к одному из множеств Е!КИТ не смогут быть добавлены ни терминалы, ни е.
!. Если Х вЂ” терминал, то НКЯТ (Х) = (Х). 2. Если Х вЂ” нетерминал и имеется продукция Х вЂ” У! Уз... Уь для некоторого lс > 1, то поместим а в НКВТ(Х), если для некоторого! аЕ ЯКУТ(У,) и е входит во все множества НКЯТ(У!), ..., ЯКУТ(У, ~), те. У~... У, ~ =~ е. Если е входит в НКБТ (!' ) для всех 3' = 1, 2,..., й, то добавляем е к Е!КИТ (Х).
Например, все, что находится в множестве ЯКУТ(Уз), есть и в множестве ЯКУТ(Х). Если У~ не порождает е, то больше мы ничего не добавляем к НКБТ(Х), но если У! =~ г, то к НКЯТ(Х) добавляется НКЯТ(Уз) и т.д. 3. Если имеется продукция Х вЂ” г, добавим е к НКБТ (Х). Теперь можно вычислить Р!КИТ для любой строки ХзХз... Х„следующим образом.
Добавим к ЯКУТ (Х~Хз... Х„) все не-е-символы из НКБТ (Х~). Добавим также все не-е-символы из ЯКУТ(Хз), если еЕНКЗТ(Х!), все не-е-символы из Е!КИТ(Уз), если е имеется как в НКБТ (Х!), так и в Р1КБТ(Хз), и т.д. И наконец, добавим г к НКБТ(Х~Хз... Х„), если для всех 1 Р!КБТ(Х,) содержит г. Чтобы вычислить РО!.!.0%(А) для всех нетерминалов А, будем применять следующие правила до тех пор, пока ни к одному множеству ЕОЬ!.0% нельзя будет добавить ни одного символа. 1. Поместим 5 в РО!.!.0%(Я), где о — стартовый символ, а 3 — правый ограничитель входного потока.
287 4.4. Нисходящий синтаксический анализ Если имеется продукция А — а В Д, то все элементы множества НКВТ (13), кроме г, помещаются в множество РОЬЬ0%(В). Если имеется продукция А — а В или А — а В 13, где НКВТ Щ содержит е, то все элементы из множества г01Л.0%(А) помещаются в множество ГОЬЬ0% (В). Г1КЯТ(Е) = НКЯТ(Т) = НКЯТ(Е) = ((,Ы). Что бы понять, почему это так, заметим, что две продукции для Е имеют тела, начинающиеся с указанных терминальных символов — !д и левой скобки. Т имеет только одну продукцию, тело которой начинается с Г.
Поскольку Р не порождает г, НКЯТ(Т) должно быть тем же, что и НКВТ(Г). Те же рассуждения применимы и к Р1КБТ (Е). НКВТ(Е') = (+, с). Причина этого в том, что одна нз двух продукций для Е' имеет тело, начинающееся с терминала -ь, а тело второй — е. Ко- гда нетерминал порождает г, мы помещаем е в множество НКВТ этого нетерминала. НКБТ(Т') = (*, г). Аргументация в данном случае аналогична аргумен- тации для НКВТ (Е'). 3. 4.
РОЬЬ0%(Е) = РОЛЛ.0% (Е') = (), 3). Поскольку Е является стартовым символом, множество РОЛЛ.0% (Е) должно содержать 3. Тело продукции (Е) объясняет, почему в гОЬЬ0%(Е) входит правая скобка. В случае Е' заметим, что этот нетерминал появляется только в конце тел Е-продук ций. Таким образом, множество РОЬЬ0%(Е') должно быть тем же, что и ГОЬЬ0% (Е).
РОЬ 0%(Т) = РОЛЛ.0% (У') = (+, ), 3). Заметим, что в продукциях грамматики за Т всегда следует Е'. Таким образом, все элементы множества НКЯТ (Е'), кроме е, должны находиться в РОЬЬ0%(Т). Это объясняет наличие символа +. Однако, поскольку НКБТ(Е') содержит с (т.е. Е' ~ с), а Е' представляет собой целую строку, следующую за Т в телах Е-продукций, все, что находится в г01Л.0% (Е), должно также находиться и в ГОЬЬ0% (Т). Это объясняет наличие символа 3 и правой скобки. Что касается Т', то, поскольку этот нетерминал появляется толью в конце Т- продукций, должно выполняться равенство РОЬЬ0% (Т') = РОЬЬ0% (Т).
ГОЬЬ0%(Г) = (+, ч, ), 3). Аргументация аналогична аргументации для Твп.5. а Пример 4.16. Вновь обратимся к нелеворекурсивной грамматике (4.14). В этом случае мы найдем следующие значения НКВТ и РОЛЛ,0%. 288 Глава 4. Синтаксический анализ 4.4.3 Щ1)-грамматики Предиктивные синтаксические анализаторы, т.е. синтаксические анализаторы, работающие методом рекурсивного спуска без возврата, могут быть построены для класса грамматик, называющегося Щ1). Первое "1." в Щ1) означает сканирование входного потока слева направо, второе "1." — получение левого порождения, а "Г' — использование на каждом шаге предпросмотра одного символа для принятия решения о действиях синтаксического анализатора. Класс грамматик Щ1) достаточно богат для того, чтобы охватить большинство программных конструкций, хотя при написании грамматики для исходного языка требуется аккуратность. Например, в ЕЬ(1)-грамматике не может быть ни левой рекурсии, ни неоднозначности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
