Главная Промышленная автоматика.

гл. 5. однопроходный синтаксический анализ без возвратов

5.1.3. Следствия определения 11)-грамматики

Покажем, что для каждой ЬЬ(й)-грамматики можно мехаин-чески построить корректный -предсказывающий алгоритм разбора. Так как ядром предсказывающего алгоритма является управляющая таблица, надо показать, как строить по грамматике такую таблицу. Начнем с некоторых следствий определения ЬЬ(й)-грамматики.

В определении ЬЬ(й)-грамматики утверждается, что для данной левовыводимой цепочки wAa цепочка w и непосредственно следующие за ней k входных символов однозначно определяют, какое применить правило для развертки нетерминала Л. Поэтому на первый взгляд может показаться, что для определения нужного правила надо помнить всю цепочку w. Однако это не так. Докажем теорему, очень важную для понимания ЬЬ(/е)-грамматик:

Теорема 5.2. КС-грамматика G=(N, 2, Р, S) является ]Л.[к)-грамматикой тогда и только тогда, когда для двух различных правил Л-и Ау из Р пересечение РШ5Тд(ра) h FlRST(yct) пусто при всех таких wAa, что 8=1 wAa.

Доказательство. Необходимость. Допустим, что tej, Л, а, Р и у удовлетворяют условиям теоремы, а Р1Р5Тд(ра) П FlRSTft(va) содержит X. Тогда по определению FIRST для некоторых у и г найдутся выводы S wAa wa wxy и S/ wAa -> wyaz] wxz. (Заметим, что здесь мы использовали тот факт, что N пе содержит бесполезных нетерминалов, как это предполагается для всех рассматриваемых грамматик.) Если (x < fe, то yz = e. Так как ft фу, то G не ЕЬ(/г)-грамматика.

Достаточность. Допустим, что G ие ЕЕ(/г)-грамматика. Тогда найдутся такие два вывода S=i>*iwAawalwx и S=>*шЛa=> wyaziwy, что цепочки х и совпадают в первых k позициях, но Ру. Поэтому л-р и А->у - различные правила из Р и каждое из множеств FIRST(pct) и FIRST;(Ya) содержит цепочку FIRST(x), совпадающую с цепочкой FIRSTft(). □

Даднм несколько приложений теоремы 5.2 к ЕЬ(1)-грамматп-кам. Пусть КС-грамматика G = (N, 2, Р, S) не содержит е-правил, н нам надо узнать, является ли она ЕЕ(1)-грамматикой. Из теоремы 5.2 следует, что G будет ЕЬ(1)-грамматикой тогда и только тогда, когда для всех A£N каждое множество Л-правил Л «1 aj.. .a„ нз Р таково, что множества FI RSTj(a,), FIRSTi(cti),---. FlRSTi(a„) попарно не пересекаются. (Отсутствие е-правил здесь существенно.)

Пример 5.7. Грамматика G, состоящая из двух правил 5-> aS\a, не будет ЕЬ(1)-грамматикой, так как FIRST(gS) FlRSTi(a) Интуитивно это можно объяснить так; видя при разборе цепочки,

начинающейся символом а, только этот первый символ, мы пе знаем, какое из правил S-aS или 5~>а надо применить к S. Q т-фугой стороны, G-это ЕЕ(2)-грамматика. В самом деле, в обозначениях теоремы 5.2, если SJwAa, то Л=5 и а -й. Так как для S даны только два указанных правила, то p = aS и уа. Поскольку РШ8Тг(а5) -ш и FlRST{a) = a, то по теореме 5-2 G будет ЕЬ(2)-грамматнкой. □

Рассмотрим ЕГ(1)-грамматикн, содержащие е-правила. Здесь удобно ввести функцию FOLLOW.

Определеиие. Пусть G = (N, 2, Р, S) - КС-грамматика, Определим FOLLOWfe(p), где ft-целое число и p€(Nu2)*, как множество {ш5->*ару и [£j FIRST(y)}. Как обычно, будем опускать k я G там, где понятно, о чем идет речь.

Итак, FObhO?{A) - это множество терминальных символов, которые могут встречаться непосредствен1Ю справа от Л (т. е. следовать за Л) в каких-нибудь выводимых цепочках, причем если а А - выводимая цепочка, то е тоже принадлежит VOLWWi{A).

Можно очевидным образом расширить определение функций FIRST и FOLLOW так, чтобы их аргументами были не только отдельные гепочки, но и множества цепочек. Иначе говоря, если (}-(N, 2, Р, S) -КС-грамматика и L(Nu2)*, то FIRST,?(/,) = {£2JteJFIRSTf(a) для некоторой цепочки aL} FOLLOW (L) - {w I w € FOLLOW (a) для некоторой цепочки

Для ЕЕ(1)-грамматик справедливо следующее важное утверждение.

Теорема 5.3. КС-грамматика G = (N, 2,P,S) являет.ся LL(1)-грамматикой тогда и только тогда, когда для двух различных правил Л->Р и А~у пересечение FIRSTj (рFOLLOW, (Л)) п FIRST, (yFOLLOWl(Л)) пусто при всех Л€N.

Доказательство. Упражнение. □

Таким образом, G является ЕЕ(1)-грамматикой тогда и только тогда, когда для каждого множества Л-правил Л ... а,

(1) множества FlRSTj(aj), FIRST, (а), .... FIRST, (а„) попарно не пересекаются,

(2) если a,=i>V, то FIRST Лу) П FOLLOW,(/i) 0 для

Это просто переформулировка теоремы 5.3. Может показаться, что теорема 5.3 непосредственно обобщается на ГЬ(й)-грам-матнки. Мы Хотим предостеречь читателя, что это не так. КС-



грамматика G, для которой

(5.1.1) если Л->р и А-уу - различные Л-правила, то

FlRST(pFOLLOW (Л)) п FIRSTLY FOLLOW {)) = 0

называется сильно LL (к)-грамматикой. Каждая LL (1)-грамма-тика - сильно LL (1)-грамматнка, но, как показывает следующий пример, для А: > 1 существуют LL (/е)-грамматики, не являющиеся сильно LL (/г)-грамматиками.

Пример 5.8, Пусть грамматика G определена правилами S -аАаа \ ЬАЬа А-Ь\е

С помощью теоремы 5.2 можно убедиться, что это LL (2)-грам-матнка. Возьмем вывод S=aAaa. Заметим, что FlRST2(bGa)n FIRST2 (йй)0. В обозначениях теоремы 5.2 а=--аа, рЬ и у = е. Аналогично,если 5=ЬЛЬй,то FIRST2(bba)n FlRST2(ba)-.0, Так как все выводы в грамматике G имеют длину 2, по теореме 5.2 G будет LL (2)-грамматикой. Но FOLLOW2 (Л) {аа, Ьа), так что

FIRST ф FOLLOW, (Л)) п FIRST, (FOLLOW,(Л)) = {Ьа]

Условие (5.1.1) нарушено, и, значит, LL (2)-грамматика G не является сильно LL (2)-грамматикой. □

Одно из важных следствий определения LL (/г)-грамматики состоит в том, что леворекурсивная грамматика не может быть LL(/е)-грамматикой ни для какого к (упр. 5.1.1).

Пример 5.9. Пусть грамматика G определяется двумя правилами S-Sa\b. Возьмем, как и в теореме 5.2, вывод S=Sa, где iO, A=S, а = е, р = 5а н у = Ь. Тогда для ik

FiRSTft (Saa) П FIRST {Ьа) = йа-

Таким образом, G не может быть ЕЕ(й)-грамматикой ни для какого к. □

Важно также заметить, что каждая ЬЬ()-грамматика однозначна (упр. 5.1.3). Поэтому, если дана неоднозначная грамматика, сразу можно сказать, что она не ЬЬ(/г)-грамматика.

В гл. 8 мы покажем, что для многих детерминированных КС-языков не существует ЬЬ(/г)-грамматик. Один из таких языков - язык {a"Ob"rt> l}U{tt"lb" 1}. Кроме того, неразрешима проблема распознавания, существует ли для данной КС-грамматики G, не являющейся ЬЬ(й)-грамматикой (й фиксировано), эквивалентная ей ЬЬ(/г)-грамматика. Но несмотря на эти неприятности, есть все же ситуации, в которых к данной не ЬЬ(1)-грамматике можно применить преобразования, позво-

ляющие превратить ее в эквивалентную LL (1)-грамматику. Приведем здесь два таких преобразования.

Первое-устранение левой рекурсии. Проиллюстрируем этот прием на примере.

Пример 5.10. Пусть G - грамматика S"»-Sa/7, которая, как мы видели в примере 5.9, не является LL-грамматикой. Эти два правила можно заменить тремя правилами

S-bS S-aS\e

получив при этом эквивалентную грамматику С помощью теоремы 5.3 легко показать, что G -LL (1)-грамматика. □

Другое полезное преобразование-левая факторизация (или вынесение левого множителя). Этот прием тоже проиллюстрируем на примере.

Пример 5Л1. Рассмотрим LL (2)-грамматику G с двумя правилами SaS\a. В этих двух правилах „вынесем влево за скобки" символ а, записав их в виде S~a{S\e). Иными словами, мы считаем что операция конкатенации дистрибутивна относительно операции выбора альтернативы (обозначаемой вертикальной чертой). Затем заменим эти правила на

SaA AS\e

получив тем самым эквивалентную LL (1)-грамматйку. □

В общем случае процесс левой факторизации заключается в замене правил Л -j-ap .. . ар„ правилами Л -аЛ и А-

Pti---ip„.

5.1.4. Разбор для LL 1-грамматик

Ядром -предсказывающего алгоритма разбора является управляющая таблица М. В этом и следующем разделах мы покажем, как для каждой LL (/г)-грамматики G построить корректную управляющую таблицу, и таким образом докажем, что для нее возможен левый разбор с помощью /г-предсказывающего алгоритма. Сначала исследуем важный частный случай, когда j - LL (1)-грамматика.

Алгоритм 5.1. Управляющая таблица для LL(1)-1"рамматики.

Вход. ЬЬ(1)-грамматика G=(N, S).

Выход. Корректная управляющая таблица М для грамматики G.

А. Ахо, Дж. Ульмав. т. I



FT А

выброс

Bbt6pOC

выброс

выброс

выброс

ДОПУСК

Рис. 5.4. Управляющан таблица для грамматики G.

рой рекурсии, как в примере 5.10. Кстати, G не является LL-грамматикой.

На шаге (1) алгоритма 5.1 найдем элементы строки таблицы для нетерминала £. Здесь FIRST, [ГЯ] {(, а}, так что (] \ТЕЛ\ и М[Е,а\\ТЕ,\\ Все остальные элементы этой строки - ошибки. Вычислим теперь строку для нетерминала Е. Заметим, что FIRST, [+7] = + /так что М [£, -f ] = lTE, 2]. Таккак есть правило£е, мы должны вычислить FOLL0Wi[E]= {е,)}. Таким образом, М\Е,е\-М\Е,)\ = \e,Z\ Каждый из остальных элементов строки для Я -ошибка. Продолжая в том же духе, получим управляющую таблицу для G, показанную на рис. 5.4. Ячейки, в которых должна стоять ошибка, оставлены пустыми.

1-предсказывающий алгоритм разбора с помощью этой таблицы проанализирует входную цепочку (йй-а) так;

[(а*а), Е%,е\\{аа), ТЕ%, 1]

РГЕ%, 14] h-[(fl*fl), {Е)ГЕ%, 147] Ь[а«а), Е)ГЕ%, 147] У-1аа), ТЕ)ТЕ%, 1471] -[а*й), FTE)TE%, 14714] Ь-[а«й), аТЕ)ТЕ%, 147148]

ТЕ)ГЕ%, 147148] \-\;а), FTE)TE%, 1471485]

FTE)TE$, 1471485] \-[а),аГЕ)ГЕ, 14714858] -[), ГЕ)ТЕ$, 14714858] [-[), F)TE$, 147148586] ) ТЕ$, 1471485863] \-[е, ТЕ, 1471485863] 14714858636] \~[е, $, 147148586363] □

Теорема 5.4. Алгоритм Ь.\ строит корректную управляюиую таблицу для LL {\)-грамматики G.

Доказательство. Заметим сначала, что если G -LL(1)-грамматика, то на шаге (1) алгоритма 5.1 для каждого элемента М{А,а) управляющей таблицы определяется не более одного значения. Это замечание - просто переформулировка теоремы 5.3.

Далее, прямой индукцией по числу шагов I-предсказывающего алгоритма Л с управляющей таблицей М можно показать, то если {xy,S$,e)\-"*{у,а$, п), то 5я=>ш. Другой индукцией

Метод. Будем считать, что $-маркер дна магазина. Таблица М определяется на множестве (N и 2 и {$})Х (2 и {е}) следующим образом:

(1) Если Л--правило из Р с номером i, то М{Л,а) (а, i] для всех афе, принадлежащих FIRST,(a). Если FIRSTj(a) то М{А,Ь) = {а,1) для всех 6 € FOLLOW, (Л).

(2) М (а, й) = выброс для всех а 2.

(3) М ($, ) допуск.

(4) В остальных случаях ошибка для XNu 2 и {$} и aEXlj{e\. П

Прежде чем показать, что алгоритм 5.1 дает для грамматики G корректную управляющую таблицу, рассмотрим пример.

Пример 5.12. Посмотрим, как строится управляющая таблица для грамматики G с правилами

(1) Е ~ТЕ (2) E~-hTE

(3) Е~е (4) Т ~FT

(5) TFV (6) Т~е

(7) F ~{Е) (8) F

С помощью теоремы 5.3 можно проверить, что G - LL(1)-грамматика. На самом деле внимательный читатель заметит, что грамматика G получена из G в результате устранения ле-л ( ) + * е





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 [63] 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.0041