Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 105
Текст из файла (страница 105)
о' Если п = 2, . это множество состоит нз правйл А — В /В, 1 2 В,— а, и В,— а,. Для 1((«г> В случае (а;1=-1 можно положить В<=а, и исключить правило Вг — ао (6) Правило А — а,/и /.../а„, где а; — цепочка нетсрминалов и терминалов, заменяет множество правил А — »а,'(а,'/...(а„' и Х вЂ” а для каждого терминала а, где а; — цепочка ао в которой каждый терминал а заменен нетермийалом Х,. Начиная с этого момента мы будем допускать включение -:.»Р в ЯНРОВ-программы расширенных правил указанного типа.
Приведенные выше определения позволяют механически строить эквивалентную ЯНРОВ-программу, удовлетворяющую первоначальному определению. Эти расширенные правила имеют естественный смысл, Напри- х мер, если для А есть правило А- г'1);... )'„, то вызов А успешен тогда и только тогда, когда вызов г'< успешен в той входной позиции, где был сделан вызов А, вызов г', успешен там, где закончился вызов )~„вызов У, успешен там, где закончился вызов )'„и т. д.
Аналогично, если для А есть правило А — а,/а,(.../аи, то вызов А успешен тогда и только тогда, когда а, достигает успека там, где вызван А; либо когда а, приводит к неудаче, но и, достигает успеха там, где вызван А, и т. д. Пример 6.2. Рассмотрим расширенную ЯНРОВ-программу Р = ((Е, Р, Т), (а, (,), +, и), В, В), где В состоит из правил Š— Т+Е(Т Т Рит/РР— (Е)/а Читателю предлагаем убедиться в том, что Е(Р)»-Е(ви), где ний. би — наша стандартная грамматика для арифметических вы ° раже- Чтобы привести Р к стандартной форме, сначала, применяя (6), введем новые нетерминалы Х„Х<, Х>, Х и Х,, Правила станут 5! В такимк: 6.1.
нисходящий РАВБОР с ОРРАниченными ВозВРАтАми Е ТХ»Е/Т Т вЂ” РХ,Т/Р Р Х,ЕХ,(Х Х,—. а Х< — ( ' ' х, ) Х,— + Х Согласно (6), первое правило заменяется правилами Š— В,/Т н В, — ТХ,Е. Учитывая (4), заменяем В,— Тх»Е правиламн В, ТВ, н В,— Х Е. Затем заменяем нх на- В,— ТВ,/Р, Ви — Х Е(Р и Р— (. Правило Š— В,(Т заменяется на Е-,В,С/Т и С вЂ” е. В результате получим множество правил Х, а Р В,. Х,Т/Р Х, ( Е В,С/Т Р В,С/Х Х,-) В, ТВ,(Р В, Х,В„(Р Х, + В„х Е/Р В ЕХ>(Р Х„и Т Вис/Р С е В, РВ</Р ' Для простоты мы отождествили с нетермнналом С каждый не- терминал Х, для которого получается правило Х вЂ”; е, и с петер.
миналом Р каждый 1', для которого К вЂ” (. () Всякий раз, когда ЯНРОВ-программа распознает цепочку и>, можно сверху вниз построить, дерево разбора" этой цепочки, прослеживая последовательность ЯНРОВ>операторов, выполняемых прн распознавании ш> Внутренние вершины этого дерева соответствуют нетерминалам, вызываемым в ходе выполнения программы и сообщающим об успехе.
Алгоритм 6.1. Дерево разбора, соответствующее выполнснию ЯНРОВ-программы. Вход. ЯНРОВ-программа Р=(Ы, 2, Р; 3) и такая цепочка и> 6 2', что В =ои (и> 1, з) . Выход, Дерево разбора цепочки и>. Метод. Ядро алгоритма образует рекурсивная процедура стройдерево, которая по утверждению вида А=о (х(у»з) (эго ее аргумент) строит дерево с корнем, помеченяым А, и кроной х. Вначале эта процедура вызывается для утверждения В =>и(п>(,з), 1Т» 519 гл е, алгоритмы рдзворд в ограниченными аозврдтдми Процедура стройдерево: Пусть А =э'" (х(у;з) — вход проце, дУры. ве (1) Если для А есть правило А — а или А- в, то постр и в, о построить . чен ршнну с меткой А ц для нее одного прямого потомка, поме-: ного а или в соответственно. Остановиться. (2) Если ля А д есть правило А ВС~О и х можно предста- ', вить в виде х=-х,х„так что В=э (х,', ,х,у,з) и С=э"'*(х 1, ) то пост оить ве и з(х у,з) ° стройдерево ' я а р ршину, намеченную А.
Выполнить процеду у ' мента С=у"*(х (,з). дл ргумента В=зз (х,(ху,з), а затем для аргу- н и деревья к ве шине, ( з1у, ). Присоединить получившиеся нри этом:, получнвшегося в е Р , помеченной А, так, чтобы корень дерева з потомком этой ве шин р зультате первого вызова, атал левым прямым. „,;. ршины, а норень второге дерева — правым. не выпол- дерева единственным стра дерево для этого аргумента н сделать корень получившегося кой . Остановиться. П ым потомком уже построенной вершины с мет- Заметим, что и о сивно только ля процедура стройдеревв вызывает аебя рекур-, д меньших значений титан что алгоритм 6.1 должен в конце концов остановиться. мощью алгоритма 6,1 построим дерево раз- Пример 6.3, С помо ора, порождаемое ЯНРО входно цепочки- айа. ЯЙРОВ-программой )в из примера 6.1 для . М':;.
В . р ц дуру стройдерево для утверждения Вначале вызовем п о е соответственно. Затем вызовем эту п оцед т н у, учтоА и В успешно распознают цепочки анба аким о разом пост о ! ак м Р, роение дерева начнется так, как показано д я а сразу приводит к успеху, поэтому ершние присоединяется один прямой потомок, помечен- приводят к успеху для и н Ь соответстпоказа аким о разом, п е ы казанного на рис. 6.1, б. р д дущее дерево вырастет до'дерева Ф р успеху для Ь, так что вершина, поме- С сразу приводит К с енная, получит одного потомка, помеченного Ь.
Вызов В успешен для а, поскольк прямого потомка„ по льну успешеи вызов А, так что В получает томка, помеченного а. меченного А, а он в свою очередь — по- п а. Все дерево показано на рис. 6.1, в. С) Заметим, что если н программа азбо а, то множество ЯНРОВ-правил трактуется как Р Р, всякий раз, когда нетерминал сообщает 526 ел, нисходящия развор с ограниченными возаратдми об успехе, для распознанной им части входной цепочки можно построить соответствующий перевод (который позднее можно аннулировать), причем используются переводы „потомков" этого нетермннала в смысле только мто описанного дерева разбора. 1,l~ Рнс. 6.1. Построение дереве разбора с иомощьвз ЯНРОВ-программм.
Этот метод трансляции подобен сннтанснчески управляемой трансляции для контекстно свободных грамматик, О нем еще будет идти речь в гл. 9. Корректность алгоритма 6.! нельзя „доказать", потому что, как уже говорилось, он сам служит конструнтнвным определением дерева разбора, порождаемого ЯНРОВ-программой. Однако легио показать, что кропай этого дерева является входная цепочка. Индукцней по числу вызовов процедуры стройдерево можно показать, что если она вызывается для аргумента А~" (х1у, з), то результатом будет дерево с кроной х.
Некоторые' из успешных результатов будут аннулированы. Иными словами, когда А=о (ху(х, з) и есть правило А- ВСАТ, может оказаться, что В~+(х1уг, з), но С=>+((уг,(). Тогда соотношение В=~+ (х)уг, з) и все успешные шаги, с помощью которых оно было построено, иа самом деле не включаются в определение дерева разбора входной цепочки (ие считая самого отрицательного результата). Этп успешные шаги ие отражены в дереве разбора, как и вызов процедуры стройдерево для аргу- 521 ГЛ б. АЛГОРИТМЫ РАЗВОРА С ОГРАНИЧЕННЫМИ ВОЗВРАТАМИ »Л. НИСХОДЯЩИЙ РАЗБОР С ОГРАНИЧЕННЫМИ ВОЗВРАТАМИ мента В=ВА" (х1уг, з).
Но в него включаются все успешные шаги, которые в конечном счете приводят к успешному распознаванию входной цепочки. 6Л,2. 'ЯНРОВ и детерминированные КС-языки Может оказаться довольно трудным установить, какой язык определяет ЯНРОВ-программа. Чтобы дать представление об определяющей силе ЯНРОВ-программ, докажем, что каждый детерминированный КС-язык с концевым маркером распознается некоторой ЯНРОВ-программой. Кроме того, существует тесная связь между деревьями разбора, порождаемыми этой программой, и деревьями выводов в „естественной" КС-грамматике для этого языка, которая строится по соответствующему ДМП-автомату так, как описано в лемме 2.26.
Лемма 6.2 позволяет упростить представление ДМП-автомата, используемое в этом разделе. Лемма 6.2. Если Е =Е, (М1) для ДМП-автомата М„то Е=Е,(М) для ДМП-автомата М, который на каждом свсем шаге может увеличить длину магазина не более чем на 1. Доказательство. Доказать это утверждение было предложено еще в упр. 2.5.3. Говоря неформально, надо вместо шага, заменяющего 2 цепочкой Х, ... Х» для /з > 2, сделать шаги, заменяккцие 2 на Г' Х„, 1'» на 1'„;Х 1О ..., )«, иа 3«,Х» н 1', иа Х,Х,. Все У'; — это новые магазинные символй, причем верх магазина расположен слева.
(1 Лемма 6.3. Если Š— детерминированный КС-язык и $ — новый ' символ, то Е5 Е, (М) для некоторого ДМП-автомата М. Д о к а з а т е л ь с т в о. Доказательство получается простой модификацией доказательства леммы 2.22. Пусть. Е = Е (М,). Тогда М моделирует М„храня в конечной памяти своего управляющего устройства очередной входной символ. Если М„ переходит в заключительное состояние и 6 †очередн входной символ, то М стирает содержимое магазина. Так как никаких других шагов не требуется и они невозможны, то М вЂ” детерминированный МП-автомат. П Теорема 6.1. Пусть М=((г, Х, Г, б, д„Х„Р) — ДМП-автомат и Е = Е, (М).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
