Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 78
Текст из файла (страница 78)
сли (го, Хзб, е) г — *(е, 5, и), то будем писать б(га)=п и назы"вть и выходом алгоритма 4 для входа ги. Если из конфигурации (ю, Х,„5, е) допускающая конфигурация не достигается, то будем говорить, что значение л(ш) не определено. Переводом, опреде- ') 8 оригинале рор.— Прим. перев. 5 ь ьь(еРГРАммАтики еерллий еимвал магиеили Я г, $) — (д, 5$, г) а, 5).=(д, А5, 1) Ь, 5) = (ц, г, 2) а, А) --- (д, г, 3) Ь, А) =(ц, 5А, 4) $, 5) — (допуск, г, г) 6 (д, 6 (ц, 6 (д, 6 (д, 6 (ц, 6 (ь), Легко видеть, что (ю$, А(ьв) =- и, 38! 360 Гл. 3.
ОднопРОходиыи синтАксический АИАлиз Без ВОБВРАТОБ ляемым алгоритмом А, называется множество т(А) —... (( А(и!) —.— и). Будем называть Й-предсказывающий алгоритм разбора А для ' КС-грамматики 6 корректным в том случае, когда (1) ь(6) = (ьв «А(ьи) определено), (2) если А(и!) = п, то л — левый разбор цепочки ьи. Если работой й-предсказывающего алгоритма А руководит управляющая таблица М и он корректен для КС-грамматики 6, то М будем называть корректной управля!пщгй таблицей для 6. леавиелеела Риы З.З. Упрлвлн!пп!Зц таблица злгпрятиа А. Пример 5.5. Построим 1-предсказывающий алгоритм разбора А для лростой Щ1)-грамматики 6, из примера 5.2.
Прежде всего занумеруем правила грамматики 6,: (1) 5 аА5 (2) 5 — Ь (3) А — а (4) А Ь5А Управляющая таблица алгоритма А показана на рис. 5.3. С помощью втой таблицы алгоритм А так проанализирует входную цепочку аЬЬиЬ: (аЬЬаЬ, 5$, г) « — (аЬЬаЬ, аА5$, 1) 1 — (ЬЬаЬ, 45$, 1) (--(ЬЬаЬ, Ь5А5$.
14) « — (ЬаЬ, 5А5$, 14) «-(Ьау, ЬА5$, 142) « — (аЬ, А5$, 142) «--(аЬ, а5$, 1423) « — (Ь, 5$, !423) « — (Ь, Ь$, 14232) « — (г, $, 14232) На первом такте М(5, а)=(аА5, 1), так что верхний символ магазин азина 5 заменяется на аА5 и номер правила 1 записывается на выходной лепте. На следующем такте М(а, а)=выброс, так что а а выбрасывается из магазина и входная головка сдвигается на одну позицию вправо. Продолжая в том же духе, получаем допускающую конфигурацию (е, $, !4232). Очевидно, что 14232 — левый разбор цепочки аЬЬиЬ и, более того, А — корректный 1-предсказывающий алгоритм разбора для грамматики 6, !з й-предсказывающий алгоритм разбора для КС-грамматики 6 можно моделировать на детерминированном МП-преобразователе с концевым маркером на входной ленте.
Так как входная головка МП-преобразователя может обозревать только один входной символ, аваицепочка должна храниться в конечной памяти управляющего устройства. Остальные детали моделирования очевидны. Теорема 5.1. Пусть А — й-предсказываю!ций алгоритм разбора для КС-грамматики 6.
Тогда существует такой дгтгрлгинираванный МП-преобразователь Т, что т(Т) = ((иг$, и) 1А(иг) =и). Доказательство. Упражнение. (! Следствие. Пусть А — корректный й-пргдсказь!вающий алгоритм разбора для КС-грамматики 6. Тогда для 6 существует детерминированный левый анализатор. Пример 5.6.
Построим детерминированный левый анализатор Р, для 1-предсказывающего алгоритма нз примера 5.5. Так как грамматика простая, получится небольшой ДМП-преобразователь, на каждом такте сдвигающий входную головку вправо. Левый анализатор будет использовать $ в качестве маркера правого конца входной ленты, а также маркера дпа магазина. Пусть Р, =-.
((д„д, допуск), (а, Ь, $), (5, А, а, Ь, $), 6, ць, $, (допуск«), где 6 определяется равенствами п)Ет(Р!) тогда и только тогда, когда ГЛ. 3. ОДНОПРОХОДНЫИ СИНТАКСИЧЕСКИЙ АНАЛИЗ БВЗ ВОЗВРАТОВ Мс. С„С.САНГРАММАТИКИ 5АЗ.З. Спедствия определения ЩЦ-грамматики Покажем, что для ках<дой 1.1(я)-грамматики можно мехаия. чески построить корректный и-предсказывающий алгоритм рзз.
бора. Так как ядром предсказывающего алгоритма является управляющая таблица, надо показать, как строить по граьс>са. тике такую таблицу. Начнем с некоторых следствий определения 1А.(!с) грамматики. В определении Ы(й)-грамматики утверждается, что для данной левовыводимой цепочки щАа цепочка ис и непосредственно следующие за ней й входных символов однозначно определяю, к акое применить правило для развертки нетермннала А. Поэтому на первый взгляд может показаться, что для определения нужного правила надо помнить всю цепочку сс.
Однако это не так, Докажем теорему, очень важную для понимания 1.1.(й)-грзмматикс Теорема 5.2. КС-грамматика 6=-(Х, Х, Р, 5) является )!.(сс)- грамматикой тогда и только тогда, когда для двух различных правил А — р и А — у из Р пересечение Г!КЗТА(!Зсх) П Г)КЗТА(уи) пусто при всех таких исАа, что 5=>,*си«Аа. Доказательство. Необходимость. Допустим, что ис, А, а, (! и у удовлетворяют условиям теоремы, а Г!К5тА(ра) и Г(К5ть(угс) содержит х.
Тогда по определению Г!К5Т для некоторых у и г найдутся выводы 5 =>; исАа ~с исра =Ос" исху и 5 =>с" исА«а =>, исусх: — '«с" исхг. (Заметим, что здесь мы использовали тот факт, что 5 пе содержит бесполезных нетерминалов, как это предполагается для всех рассматриваемых грамматик.) Если (х( < й, то у = — г =-е. Так как ~Фу, то 6 не !.Е()с)-грамматика. Достаточнсспсь. Допустим, что 6 ие 11.(й)-грамматика.
Тогда найдутся такие два вывода 5 =>,*исАи= >, цсра=>! исх и 5 =>,*исАа= > — с ссуи~с" ису, что цепочки х и у совпадают в первых й позициях, но ~~у. Поэтому А — р и А — у — различные правила из Р и каждое из множеств Г(К5ТА(бсх) и Г1К5Т„(уа) содержит цепочку Г(К5Т,(х), совпадающую с цепочкой Г)ЙЗТА(у). сл Дадим несколько приложений теоремы 5.2 к Е1(!)-Грзмьсатсскам. Пусть КС-грамматика 6 = (ст', Х, Р, 5) не содержит е-правил, и нам надо узнать, является ли она ) 1.(!)-Грамматикой.
Из теоремы 5.2 следует, что 6 будет ) 1.(1)-грамматикой тогда и только тогда, когда для всех А~)т) каждое множество А-правил А ас ~а„,(... (а„из Р таково, что множества Г1К5Т,(и,), ПК5Т,(а,),.", Г1КьТ,(сс„) попарно не пересекаются. (Отсутствие е-правил здесь существенно,) Пример 5,7. Грамматика 6, состоящая из двух правил 5 — а5(а не будет 1.1.(!)-грамматикои, так как Г1КВТ,(а5) =- Г1КЗТ,(а) «=с. Интуитивно это можно объяснить так: видя при разборе цепочки ззз начинающейся символом а, только этот первый символ, мы пе знаем, какое из правил 5 — а5 или 5 — «а надо применить к 5.
тругой стороны, 6 — это !.1.(2)-грамматика. В самом деле, в обозначениях теоремы 5.2, если 5=>сисАа, то А==-5 и я=е. Та„как для 5 даны только два указанных правила, то р — а5 и у=а, Поскольку Г!Й5Т,(а5) — --аа и Г(К5Т,(а) =а, то по теорс '«се 5.2 6 будет 1.1.(2)-грамматикой. (,) рассмотрим 11(1)-грамматики, содержащие е-правила. Здесь лобио ввести функцию ГО!.1.0%БА'. Определение. Пусть 6 = ()т(, лз Р, 5) — КС-грамматика.
Определим Г01.1.0%7(р), где й — целое число и (1~(1А(!) Х)', как множество (ис~5=> ассу и исЕГ(КЗТАС(1«)). Как обычно, будем опускать й и 6 там, где понятно, о чем идет речь. Итак, Г01.1.0%7(А) — это множество терминальных символов, которые могут встречаться непосредственно справа от А (т. е.
следовать за А) в каких-нибудь выводимых цепочках, причем если аА — выводимая цепочка, то е тоже принадлежит ГО1Л.О РГс!(А ) . Можно очевидным образом расширить определение функций Г!КЗТ и ГО!10% так, чтобы их аргументами были не только отдельные цепочки, но и множества цепочек. Иначе говоря, если 6=-(Х, Х, Р, 5) — КС-грамматика и !. ~(1А1(! Х)', то Г1ЙВТГ (! ) = (ис ~ ис Е Г(КЗТА' (и) для некоторой цепочки а ~!.) ГО(.10!Асьа (!.) = сис / сс ~ ГОП.ОБА'(я) для некоторой цепочки схЕ!) Для 11.(!)-Грамматик справедливо следующее важное утверждение.
Теорема 5.3. КС-грамматика 6 =-(Х,Х,Р,5) являеспся Щ!)- грамматиссой тсгда и только пюгда, когда для двух различных правил А -э р и А у пересечение Г1КЗТ, (5 Г01.10%~с (А)) П Г(ЙЗТТ (Т ГО!А Отсс(А)) пусто при всех А ~Я, Доказательство. Упражнение. Таким образом, 6 является !.1.(1)-грамматикой тогда и только тогда, когда для каждого множества А-правил А — «. а, ~ сх, )... ( а„ (!) множества Г(КЗТс (а,), Г!К5Т, (а,),..., Г1ЙЗТ, (сх„) попарно не пересекаются, (2) если ис=>" е, то Г1К5Т, (ис) П ГО(.! 0%, (А) = 8 для ~ ~! (~ и, с ~ 1. Зто просто переформулировка теоремы 5.3. Может показаться, что теорема 5.3 непосредственно обобщается на Щй)-грамматики. Мы хотим предостеречь читателя, что это не так. КГ- ЗВЗ Гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
