Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 85
Текст из файла (страница 85)
зание. Покажите, что (15, шб, у) '; — А,(й', си'Ь, у') тогда и только тогда, когда (соб, иу)1 — м (ис'Я, й'у'). Упр. 12. Для произвольного слабого СМ)с-распознавателя М постройте эквивалентный ему слабый СМК-распознаватель М', команды которого удовлетворяют условиям упр. 11. Упр. 13. Покажите, что для произвольного СМК-распознавателя можно построить эквивалентный ему ДМП-автомат, и обратно (т. е. СМК-распознаватели определяют в точности класс детерминированных КС-языков). Рассмотрим теперь так называемый дна граммер Конвэя [19631 —. МП-распознаватель, управляющее устройство которого задается конечным множеством 1) „синтаксических диаграмм". Содержательно, диаграмма с(Есс определяет некоторый „синтаксический тип", т.
е. множество цепочек 1., распознаваемых диаграммсром при „прохождении" диаграммы й, Связь между й и 1. в диаграммере аналогична связи между нетермипалом А и множеством 1.5 цепочек, выводимых из Л, в КС-грамматике. Чтобы подчеркнуть эту связь, определим вначале синтаксические диаграммы частного вида, непосредственно связанные с КС-правилами, Определение. КС-диаграммой с(А, соответствующей множеству А-правил А ХИ...Х„,(Х„...Х,а,~...(ХА,...Хь„ назовем помеченный ориентированный граф, изображенный на рис.
Д.1. В этой диаграмме вершина 1 начальная, всршина 1 заключительная, а в нумерации вершин важно лишь то, что она взаимно однозначна. Нетерминал А считается именем диаграммы с(А. КС диаграммером, соответствусощим КС-грамматике 6 = р Х, Р, О), назовем четверку М =(Х, с», 11, да), где 0= (д„с Л а )Ч) и с1 — начальная диаграмма.
Пример б. КС-диаграммер Мо,— ((а, Ь), (В, А), сс, с1 ), соответствующий КС-грамматике 6, примера 2, состоит из двух КС диаграмм, изображенных на рис. Д.2. гс Рис, Д,2. КС-диаграммер. В общем случае синтаксической диаграммосс (С-диаграммой) над парой непересекающихся алфавитов Х и Л назовем конечный помечс.иный ориентированный граф, вершины которого занумерованы н выделены одна начальная вершина (с номером 1) и одна илн несколько заключительных вершин. Каждая дуга помечена символами либо а 6 Х0 (е), либо йС Л, либо (с(, с) (содержательно, с' — номер заключительной вершины диаграммы, обозначенной 51 и имеющей несколько заключительных вершин).
В начальную вершину дуги не входят, нз заключительной— не выходят. Диаграммером назовем четверку М=(Х, Л, сгс, й,), где Х— конечный входной алфавит, Л вЂ” конечный диаграммный алфавит (его символы служат именами или обозначениями диаграмм), 0 — конечное множество С-диаграмм над алфавитами Х и Л (прнчем ХИЛ= — Я и между Л и О установлено взаимно однозначное соответствие, именующее диаграммы), Ы,— начальная диаграмма с одной заключительной вершиной.
Состоянием диаграммера М назовем пару (а, с), где с(сВ и с — номер некоторой вершины диаграммы с(, т. е. состояние— это по существу вершина диаграммы, обозначаемая как пара. Множество состояний с,с является также магазинным алфавитом диаграммера М (как н у СМКураспозссавателя). Конфигурассия диаграммера имеет вид ((а, с), ис», ус)), где (й, с) Е Я вЂ” текущее с"стояние, ш ~ Х" — необработанная часть входной цепочки, ус1е* †магазинн цепочка (верхний символ слева), В--концеВОй МарКЕр ВХОда И МаГаЗИНа (» ~ Х 11С,"с). Оссределим один такт работы диаграммера М, т.
е, отнопсенне на его конфигурациях. Пусть дана конфигурация ((с(, с), аис3 ур), где ааХ либо а=ис=е. гл. л. одиопгоходиып сиптлксичвскии АнАлиз Без Возвгхтов (а) Если из вершины ф, 1) выходит дуга, помеченная сим волом аЕХ н входящая в вершину ф, 1), то ((Й, 1), аю$, уй) ! — ((д, 1), ыф, 7$) т. е. делается переход из (й, 1) в (д, 1) по дуге, помеченной а и сдвигается входная головка.
(б) Если условие в (а) не выполнено, но из (А 1) выходит дуга, помеченная именем диаграммы д' или парой (д', 1), то ((д, 1), аш6, 7$) !--((д', 1), аю6, (д, 1) 76) т. е, состоянием становится начальная вершина диаграммы д', а в магазине запоминается вершина (й, 1), к которой надо вернуться позднее, когда будет пройдена диаграмма Ы'. (в) Если ие выполнены условия ии в (а), ни в (б), но нз (Ы, 1) выходит дуга, помеченная е и ведущая в (й, !), то ((е(, 1), июле, 7$)' — ((д, 1), аю$, уЯ т.
е. „пустая" дуга проходится в последнюю очередь без изменения входа и магазина. (г) Если (Ы, 1) — заключительная вершина, т=(д', у) у' и дуга с меткой (д, 1) ведет из (сГ, !) в (сГ, Й), то ((д, !), арф, (а', 1) у'$) ) — ((д', й), аида, у'6) т. е. информация о следующем состоянии извлекается из магазина (как у СМЙ-распознавателя). В этом случае диаграмма д уже пройдена, и надо перейти а (д', й) по дуге, соответствующей заключительной вершине (й, 1). Заметим, что для текущего входного символа а и текущей вершины (д, 1) выбор выходящей из нее дуги играет роль выполнения очередной команды распознавателя, Пункты (а) — (в) показывают, что диаграммер, так жс как простой МП-распознаватель и СМВ-распознаватель, пытается сначала выполнить команду, помеченную символом а, и в последнюю очередь — команду, помеченную е.
Отметим еще, что диаграммер является, вообще говоря, недетерминированным распознавателем, так как может случиться, что из (д, 1) можно выйти по разным дугам, т. е. выполнить разные команды. Пусть (д, 1) — заключительная вершина диаграммы д. Языком, распознаваемым диаграммером М при прохождении диаграммы а из ее начальной вершины в вершину (е(, 1), назовем множество Евь !=-( ЕХ*~(Ф. 1), Ф, 3)( — *((А '), $, 3)) Если Ы имеет одну заключительную вершину 1, то вместо 7«,п будем писать Е .
Язык, распознаваемый диаграммером М,— это множество Е (М) =Ее,. дополнения Упр. 14. Покажите, что (а) если Мо=(Х 11 Е', д) — КС-диаграммер, соответствую- щий КС-грамматике 6=(ч, Х, Р, 5), то Е4„~Ел-— .(ш(А=лаю) в частности, Е (Ма) ~ Е(6). (б) еслк 6 — пссвдоРазделепнаЯ гРамматика и Ма — соответ- твующий ей простой МП-распознаватель, то Е (Мо) =Е (Ма) (н, значит, если грамматика 6 слаборазделенная, то Е (Мо) =- .-Е(6)). Упр. 16.
Для произвольной КС-грамматнки постройте экви- валентный ей КС.диаграммер. Упр. !6. Для произвольного диаграммера постройте эквива- лентный ему (недетерминированный) МП-автомат. Из упр. 15 и 16 следует, что днаграммеры распознают в точ- ности класс КС-языков. Наложим на диаграммер ограничение, аналогичное ЕЕ(1)- условию или условию разделенности для КС-грамматики и по- зволяющее сделать детерминированным выбор дуги на каждом шаге. С каждой меткой Х, помечающей дугу диаграммера М, свя- жем соответствующее ей „множество первых символов" Р(Х), определяемое так: (!) г" (а).=-(а) для аЕ Х 1! (е), (2) если д обозначает диаграмму с одной заключительной вершиной, то г" (д) =- (а ! (а Е Х и аю Е Е,) или (а =. е и е Е Ее)) (3) г ((г(, 1)) =(а!(аЕХ и аю ЕЕ«о) или (а=е и еЕЕ«п)). Назовем диаграммер М разделенныа, если для каждой вер- шины (Н, 1), из которой выходят л дуг, помеченных метками Х„..., Х„, множества г" (Х,), ..., г" (Х,) попарно не пересе- каются.
Для разделенного диаграммера М доопределим отноше- ние )-: для текущего символа а н вершины (состояния) (д, 1) выбирается выходящая из нее дуга с меткой Х, для которой аЕг" (Х), а если таковой иет, то дуга, для которой еЕг" (Х). Заметим, что выбрать можно только одну дугу.
ств ю Упр. 17. Покажите, что если КС-диаграммер М, соответвующий КС-грамматике 6, разделенный, то 6 эквивалентна о "севдоразделеиной грамматике 6' и Е(Мо)=1.(Ма ) для соот- вегству!ощего 6' простого МП-распознавателя Ма (ср. с упр.14(б)). В г ам, Рработе [Ломет, 1973] изучаются детерминированные диа- Раммеры следующего специального вида. Определение. диаграммер М = (Х, Л, Р, Й ) назовем Е-диаером, если в каждой его диаграмме все дуги, выходящие !4 х х'Ф~ дж.
ульмаи, т, 4!7 гл, к однопроходный сиитлксический лнллиз вез возвратов из начальной вершины, помечены разными входными символамн, а все дуги, выходяп1ие из незаключнтельпой вершины, помечепьг парами (г(, ю',), (с), 1а), ..., (д, 14) для Й= 1, обозначающиьш заключительные вершины некоторой диаграммы г(.
Очевидно, что (.-диаграммер является детерминированным распознавателем. "*Упр. 18, Покажите, что для каждого детерминированного КС-языка существует распознающий его ).-диаграммер. Рассмотренные до сих пор детерминированные нисходящие анализаторы с магазинной памятью строят только один начальный отрезок левого вывода, совместимый с обработанной частью входной цепочки. В (Алгол 681 (гл. !) описан анализатор (назовем его синхронным), который пытается синхронно следить за несколькими левыми выводами ').
Определение. Синхронным распознавателем Мо, соответствующим КС-грамматике 6 =- (Ь(, Х, Р, 5), назовем пятерку (Х, Ь(, О, г(э, 1з), где (Х, Х, В, г(з) — КС-диаграммер, соответствующии грамматике 6, а Π— -множество состояний, элементами которого служат множества вершин диаграмм из О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
