Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 71
Текст из файла (страница 71)
Покажите, что описанная выше конструкция дает для КС-грамматики й недетерминированный анализатор по левому участку. 4.1.24. Постройте алгоритм разбора по левому участку с возвратами. Пусть 44=(Х, Х, Р, 5) — КС-грамматика, не содержащая правил с правыми частями длины 0 и 1. (Такая грамматика существует для каждого КС языка Еа:- [ге(!РЕМУ* и 1ге() 2). Для б можно построить недетерминированный правый анализатор типа „перенос — свертка", у которого каждый символ магазина является парой вида (Х, Е, где Х б )чз(120 (Ц ($ — правый концевой маркер магазина), а 1,! — множество правил из Р, причем для каждой правой части правила указаны всевозможные префиксы, которые могли быть распознаны к данному моменту разбора (это делается с помощью точек, поставленных между некоторыми символами правых частей).
Перед символом Х! в правиле А — Х,Х,... Х„точка ставится тогда и только тогда, когда Х,...Х,,— суффикс цепочки символов грамматики, находящейся в магазине. Шаг переноса можно сделать, если текущий входной символ служит продолжением некоторого правила.
В част!юсти, его ыо>к. но сделать всегда, когда А — ы принадлежит Р, а текушвй ВХОдиай СИМВОЛ Прниадпсжнт г1!45ТХ(и). Шаг свертки можно сделать, если достигнут конец правой части правила. Допустим, что таким правилом является А- !х. Чтобы сделать свертку, удалим из верхней части магазина 1а~ символов. Если теперь верхним символом магазина стал (Х, Е, пишем в магазин (А, !4'), где ье' вычисляется по ('„! в предположении, что А распознан, т, е. 1е' образуется нз (4 переносом через А всех точек, стоящих непосредственно слева от А, и добавлением точек па левых концах правых частей, если их там еще не было. !!ример 4.7. Рассмотрим грамматику 5 — 5с1аЬ и входную цепочку аЬс. Вначале в магазине анализатора находится символ (3, 14,)„где 444=5 — 5с! аЬ.
Затем можно перенести первый входнои символ и записать в магазин (а, 14!), где Ял= =5 5е( а Ь. Здесь либо можно находиться в начале правил 5-- 5с ~аЬ, либо можно считать, что прочитан первый символ а правила 5- аЬ. Перенося следующий входной символ Ь, запишем в магазин (Ь, ©, где 1,!з =- 5 - 5с! аЬ .
Затем можно сделать свертку, используя правило 5 в пЬ. Магазин будет теперь содержать (3, !1,)(5, !ез), где !4,=--5 — *5 е( аЬ. П Домелки предложил реализовать этот алгоритм с помощью двоичной матрицы т)4, представляющей правила, и двоичного вектора 1Г, представляющсго возможные позиции в каждом правиле. В описанном выше а|шоритме можно вместо !1 брать век. тор )Г. Каждый новый вектор в магазине легко вычисляется по М и текущему значению вектора )Г с помощью простых поразрядных двоичных операций. 4.1,26. Используйте алгоритм Домелки для определения возА4ожных сверток в алгоритме 4.2. Замечания по литературе хо я.
Многие рзяяие компиляторы яомпялятороз и аяптзясяческп упрзяляем ые мп ляторы яапользаззлн яедетермяпяроязяяые ллпжятмы разбора. Взр дов япсходщпего разбора с яаззрзтзмя яспользавзлясь в халшяляторе рязляампялятороз Вйухерз я Морриса (Розен, !96761 я з апатзча построепйя компиляторов Мй4А1Шоргз, 19641. В системе спмвольяого прагрзммярозания яедегермяяяроззяпый яяслодяп!яй зязляза!ор модсляруетая пзрал. лзльзым зыпалпепием зсех допустямых поалсдоззтельпаатей тактов ',Р й. д, 9661.
Методы яясхадяп!аго разбора с зозпрзтзмя применялись тзхже , 'е ° для аяптзяспческото анализа зстестпеяяых языков (Купа л Этт!!ягор, 19621. О яя. рятм Ай д м яз самых ранних апублпяапзяпых злгаритмоз разбора был з гол учзатк . Об "ранах !1961], рзботззшяй по существу методом разбора па левому у. зары рзяаях методов разбора сделаны 4йлойдол! 119646й 4!ятзмом !тля 119641 я Гряффятсом я Петриком 119661. Аяге 19 яяя заза Р 119681 описывает яяаходщпяй алгоритм, я котором для умепы ерзтап употребляютая первые я паслздпяз символы, оыподпмые яз и петормплзлз В Недетермяяироззпяые злгорятмы рассматриваются з работе зайдя 1196761 ГЛ.
4. ОБЩИЕ МЕТОДЫ СИГгт«КСИЧЕСКОГО АНАЛИЗА «.Э. ТАБЛИЧНЫЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА Одна реализация алгоритма Домелки описана Хекстом н Робертсом [!9ТО) з) В обзорной статье Коэна и Готлиба [!9701 описывается использование в алгоритмах разбора (с возвратами и без пих) представлений КС-грамматик с помощью списочных структур. йд. 1АБЛИЧНЫЕ ИЕ1ОДЫ СИН1АКСИЧЕСКОГО АНАЛИЗА Мы изучим два метода синтаксичесного анализа, работающие для всех контекстно-свободных грамматик: алгоритм Кока — Яп. гера — Касами и алгоритм Эрли.
Каждый нз них требует времени п* и емкости и', но последнему алгоритму для однозначных грамматик достаточно времени а'. Кроме того, можно добиться, чтобы алгоритм Эрли тратил линейныс время и емкость для большинства грамматик, которые можно анализировать за линейное время методами, излагаемыми в последующих главах. 4.2А. Апгоритм Кока — Янгера — Каками В последнем разделе мы обнаружили, что нисходящие н восходящие алгоритмы с возвратами могут затрачивать на разбор экспоненциальное время. Здесь мы изложим метод, для которого гарантируется, что оп выполнит ту же работу для произвольной грамматики за время, пропорциональное кубу длины входной цепочки, Это по существу метод „динамического программирования"„ и мы включили его сюда из-за его простоты.
Сомнительно, однако, что он найдет практическое применение, поскольку (1) время пэ слишком велико, чтобы его можно было позволить потратить на разбор, (2) используемая емкость памяти пропорциональна квадрату длины входа, (3) метод равд. 4.2.2 (алгоритм Эрлн) во всех отношениях так же хорош, как этот, а для многих грамматик даже лучше. Метод работает следующим образом. Пусть 6=-([«[, Х, Р, В)— КС-грамматика без е-правил в нормальной форме Хомского.
Про. етое обобщение алгоритма работает и для грамматик, не находящихся в этой нормальной форме; мы оставим это обобщеияе читателю. Так как КС-грамматика без циклов лево- и правопо. крывается КС-грамматикой в нормальной форме Хамского, то это обобщение не так уж важно. Пусть го.=а,аэ...а„— входная цепочка, катару!о нужно разо брать согласно грамматике 6. Предполагается, что а,бХ дл" ! «=. ! ~' п. Суть алгоритма состоит в построении треугольнои табла«[ы Разбора Т, элементы которой обозначим!а, где 1-- « ~'1 ') Уместив упомянуть работмсзмогоДомелкн [Г964,!966),-При«ь перез 352 и 1() (г! — «'+1.
Значениями переменных тг будут подмнон«ества множества Ч Нетермипал А будет пыринздлежать тогда и только тогда, когда А=; "а,а;„...аг„. „т. е. когда из А выводятся 1 входных символов, начиная с позиции т«частности, входная цепочка гг«принадлежит Т. (6) тогда и только тогда, когда В Е (,„, Таким образом, чтобы выяснить, принадлежит ли го языку Т.(6), вычислим для ге таблицу разбора Т и посмотрим, принадлежит ли В ее элементу Г,„. Затем, если нужен один (или все) разбор цепочки ш, его можно построить с помощью таблицы разбора. Для этой цели можно использовать алгоритм 4.4.
Сначала мы приведем алгоритм, вычисляющий таблицу разбора, а затем алгоритм, строящий разборы по этой таблице. Алгоритм 4.3. Ал гор и тм разбора Кока — Я н ге ра— Касами. Вход. КС-грамматика 6 — --(К, Х, Р, В) в нормальной формс Хомского без е-правил и входная цепочка м«=-а,а,...а„ЕХ". Выход. Таблица разбора Т для цепочки го, такая, что А Е1. тогда и только тогда, когда А ~'"а,а„,...а!« П ел!о . (1) Положить Ги = (А [А - аг принадлежит Р) для каждого К После этого шага из А Е Гг, следУет, очевидно, А~." а! (2) Допустим, что уже вычислены ГП для всех 1(1(п н всех 1= .)' (1.
Положить Г, =--(А [ для некоторого 1(й <1 правило А - ЙС принадлежит Р, В Е !м и СЕ Г;««, у «) ') Так как 1(й <1, то л и ) — л меньше 1. Таким образом, г!« и гг,«, у вычисляются раньше, чем Г,, После этого шага нз А Е угу следУет А ВС + ... С .=> ~ а;...а,, «,С => а,...аг„,а,,«...а « (3) Повторять шаг (2) до тех пор, пока не станут известны (п для всех 1(«'~~а и 1 )(и — «+1. () Пример 4.8. Рассмотрим грамматику 6 в нормальной форме Хомского с правилами В- АА[АО!Ь А - ВА !АЗ[а 1 что со ) Заметим, что мы ие обсуждаем в деталях, как это сделать. Очевидно, о соответствующее вычисление можно выполнить нз вычислительной машине. этого Когда речь пойдет о времепнбй сложности алгоритма 4.з, будут даны детали ого шага, обеспечивающие его эффективное вмполнение.
12 А. Акз, Дж, Ульизн. э. ! зя ГЛ 4 ОБН1ИЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА 4.К ТАБЛИЧНЫЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА Пусть аЬааЬ вЂ” входная цепочка. Таблица разбора Т, получающаяся в результате работы алгоритма 4.3, показана на рис 4.8. После шага (1) 1„=-(А), так как А — а принадлежиг Р и а,— -а. На шаге (2) в (.„добавляем 3, так как Я вЂ” АА принадлежит Р и А принадлежит йм и 1„. Заметим вообще, что, как видно 1 2 5 4 5 Рис. 4.8. Таблина разбора Т. из рисунка, Гы для ( - 1 можно вычислить, обследовав нетерминалы в следующих парах элементов таблицы разбора: (Гн 14 ~ ь / — з) (1~4 Г!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
