Конспект лекций Рекомендовано Учебно-методи
Скачать 1.01 Mb.
|
│ входной цепочки │ предшеств. │ выполнения действия │ ├──────────────────┼────────────┼─────────────────────────┤ │ │ │ # │ ├──────────────────┼────────────┼─────────────────────────┤ │ b ( a a ) b # │ <. │ # <. b │ ├──────────────────┼────────────┼─────────────────────────┤ │ ( a a ) b # │ <. │ # <. b <. ( │ ├──────────────────┼────────────┼─────────────────────────┤ │ a a ) b # │ <. │ # <. b <. ( <. a │ ├──────────────────┼────────────┼─────────────────────────┤ │ a ) b # │ .> │ # <. b <. ( │ ├──────────────────┼────────────┼─────────────────────────┤ │ M a ) b # │ <. │ # <. b <. ( <. M │ ├──────────────────┼────────────┼─────────────────────────┤ │ a ) b # │ =. │ # <. b <. ( <. M a │ ├──────────────────┼────────────┼─────────────────────────┤ │ ) b # │ =. │ # <. b <. ( <. M a ) │ ├──────────────────┼────────────┼─────────────────────────┤ │ b # │ .> │ # <. b <. ( │ ├──────────────────┼────────────┼─────────────────────────┤ │ L b # │ =. │ # <. b <. ( L │ │ M b # │ =. │ # <. b M │ ├──────────────────┼────────────┼─────────────────────────┤ │ b # │ =. │ # <. b M b │ ├──────────────────┼────────────┼─────────────────────────┤ │ # │ .> │ # │ ├──────────────────┼────────────┼─────────────────────────┤ │ S # │ <. │ # <. S │ ├──────────────────┼────────────┼─────────────────────────┤ │ # │ .> │ Анализ завершен успешно │ └──────────────────┴────────────┴─────────────────────────┘ ш0 2Упражнение. 0Предложите варианты диагностики возможных ошибок во входной цепочке при использовании таблицы предшест- вования. 29. ГЛОБАЛЬНЫЙ АНАЛИЗАТОР Глобальный анализатор, известный также под названием ана- лизатора Унгера [2], реализует нисходящий метод синтаксическо- го анализа. Этот метод относится к числу рекурсивных методов, и поэтому может быть причислен к множеству методов, объединен- ных названием "методы рекурсивного спуска". . - 61 - Преимущества метода Унгера заключаются в следующем: - достаточно простой алгоритм анализа; - наличие непосредственной связи между алгоритмом анализа и грамматикой, что способствует повышению надежности програм- мирования анализатора; - глобальный характер метода позволяет включать в анали- затор элементы генерации объектного кода, так как в каждый мо- мент известно правило вывода, по которому производится разбор, хотя компоненты этого правила еще не до конца разобраны. Вообще говоря, метод Унгера не является детерминирован- ным. Тем не менее, как и в случае LL- и LR-анализаторов, а также анализатора предшествования, можно сформулировать опре- деленные ограничения, накладываемые на исходную грамматику, при выполнении которых анализ будет выполняться без возвратов. На этих ограничениях мы останавливаться не будем. Перейдем к описанию основной идеи метода. Пусть имеется некоторая КС-грамматика с начальным симво- лом I. Основу анализатора составляет рекурсивная функция MATCH(N,x), где N - некоторый нетерминальный символ, а x - терминальная цепочка. Функция MATCH возвращает значение true, если в грамматике возможен вывод: N=>x, в противном случае функция возвращает значение false. Проверка выводимости N=>x начинается с выбора одного из имеющихся правил вывода для нетерминала N. Пусть выбрано неко- торое правило вида: N-> x1 N1 x2 N2 ... xt. Если цепочка x не может быть представлена в виде x=x1 z1 x2 z2 ... xt, то выби- рается следующее правило. Если более правил нет, функция фор- мирует отрицательный результат. Если же сопоставление найдено, то результат определяется выводимостью: N1=>z1, N2=>z2, ... , N(t-1)=>x(t-1). Для этого рекурсивно вызываются функции MATCH с соответствующими параметрами. Если хотя бы одна функция возвращает результат false, то проверяется следующий вариант разбиения. И так продолжается для всех оставшихся разбиений и правил вывода. Таким образом, для того, чтобы убедиться в принадлежности цепочки x языку с начальным символом I, необходимо вызвать булевскую функцию MATCH(I,x). Для ускорения работы анализатора применяются так называе- мые ускоряющие тесты. Перечислим некоторые из них. - 62 - 2Тест "на длину". 0 Прежде чем проверять выводимость цепоч- ки, следует убедиться, что эта цепочка не имеет длину больше или меньше, чем длины цепочек, выводимых из рассматриваемого нетерминала. 2Тест "на начало". 0 Прежде чем проверять выводимость цепоч- ки, следует убедиться, что эта цепочка имеет начальный символ, принадлежащий множеству начальных символов для цепочек, выво- димых из рассматриваемого нетерминала. 2Тест "на конец". 0 Прежде чем проверять выводимость цепоч- ки, следует убедиться, что эта цепочка имеет конечный символ, принадлежащий множеству конечных символов для цепочек, выводи- мых из рассматриваемого нетерминала. 2Тест "на середину". 0 Прежде чем проверять выводимость це- почки, следует убедиться, что эта цепочка не имеет внутренних символов, недопустимых для цепочек, выводимых из рассматривае- мого нетерминала. 2Тест "на скобки". 0Если для грамматики выделено подмно- жество терминальных символов, называемых скобочными и правые части всех правил вывода имеют правильную скобочную структуру, то применим следующий тест: прежде чем проверять выводимость цепочки, следует убедиться, что эта цепочка имеет правильную скобочную структуру. 2Упражнение. 0Для проверки перечисленных тестов требуется выполнить подготовительную работу по анализу грамматики: 1) опишите процедуры формирования множеств начальных, ко- нечных и внутренних символов для нетерминалов грамматики. Эти множества называются PRE(N), POST(N), ALPHA(N); 2) опишите процедуру определения минимальной и максималь- ной длин цепочек, выводимых для заданного нетерминала грамма- тики (обратите внимание: может оказаться, что из нетерминала могут выводиться цепочки любой длины, то есть максимальная длина цепочки будет тогда равна бесконечности). . - 63 - 210. ОБРАБОТКА ОШИБОК 210.1. Синтаксические ошибки До сих пор мы рассматривали действия анализатора лишь по установлению соответствия или несоответствия входной цепочки данному языку. В качестве побочного эффекта определялась структура предложения. Если встречалась недопустимая конструк- ция, то анализатор прекращал работу. На практике встречается такое, но, пожалуй, это не лучший выход из положения. Кроме того, мы не затрагивали вопросы диагностирования ошибок. А что же более всего нас устроило бы в ошибочной ситуации? Вот неко- торые желательные качества транслятора: - наиболее полная и точная диагностика по обнаруженной ошибке, - по возможности полное перечисление всех допущенных оши- бок, - минимальное количество "наведенных" ошибок. Анализатор в ошибочной ситуации, чтобы продолжить разбор, должен "понять", что же имел в виду автор неправильной прог- раммы. Решить эту задачу в полном объеме практически невозмож- но. Здесь же мы сформулируем лишь некоторые рекомендации [3]: 21 0) входной язык должен быть достаточно простым, чтобы эф- фективно решать задачу восстановления в ошибочной ситуации. (Примеры упрощения языка: введение специальных служебных слов, добавление всевозможных сбалансированных скобочных символов, полная спецификация всех об"ектов, запрещение принципа умолча- ния); 22 0) процедура анализа, обнаружившая ошибку, не должна прекращать работу. Она должна продолжить чтение входной цепоч- ки до момента, возможного для продолжения анализа. У классиков это требование звучит так: "Не поднимай панику!". Однако, для диалоговых трансляторов целесообразно сразу сообщать об обна- руженной ошибке. Если язык уже определен, то остается сделать упор на реа- лизацию второй рекомендации. Для этого каждая процедура анали- за должна располагать множеством внешних символов (ограничите- лей), и тогда чтение входной цепочки после обнаружения ошибки можно будет продолжить без синтаксического анализа до ближай- - 64 - шего символа из этого множества. Очень часто в роли внешнего символа выступает точка с запятой. С другой стороны, ошибка может заключаться именно в про- пуске этого внешнего символа. Тогда нежелательно пропускать целиком конструкцию до следующего внешнего символа. Поэтому, добавим к внешним символам символы, начинающие новые конструк- ции (такие как: begin, for, if и прочее). Эти символы называ- ются символами возобновления. Ниже приводится процедура Test, сообщающая об ошибке с номером n и продолжающая поиск внешнего символа (s1) или символа возобновления (s2). procedure Test (s1, s2 : symset; n : integer); begin if not(sym in s1) then begin Error(n); s1:=s1+s2; while not(sym in s1) do Getsym end end; Эта процедура должна вызываться всякой процедурой анали- за, обнаружившей ошибку. Заметим, что если пропущен какой-либо внешний символ, то наличие символов возобновления, по существу, позволяет испра- вить эту ошибку и продолжать анализ как ни в чем не бывало. Ниже приведен пример фрагмента процедуры анализа составного оператора (см. анализатор языка PL/0). . . . if sym=begisym then begin Getsym; Statement([semicolon,endsym]+fsys); { здесь fsys - используемый формальный параметр процедуры ана- лиза составного оператора. } { Процедура Statement при обнаружении ошибки через Test найдет или внешний символ, или символ возобновления } - 65 - while sym in [semicolon]+statbegsys do { пока ";" или начало оператора } begin if sym=semicolon then Getsym else Error('отсутствует ...'); statement([semicolon,endsym]+fsys) end; if sym=endsym then Getsym else Error('требуется ...'); end Конечно, все варианты предусмотреть невозможно, однако, хороший транслятор должен обладать следующими свойствами: 1) никакая цепочка не должна приводить к катастрофе; 2) все конструкции, которые по определению языка являются незаконными, должны обнаруживаться и отмечаться; 3) ошибки должны правильно диагностироваться и не должны приводить, по возможности, к наведенным ошибкам; 4) предлагаемые транслятором действия по устранению оши- бок должны носить характер рекомендаций и не должны порождать новых ошибок, если следовать этим рекомендациям. 210.2. Контекстные ошибки Обычно, языки программирования описываются КС - граммати- ками, но, как известно, этого недостаточно. Как быть с кон- текстными свойствами языка? Здесь возможны два пути: усложне- ние формального аппарата описания языка или написание конкрет- ных контекстных проверок в данном трансляторе. Что касается первого пути, то здесь следует отметить атрибутные грамматики [9,11], позволяющие описывать большинство контекстных условий. В нашей стране, в частности, велись работы в этом направлении в Москве (проект системы построения трансляторов СУПЕР - син- таксически-управляемый перевод). Второй путь достаточно хорошо проработан и заключается в создании и контроле всевозможных таблиц. . - 66 - Например, для контроля единственности описаний переменных величин используется таблица идентификаторов. Если реализуемый язык имеет блочную структуру, то и помещаемый в таблицу иден- тификатор, помечается значением уровня блока. Иногда необходи- мые проверки включаются в грамматику. Получающиеся грамматики называются атрибутными, но здесь мы их не рассматриваем. 2Упражнение. 0 Сформулируйте необходимые проверки для конт- роля единственности и обязательности описания всех величин. Отметим, что некоторые из контекстных условий могут быть проверены уже на стадии лексического анализа. 211. ГЕНЕРАЦИЯ КОДА Излагаемый в данной главе материал взят из уже цитирован- ной работы Вирта [13], а также представляет собой скромный вклад автора [14-16]. Как уже отмечалось, процесс компиляции можно разбить на несколько этапов. После того, как программа проанализирована, сформированы необходимые служебные таблицы, определена син- таксическая структура, компилятор должен перейти к построению объектного кода. Чтобы не ориентироваться на какой-то конкрет- ный машинный язык, проиллюстрируем процесс генерации на приме- ре некоторого условного языка. В качестве такого языка возьмем промежуточный язык Вирта известный под названием Р-кода [13]. В данной работе [13] Р-код применяется как выходной язык транслятора. Входным языком является подмножество языка Паскаль. Это подмножество получило название Паскаль-S. По сравнению с полным Паскалем в этом подмножестве отсутствуют записи с вариантами, оператор присоединения и оператор перехо- да. На рисунке 15 приведена соответствующая Т-схема. ш1 ┌───────────────────────────────┐ │ Паскаль-S Р-код │ └──────────┐ ┌──────────┘ │ Паскаль │ └─────────┘ Рис. 15. Схема трансляции языка Паскаль-S ш0 Нам интересна эта реализация, так как ее принципы можно рассмотреть в рамках учебного пособия. В то же время вырази- - 67 - тельная мощность Р-кода позволяет использовать его после неко- торого расширения в качестве выходного языка для многих импе- ративных языков. Идея расширения кода интересна и сама по себе. Представим себе, что у нас имеется программа интерпретатора. Пусть неко- торый новый язык отличается, скажем, управляющими операторами. Тогда можно попытаться дополнить наш Р-код новыми командами, удобными для предствления этих операторов. Обычно в этом слу- чае изменения интерпретирующей машины могут быть незначитель- ны, а этап генерации существенно упрощается, так как команды объектного языка оказываются приближенными к операторам вход- ного языка. Вряд ли Р-код может претендовать на роль уни- версального объектного языка, но трансляция на него императив- ных языков вполне возможна. В специальной литературе печата- лись исследования по применению Р-кода для трансляции таких языков как Фортран и Алгол-60. Ниже представлен интерпретатор Р-кода, кратко описаны ко- |
Похожие:
 | Конспект лекций Владимира Климентьева по истории философии, отредактированный... Рекомендовано Министерством общего и профессионального образования Российской федерации в качестве учебника для студентов высших... | | Курс лекций 2-е издание, стереотипное Минск 2005 удк 008(076. 6) Рекомендовано к изданию Комиссией по приемке и аттестации электронных версий учебных и учебно-методических материалов Академии управления... |
| С. П. Филин Концепции современного естествознания: конспект лекций Конспект лекций соответствует требованиям Государственного образовательного стандарта высшего профессионального образования РФ и... | | Учебно-методический комплекс Специальность: 080801. 65 (351400) Прикладная... С 56 Современная информационная культура: Учебно-методический комплекс / авт сост. С. Б. Голубцов – спб.: Ивэсэп, 2010. – 42 с |
| Конспект лекций раскрывает содержание и структуру учебной дисциплины... Налоговое право : конспект лекций / сост доцент Р. В. Бобринев; Кузбасский институт экономики и права. – Кемерово, 2011 – 144 с | | Тема Содержание Нормативно-правовые документы и учебно-методическое обеспечение к началу учебного года |
| Конспект лекций Анализ рынка Форекс Учебно-тематический план дисциплины «Учет и операционная деятельность в банках» 7 | | Учебно-методический комплекс по дисциплине «Философия права» Учебно-методический комплекс включает учебную программу курса, учебно-тематический план, конспект лекций, планы проведения семинарских... |
 | И. В. Кузьмин «29» августа 2013 года ... | | Организация производства курс лекций Рекомендовано к печати методической комиссией экономического факультета ггау, протокол №1 от 22. 09. 2004 г |
| Конспект лекций по философии Часть 1 Античная философия Новосибирск... Савостьянов А. Н. Конспект лекций по философии / Новосиб гос ун-т. Новосибирск, 2007. Ч. Античная философия. 68 с | | Информационный бюллетень новых поступлений книг за сентябрь 2011 года Амангельдиева Ж. А. Финансы: учебно-методи-ческий комплекс. Астана: Казату, 2010. 146с. 1 Сбо., 2 н а., 2 ч з., 1 оф., 59 уч а |
| Конспект лекций по курсу хозяйственного права тема Понятие хозяйственного права Кафедра Истории, социологии и права Назаров Андрей Александрович конспект лекций по курсу хозяйственного права | | Рабочая учебная программа по дисциплине конспект лекций по дисциплине Дисциплина входит в федеральный компонент профессионального цикла дисциплин специальности и является обязательной для изучения. Данный... |
| Рабочая учебная программа по дисциплине конспект лекций по дисциплине Дисциплина входит в цикл общих математических и естественнонаучных дисциплин специальности и является дисциплиной по выбору студента.... | | Конспект лекций по высшей математике. В 2 частях. Часть М.: Айрис-пресс,... Баранова Е. С., Васильева Н. В., Федотов В. Л. Практическое пособие по высшей математике. Типовые расчеты. Учебное пособие. — Спб:... |
