Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 6
Текст из файла (страница 6)
В противном случае выдастся сообщение об ошибке. Заметим, что если в верхушке магазина находится Е, то никакие свертки невозможны. Поскольку вторая компонента метки представляет собой символ, находящийся в верхушке магазина, во многих случаях >дается избежать его ненужной проверки, если извсспго, чтб зто за символ, Зная, что в верхушке магазина находится символ Е, можно было бы заменить операторы (7.2.1) на 5Е: !) )! В 5) (+ — -'; ! В 5+ бме(5 ! допуск ошибка Здесь оператор ошибки стоит последним не случайна.
Когда Е находится в верхтшкс магазина, тек)щим входным сиывололг должен бь7ть один из символов ), -, 'или 5. В противном сл>- чае мы получаем ошибку Соагветственно упорядоччв операторы, можно сначала провести проверку на ), потом на -7-, а затем на 9 и, если ни один из этих символов не является текущим входным символом, сообщить об ошибке.
Строка, отвечающая на рис. 7.9 символу Т, порождает оаераторы (7.2.2) 5Т7 '(". — "! 45 В ЕТ7 Е+Т! Е! СТ Т! Е! СТ СТ: !) ! 5Е !+ 5Е 5Е ошибка Здесь Т='В порождает первый Оператор, Тйл), ТЗ 4- и Т блб указывают, что, если в верхушке магазина находится символ Т„ нада выполнить свертку. Так как мы рассматриваем грамматику слабого предшествования, то в соответствии с леммой 5.4 при свертке всегда применяется правило с самой длнн- гл. г лгетоды опти«1изхции синт*ксичесКих хнхлизлтозов тг оптимизация хнхлизхтоеов «лопдх — зелисх ной правой частью вх всех применимых правил.
Таким образом, сначала выясняем, содержится лн в верхушке магазина комбинация Е,'-Т. Если да, то заменяем Е+Т на Е. В противном случае свертываеи Т в Е. Какой бы из ЕТ.операторов ни применялся, известно, что в верхушке магазина находится символ Т. По«гому можно написать РТ: Е+4е! Е! СТ зр! — Е! Ст и тем самым вновь избежать ненужной проверки верхнего символа магазина. После выполнения свертки проверяется, была ли оиа законной. Иными словами, выясняется, что представляет собой теку.
щий входной символ: ), + или $. Для зтого используется группа операторов проверки, помеченных СТ. Если текущий входной символ †), не Ь и пе 3, та вьщается сообщение об ошибке. Порядок действий, при котором вначале делается свертка, а затем проверяется, надо ли было ее делать, может не всегда оказаться желательныи, но, выполняя зги действия именно в таком порядке, мы получаем возможность совместить общие операции проверки, Для проведения такой проверки введем вычисляеыый оператор перехода вида указываюаГий, что верхний символ магазина должен стать послед.
ним символом меюаь Можно заменить операторы проверки в (7.2.2) последовательностью операторов СТ: !) 6 (+! 6 )б! 6 ошибка С: ур! ! бур Теперь можно применять зги операторы проверки и в других последовательностях. Например, если в 6, свертка выполняется, когда в верхушке магазина находится Т, то новым верхнич символом магазина должен быть символ Е. Таким образом, все операторы в группе СТ передают управление на метку БЕ. Однако, вообще говоря, возможны свертки н в несколько различных нетермицалов, и тогда тот же вычисляемый оператор перехода работает с другими верхними символами магазина.
Наконец, ради удобства 'позволим операторам иметь более одной метки. Польза от такого допущения, которое несложао 32 реализовать, станет ясной в дальнейшем. Приведем алгоритм, использующий изложенные идеи. Алгорити 72. Построение анализатора Флойда— Эванса по обратимой грамматиие слабого пред- шествования. « Заг «Еа, ! а, а, ! )а„ а, ! (а. аг! «Еа« ЕХЕ и, з(е! Л, ! выдача р, СХ, а,ф-! А, ! выдача р, СХг вылача рз СХг ошибка С С А„! ! Ь, СХЛ ! ! ошибна А.
зз«цш, ъ' т 3 Вход. Обратимая граыматика слабого предшсствоваиия 6 (7(, 2, Р, Е). Выход. Анализатор на языке Флойда — Эванса дяя 6. Л(еж од. (1) 11айти для 6 отношения предшествования Вирта — Вебера. (2) Линейно упорядочить мвожество МБВ() (й); например, так: (Х„Х„..., Х ! (3) Порождать операторы для Х„Х„..., Х„следующим образом. Допустим, что Хг нс является начальным символом и либо Хг(а, либо Х, ' а для всех а из (ао а„..., а ! и Хг)зЬ для всех Ь нз (Ьо Ь„..,, Ьг!. Кроме того, предположим, что Л, -- а,Хо А, ц,Х„..., А«а„Х, — правила, в которых Х,— последний снчвол правой части, расположенные так, что и Х; не является суффиксом цепочки а«Х, при р ( Ф Считаем, что А« .
ц«Х, имеет номер рз, 1(Ь(й. Затем порождаем операторы ЕХЛ Гл. Т. МЕТОДЫ ОПТИЛ!ИЗАЦИН СИНТАКСИЧЕСКИХ АНАЛИЗАТОРОВ Если ) =О, то первый оператор группы )тХ; имеет также метку 5Хг, Если й 6, то оператор ошибки в группе )(Х, имеет метку РХ, Если Х,— начальный сиьгвол, то делаем все, как раныпе, и добавляем в конец группы 5ХВ оператор 5 з(А(5 ) допуск 55 †начальн состояние анализатора. (4) Добавить вычисляемый оператор перехода 6: Р) )5УУ- Е) Пример 7.6. Рассмотрим грамматику 6,.
По строке Е матрицы предшествования можно получить операторы 5Е: А'Тл): Т л 4Е -АА Заметим, что третий оператор не нужен, потому что сравнение, выполняемое вторым оператором, всегда дает положительный результат. В принципе можно включить в алгорити 7,2 проверку, позволяющую не порождать ненужные операторы. В дальнейшем мы будем считать, что ненужные операторы не порож. даются. По строке а получаем операторы Еш Уй) Е Отметим, чю операторы проверки для и совпадают с операторами вроверки для Р. В следующем разделе мы опишем в общих чертах алгоритм, объединяющий излишние операторы. На самом двлс операторы ') Отнесли лааальзавлиле Вескальлих натах у адаага ааарзтарл. Здесь группа ля пугтл.
Сл.' () (+ )» (6 Т( выдача 3 — Т( выдача 4 ошибка ) ) + 5 ( 6 б 6 6 ошибка выдача 6 СО 6 б 6 ) 6 ошибка Т.Л. ОПТИМИЗАЦИЯ АНАЛИЗАТОРОВ ФЛОЙДА — ЭВАНСА проверки, помеченные меткой СТ, всегда ногино слить с операторами, помеченными меткой СЕ, написав Сп: СР; )е 6 6 6 б ошибка СТ: () )б ) В нашем алгоритме слияния будут также выполняться частные объединения такого рода. Строка матрицы предп~ествовання, помеченная символом (, порождает операторы 5( (( () )л а) з5( *5а ошибка Аналогичные операторы порождаются строками, помеченными символами +, л и 5.
П В качестве упражнения предлагаем проверить, что алгоритм 7.2 порождает для б корректный правый анализаюр, 7.2.2. Усоввршонствованнв анализаторов Фиойдз— Эванса В данном разделе мы изучим методы, применяемые для уменьшения числа операторов переноса и проверки в анализаторе Флойда †Эван, построенном с помощью алгоритма 7.2. Наш основной метод состоит в слияпии общих операторов переноса и общих операторов проверки. По ходу дела могут добавляться дополнительные операторы, вызывающие безусловные переходы, но мы будем считать, что их относительный вес сравнительно мал.
Обсудим, как выпшшяется слияние операторов переноса; тот же метод применим и для слннния операторов проверки. Пусть 6 †.(Ы, 2, Р, 5) †обратил~ грамматика слабого пред- шествования и М вЂ” ее матрица отношений предшествозания Вирта — Вебера. Матрица М определяет операторы переноса и проверки, возникающие в алгоритме 7.2. По матрин~е предшествования М построим совмещенную млсь Рану иеренгсав М, следую|циц образом: (!) Выбросим зсе элементы зь и заменим ' на чч.
(Так как мы интересуемся только переносами, отношении с( и ножно Отождествить.) (2) Если две или более строки полученной матрицы совпадают, заменим их одной строкой в М„ причем свяжем с этой новой 35 гл т, лштоды оптимизации синтгксичвских лнглизатогов строкой множество тех символов из Р)() 2 0 ((ь), с которыми были связаны исходные строки, (3) Выбросим все строки, ие содержащие элементов В! полученную матрицу обозначим М,. Пример 7.10, Совмещенная матрица переносов для 6„ полученная из матрицы рис.
7.9, изображена иа рис. 7.13. Зта сов. ( в у + г т з оптимизация ьнализьтогов алопда — эванса Путь из 8 в Л, проходищий через 1', в графе переносов допускает следующ)то иптерпрета'гию, Метка !(21, 1') ранна числу операторов переносов, построенных для строки У матрицы М, Таким образом, число операторов переноса, порождаемых для строк У и г, равна 1(кг, 1О.Р((8, л). Однако, если в графе есть а, аг аь аь в аь (1+ * Ф) Пз Раг. 7.1З. Мгтрищ пгреаасав Зьь. зь 37 Ргг 7,15. Савмегььаага матрагг игрьаосгв. мещепная матрица переносов точно отражает ситуации, в которых анализатор выполняет першьос.
С) По совмещенной матрице переписав М, построим неупорядо- ченный помеченный ориентированный граф (А, 77), называемый графам пгргмпгав, связанным с М,: ( ) Для каждой строки матрицы М„ помеченной символом 1', ! в А найдется вершина, помеченная символом У. ( ) Существует одна дополнительная вершина, помеченная 2ь С символом !З, которая представляет фиктивную пустую ст о ( ) Если строка У матрицы М, покривившая строкон Л ыат- 3 р ку. рицы М, (т. е. в каждом столбце, где !' имеет элемент строка Л тоже имеет элемент сй), то дуга [У, Л) содержится в 77.
та дуга помечена числом, равным числу столбцов, в которых 7. имеет элемент ьд, а У вЂ” нет. Заметим, что строка У может быть пустой. Метку дуги (У, Л) обозначим через 1(), Е). Пример 7.11. Рассмотрьььь матрицу переносов М„приведениуьо на рис. 7.16. Граф переносов, связанный с М„изображен на рис. 7.17. Ясно, что граф переносов представляет собой ориентирован.
ный ациклический граф с единственным корнем !З. Число опе- раторов переноса, порождаемых алгоритмом 7.2, равно числу элементов переноса (гу или ' ) матрицы предшествоваияя М. сиользуя матрицу переносов М, и сливая строки с совпадаю- щими элементами переноса, можйо уменьшить число треб)смых операторов переноса. Метод заключаетсн в построении для графа переносов аригмтььритиинага аггпавнага двргви (аглюга) (т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
