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

рации с помощью конечного числа разумно определенных элементарных операций.

**4.1.14. Найдите необходимое и достаточное условие, которому должна удовлетворять грамматика, чтобы алгоритм 4.2 работал на ней без возвратов. То же для алгоритма, модифицированного, как в упр. 4.1.12.

4.1.15. Найдите грамматику без циклов н без е-правил, для которой алгоритм 4.2 тратит экспоненциальное время.

4.1.16. Улучшите границу, указанную в лемме 4.4, для грамматик, не содержащих е-нравил.

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

Определеиие. Опишем в общих чертах язык программирования, на котором можно записывать недетерминированные алгоритмы. Назовем этот язык НДФ (недетерминированный Фортран), потому что он состоит из операторов, подобных операторам Фортрана, плюс оператор CHOICE (rti, ...,rt,), где /г>2 и п, -

номера операторов.

Чтобы определить смысл программ в языке НДФ, мы постулируем существование интерпретатора, способного выполнять любое конечное число программ вкруговую (т. е. работать с каждой программой но очереди в течение фиксированного числа машинных операций). Смысл обычных операторов Фортрана предполагается известным. Однако если выполняется оператор CHOICE (rt, ...,nJ), то интерпретатор изготавливает k копий программы и всей ее области данных (т. е. текущих значений переменных). Управление передается оператору в i-й копни программы (lik). Весь выход выдается на одно устройство печати и весь вход поступает с одного читающего устройства (лучше считать, что перед выполнением первого оператора CHOICE весь вход уже прочитан).

Пример 4.5. Следующая программа на языке НДФ печатает один или более раз сообщение НЕ ПРОСТОЕ, если ее входом служит не простое число, и не печатает ничего, если вход - простое число:

READ N 1-1

С ВЗЯТЬ ЗНАЧЕНИЕ I БОЛЬШЕЕ 1

1 I-I + 1 CHOICE (1, 2)

2 IF(I .EQ. N) STOP

346 "

С ОПРЕДЕЛИТЬ ЯВЛЯЕТСЯ ЛИ I С ДЕЛИТЕЛЕМ N НЕ РАВНЫМ N IF((N/I)*I .NE. N) STOP WRITE (НЕ ПРОСТОЕ) STOP □

*4.1.18. Напишите программу на НДФ, печатающую все решения „проблемы восьми ферзей" (выбрать на шахматной доске восемь полей так, чтобы никакие два из них не лежали на одной горизонтали, вертикали или диагонали).

*4.1.19. Напишите программы на НДФ, моделирующие левый и правый анализаторы.

Было бы хорошо, если бы существовал алгоритм, определяющий для данной программы на НДФ, будет лн она на каком-нибудь входе работать бесконечно. К сожалению, эта проблема неразрешима ни для Фортрана, ни для какого другого достаточно мощного языка программирования. Однако на этот вопрос можно ответить, если предположить, что ветвлением в программе (связанным с операторами IF и GOTO, а не с CHOICE) управляют не значения переменных программы, а некий „демон", который пытается заставить программу работать бесконечно. Назовем программу на НДФ останавливающейся, если ни для какого входа не существует последовательности ветвей и недетерминированных выборов, заставляющей какую-нибудь копию программы выполнить больше операторов, чем некоторое фиксированное число, причем это число зависит от числа входных перфокарт, предоставленных для данных. (Предполагается, что если программа пытается читать, а доступные для этого данные отсутствуют, она останавливается.)

*4.1.20. Постройте алгоритм, определяющий, останавливается ли программа на НДФ при условии, что переменные циклов DO никогда не уменьшаются).

*4.1.21. Дайте алгоритм, который по останавливающейся программе иа НДФ строит эквивалентную ей программу на Алголе. Под „эквивалентной программой" мы должны понимать программу на Алголе, выдающую результаты в одном из тех порядков, в которых их может выдать программа на НДФ (определенный Порядок для программы на НДФ не задан). Алгол предпочитается Фортрану из-за того, что здесь очень удобно применить рекурсию,

) Так как для Фортрана без оператора DO любое нетривиальное свойство программ неразрешимо, возникает сомнение, можно ли неясное определение останавливающейся ГТДФ-программы истолковать так, чтобы это упражнение имело решение.-Ярил*, перев.



(5) Р -(£)

(6) Е-а

Недетерминированным анализатором по левому участку для грамматики G будет МП-преобразователь

М({д}, 2, NXNUNUS, {1, 2, ...,6}, б, д, £. 0) где б следующим образом определяется для всех Л€N:

(1) (а) б(, е, [Л, Е]} содержит (д, +Г[Л, £], 1),

(б) 8{д, е, [А, Т]) содержит (д, [Л, £], 2),

(в) б (q, е, [Л, F]) содержит [д, f Г[Л, Г], 3) и (д, [Л, Г], 4),

(г) 8(д,е,А) = {{д, ()[Л,Р],5), (д,а[А,Е1 6)}.

(2) 6 (д, е, [Л, Л]) содержит (7, е, е).

(3) б (д, а, а) = {{д, е, е)} для всех а € 2.

Устроим разбор входной цепочки а \ а -\- а с помощью УИ. Дерево вывода этой цепочки показано на рис. 4.7. Так как

Рис. 4.7. Дерево вывода цепочки а\а-\-а,

МП-преобразователь М имеет только одно состояние, оно в дальнейшем не указывается. М начинает работу в конфигурации

(aja-ffl, £, е)

Поскольку второе правило из (1г) применимо (как и первое), М может перейти в конфигурацию

(аа + а, а[Е, Р], 6)

Здесь с помощью правила 6 порожден левый участок а. Символ а сравнивается затем с текущим входным символом, и это дает

(ta + a, [£, Р], 6)

Теперь Можно воспользоваться первым правилом нз Пв) и получить г г- V /

(ta-fa, \Т[Е, Г], 63)

4.1.22, Постройте по КС-грамматике G = (N, 2, Р, S) такую КС-грамматику что £(G) = 2* и если SjqW, то Sn=GW.

По грамматике можно построить МП-преобразователь (верх его магазина будет расположен слева), который ведет себя как недетерминированный анализатор по левому участку для этой грамматики. Этот анализатор будет использовать в качестве магазинных символов нетерминалы, терминалы и специальные символы вида [Л, В], где Л и В - нетерминалы.

Появляющиеся в магазине терминалы и нетерминалы служат „целями", которые должны распознаваться сверху вниз. В символе [Л, В] нетерминал Л-текущая цель, которую нужно распознать, а В - нетерминал, только что распознанный снизу вверх. По КС-грамматике G = (N, 2, Р, 5) построим МП-преобразователь М={{д\, 2, NxNuNUS, Д, 6, д, 5, 0), который будет анализатором по левому участку для G. Здесь А = {1, 2, р} - множество номеров правил, а 6 определяется так:

(1) Допустим, что Л--.-а-правило из Р с номером i.

(а) Если а имеет вид бр, где J5€N, то 6{д, е, [С, В]) содержит [д, р[С, Л], () для всех С 6 N. Здесь предполагается, что левый участок В уже распознан снизу вверх, так что символы цепочки р становятся целями, которые нужно распознать сверху вниз. Как только цепочка р будет распознана, будет распознан н нетерминал Л.

(б) Если а не начинается нетерминалом, то 6 (д, е, С) содержит (9, а [С, Л], i) для всех CN. Здесь нетерминал Л будет распознан, как только будет распознана цепочка а.

(2) б(<7, е, [Л, Л]) содержит (д, е, е) для всех Л€N. Здесь вхождение цели Л, которой мы занимались, уже распознано. Если это вхождение Л не является левым участком, то [Л, Л] устраняется нз магазина и это означает, что данное вхождение Л было той целью, которую мы искали.

(3) 6 (7, а, а) = {(д, е, е)} для всех а€ 2. Здесь текущей целью служит терминальный символ, совпадающий с текущим входным символом. Будучи распознанной, эта цель устраняется.

МП-преобразователь М определяет перевод {(ш, n)\wL(G) и п - разбор цепочки ш по левому участку}.

Пример 4.6. Рассмотрим КС-грамматику G = (N, 2, Р, S) с правилами

(1) ЕЕ + Т

(2) Е~Т

(3) T~FT

(4) T~F



ГЛ, 4, ОБЩИЕ МЕТОДЫ СИНТДКСПЧРХКОГО АНАЛИЗА

Здесь левый участок правила T-F\T будет распознан, как только найдутся f и Т. После этого можно перейти в конфигурации

(а + а, Г [Я, П, 63)Ь(й+й, а[Т, F][E, Г], 636)

[Т, F][E, П 636) [-{-ha, [Т, Т][Е, Т], 6364)

В данный момент Т служит текущей целью и найдено вхождение Т, которое НС является левым участком. Поэтому, применяя (2), можно стереть эту цель и получить

( + [Е, Т], 6364)

Продолжая в том же духе, получаем последовательность конфигураций

[Е, El 63642+Т[Е, Е], 636421) \-(а, Т[Е, £], 636421) \-(а, а[Г, £][£, £], 6364216)

{Т. F][E, Е], 6364216) \-(е, [Г, Г][£, £], 63642164) \-(е, [£, £], 63642164) \-(е, е, 63642164) □

*4.1.23. Покажите, что описанная выше конструкция дает для КС-грамматики G недетерминированный анализатор по левому участку.

4.1.24. Постройте алгоритм разбора по левому участку с возвратами.

Пусть G = (N, 2, Р, S) -КС-грамматика, не содержащая правил с правыми частями длины О и 1. (Такая грамматика существует для каждого КС-языка L{w\wEX* и jiy2}. Дли G можно построить недетерминированный правый анализатор типа „перенос-свертка", у которого каждый символ магазина является парой вида (X, Q), где X U 2 U {$}($-правый концевой маркер магазина), а Q-множество правил из Р, причем для каждой правой части правила указаны всевозможные префиксы, которые могли быть распознаны к данному моменту разбора (это делается с помощью точек, поставленных между некоторыми символами правых частей). Перед символом Х- в правиле Л-ХДз...Х„ точка ставится тогда и только тогда, когда Xi...X,- j - суффикс цепочки символов грамматики, находящейся в магазине.

Шаг переноса можно сделать, если текущий входной символ служит продолжением некоторого правила. В частности, его можно сделать всегда, когда Л->а принадлежит Р, а текущий входной символ принадлежит FlRSTi(a).

ЗАМЕЧАНИЯ ПО ЛИТЕРАТУРЕ

Шаг свертки можно сделать, если достигнут конец правой части правила. Допустим, что таким правилом является Л-а. Чтобы сделать свертку, удалим из верхней части магазина а символов. Если теперь верхним символом магазина стал (X, Q), пишем в магазин (Л, Q), где Q вычисляется по Q в предположении, что А распознан, т. е. Q образуется из Q переносом через Л всех точек, стоящих непосредственно слева от Л, и добавлением точек па левых концах правых частей, если их там еще не было.

Пример 4.7. Рассмотрим грамматику S~Sc\ab и входную цепочку аЬс. Вначале в магазине анализатора находится символ ($, Qo), где Qf = S-Sc\-ab. Затем можно перенести первый входной символ и записать в магазин (а, Q), где Qy =

-у *Sc \ *a*b. Здесь либо можно находиться в начале правил S-ySc\ab, либо можно считать, что прочитан первый символ а правила S-*-аЬ. Перенося следующий входной символ Ь, запишем в магазин {Ь, Q), где S*Sc\ *аЬ. Затем можно сделать свертку, используя правило S--аЬ. Магазин будет теперь содержать ($, Qo)(5, Q,), где QS- -S-cl - ab, □

Домёлки предложил реализовать этот алгоритм с помощью двоичной матрицы М, представляющей правила, и двоичного вектора V, представляющего возможные позиции в каждом правиле. В описанном выше алгоритме можно вместо Q брать вектор V. Каждый новый вектор в магазине легко вычисляется по М и текущему значению вектора V с помощью простых поразрядных двоичных операций.

4.1.25. Используйте алгоритм Домёлки для определения возможных сверток в алгоритме 4.2.

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

Многие ранние компиляторы компиляторов и синтаксически управляемые компиляторы использовали недетерминированные алгоритмы разбора. Варианты методов нисходящего разбора с возвратами использовались в компиляторе компиляторов Брукера и Морриса [Розен, 19676] и в системе построения J°Jl™3TopoB МЕТАШорре, 1964]. В системе символьного программирования UJCjENT недетерминированный нисходящий анализатор моделируется параллельным выполнением всех допустимых последовательностей тактов [Рейнольде, 1965]. Методы нисходящего разбора с возвратами применялись также для синтаксического анализа естественных языков [Куно и Эттиигер, 19G2J.

Одним нз самых ранних опубликованных алгоритмов разбора был алгоритм Айронса [1961], работавший по существу методом разбора по левому участку. Обзоры ранних методов разборасделаны Флойдом [19[i46], Читэмом и Сэттли [19G4] и Грнффитсом и Петриком [1965].

Иия Пб8] описывает нисходящий алгоритм, в котором для умеиьше-нет употребляются первые и последние символы, выводимые из

Флоп" Недетерминированные алгоритмы рассматриваются в работе





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