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

4.2.2. С помощью алгоритма 4.4 получите левые разборы для тех цепочек из упр. 4.2.1, которые принадлежат языку L{G).

4.2.3. С помощью алгоритма 4.5 постройте по грамматике G из упр. 4.2.1 списки разбора для цепочек из этого же упражнения.

4.2.4. С помощью алгоритма 4.6 постройте правые разборы для тех цепочек из упр. 4.2.1, которые принадлежат языку

4.2,5- Пусть грамматика G задана правилами 5 -> 551 й. С помощью алгоритма 4.5 постройте несколько списков из последовательности /о, /i, ... для входной цепочки аа ... . Сколько элементарных операций требуется для вычисления ?

4.2.6. Докажите теорему 4.6.

4.2.7. Докажите, что алгоритм 4.4 порождает левые разборы.

4.2.8. Дополните доказательство георемы 4.9 (необходимость условия).

4.2.9. Покажите, что для произвольной КС-грамматики алгоритм Эрли заканчивает работу за время 0().

4.2.10. Дополните доказательство леммы 4.6.

4.2.11. Для теорем 4.10-4.12 опищите разумное множество элементарных операций.

4.2.12. Докажите теорему 4.10.

4.2.13. Докажите теорему 4.11.

4.2.14. Покажите, что алгоритм 4.6 порождает правые разборы.

4.2.15. Модифицируйте алгоритм 4.3 так, чтобы он работал для КС-грамматик не в нормальной форме Хомского. Указание: Элемент tj должен содержать не только нетерминалы Л, из которых выводится а,-... aify, но также и некоторые подцепочки правых частей правил, из которых выводится а... Uif--

*4.2.16. Покажите, что для линейных грамматик можно модифицировать алгоритм 4.3 так, чтобы он заканчивал работу за время O(tt).

*4.2.17. Можно модифицировать алгоритм 4.3, используя „заглядывание вперед* на йО символов. По данной грамматике G и входной цепочке waa.. ... а„ будем строить таблицу разбора Т так, что содержит А тогда и только тогда, когда

(1) 5=Ф*аЛх,

(2) Л+а, ...G,.y i,

(3) fl/4-A+y4l • • - «/4.y4A-i = FIRST W.

Таким образом, Л помещается в ячейку tj при условии, что k входных символов, расположенных справа от могут

законно появиться после Л в некоторой выводимой цепочке. Алгоритм 4.3 „заглядывает вперед" на О символов. Модифицируйте алгоритм 4.3 так, чтобы он заглядывал вперед на 1 символов. Какова временная сложность такого алгоритма?

*4.2.18. Можно и алгоритм Эрли модиф1гдировать так, чтобы он использовал заглядывание вперед. При этом ситуации будут иметь вид [Л-а-р, (, и], где и-„увиденная впереди" цепочка длины k. Эта ситуация включается в список /у, только если существует вывод 8=>*уАни, где у=5>*а ... а, а=*ау ... а и FlRST/(Pw) содержит aj+y ...aj+. Доведите до конца модификацию алгоритма Эрли, включающую заглядывание вперед, и затем исследуйте временную сложность полученного алгоритма.

4.2.19. Модифицируйте алгоритм 4.4 так, чтобы он порождал правые разборы.

4.2.20. Модифицируйте алгоритм 4.6 так, чтобы он порождал левые разборы.

4.2.21. Покажите, что можно модифицировать алгоритм 4.4 так, чтобы он порождал разбор за линейное время, если при построении таблицы разбора каждый нетерминал А tij снабдить указателями, дающими те нетерминалы Bt,, и С tifjj, которые привели к тому, что на щаге (2) алгоритма 4.3 нетерминал А был помещен в ячейку tj.

4.2.22. Покажите, что если модифицировать алгоритм 4.5, включив в него для каждой ситуации указатели, дающие те Ситуации, которые привели к тому, что данная ситуация была Включена в список, то правый (или левый) разбор можно получить по списку разбора за линейное время.

4.2.23. Модифицируйте алгоритм 4.6 так, чтобы он работал для произвольных КС-грамматик (включая грамматики с циклами). Указание: Введите в списки указатели, как в упр. 4.2.22.

4.2.24. Каково максимальное число ситуаций, которые могут появиться в списке /у в ходе работы алгоритма 4.5?

*4.2.25, Говорят, что грамматика G имеет конечную степень неоднозначности, если существует такая константа k, что любая Цепочка wEL{G) имеет не более k различных левых разборов. Покажите, что алгоритм Эрли тратит время 0{п) для любых грамматик, имеющих конечную степень неоднозначности.

Открытые проблемы

Мало что известно о том, какое на самом деле необходимо время для синтаксического анализа произвольной КС-грамматнки.



Фактически нет хорошей верхней оценки времени, требуемого для распознавания цепочек из L{G) для произвольной КС-грамматики G, не говоря уже о разборе. Поэтому предлагаем следующие открытые проблемы п области исследования.

4.2.26. Существует ли верхняя граница, меньшая чем 0{п), для времени распознавания произвольного КС-языка на некоторой разумной модели машины с произвольным доступом к памяти или на многоленточной машине Тьюринга

4.2.27. Существует ли лучшая верхняя граница, чем О(п-), для времени распознавания однозначных КС-языков?

Проблемы для исследования

4.2.28. Найдите КС-язык, который нельзя распознать за время / (/?) на машине с произвольным доступом к памяти или машине Тьюринга (последнее сделать легче), где /(п) растет быстрее п, т. е. lim [n/f (п)) = 0. Можете ли Вы указать КС-язык,

который, по-видимому, требует времени для распознавания больше, чем О (п") (даже если Вы не умеете это доказать)?

4.2.29. Найдите широкий класс КС-грамматик, для которых разбор с 1ЮМ0щью алгоритма Эрли возможен за линейное время. Найдите широкий класс неоднозначных грамматик, для которых разбор с помощью алгоритма Эрли возможен за время О(п-). (Отметим, что в первом из этих классов содержатся все детерминированные языки.)

Упражнения на программирование

4.2.30. Для одной из грамматик, данных в приложении, постройте синтаксический анализатор, использующий алгоритм Эрли.

4.2.31. Постройте программу, которая воспринимает в качестве входа произвольную КС-грамматику и выдает для нее анализатор, использующий алгоритм Эрли.

Замечания по литературе

Алгоритм 1.3 был независимо изобретен несколькими авторами. В книге Аейса [1967] излагается одна из версий этого алгоритма, которая приписывается там Дж. Коку.

Янгер [1967] с помощью алгоритма 4.3 показал, что временная сложность проблемы принадлежности для КС-языков не больше О Аналогичный алгоритм приведен в работе Касами [1965]. Алгоритм 4.5 описан в диссертации Эрли [1968]. В работе Касами и Тории [1939] сообщается об алгоритме, анализирующем однозначные КС-грамматики за время О («-).

) Прямо в таком виде эта проблема решена в работе Валианта [1975], где доказана верхняя оценка О (я"-). Неизвестно, однако, можно лн еще понизить эту оценку. (См, также [Грэхем и др., 1976].) -Ярл*. перев.

ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ БЕЗ ВОЗВРАТОВ

В гл. 4 излагались алгоритмы с возвратами, позволяющие моделировать недетерминированные левые и правые анализаторы для широкого класса контекстно-свободных грамматик. Однако оказалось, что в некоторых случаях такое моделирование с точки зрения затрат времени слинп<ом расточительно. В этой главе мы рассмотрим классы КС-грамматик, для которых можно построить эффективные анализаторы, расходующие на обработку входной цепочки длины п время сп и память с/?, где и - малые константы.

За эту эффективность приходится расплачиваться тем, что пи один из классов грамматик, для которых можно строить такие э4)фективные анализаторы, не порождает все КС-языки. Однако похоже, что эти ограниченные классы грамматик адекватно отражают все синтаксические черты языков программирования, обычно определяемых с помощью КС-грамматик.

Излагаемые в этой главе алгоритмы разбора характеризуются тем, что входная цепочка считывается один раз слева направо и процесс разбора полностью детерминирован ). Фактически мы просто ограничиваем класс КС-грамматик так, чтобы для грамматик из этого класса всегда можно было построить детерминированный левый или правый анализатор.

Классы грамматик, рассматриваемые в данной главе, содержат

(1) LL (й)-грамматнки, для которых левый анализатор работает детерминированно, если позволить ему принимать во внимание k входных символов, расположенных справа от текущей входной позиции 2);

(2) LR ()-грамматпки, для которых правый анализатор работает детерминированно, если позволить ему „видеть" k входных символов, расгюложепных вслед за текущей входной позицией;

Существенно еще и то, что рабочая память представленных здесь алгоритмов-это одни магазин, а не, скажем, лента машины Тьюринга или два ззта.- Прим. перев.

) Это ие приводит к расширению понятия ДМП-преобразователя, так ак k „увиденных впереди символов хранятся в конечиол памяти управляющего устройства.



Идею, лежащую в основе понятия ЕЕ(й)-грамматики, интуитивно можно объяснить так: если мы строим левый вывод S:=±>}w и уже построили 5=Ф( а,. . .=> а. так, что а/=;гг;, то

можно построить т. е. сделать очередной шаг вывода, видя

только законченную часть цепочки и „еще немножко", а именно следующие k входных символов цепочки w. (Заметим, что законченная часть цепочки сс - является префиксом цепочкн w.) Важно отметить, что если мы не видим всей цепочки kj, когда строится то фактически не знаем, какая терминальная цепочка в конечном счете выводится из. 5. Таким образом, нз условия,


Рнс. 5.1, Дерево вывода цепочки wxy,

налагаемого на ЕЕ(й)-грамматику, вытекает, чтоа по существу не зависит (не считая следующих k терминальных символов) от того, что выводится из незаконченной части цепочки а.

В терминах деревьев этот процесс выглядит так: дерево вывода цепочки wxy в ЬЬ()-грамматике строится, начиная с корня, детерминированно сверху вниз. А именно, если уже построено частичное дерево вывода с кроной wAa, то по ес и первым k символам цепочки ху можно сказать, какое правило применить к А. Набросок завершенного дерева показан на рис. 5.1.

Напомним, что в гл. 4 для КС-грамматики G(N, 2, Р, 5) была определена функция FIRSTfc(a) (где k - целое число иаб (N U2)*), равная {wX* \ либо ш < й и а -qw, либо \ w\ = k и a*Qwx для некоторого х\. Мы будем опускать k и G, если зго не вызовет недоразумений, и писать просто FIRST.

Если а состоит только из терминалов, то FIRST,;(a) = {ш}, где оу - это первые k символов цепочки а при \a\k и ш = а Ри а<. В этом случае будем писать FIRST/(a) гс), а не {ш}. Значение FIRSTg(a) легко находится по заданной грамматике G. Соответствующий алгоритм мы опишем в разд. 5.1.6.

(3) Грамматики предшествования, для которых правый анализатор может находить основу правовыводимой цепочки, учитывая только некоторые отношения между парами ее смежных символов.

5,1. 11()-ГРДММАТИКИ

В этом разделе будет изучен самый широкий „естественный" класс левоанализируемых грамматик, а именно класс LL ()-грамматик.

5.1,1, Определение 11{)-грамматики

Для начала предположим, что G- (N, 2, Р, 5) -однозначная грамматика и -оДз. . - цепочка из Тогда существует

единственная последовательность левовыводимых цепочек а, для которой Sa, а/р.=а,. при 0(</п н

aw. Последовательность р„/7, .. .р.-левый разбор цепочкн w.

Допустим, что мы хотим найти этот левый разбор, просматривая W один раз слева направо. Можно попытаться сделать это, строя последовательность левовыводимых цепочек а, а, ...

Если ciiUy ... ujA, то к данному моменту анализа мы уже прочли первые / входных символов и сравнили их с первыми / символами цепочки а,-. Было бы желательно определить а,+, зная только ... Qj (часть входной цепочки, считанную к данному моменту), несколько следующих входных символов ij+ij+z- Ъ+к j некоторого фиксированного k) и нетерминал А. Если эти три фактора однозначно определяют, какое правило надо применить для развертки нетерминала Л, то «..1 точно определяется по а. и k входным символам ujuj .. .йу+ь-

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

Определение. Пусть а -хр-такая левовыводимая цепочка в грамматике G~(N, 2, Р, 5), что х£Х*, а р либо начинается нетерминалом, либо пустая цепочка. Будем называть х законченной чдстью цепочки а, а незаконченной частью. Границу между X и р будем называть рубежом.

Пример 5.1. Пусть а = аЬасАаВ. Тогда abac-законченная часть цепочки а, ЛаВ -незаконченная часть. Если ааЬс, то ai)c-законченная часть н е -незаконченная часть, а рубежом для них служит правый конец цепочки. □





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.0046