Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 19
Текст из файла (страница 19)
В алгоритме расщепления грамматики иетерминал А рассматривается как начальный символ соответствующей грамматики, а ЕОЕЕОУУ(А) †к множество возможных аванцепочек для начального множества ситуаций, отвечающего подграмматике бл. Основная цель †объединен некоторых множеств ситуаций, имеющих одинаковые ядра. Сходство этого алгоритма с Я.)((1)- алгоритмом очевидно. В самом деле, как мы увидим, ЯЫ(1)- алгоритм представляет собой алгоритм расщепления грамматики с Х'=Х.
В законченном виде четод выглядит следующим образом. (1) Для данной грамматики 0 = (Х, 2, Р, Я) находим подходящее множество расщепляющих нетерминалов Х'щХ. Включаем Л в Х'. Это множество должно быть достаточно велико для того, чтобы гралгматики-компоненты были небольшими и я~оды для каждой компоненты легко строилось множество Ы(1)-таб.чиц. В то же время число компонент не должно быть слишком большим, чтобы при построении множества таблиц метод не оказался непригодным. (Последнее замечание относится только к грамчатякам, ие являющимся Эьк-грал!ллатнкаллн.
Если грамматика является БЕЕ-грамматикой, то подойдет любой выбор множества Х', а наименьшее множество таблиц будет получено при Х =Х'.) (2) После выбора множества Х' находил1 грамматики-кампо. ненты по алгоритму 7.11. (3) Применяя описанный ниже алгоритм 7.!2, вычисляем множества (.К(1)-ситуаций для каждой из грамматик-компонент. (4) Воспользовавшись затем алгоритмом 7.13, объединяем мвожества-компоненты в систему У множеств ситуалгнй для исходной грамматики.
Этот прием не всегда дает систему непроти- гл. т. мнтоды оптвмизлцяи синг»кснчаских анализ»тозов тл. методы постРоения ьж«ьанллнэлтогов воречивых множеств ситуаций для исходной грамматики, Однако, если снстемв К непроткворечива, множество Б))(1)-таблиц строится затем по «Т обычным способолг. А л г о р н т м 7.12. П о с т р о е и и е м н о ж е с т в )К (1)-с н т у ацкй для грамматик-компонент исходной граммат и к и. Вход. Грвмматика б = (Р], 2, Р, 5), подмножество ]л)' множества В, содержащее 5, и грамматнкн-компоненты бл для всех А ЕВ' Выход. Множества БЕ(!)-ситуаций для всех грамматнк-компонент.
Метод.Для удобства обозначений положим Р)'=(5„5»...,5„). Будем обозначать бз, как б, Пусть А — множество Б))(1)-ситуаций. Вычислим залыкание А' множества А относительно бл. Метод вычнслення напоминает алгоритм 3.3, но не совпадает с ням. А' определяется следующим образом; (1) А ад А' (т. е, все элементы множества А принадлежат А'). (2) Если [В а Сд, и]ЕА' н С 7 — правило нэ бл, то [С 7, о]ЕА' для всех оЕР!КБТ«о(д'и), где р' — это пеночка 3, в которой все символы нз )Ч заменены соответствующнмн символами из М.
Таким образом, в ситуациях все аваицепочкн принадлежат В', а первые компоненты соответствуют правилам грамматики бл. Для каждой грамматики б, построим систему К, множеств Е))(1)-ситуаций для бр (1) Пусть А',— замыкание (относительно бд множества (!5г .а, а])5, а — правило грамматнкн бг н аЕР01Л.ОТ«<л(5,)). Положим Р, =. ( 4) . (2) Повторять шаг (3) до тех пор, пока к Ф не перестанут добавляться новыс множества снтуапнй. (3) ПУсть Х пРинадлежит Р)() 2()й. Если Абдо положим ~'=([А аХ д, и]) [«! а Хд, и] В А). Добавим к У, замыкание А" (относнтельно 6,) множества А'. Итак, А"=ПОТО(А, Х). Отметим, что результат ве изменится, если пополнить каждую грамматику-компоненту нулевым правилом вместо того, чтобы включать РОС].ОУЧ(А) в множество аванцепочек начального мно.
жества снтуаиий. Пример 7.29. Применим алгоритм 7.12 к грамматике 6, с ]й'=(Е, Т). Находим, что ГО).!ОУ«г(Е) — (+, ), е) н ГО!.!О]У(Т) = =(+, », ), е). Таким образом, согласно шагу (!), Аа состоит Т Т Р .1-/ /)/е) г. т .Р, - /«д/е! ГР (Е).
4/ /)/«1 !Р а, 4-/«д/е] г. г. А«П !т г. *Р, -1-/«М«! 17 Р, -1-/ /)/е) ГР (. Е). -г /«/)/«! ! Р а , -1- / /)/е) < !Г 7 «.Р, -!-/«В/е] !Р .(Е), -1-/ /)/е! !Р а, +/«/Ее! (Р (Е ), -1-/'ЛП 17 т Р., +/ де! (Р (Е), л-/ ЛП г, т. г. Рис. 7АЗ. С»ст«мя м»«мест» с»туааий ал» Пт; Заметны, что когда Аа строится по ,(а, символ Т, например, является терминалом, н опера«!ия замыкания ие дает навык ситуаций.
(] Приведем теперь алгоритм, который при определенных условиях строит по множествам ситуаций, образованным для грам- гээ нз ситуаций [Е .Е+ Т, +/)/е] [Е Т, +/)/е] Аналогично А,г состоит нз снтуацнй [Т Т Р, +/~/)/е] [Т Р, +/»/)/е] [Р (Е), +/»/)/е] [Р а, +/»/)/е] Вся система множеств ситуаций, построенных для бт показана на рнс. 7.42, а такая же система для бг — на рнс.
7.43. Аа !г !е .ешт, 4./)/.! ! !Е Т, -лд/«! Аг . '!Е Е..(-Т, -)-д,'«! А«а: !Е 2» --/)/г! А«: !Е Е-1- т, -(-д/е) А«а: )е Еч4- р -!-д/е! Рнс. 7.42. Систем» м»ож»ег» ситуаций да» Ол. ГЛ. Т МЕТОДЫ ОПТИМИЗАЦВИ СИНТАКСИЧЕСКИЕ АНАЛИЗАТОРОВ 1.4, МЕТОДЫ ПОСТРОЕНИЯ СИ!1! АНАЛИЗАТОРОВ матик-компонент с помощью алгоритма 7.12, множества ЕЕ(1)-си- туаций для исходной грамматики. Ал го ритм 7.13. Построен ие множества Е(1(1) таб т иц по м нож ест вам )Я(1) ситуаций для г р ам мат и и.компонентит Влад. КЕ-гралпватика 6 — -(Е, Е, Р, 3), расщепляющсе чио.
жество нетерминалов ВР =-(В„ВМ ..., 5„] и система (А'„А'„ ..., А'„) множеств !.Е(1)-ситуаций для всех грамматик-компонент 6,. Вмлад, Допустимое множества ЕЕ(1)-таблиц для 6 или сообщение о том, что данные множества ситуаций ие позволяют по. лучить допустилюе множество таблиц. Метод. (1) В первых комповентах всех ситуаций заменить символы вида 31 иа ВР Все 31 принадлежат М'. Для измененных таким образом множеств ситуапий сохраним прежние обозначения.
(2) Пусть У„= ([3; ВО е]]. Применить к 71 операцию но. полнениа и обозначи~ь новое множество также чеРез ую В объединенной системе множеств светуаций 34 будет „начальным" множеством. Операция пополнения. Если множество А содержат ситуапию, у которой первая компонента имеет вид А и Вр и В=Раб.у для некоторых Вт 6 ВК и у Е (В 02)', то к А добавить А',. Повторять эту процедуру до тех пор, пока к А будут добавляться новые множества ситуаций. (3) Построим систему У множеств ситуаций, достижимых из У, Сначала У =-(7,]. Звтелг повторяем шаг (4) до тех пор, пока к ю не перестанут добавляться новые множества ситуации.
(4) Пусть 3 511". Можно представить 7 в виде 10 А(,'0.1(',0 0А,'", где А — либо пустое множество, либо одно иэ мно. жеста ([В; Я„е]) или ([3( 3, °, е]). Для всех Х из МОЕ положим А'=-ПОТО(А, Л) н Ал" =ООТО(АЫ, Х)') Обозначим через 3' объединение 1 н таких А„' . Применим операцию пополнения к 3' и обозначим новое множество также че]жз Р'. Пусть КООТО') — таиая фуикцил, что КООТО(3, Х) — -У, тюли Р, Х и 3' связаны опнсадным выше образом.
Добавим множе- 1) Здесь имвкгсв в лмду фуккекв БОТО длл С.. Бслв Х вЂ” рлащеллвющмя 1 квырмкивл, та вместо Х берем Х. ') Буква К абявви» своем лаявлаваем Д. Дм. Карвиьяку, ватару ааасиввекага матадв. ство 3' к свстеме У, если его там еще нет. Будем повторять этот процесс до тех пор, пока какие-то 7 6лт" и Х ЕВ02 позво- ляют добавить к д' новое множество КООТО(У, Х). (5) Когда к т" перестанут добавляться новые множества си- туаций, построим по ТЕ множество ЕЕ(1)-таблиц, пользуяс~ методами равд. 5.2.5.
Если таблица Т = <Е й> была построена по множеству 7, та 3(Х)=КООТО(7, Х). Если котя бы одно из множеств ситуапий порождает конфликты действий при рав- боре, сообщаем об ошибке. Пример 7.30. Применим алгоритм 7.13 к множествам ситуа- ций, приведенным на рис. 7.42 и 7.43. Результат выполнения шага (1) очевиден. В процессе выполнения шага (2) сначала образуется множество 3 = ([Е' .Е, е(), а после примеиеиия 4 е операции пополнения -множество 3„-.1(Е' .Е, а]) 0А, 0,41. В начале шага (3) У =- (Зв).
Переходя к шагу (4), сначала вычисляем У, =ПОТО(бю Е) -- ПЕ' Е °, к() 0,:ге Другими словамн, ПОТО(([Е' Е, е]), Е) = ([Е' Е, е]) н ПОТО(Аве, Е)=Ат'. Множество ПОТО(АТ, Е) пусто. Операция пополнения не расширяет ба Затем вычисляем 3, ООТО(УМ Т)= = Ае0 А,'. Операция пополнения не расширяет 31. Продолжая в том же духе, получаем систелву множеств ситуалнй длл Э'г 7,=([Е' .Е, л])0АецА, 31=([Е' Е, е])0АЕ 31=А," 7,=А, 3 Агец 1тц (т У 1ВЦАг 31 11 т З.=А~0 1,' У,—.-АВОА]' 311 =АР Все множества ситувцнй из б" непротиворечивы, и, значит, по д' можно построить множество ЕЕ(1)-таблиц, приведенное на рис. 7.44.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
