Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 36
Текст из файла (страница 36)
Теорема 2.16. Если Š— КС-язык, то Е=-Е(6) для некоторой приведенной КС;грамматики 6. До к а з а т е л ь с т в о. Применить к КС-грамматике, определяющей язык Е, алгоритмы 2.8 — 2.11. Определение. А-правилпж КС-грамматики называется правило вида А — сс (ие путайте А-правило с е-правилом, которое имеет вид В е). Введем еще преобразование, с помощью которого можно удалить из грамматики одно правило вида А — иВ(г. Чтобы устранить это правило, надо добавить к грамматике новые правила, получающиеся из него заменой нетерминала В правыми частями всех В-правил. Лемма 2.14.
Пусть 6=()т), Х, Р, 5) — КС-грамматика и Р содержит правило А- аВ(), где ВЕЯ, а а и р принадлежат (г') () Х)'. Пусть  — у, ) у,)...!Та) — все В-правила втой грамматики. Пусть 6'=(14 Х, Р' 5), где Р'=(Р— (А аВЩ) () (А-~пуф) ауг() ~...[ауД Тогда Е (6) = Е (6 ). у р О г ц ) '!асти грамматику называют приведенной, просто если в ней нет бесс!Олеаиых симеонов.— Прим.
перев. 175 Гл. 3. элеме нты теОРии языКОВ З.з. коитакстиО ГЗОБОдиые языки Пример 2.25. Устраним правило А — аАА из грамматики б, имеющей два правила А — «аАА ~ Ь, Применим лемму 2.14, полагая и=а, В=А и 5 — А, и получим грамматику 6' с правиламн А — ааААА ( иЬА ) Ь Деревья выводов цепочки ааЬЬЬ в грамматиках 6 и 6' показаны на рис. 2.12. Заметим, что эффект этого преобразования ! ! ! ь в а е Рнс.
2.!2. Дерезья выводок а — з грамматике б; б — з гсзз«ызтнке б'. состоит в "склеивании" корня дерева на рнс. 2.12, а с его вторым прямым потомком. 2.4.3. Нормальная Форма Хомсиого Определение. КС-грамматика 6 =- (1ч, Х, Р, В) называется грамматикой в норлзпльной форме Хо«вского (или в бинарной нормальной форд!а), если каждое правило пз Р имеет один из следующих видов: (1) А ВС, где А, В и С принадлежат Р1, (2) А — а, где а ~ Е, (3) 5 — г, если г ~ Е (6), причем В не встречается в правых частях правил. Покажем, что каждый КС-язык порождается грамматикой в нормальной форме Хомского.
Этот результат полезен в тех случаях, когда требуется простая форма представления КС-языка. Алгоритм 2,12. Преобразование к нормальной форме Хомского. Вход. Приведенная КС-грамматика 6=(>1, 2, Р, В). Выход, КС-грамматика б' в норь!альной форме Хомского, эквивалентная 6, т. е. Е(6') =Е(6). Мгп!Од. Грамматика 6' строится по 6 следующим образом: (1) Включить в Р' каждое правило из Р вида А — а. (2) Включить в Р' каждое правило из Р вида А — ВС, (3) Вкл!Очить в Р' правило 5- г, если опо было в Р. 176 (4) Для каждого правила из Р вида А Х,,Х„, где й > 2, включить в Р' правила А Х <Хз Х > <Х,...Х„>-Х;<Х,...Х,> <Х зХ,Х„> Х;.
з <Х„,Х„> <Х,Х > Х',Х' где Х; = Хо если Х! с Х; Х; — новый нетерминал, если Х! а 2; <Х!...Х„> — новый нстерминал. (5) Для каждого правила из Р вида А — Х,Х„где хотя бы один из символов Х, и Х, принадлежит 2, включить в Р' правило А Х;Х:. (5) Для каждого нетерминала вида а', введенного на шагах (4) и (5), включить в Р' правило а' а, Наконец, пусть М'— это Ь) вместе со всеми новыми нетерминалами, введенными при построении Р'. Тогда искомой грамматикой будет 6'=(Ы', Е, Р', В)').
() Теорема 2.17. Л!7сть Š— КС-язык. Тогда Е=-Е (6') для некоторой КС-гражлгатики 6' г нормальной форд!г Хомского. Д о к а з а т е л ь с т в о. По теореме 2.15 Е определяется приведенной грамматикой 6. Алгоритм 2.12 строит по ней грамматику б', которая, очевидно, имеет нормальную форму Хомского. Остается показать, что Е(6) =-Е(6'). Это доказывается применением леммы 2.14 к каждому правилу грамматики б', в правую часть которого входит а', а затем к правилам с не- терминалами вида <Х!...Хд>.
Пример 2.26. Пус1ь 6 — приведенная КС-грамматика, определяел!ая правилами 5 — ОАВ ~ ВА А — ВВВ~ а  — АО1Ь Строим Р' алгоритмом 2.12, сохраняя правила 5 — ВА, А — а,  — АВ и  — Ь, Заменяем 5 — аАВ правилами  — а'<АВ> и <АВ> — АВ, а А — ВВ — правилазщ Л В <ВВ> и <ВВ>- ВВ. Наконец, добавляем а' — а. В результа!е получаем грамматику ') Авторы забыли исключить 5 кз правых честей прззнз!. Нодо либо мсднфнннроззть алгоритм 2.!2, либо, кроше, ззестн поные символ 3' н прззнло Я' — Л н прежде, чем применять алгоритм 2.!2, сдслзть прнзеденне грзммзтнкн.— Г! рил.
рзгс 177 гл. контекстно.сноводные языки Гл. а. Элементы теОРии языкОВ 5 — а' <АВ) ~ ВА А - В <ВВ>(а  — А5(Ь <АВ> — АВ <ВВ> — ВВ а'- а') () Е- Е+Т)Т Т вЂ” Т ар(Р Р- (Е) ~)а 179 178 6'=(1'м (а, д), Р', 5), где гч' =-(5, А, В, <АВ>, <ВВ>, а')„а р состоит из правил ?.4.4. Нормальная форма Грейбвх Теперь покажем, что для каждого КС-языка можно найти грамматику, в которой все правые части правил начинаются с терминалов.
Построение такой грамматики основано на устранении так называемой левой рекурсии. Определение. Нетерминал А КС-грамматики 6=(1ч, Е, Р, 5) называется рекурсивным, если А =)" аА!з для некоторых са и (1. Если а=е, то А называется леворекурсилным. Аналогично, если (з=е, то А называется праворекурсивным. Грамматика, имеющая хотя бы один леворекурсивный нетерминал, называется лево- рекурсивной. Аналогично определяется праворекурсивная грамматика.
Грамматика, в которой все нетерминалы, кроме, быть может, начального символа, рекурсивные, называется рекурсивной, Некоторые из обсуждаемых далее алгоритмов разбора не могуг работать с леворекурспвиыми грамматиками. Покажем, что каждый КС-язык определяется хотя бы одной не леворекурсивной грамматикой. Начнем с устранения в КС-грамматике непосредственной леворекурсивности. Лемма 2.1О. Пус!па 6=(Х, Е, Р, 5) — КС-грамматика, в которой А = Асс, ) Аа,(...) Аа,„)(3,)(3 (...
(ба — все А-правила из Р и ни одна из цепочек ()г не начинал!пел с А, Пусть 6'=()Ч()(А'), Х, Р', 5) где А'--новый нетерминал, а Р' получается из Р заменой А-правил правилами ') А 0.11.!" )1.!0 А'!().А'!" Р.А' А'- а,!аа)...(ам)а,А'!ааА'!...(а А' Тогда Е(6') =Е(6). ') 1)адо еще устранить В нз праапй части правила  — АВ.— Прем. ргб, е) Заметим, чтс праапла А Иг ссдержатсн нак а исходном, так н а реаультнрующем множестве А-праанл. Д о к а з а т е л ь с т в о. 11епочкп, которые можно получить в грамматике 6 из нетерминала А применением .4-правнл лишь к самому левому нетсрминалу, образуют регулярное множество (()ь+()е+ ° ° ° +й,)(сс1+па+ ° .. +ам) *. Это в точности те не, которые можно получить в 6' из А с помощью правых аз А'-п а- выводов, применив один раз А-правнло и несколько раз '-правила.
(В результате весь вывод уже не будет левым,) Все шаги вывода в 6, на которых не используются А-правила, можно непосредственно сделать в 6', так как пе А-правила в 6 и ' одни и те же. Отсюда можно заключить, что Е (6') с Е(6). Обратное вкл!очение доказывается по существу так же. В 6' берется правый вывод и рассматриваются последовательности шагов, состоящие ич одного применения А-правила и нескольких применений А'-правил. Таким образом, Е( ) = =- Е (6').
Г) На рис. 2.13 показано, как действует преобразование, описанное в лемме 2.!5, на деревья выводов. 'Рнс. 2.!3. Части деревьев: а — часть дереаа н'м; б — соотаетстаующан часть а Пример 2.27. Пусть 6,— наша обычная грамматика с прави- лами ГЛ. |К ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ гм. ко||такстно-своводные языки Если применить к ней конструкцию леммы 2.15, то получится эквивалентная ей грамматика 6' с правилами Е Т/ТЕ' Е' — + Т /+ ТЕ' Т- Р/ГТ' Т' —,'Р/,РТ р — (е)/а Е) Теперь мы готовы описать алгоритм, устраняющий левую рекурсию из приведенной КС-грамматики.
По идее этот алгоритм подобен алгоритму решения уравнений с регулярными коэффициентами. А л г о р и т м 2.13. У с т р а н е н и е л е в о й р е к у р с и и. Вход. Приведенная КС-грамматика 6=(Х, Х, Р, Б). Выход. Эквивалентная КС-грамматика 6' без левой рекурсии. Айетод. (1) Пусть 5! =- (А„..., А„/, Преобразуем 6 так, чтобы в правиле А,— а цепочка а начиналась либо с терминала, либо с такого Л,, что 1> С С этой целью положим г'= 1.
(2) Пусть множество Акправил — это А, — А,а,/ ... .../А|а,„/|3,/.../|3р, где ни одна из цепочек р, нс начинается с Ам если 7г(г, (Это всегда можно сделать.) Заменим А,-правила правилами А; !3,/... //)р/р,А;/.../ррА/ А;.— а,/.../а /а,Л;/.../а А;. где А; — яовый нетсрминал. Правые части всех Акправил начинаются теперь с терминала или с Аь для некоторого к > г.
(3) Если |' — н, полученную грамматику 6' считать результатом и остановиться. В противном случае положить г =-г + 1 и 1-1. (4) Заменить каждое правило вида А, — А а правилами Л| — г га/...//! а, где А — /!г/.../5 — все Ат-правила. Так как правая часть каждого А,-правила начинается уже с терминала или с А„для й > 1, то и правая часть каждого Акправнла будет теперь обладать этим свойством, (5) Если 1:.
†— 1, перейти к шагу (2). В противном случае положить )=1+1 и перейти к и|агу (4). й Теорема 2.18. Каждый КС-язык олределлетсл не лееорекуреиеной гражишпикой. Д о к а з а т е л ь с т в о. Пусть 6 — приведенная грамматика, порождающая КС-язык Е. При применении к ней алгоритма 2.13 гво используются только те преобразования, которые упоминаются в леммах 2.14 и 2.15. Поэтому результиру|ощая грамматика 6' порождает Б. Сформулируем два утверждения, которые по существу уже встречались в конце описаний шагов (2) и (4) алгоритма 2.13: (2.4А) После выполнения шага (2) для |' правая часть каждого Лкправила начинается с терминала или с такого А,, чтой>Е (2,4,5) После выполнения шага (4) для г и 1 правая часть каждого Акправила начинается с терминала или с такого А, что 7г > !'. Докажем, что (2.4,4) истинно для всех (=п, а (2А.5) истинно для всех таких пар (г, !), что г ~н н г >1.
Рассмотрим значения параметров | и (г, 1) утверждений (2.4.4) н (2.4.5) в том порядке, в каком опн встречаются в ходе работы алгоритма 2,13 на шаге (2) н шаге (4) соответственно: 1, (2, 1), 2, ..., г — 1, (г', 1), ..., (г, 1), (г,г — 1),г, ...,(н,гг — 1),и и проведем доказательство индукцией по значениям параметров в этом упорядочении. Базис. Так как на шаге (2) цепочки р„ ..., /)р не могут начинаться с А„ то для г = 1 утверждение (2.4.4) истинно. Шаг индукции. Предположим, что (2.4.4) и (2.4.5) истинны для значений параметров, предшествующих (г, 1). Так как 1< г', то по предположению индукции (2.4.4) истинно для 1'. Поэтому ца шаге (4) каждая из цепочек /1„..., (! начинается с терминала или с такого А„что 1г > !. Но после завершения шага (4) цепочки 5„..., /) становятся префиксами правых частей Акправил, Следовательно, (2.4.5) истинно для (|', !).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
