Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 73
Текст из файла (страница 73)
Так как 5Е(„, А Е1„и А — 5А — четвертое правило, то реп (2, 4, А) выдаст 4 и вызовет реп (2, 1, 5), а затем реп(3, 3„А). Продолжая в том же духе, получим левый разбор 164356263. Заметим, что 6 — неоднозначная грамматика; в самом деле, цепочка аЬааЬ имеет более одного левого разбора. В общем случае нельзя по таблице разбора получить все разборы входной цепочки за менее чем экспоненциальное время, так как у нее может быть экспоненциальное число разборов.
Заметим, что алгоритм 4.4 можно сделать более быстрым, если при построении таблицы разбора помещать указатели в те элементы, которые приводят к появлению новых элементов (см. упр. 4.2.21). 4.?.?. Алгоритм Эрлн В этом разделе мы изложим метод синтаксического анализа, позволяющий для произвольной КС-грамматики разобрать входную цепочку за время 0(п'), использовав при этом емкость памяти 0(па), где п — длина входной цепочки. Кроме того, если грамматика однозначная, то время квадратичное, н для большинства грамматик языков программирования алгоритм можно модифицировать так, чтобы время и емкость стали линейпымп функциями от длины входной цепочки (упр.
4.2.18). Сначала мы неформально опишем основной алгоритм, а потом покажем, что вычисление можно организовать так, что получатся указанные выше границы сложности. Основная идея алгоритма состоит в следующем. Пусть 6= (Я, Х, Р, 5) — КС-грамматика и ц ==а,а,... а„— входная цепочка из Х'. Объект вида [А — Х,Х, ... Х„Х„, ... Хм. 1) на- 35В Ч 2. ТАБЛИЧНЫЕ МЕТОДЫ СИНТАКСИЧРГКОГО АНАЛИЗА зовемситуаь(ией,относящейсякцепочке п2, если А — Х;...Х правило из Р и 0(~' =.п. Точка между Х„и Хе„является метасимволом, не припадлсжащим пи Гч, ни Х.
Число й может быть любым целым числом от нуля (в этом случае точка — первый символ) до т (в этом случае она — последний символ) '). Для каждого 0(1(н мы построим такой список ситуаций 1, что [А я4 1) принадлежит 1; для 0«=1(1 тогда н только тогда, когда для некоторых у и б существуют выводы 5=>'уАб, у=эча, ...
а, и а=>ааа„, ... а,. Таким образом, между второй компонентой ситуации и помором списка, и котором она появляется, заключена часть входной цепочки, выводимая из а. другие условия, налагаемые иа ситуацию, просто гарантируют возможность применения правила А — ар в выводе некоторой входной цспочки, совпадающей с ьп до позиции 1. Последовательность списков 1„1„..., 1„будем называть тсасио.~ разбора для входной цепочкй ю.
Заметим, что п2 принадлежит 1 (6) тогда и только тогда, когда в 1„есть ситуация вида [5 а, О). Опишем алгоритм, который по произвольной данной грамматнке порождает список разбора любой входной цепочки. А л г о р н т м 4.5. А л г о р и т и Э р л и. Вход. КС-грамматика 6 -= (и)„Х, Р, 5) и входная цепочка щ=-а,а, ... аа из Х*. Выход. Список разбора 1„1„..., („для Пеночки ьн, Метод. Сначала строим 1,: (1) Если 5 — а — правило из Р, включить в [5 — .Те, О[ в 1,. Далее выполнять шаги (2) и (3) до тех пор, пока в 1, можно включать новые ситуации. (2) Если [В у, О) принадлежит 1,'), включить в 1, ситуацию [А — ееВ 6, О) для всех [Л ее В)), О), уже принадлежащих 1,. (3) Допустим, что [А- се В6, 01 принадлежит 1„. Для каждого правила, из Р вида  — у включить в 1, ситуацию [В у, О[ (если она еще не там).
После того как построены 1„1„..., 1,, строится 1~. (4) Для каждой ситуации [ — сс а~, (~ из 1, „для которой а=а~, включить в 1 ситуацию [В- аа 6, 2). Далее выполнять шаги (5) н (6), пока в 1, можно включать новые ситуации. (5) Пусть [А — а °, 21 принадлежит 1,. Искать в 1; ситуации вида [В а Ар, й]. Для каждой из них включить в 1, ситуацию ~а- а.а, ьь 2е ~ » А, бу 1.'~ —,им ') Заметим, что Т может быть е. Таи начипастси применение правиаа (Э), 359 ГЛ, в, ОБщие метОды синтаксическОБО АИАлиза (6) Пусть [А а В[), 1] принадлежит 1,.
Для каждого В- у из Р включить в 1, ситуацию [ — у, 1]. Заметим, что рассмотрение ситуации, в которой справа от точки стоит терминал, на шагах (2), (3), (5) и (6) не дает новых ситуаций, Итак, алгоритм состоит в построении 1Р для 0(1 " п. Пример 4.10. Рассмотрим грамматику 6 с правилами (1) Š— 7+Е (2) Š— Т (3) Т вЂ” Рат (4) т-Р (6) Р-(Е) (6) Р и и входную цепочку (а+а)аа. На шаге (1) включаем в 1, ситуа. ции [Е- Т+Е, О] и [Е= Т, О]. Рассмотрениеэтих ситуаций приводит к включению в 1, посредством шага (3) ситуаций [Т вЂ” .Рат, О] и [т Р, 0].
Продолжая этот процесс, добавляем [Р ° (Е), О] и [Р- а, 0]. Другие ситуации уже нельзя вклю- чить в 1,. Теперь построим 1,, По правилу (4) включаем [Р— ( Е),0], так как а,— -(.Тогда правило (6) позволяет включить [Š— Т+Е,]~, [е- т', ц', [т- Р:. т, ц, [т- Р, ц, [Р-.(е), ц' ' [Г а, Ц. Теперь в 1, уже нельзя включить новые ситуации. Чтобы построить 1,, заметим, что а,» — -а и по правилу (4) ситуацию [Р- а., Ц нужно включить в 1,. Затем по правилу (6) рассмотрим эту ситуацию, перейдем к списку 1! и поищем в исм ситуации, в которых Р стоит непосредственно справа от точки. Две такие ситуации найдутся, и мы включим [Т Р аТ, Ц и г,т — Р, Ц в 1,, Рассмотрение первой из них не дает ничего, а вторая заставляет обратиться к 1, в поисках ситуаций, содер- жащих Т.
Еще две ситуации [Е- У ° +Е, Ц и [Š— Т, Ц включаются в 1,. Снова первая не дает ничего, а вторая при- водит к включению [Р— (Е ), 01 в 1,. Теперь никакие ситуа- ции нельзя включить в 1„так что список завершен. Содержимое всех списков приведено на рис. 4.9. Так как ситуация ]Е- 7, О] включена в последний список, входная цепочка (а+а) в а принадлежит Ь (6). При анализе алгоритма Эрли мы будем действовать по сле- дующему плану.
Сначала докажем корректность упомянутой ранее неформальной интерпретации ситуаций. Затем покажем, что если грамматика 6 однозначная, то при разумном понятии элементарной операции время выполнения алгоритма квадра- тично зависит от длины входной цепочки. Наконец, покажем, как по списку разбора построить разбор и фактически как это сделать за квадратичное время. 340 Рас. 4.9, Списки разбора дая примера 4.10.
ва [Е ° Т+Е, О! [Е ° Т, О[ [т — Рат, О! [Т ° Р, О! [Р «Е), О] 1Р— - ° а, 0] )в [Š— Т+ Е,Ц [Р т+е, з[ [Р— т, з! ]т — .Р.т, 31 (Т вЂ” ».Р, 3! [Р— -» «Е), 3[ [Р» а, 3! )в 1Т Ра Т,О] [Т вЂ” ».Рвт, 6! [т Р,6[ [Р— » «Е), 6! [Р— » а,б] I! [Р (Е),61 [Е .Т-«-Е, ц т,ц [т-- Рат, Ц «Т — » Р,Ц [Р— » «Е), Ц [Р— »а,Ц вв [Р—,, з] [т Р"в т, З1 [т — Р., з] [Е --» Т +Е, 3[ [Š— »Т, 3! т-ре., ц [Р «Е),О! у! [Р 1.
а., 6) [Т вЂ » Р а Т, 6] [т Р., 6] [т Р'т., О! [Е Т ]Е,О1 [Е т., О] вв [Р— »а, Ц [т Р. т,ц «т Р.,ц [Š— Т. +Е, Ц [Š— »Т, Ц [Р— [Е.) О! в'5 [Р (Е), 01 [Т вЂ” Р вТ, О] [Т вЂ” »Р, 61 [Е т+Е,О1 [Š— » Т., О] ГЛ. >. ОБЩИЕ МЕТОДЫ СИНТАКСИЧГСКОГО АНАЛИЗА 4 2. ТАБЛИЧИЬШ МБТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА Теорема 4.0. В списке разбора, построснног> алгоритмом 4,5, [А -- и р, >] принадлгжит 1 тогда и п>олько тогда, когда >х=.>'а>„...
ат и существуют такис цепочки у и д, ч>по 5=>'уА6 и у=>'и, ... аи До к аз а тел ьств о. Необходиг>ость. Зту часть теоремы докажем индукцией по числу ситуаций, которые включаются в 1„, 1„..., 1, до того, как в 1т включается [Л вЂ” а [1, >]. Для доказательства базиса (здесь это будет 1,) заметим, что а=>" с для каждой ситуации, включенной в !„так что 5=>" уА6 при у — с. Для доказательства шага индукции допустим, что список 1, уже построен и предположение индукции верно для всех ситуаций, включенных в списки 1; при >Б.1'. Пусть [А — а р, 1] включается в 1, по правилу (4). То>да а=и'а> и [А — а' аур, >] входит в 1,, По предположению индукции й'=>" а».>...
а, и существуй>т такие цепочки у' и 6', что5=-.'>'у ЛЬ' и у' >'а,...а;, Отсюда следуст, что и = >х'а~ — >*а;,, ... и, и нужное утверждение выполняется при у=у' и 6= 6'. Пусть теперь [А — а (1, >"1 включается по правилу (5). Тогда >Б- >х'В для некоторого В61з' и [А- м' Вр, >] входит в 1А для некоторого >г. Кроме того, [В т), й] входит в 1, для некоторой цепочки >1 Е ()Ч 1) Х)'.
По предположению индукции >1 =.>' аА„, ... ат и а' =.>'а>„... а„. Поэтому а =а'В =.>*о;, ... а,. В силу того же предположения существуют такие у' и 6', что 5=>*у'АЬ' и у'=>" а, ... ан Остальная часть нужного нам утверждения выполняется опять при у =у' и 6=ЬГ. В последнем случае, когда [А — >х [>, >] включается по правилу (6), а —.-с и > — 1. Злемептарную проверку нужного утверждения предоставляем читателю, так что первую часть теоремы считаем доказанной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
