Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 70
Текст из файла (страница 70)
4.1.16. Улучшите границу, указанну4о в лемме 4.4, для грам. матнк, не содержащих е-правил. 4.1.17. Покажите, что если в грамматике О, не содержащей бесполезных символов, есть либо цикл, либо е-правило, то алгоритм 4.2 не будет останавливаться на цепочках, не принадлехгащнх языку ь (6). Определение. Опишем в общих чертах язык программирования, иа котором можно записывать недетерминированные алгоритмы. Назовем этот язык НДФ (недетерминированпый Фортран), потому что он состоит из операторов, подобных операторам Фортрана, плюс оператор СН01СЕ(п„..., пь), где й) 2 и и„..., и„— номсра операторов.
Чтобы определить смысл программ в языке НДФ, мы постулируем существование интерпретатора, способного выполнять любое конечное число программ вкруговую (т. е. работать с каждой программой по очереди в течение фиксированного числа машинных операций). Смысл обычных операторов Фортрана предполагается известным. Однако если выполвяется Оператор СН01СЕ(п„..., и ), то интерпретатор изготавливает й копий программы и всей ее области данных (т. е, текущих значений переменных).
Управление передается оператору и! в гсй копии программы (! (! ~й). Весь выход выдается на одно устройство печати н весь вход поступает с одного читающего устройства (лучше считать, что перед выполнением первого оператора СН01СЕ весь вход уже прочитан). Пример 4.5. Следующая программа на языке НДФ печатает один или более раз сообщение НЕ ПРОСТОЕ, если ее входом служит не простое число, и не печатает ничего, если вход— простое число: КЕА(А !! 1=1 С ВЗЯТЬ ЗНАЧЕНИЕ ! БОЛЬШЕЕ 1 1 1=1+1 СН01СЕ (1, 2) 2 1Г (1,Е(). 4А!) ВТОР 346 С ОПРЕДЕЛИТЬ ЯВЛЯЕТСЯ ЛИ 1 С ДЕЛИТЕЛЕМ ~Х НЕ РАВНЫМ Х 1Г((И~1) я1 .ХЕ. Щ ВТОР ЖР1ТЕ (НЕ ПРОСТОЕ) ВТОР П я4.1.18. Напишите программу иа НДФ, печатающую все решения „проблемы восьми ферзей" (выбрать на шахматной доске восемь полей так, чтобы никакие два нз них не лежали на одной горизонтали, вертикали или диагонали).
*4.1.19. Напишите программы на ПДФ, моделирующие левый и правый анализаторы. Было бы хорошо, если бы существовал алгоритм, определяющий для данной программы на НДФ, будет ли она на каком- нибудь входе работать бесконечно, К сожалению, эта проблема неразрешима ни для Фортрана, ни для какого другого достаточно мощного языка программирования. Однако на этот вопрос можно ответить, если предположить, что ветвлением в программе (связанным с операторами 1Г и СОТО, а не с СН01СЕ) управляют не значения переменных программы, а некий „демон", который пытается заставить программу работать бесконечно.
Назовем программу на НДФ оспгаиавливаюитейся, если ни для какого входа не существует последовательности ветвей и недетерминированвых выборов, заставляющей какую-нибудь копию программы выполнить больше операторов, чем некоторое фиксированное число, причем это число зависит от числа входных перфокарт, предоставленных для данных. (Предполагается, что если программа пытается читать, а доступные для этого данные отсутствуют, она останавливается.) "4.1.20. Постройте алгоритм, определя4ощий, останавливается ли программа на НДФ при условии, что переменные циклов !10 никогда не уменьшаются').
"4.1,21. Дайте алгоритм, который по останавливающейся программе иа НДФ строит эквивалентную ей программу на Алголе. Под Рэквивалентиой программой" мы должны понимать программу на Алголе, выдающую результаты в одном из тех порядков, в которых их может выдать программа на НДФ (определенный порядок для программы на НдФ пе задан). Алгол предпочитается Фортрану нз-за того, что здесь очень удобно применить Р "РР РР ФРФ Й р р РФ Р Р Ю ~рогрямм неразрешимо, возникает сомнение, можно ли неясное определение останавливающейся !!АРФ-прпгрлмрры истолковать так, чтобы эго упражнение имело решение.— Прим. РРРрся. Злг ГЛ, 4, ОЕЩНЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА 4.1.22, Постройте по КС-грамматике 6=(Х, Х, Р, Я) такую КС-грамматику С', что Е(6')=Х* и если Я„=~О4е, то Ви — ->о ю.
По грамматике можно построить МП-преобразователь (верх его магазина будет расположен слева), который ведет себя как .Недетерминированный анализатор по левому участку для этой грамматики. Зтот анализатор будет использовать в качестве ма- газинных символов нетерминалы, терминалы и специальные символы вида [А, В|, где Л и  — нетерминалы. Появляющиеся в магазине терминалы и нетерминалы служат „целями", которые должны распознаваться сверху вниз. В сим- воле [А, В) нетерминал А — текущая цель, которую нужно рас- познать, а  — нетерминал, только что распознанный снизу вверх.
По КС-грамматике 0 = (Х, Х, Р, Я) построим МП-преобразователь М=((д), Х, ХХХХХХХХ, Л, 6. д, Я, 8), который будет ана- лизатором по левому участку для С. Здесь Ь=(1, 2, ..., Р)— множество номеров правил, а 6 определяется так: (1) Допустим, что А- и — правило из Р с номером 4. (а) Если а имеет вид ВР, где ВЕХ, то 6(д, е, [С, В1) содержит (д, 6[С, А1, 4) для всех С 6Х. Здесь предполагается, что левый участок В уже Распознан снизу вверх, так что символы цепочки () становятся целями, которые нужно распознать сверху вниз.
Как только цепочка Р будет распознана, будет распознан н нетерминал А. (б) Если а ие начинается нетермнналом, то 6(д, е, С) содержит (д, а [С, А), 4) для всех С Е Х. Здесь нетерминал А будет распознан, как только будет распознана цепочка а, (2) 6(д, е, [А, Л|) содержит (4), е, е) для всех А ЕХ. Здссь вхождение пели А, которой мы занимались, уже распознано. Если это вхождение А ие является левым участком, то [А, А( устраняется нз магазина и это означает, что данное вхождение А было той целью, которую мы искали. (3) 6(д, а, а)=-((д, е, е)) для всех аЕ Х. Здесь текущей целью служит терминальный символ, совпадающий с текущим входным символом. Будучи распознанной, эта цель устраняется.
МП-преобразователь М определяет перевод ((ю, п)(вЕЦ44) и п — разбор цепочки ю по левому участку). Пример 4.6. Рассмотрим КС-грамматику 6 = (Х, Х, Р, 5) с правилами (1) Е- Е+Т (2) Е- Т (3) Т .Р)Т (4) Т вЂ” Р 34а упражнения (5) Р— (Е) (6) Р— а Педетерминированным анализатором по левому участку для грамматики С будет МП-преобразователь М=((ч), Х, ХХХ() Х() Х, (1, 2, ..., 6), 6, д, Е, 16') где 6 следующим образом определяется для всех Л ЕХ: (1) (а) 6(4, е, ~А, Е1) содеРжит (4, +Т[А, Е|, 1), (б) 6(д, е, А, Т1) содержит (д, [А, Е1, 2), (в) 6(4,е,[А, Р)) содержит (д,(Т[А, Т1,3) и (д,[А, Т(,4), (г) 6 (д, е, А) = ((д, (Е) [А, Р), 5), (су, а [А, Р], 6)).
(2) 6 (д, е, [Л, А1) содержит (д, е, е). (3) 6(д, а, а)=((д, е, е)) для всех аЕХ. Устроим разбор входной цепочки а(а+а с помощью М. Дерево вывода этой цепочки показано на рис. 4.7. Так как у!~ 1 А~ [ 1'! Рис. 4.7. Дерево вывода цепочки а(а+а, МП-преобразователь М имеет только одно состояние, оно в даль- нейшем не указывается, М начинает работу в конфигурации (а(а+а, Е, е) Поскольку второе правило из (!г) применимо (как н первое), М может перейтн в конфигурацию (а)а-(-а, а[Е, Р(, 6) 3 десь с помощью правила 6 порожден левый участок а. Символ а сравнивается затем с текущим входным символом, и это дает (1а+а, [Е, Р1, 6) Теперь можно воспользоваться первым правилом нз (1в) и по- лучить (1 а+ а, 1 Т [Е, Т1, 63) ГЛ.
4. ОБШИЕ МЕТОДЫ СИНТАКСР!ЧРСКОГО АНАЛИЗА ЗАМЕЧАИИЯ ПО ЛИТЕРЛТРРЕ Здесь левый участок правила Т вЂ” Е)Т будет распознан, как только найдутся ! и Т. После этого можно перейти в конфигурации (а+а„Т[Е, Т1, 63) à — (а+и, а[Т, Р1[Е, Т1, 636) 'г — (+а, [Т, Р1[Е, Т1, 636) ( — (+а, [Т, Т1[Е, Т1, 6364) В данный момент Т служит текущей целью и найдено вхождение Т, которос нс является левым участком. Поэтому, приме няя (2), можно стереть эту цель и получить (+а, [Е, Ттд 6364) Продолжая в том же духе, получаем последовательность кон. фигураций (+а, [Е, Е~, 63642) — (+ а, + Т[Е, Е1, 636421) 1 — (а, Т[Е„Е1, 636421) ( — (а, а[Т, Р1[Е, Е~, 6364216) [-(е, [Т, Р'1[Е, Е1, 6364216) 'à — (е, [Т, Т'1[Е, Е1, 63642!64) 1 — (е, [Е, Е1, 63642!64) )- (е, е, 63642164) П *4.1.23.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
