Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 76
Текст из файла (страница 76)
4.2.1, которые принадлежат язык 1. (6 42" ..о. Пусть грамматика 6 задана правилами В- ВВ', С помо ью лг и — 1а. овательн щ ю алгоритма 4.5 постройте несколько списков из после- д тельности 1„ 1„ ... для входной цепочк . .... С элемента и аа.... колько нтарных операций требуется для вычисления 1а? 4.2.6. Докажите теорему 4.6.
4.2.7. Докажит, Д жите, что алгоритм 4.4 порождает левые разборы, 4.2.8. Д условия). ... Дополните доказательство теоремы 4.9 (н об нео ходимость 4.2.9. Покажи те, что для произвольной КС-грамматики алго- ритм Эрлп заканчивает работу за время 0(п'). 4.2.10. ..10.
Дополните доказательство леммы 4.6. 4.2.11. Для тео м 4, ре 4,10 — 4.12 опишите разумное множество элементарных операций. 4.2.12. Докажите теорему 4.10. 4.2.13. Докажите теорему 4.!1. 4.2.14. Покажите, что ал р , горитм 4.6 порождает правые разбо ы. 4.2.15. Модифицируйте алгоритм 4.3 так, чтобы ои работал для КС-грамматик не в нормальной форме Х . У. Элемент 7 ол ме омского. Указание: О должен содержать не только нетерм . А, которых выводится а ...
а раиналы, из я аа... а„„но также и некоторые подие- почки правых частей правил, из кото рых выводится а ... а * а '/ — а' для линейных грамматик можно моди- 4.2.16. Покажите, что время 0(п'). фицировать алгоритм 4.3 так, чтобы ь он заканчивал работу за *4.2.17. .2.17. Можно модифицировать алгоритм 4.3, заглядывание вп сред" на й= 0 символов. По данной гшмма- Р о а так, что 76 содержит А тогда и только тогда, когда (1) В=>'аАх, (2) А =Ьа аа... аа,1;, (3) аа ааа+ „,...
аа,,»; —— Р1ЙБТ»(х). Таким образом, А помещается в ячейку 1;, при условии, что й вхо кодных символов, расположенных справа от аа„„могут „аконпо появиться после А в некоторой выводимой цепочке. йлгоритм 4.3 „заглядывает вперед" на 0 символов. Модифициуите алгоритм 4.3 так, чтобы он заглядывал вперед на й-. 1 символов, Какова временная сложность такого алгоритма? *4.2.18. Можно и алгоритм Эрли модифицировать так, чтобы ои использовал заглядывание вперед. При этом ситуации будут иметь вид [А — а (), а, и|, где и — „увиденная впереди" цецочиа длины й. Эта ситуация включается в список 17 только если существует вывод В=>чуАии, где у=о'а,...
а,, а=~" аа„,... а, и Г!КБТ фи) содержит а?, .., а,„. Доведите до конца модификацию алгоритма Эрли, включающую заглядывание вперед, и затем исследуйте временную сложность полученного алгоритма. 4.2.19. Модифицируйте алгоритм 4.4 так, чтобы он порождал правые разборы. 4.2.20. Модифицируйте алгоритм 4.6 таи, чтобы он порождал левые разборы. 4.2.21. Покажите, что можно модифицировать алгоритм 4.4 так, чтобы он порождал разбор за линейное время, если при построении таблицы разбора каждый нстермипал А 6171 снабдить указателями, дающими те нетерминалы В 6!а» и С 611„ которые привели к тому, что на шаге (2) алгоритма 4.3 нетерминал А был помещен в ячейку 1;, 4.2.22. Покажите, что если модифицировать алгоритм 4.5, включив в пего для каждой ситуации указатели, дающие те сиауации, которые привели к тому, что данная ситуация была включена в список, то правый (или левый) разбор можно получить по списку разбора за линейное время. 4.2.23.
Модифицируйте алгоритм 4.6 так, чтобы он работал для произвольных КС-грамматик (вклаочая грамматики с циклами). Указание; Введите в списки указатели, как в упр. 4.2.22. 4.2.24. Каково максимальное число ситуаций, которые могут появи.гься в списке 1 в ходе работы алгоритма 4.5? *4.2.25. Говорят, что грамматика 6 имеет конечную степень неоднозначноспаи, если существует такая константа й, что любая цепочка иа61.
(6) имеет не более 7а различных левых разборов. Покажите, что алгоритм Эрли тратит время 0(п') для любых грамматик, имеющих конечную степень неоднозначности, Открытие проблемы Мало что известно о том, какое на самом деле необходимо ~рема для синтаксического анализа произвольной КС-грамматики. ГЛ. 4. ОБЩИЕ МЕТОДЫ СИГПАКСИЧЕСКОГО АНАЛИЗА Фактически нет хорошей верхней оценки времени, требуемого для распознавания цепочек из 7 (б) для произвольной КС-грамматики О, не говоря уже о разборе.
Поэтому предлагаем следующие открытые проблемы и области исследования. 4.2.26. Существует ли верхняя граница, меньшая чем 0(п'), для времени распознавания произвольного КС-языка на некоторой разумной модели машины с произвольным доступом к памяти или на мпоголенточной машине Тьюринга' )? 4.2.27. Существует ли лучшая верхняя граница, чем 0(не), для времени распознавания однозначных КС-языков? Проблемы для исследования.
4.2.28. Найдите КС-язык, который нельзя распознать за время 7(а) на машине с произвольным доступом к памяти или машине Тьюринга (последнее сделать легче), где )'(и) растет быстрее а, т. е. [пп (а[)'(и)) —.-О. Можете ли Вы указать КС-язык, и который, по-видимому, требует времени для распознавания больше, чем 0(п') (даже если Вы не умеете это доказать)? 4.2.29. Найдите широкий класс КС-грамматик, для которых разбор с помощью алгоритма Эрли возможен за линейное время.
Найдите широкий класс неоднозначных грамматик, для которых разбор с помощью алгоритма Эрли возможен за время 0(а'), (Отметим, что в первом из этих классов содержатся все детерминированные языки.) Уп раж нения на п рограмми рован не 4.2.30.,[[ля одной нз грамматик, данных в приложении, постройте синтаксический анализатор, использующий алгоритм Эрли.
4.2.31. Постройте программу, которая воспринимает в качестве входа произвольную КС-грамматику и выдает для нее анализатор, использующий алгоритм Эрли. Замечания по литературе Алгарятч 4.3 был пеззвяснмо нзобретен несколькнмн звторзмн. В книге Хейсз [1967) нзлзгзегся одне нз верснй этого алгоритма, которая прнпнсывзегся тэл1 Дж. Коку. Янгер [1967) с помощью злгорнтмз 4.3 повязал, чта временная сложяость проблемы прннэдлежнастн для КС-языков не больше О[из).
Анзлопщ. ный злгарнтм прнведен в работе Кзгзмн [1955). Алгоритм 4.5 описан в дне. сертзцнн Эрлн [И66] В работе Кзсзмн н Торна [!939) сообщзсгсн об злгорнгме, знэлнзнрующем однознзчныс КС-грзммзгнкн зз время 0(пз). ') Прямо в таком виде зтз проблема решена в работе Взлнзнтз [1975), где докэззнз верхняя оценка О (нл.е[), Неизвестно, однако, можно лн еще поннзнгь эту оценку. (См. также [Грэхем н дйо 1976).) — Прим, перез.
ОДНОПРОХОДНЫИ СИНТАКСИЧЕСКИЙ АНАЛИЗ БЕЗ ВОЗВРАТОВ В гл. „, 4 злагались алгоритмы с возвратами, позволяющие ы моделировать неде недетермпнированвые левые и правые анализатор для широког о класса контекстно-свободных грамматик. Однако оказалось, что в н в некоторых случаях такое моделирование с точки зрения затр рат времени слигпколз расточительно. В этой главе мы рассмотри м классы КС-грамматик, для которых можно постоить эффективные анализаторы, расходующне на обработку входной цепочки длины п время его и память с,п, где с, и с, — малые константы. За эту эффективность приходится расплачиваться тем, что ни один из классов грамматик, для которых можно строить такие эффективные анализаторы, не порождает все КС-языки.
Од а похоже, что эти ограниченные классы грамматик адекватно отражают все синтаксические черты языков программирования, обычно определяемых с помо1цью КС-грамматик. Излагаемые в этой главе алгоритмы разбора характеризуются тем, что входная цепочка считывается один раз слева направо и процесс разбора полностью детерминирован' ). Фактически мы просто ограничиваем класс КС-грамматик так, чтобы для грамматик из этого класса всегда можно было построить детерминированный левый или правый анализатор. Классы грамматик, рассматриваемые в данной главе, содержат (!) [Л. (й)-грамматики, для которых левый анализатор работает детерминированно, если позволить ему принимать во внимание й входных символов, расположенных справа от текущей входной позиции '); (2) [.К ()г)-грамматики, для которых правый анализатор работает дете минированно, если позволить ему „видеть" й входных символов, расположенных вслед за текущей входной позицие"; ози и и' з сгр ряпков — это одни магазин, з не, скэжем, ленте машины Тьюринга нлн двз мзгззннз.— Прил перев з) Вто не прнваднт к рзсшнренню понятия дМП-преобрззовзтеля, тзк "ек А чувнденных вцередн' снмвалов хранятся в конечной пэмнтн управляюнгего устройстве.
373 Гл. 3, ОднОпРОходный синтл1ссичасхий Анализ Ввз ВозвРАТОВ З ! !! (А1 ГРЛММА1ИКИ (3) грамматики предшествования, для которых правый ана. лнзатор может находить основу правовыводимой цепочки, , учитывая только некоторые отношения между парами ее смежных символов. 5Л. П. Щ-ТРАММАТИКИ к с В этом разделе будет изучен самый широкий „естеств н ла с левоанализируемых грамматик, а именно класс 1.1 тественныи" грамматик. ласс (й) 5ЛЛ. Определение ЩФ)-грамматики Для начала предположим, что 6 †--(Р(, Х, Р, В) †однозначн грамматика и го=а,а,...а„— цепочка из ь(6).
Тогда су1цествуст единственная последовательность левовыводимых цепочек сс„ ц = Ге. ПОСЛЕданатЕЛЬНОСтв Рер,...Р,— ЛЕВЫЙ раэбвр ЦЕПОЧКИ 1О. ив Допустим, что мы хотим найти этот левый разбор, проев р ая го один раз слева Направо. Можно попытаться сделать это, строя последовательность левовыводимых цепочек а„ц,, ...
...,и . Если ссг — а,, ауА11, то к данному моменту анализа мы уже прочли первые 1 входных символов и сравнили их с первыми 1' символами цепочки ин Было бы желательно определить ц, „зная только а,... а, (часть входной цепочки, считанн ю к данному моменту), несколько следующих входных символов (а, „а е,... а, е„для некоторого фиксированного и) и нетерминал А. Если эти три фактора однозначно определяют, какое правило надо применить для развертки нетермипала А, то а, 1 точно определяется по ц, и й входным символам а а. Г а р мматика, в которой каждый левый вывод обладает этим свойством, называется 1.С(л)-грамматикой.
Мы увид м, каж ой 11. 7екаждой (7е)-грамматики можно построить детерминироваяный левый анализатор, работающий линейное время. Сначала дадим несколько определений. О пределение. Пусть ц=хй — такая левовыводимая цепочка в грамматике 6 — ()ч", Х, Р, В), что хЕХ*, а р либо начинается нетермипалом, либо пустая цепочка. Будем называть х законченной частью цепочки ц, а () — незаконченной частью.
Границу между х и (1 будем называть рубежа,я, Пример 5.1. Пусть ц = аоасАаВ. Тогда аЬас — законченная часть цепочки ц, Аа — незаконченная часть. Если иА цос, то або — законченная часть и е — незаконченная часть а бежом для них служит правый конец цепочки. РУ 374 ядею, лежа ,, ежащую в основе понятия 1Л.(й)-грамматики, интуитивно можно о обьяснить так: если мы строим левый вывод Я =О," го ,„уже построили В=о,ц,=>, ц,=р,...=:,>,цг так, что сс,=Р,"п7, то строить ц, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
