Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 60
Текст из файла (страница 60)
(гз581, 295 ГЛ. В. ТЕОРИЯ ПЕРЕНОДА Томпсон 11988] приводят елгорнтм, который по регулярному выражению строит программу в мншинном языке, моделнру1ощую соответствующий иеде термииировенный конечный ввтомнт. Этот алгоритм применялся дли среипе. ния образцов в мощноч нзыке (4ГР, предназначенном дли редактированию текстов, Лексический енелизвтор цслссообрввно просктировить твк, чтобы он справлялся с лексическими опьнбкнми. К ним относятся, в частности, (1) темене в лексеме превнльного символа неправильным, (9) потнике в ленсему лишнего символе, (3) пропуск символе в лексеме, (4) перестановка двух смежных символов лексемы.
Технике, позволяющая обнаруживать н исправлять ошибки такого роде, описана Фримэном 119841 и Морганом 11979). Дополнительная литература го обнаружению и исправлению ошибок прн компиляции указана в замечнпинх по литературе в конце равд. !.2, ЭА. СИНТАКСИЧЕСКИЙ АНАЛИЗ Второй фазой процесса компиляции обычно является фаза синтаксического анализа, или разбора. В данком разделе мы дадим формальные определения двух распространенных типов разбора и кратко сопоставим их возможности. Займемся также вопросом о том, что значит: Одна грамматика покрывает" другую. 3.4Л. Определение разбора Мы говорим, что для некоторой КС-грамматики 6 цепочки шЕЕ(6) разобрана, или проанализирована, если известно одно (или, быть может, все) из ее деревьев выводов.
При трансля. ции такое дерево можно „физнчески" построить в памяти машины, но вероятнее, что будет использован какой-нибудь более искусный способ представления. Прослеживая шаг за шагом работу синтаксического анализатора, можно получить дерево разбора, хотя связь между Этими процессами едва ли сразу очевидна.
К счастью, большинство компиляторов осуществляют разбор моделированием МП-автомата, анализирующего входные цепочки либо сверху вниз, либо снизу вверх (см. равд. 2.6). Мы уни дим, что способность МП-автомнта проводить нисходящий ана лиз связана со способностью МП-преобразователя отображать входные цепочки в соответствующие левые выводы. Аналогично восходящий анализ связан с отображением входных цепочек' в их обращенные правые выводы. Таким образом, мы буден трактовать проблему разбора как проблему отображения цепо" чек в их левые или правые выводы. Хотя известно много дру гих стратегий разбора, мы будем опираться иа эти две.
ВЫ. СИНТАКСИЧЕСКИЙ АНАЛИЗ В разных частях книги упоминаются другие стратегии разра В упражнениях, помец(енных в конце равд. 3.4, 4.1 и 6 1 рассматривается анализ по левому участку — метод разбора, рый по своему характеру является и восходящим, и нисходящим. В равд. 6.2.1 мы обсудим методы обобщенного нисходящего и восходящего разбора. Определение. Пусть 6 =(Х, Е, Р, 5) — КС-грамматика, правила которой занумерованы 1, 2, ..., р, Пусть а б (Н () Х)е.
Тогда «1) лепим разборолг цепочки а называется последовательность правил примененных при левом выводе цепочки а из 5, (2) лравым разбором цепочки а называется обращение последовательности правил, примененных при правом выводе цепочки а из 5. Эти разборы можно представить в виде последовательности номеров из множества (1, 2, ..., р). Пример 3.22.
Рассмотрим грамматику 6, с ~акой нумерацией правил: (1) Š— Е+Т (2) Е. Т (3) Т вЂ” Т»Р (4) Т вЂ” Р (6) Р (Е) (6) Р а Левый разбор цепочки а» (а+и) — это последовательность 23466124646, а правый разбор — 64642641632. Лля описания левых и правых разборов введем дополни- тельные обозначения, Соглашение, Пусть 6= — (Х, Х, Р, 5) — КС-грамматика, пра- вила ко о а,.~, есл оторой занумерованы числами от 1 до р.
Будем писать р, если а=>,13 и применено 1-е правило. Аналогично будем писать а ~у~и, если се=>„6 и пРнменепо 1-е ИРапило. РасшиРим эти обозначения, положяв (1) а .,н,=ьу, если а н;-.'>6 и 6 п,=>у, (2) а=-Р„,„,Т, если а=9„, 11 и )3=~„, у, 3 4.2. ° Нисходящий разбе разделе мы хотим исследовать проблему левого ана- В этОм а нза для К КС-грамматик. Пусть и = г,... гн — левый разбор цечкн ге чЕ (6), где 6 — КС-грамматика. Зная и, можно построить ГЛ.
3. ТЕОРИЯ ПЕРЕВОДА х4. Сиитлксический лнллиз ДЕРево Разбора цепочки и! следующим „нисходящим" образом, Начнем с корня, помеченного 5. Тогда 4, дает правило, которое надо применить к 5. Допустим, что 4,— номер правила 5-э Х,... Х„, Присоединим й потомков к вершине, помеченной 5, и пометим их Х„ Х„ ..., Хл. Если Х! -первый слева петер. минал в цепочке Х,... Х, то первыми ! — 1 символами цепочки 4в должны быть Х,...Х4,. Правило с номером 44 должно тогда ил4еть вид Х, — ~ 1',...)'„и можно продолжить построение дерева разбора цепочки 4в, применяя ту же процедуру к вершине, помеченной Х;. Продолжая в том же духе, можно построить все дерево разбора цепочки 4в, соответствующее левому оазбору и. Допустим теперь, что даны КС-грамматика 6=((л!, Х, Р, 5), в которой правила занумерованы от 1 до р, и цепочка а!ЕХ', для которой мы хотим построить левый разбор.
Можно считать, что известны корень и крона дерева разбора и нал! остается „всего лишь" восполнить промежуточные вершины. Стратегия левого нисходящего разбора предлагает пытаться заполнять дерево разбора, начиная с корня, и двигаться слева направо, направляясь к кроне. Легко показать, что существует простая СУ-схема, отображающая цепочки языка Е(6) в их левые (или правые, если угодно) разборы.
Мы определим здесь такую СУ-схему, хотя предпочитаем исследовать МП-преобразователь, реализующий соответствующий перевод, потому что от него легко перейти к реальному выполнению этого перевода. Определение. Пусть 6 = (Я, г, Р, 5) — КС-грамматика, в которой правила запумеровапы от 1 до а. Определим СУ-схему Т! (или Т4, если 6 подразумевается) как пятерку ((л(, Х, (1, ..., р), 14!, 5), где й4 состоит из таких правил А — а, (), что А — а— правило из Р с номером 4, а Р= — 4а', где а' — это цепочка с4, из которой устранены все терминалы. Пример 3.23. Пусть 6,— обычная наша грамматика с правилами, занумерованными, как в примере 3.22.
Тогда Т, = = ((Е, Т, Р), (+, е, (, ), а), (1, ..., 6), й4, Е), ГДЕ й! СОСтОИт из правил .Е- Е+Т, 1ЕТ Е Т,' 2Т Т вЂ” ТЛР, 3ТР Т вЂ” Р, 4РŠ— (Е), 5Е Р а, 6 Пара деревьев, изображенная иа рис. 3.10, задает перевод цепочки ав(а+а). (::) 296 0 тавляем в качестве упражнения доказательство следующей теоремы: Теорема 3.10. Пусть 6-.--- (Ъ, Х, Р„5) — КС-грамл4ати4са. Тогда Т4=-((ю, )(5в=~4е).
д о к а з а т е л ь с т в о. Можно доказать индукцией, что (А А)=>~ (о4, п) тогда и только тогда, когда А„=Оса!. р1 РИС. 3.!О. ПЕРЕВОД СХЕМОЙ Т;. а — ВХОД; Π— ВЫХОД. С помощью конструкция, подобной конструкции леммы 3.2, л4ожно для любой грамматики 6 построить недетерминированный МП-преобразователь, работающий как левый анализатор для 6, Определение. Пусть 6 = ()л(, Х, Р, 5) — КС-грамматика, в кото- если 6 рой правила занумерованы от 1 до р. Пусть Мо (или М ! ! 6 подразумевается) — недетерминироваппый МП-преобразователь ((4)), 2, )л(1)Х, (1, 2, ..., Р), б, д, 5, сч), где б определяется так; ° ) (!), е, А) содержит (4), а, !), если А — а — правило из Р (1) б с номером (2) б(4), а, а)=((у, е, е)) для всех аЕТ.
Назовем Мо левым анализатором для 6. 299 ГЛ. 3. ТЕОРИЯ ПЕРЕВОДА зм. синтАксический АнАлиз Для входа се анализатор М,моделирует левый вывод в грац. матике 6 цепочки ш из Е, По правилам (1) М, каждый раз „развертывает" нетерминал, расположенный наверху магазина, в соответствии с некоторым правилом из Р и одновременно выдает номер этого правила. Если наверху магазииа находится терминальный символ, то М, по правилу (2) проверяет, совпадает ли он с текущим входным символом. Таким образом, М, может производить только левый вывод цепочки ех Теорема 3.11. Пусть 6 — (14(, Х, Р, Ь) — КС-грамматика.
Тогда ,(М,)=((, )) . До к а з а т е л ь с т в о. Еще одно элементарное упражнение на индукцию. Здесь предположение индукции состоит в том что (д, н4, л, е) )-*(д, е, е, я) тогда и только тогда, когда Л ч=:> 4Е С) Заметим, что Мо — это почти, но не совсем МП-преобразо. ватель, который получается по лемме 3.2 из СУ-схемы То. Пример 3.24. Построим левый анализатор для грамматики 6,, Здесь М, =- ((д), Х, )Ч Ц Х, (1, 2, ..., 6), б, 4(, Е, 8) где б (,), е Е) = ((4, Е+ Т, 1), (4, Т, 2) ) б (а, е Т) =- ((4(, Т Р, 3), (д, Р, 4)) б (4), е, Р) =.
44(а, (Е). 6)* Й а 6)) б (4, б, б) = ((д, е, е) ) для всех (4 Е Х Для входной цепочки а+а«а левый анализатор Ма может среди других сделать такую последовательность тактов: (41, аз;а«а, Е, е) )- (4, а+а«а, Е+Т, !) ! — (д, а+а«а, Т+Т, 12) )- (4), а (-а»а, Р+Т, 124) 1- (д, а+а «а, а+ Т, 1246) ! — (а, +а»а, +т, 1246) 1 — (д, а»а, Т, 1246) )-(Ч, а«а, Т Г, 12463) — (а, а«а, Г«Р, 124634) )- (4), а«а, а«Р, 1246346) )- (4, »а, «Р, 1246346) )- (д, а, Р, 1246346) )- (4 а, а, 12463466) 'г- (4), е, е, 12463466) !-) Левый анализатор представляет собой, вообще говоря, недетерминирова иное устройство. Чтобы пользоваться им на пракнужно уметь моделировать его детерминированио.
для некоторых грамматик (например, для тех, что содержат циклы) ПОЛНОЕ МОДЕЛИРОВаине невозможно (в данном СЛуЧае пстоМу, что некотоРые цепочки имеют бесконечно много левых РазбоРов). Кроме того, естественное моделирование, которое мы рассмотрим в гл, 4, непригодно для более широкого класса грамматик, а именно для леворекурсивных грамматик. Нисходящий анализ налагает существенное Ограничение: должна быть устранена левая рекурсия. Существует естественный класс грамматик — Они называются 1,).-грамматякамн (вход читается слева (1е(1) направо и выдается левый (!е(1) разбор) и рассматриваются в равд. 5,1,— для котоРых левый разбор можно сделать детерминированным с помощью простого приема, состоящего в том, что анализатор заглядывает яа входе на несколько символов вперед и делает очередной шаг на основе того, что он при этом видит.
ЕЬ-грамматики — это тс, которые „естественным образом" анализируются детерминированным левым анализатором. Можно рассмотреть более широкий класс грамматик, для каждой из которых возможен ДМП-преобразователь, реализующий СУ-схему Т,. Он содержит все Ы.-грам«4атики и некоторые другие, которые можно анализировать только „неестественным" способом, т. е. таким, когда содержимое магазина не отражает в отличие от анализатора М, последовательности шагов левого вывода. С точки зрения нисходящего анализа такие грамматики представляют только теоретический интерес, но мы кратко рассмотрим их в равд 3 4 4 йосходящий Займемся теперь правым разбором. Возьмем правый вывод "в грамматике 6, цепочки а+а«а из Е: Е~,Е+Т =з»„Е+Т»Р = „Е+Т =>,Е+Р«а ~,Е+а»а =Ф,Т+а»а ~,Р+а»а =~, а+а»а Записывая в об в о Ратном порядке последовательность правил, в этом выводе, получаем правый разбор 64264631 твующих в очки а а»а т'л.в.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
