Конспект лекций Рекомендовано Учебно-методи
Скачать 1.01 Mb.
|
Кроме левостороннего существуют правосторонние и смешан- ные выводы. Под правосторонним или восходящим (от терминальной цепоч- ки к начальному символу) разбором понимается обратная последо- вательность порождающих правил при правостороннем выводе. В нашем примере с цепочкой (a+b)*a правосторонний вывод соот- ветствует последовательности номеров: 2,3,6,4,5,1,4,7,2,4,6; а правосторонний разбор - это номера: 6,4,2,7,4,1,5,4,6,3,2. Позже будет показана связь левостороннего и правостороннего разборов с порядком построения дерева вывода. 23.2. Дерево разбора Найденный вывод цепочки можно представить в виде дерева, где корню дерева соответствует начальный символ грамматики, а терминальным символам соответствуют листья дерева. На рисунке 6 приведено дерево для цепочки из предыдущего примера. Обрати- те внимание, в дереве не отражен порядок применения правил вы- вода; то есть всем возможным выводам соответствует одно дере- во, поэтому дерево называется деревом разбора. Структура дере- ва наглядно показывает структуру терминальной цепочки. Номера- ми обозначены применяемые правила. - 26 - ш1 E │ 2 T │ 3 ┌─────────────┼─────────────┐ │ │ │ T * F │ 4 │ 6 │ │ F a │ 5 │ ┌─────────┼────────┐ │ ( E ) │ 1 ┌─────┼─────┐ E + T │ 2 │ 4 T F │ 4 │ 7 F b │ 6 a Рис. 6. Пример дерева вывода ш0 Теперь видно, что левосторонний разбор соответствует построению дерева разбора в порядке сверху вниз. Правосторон- ний разбор эквивалентен построению дерева снизу вверх. Для этого же примера структура может быть задана в виде линейно-скобочной записи: (E (T (T (F '(' (E (E (T (F 'a'))) '+' (T (F 'b'))) ')') * (F 'a'))) Принцип построения этой записи заключается в следующем. Выписываем в скобках символ корня дерева и символы вершин сле- дующего уровня. Если эти вершины являются корнями поддеревьев, то для них выполняем ту же процедуру. Оказывается, существуют грамматики, допускающие построе- ние различных деревьев разбора для одной и той же цепочки. Та- кие грамматики называются синтаксически неоднозначными. Языки, все порождающие грамматики которых синтаксически неоднозначны, называются существенно неоднозначными. . - 27 - 2Упражнение. 0Покажите, что следующая грамматика является синтаксически неоднозначной: 1) S -> S + S 2) S -> a Известна интерпретация построения дерева вывода, напоми- нающая игру в домино. Эта интерпретация принадлежит Де Ремеру. Она заключается в следующем [11]. Каждому правилу вывода соответствует кость домино, у ко- торой одна сторона представлена половинкой квадрата с надписью нетерминала левой части правила вывода, а другая сторона кости содержит половинки квадратов для нетерминалов и целые квадраты для терминальных символов. Их порядок следования определяется порядком следования соответствующих символов в правой части правила вывода. Каждая половинка или целый квадрат помечены соответствую- щим нетерминальным или терминальным символом. Считается, что эти половинки и квадраты соединены эластичными нитями с поло- винкой нетерминала левой части. Количество таких костей опре- деляется потребностью игрока (потенциально их бесконечно мно- го). В начале игры на игровом поле расположена половинка квад- рата, подписанная начальным символом грамматики. Далее необхо- димо подбирать кости таким образом, чтобы половинки образовы- вали полные квадраты. Естественно, как и в настоящем домино, стыкуются только одинаково помеченные половинки. Цель игры - добиться того, чтобы на игровом поле остались только целые квадраты, образующие в порядке слева направо за- данную в начале игры терминальную цепочку. На рисунке 7 приведен пример размещения костей домино для построения терминальной цепочки "a*b" (для грамматики из пунк- та 3.1) . - 28 - ш1 ┌─────────┐ │ E │ ├─────────┤ │ E │ └────┬────┘ ┌────┴────┐ │ T │ ├─────────┤ │ T │ └────┬────┘ ┌──────────────┼───────────────┐ ┌────┴────┐ │ ┌────┴────┐ │ T │ │ │ F │ ├─────────┤ │ ├─────────┤ │ T │ │ │ F │ └────┬────┘ │ └────┬────┘ ┌────┴────┐ │ │ │ F │ │ │ ├─────────┤ │ │ │ F │ │ │ └────┬────┘ │ │ ┌────┴────┐ ┌────┴────┐ ┌────┴────┐ │ │ │ │ │ │ │ a │ │ * │ │ b │ │ │ │ │ │ │ └─────────┘ └─────────┘ └─────────┘ ш0 Рис. 7. Пример игры Де Ремера 23.3. Классификация методов разбора Методы разбора делятся на нисходящие, восходящие и сме- шанные. Это деление определяется порядком построения дерева разбора. Отказ от принятого решения в процессе разбора цепочки на- зывается возвратом. Методы разбора делятся на детерминированные (без возвра- тов) и недетерминированные (с возвратами). Недетерминированные методы более дорогостоящи по сравнению с детерминированными с точки зрения расхода времени и памяти. Сложность при осущест- влении возврата связана с необходимостью аннулирования некото- рых ранее выполненных действий. Конечно, здесь удобны ре- курсивные алгоритмы, которые, однако, в свою очередь не очень эффективны. . - 29 - 24. ЛЕКСИЧЕСКИЙ АНАЛИЗ 24.1. Регулярные выражения Лексический анализ - это первая фаза компиляции. На этом этапе осуществляется группирование строк литер в слова-симво- лы. Примеры таких символов: идентификаторы, служебные слова, числа, разделители. В однопроходных трансляторах лексический анализ выполняется одновременно с грамматическим разбором и генерацией кода, однако, имеет смысл представлять лексический анализ как отдельную фазу. Обычно символы входного языка могут быть сгенерированы с помощью регулярных выражений. 2Определение. 0Регулярное выражение задается следующим об- разом [11]: 21 0) любой символ исходного алфавита или пустая цепочка - это регулярное выражение, 22 0) если P и Q - регулярные выражения, то PQ (за P следует Q - операция конкатенации) - это регулярное выражение, 23 0) если P и Q - регулярные выражения, то P│Q (P или Q - операция выбора) - это регулярное выражение, 24 0) если P - регулярное выражение, то P* (нуль или более экземпляров из P. Здесь "*" - операция повторения) - это регу- лярное выражение. Приоритеты (в порядке убывания): повторение, конкатена- ция, выбор. Например, вещественное число в форме без порядка может быть представлено формулой: (+│-│)dd*.dd* , где d - произвольная цифра. По регулярному выражению легко написать регулярную (авто- матную) грамматику. Автоматная грамматика называется регулярной, если в ней нет правил вывода вида: S->aS, где S -начальный символ грамма- тики. Легко заметить, что любая автоматная грамматика без тру- да трансформируется в регулярную введением нового начального символа. . - 30 - Для предыдущего выражения из предыдущего примера регуляр- ная грамматика будет следующей (здесь под номерами 4, 5, 7 и 8 приведены схемы правил, каждая из которых представляет по десять правил с соответствующими десятью цифрами): 1) R -> + S 5) T -> d T 2) R -> - S 6) T -> . V 3) R -> S 7) V -> d 4) S -> d T 8) V -> d V Существует полное соответствие между регулярными выраже- ниями ( и, следовательно, регулярными грамматиками ) и конеч- ными автоматами, описанными ниже. 24.2. Конечные автоматы Приведем определение детерминированного конечного автома- та [2]. 2Определение. 0 Под конечным автоматом понимается совокуп- ность следующих пяти объектов: 1) K - конечное множество состояний, 2) A - конечный алфавит, 3) S - начальное состояние (из множества K), 4) F - множество заключительных состояний (подмножество K). 5) D: K*A -> K - частично определенная функция переходов. Говорят, что 2конечный автомат принимает 0(допускает) вход- ную цепочку, если при ее анализе, начиная с начального состоя- ния, функция D определена на каждом шаге, и последнее состоя- ние автомата является заключительным. Говорят, что 2конечный автомат не принимает 0 (не допускает) входную цепочку, если или последнее состояние автомата не яв- ляется заключительным, или на каком-либо шаге не определена функция D. Автомат называется недетерминированным, если отображение D многозначно, то есть на всех или некоторых наборах парамет- ров выходное значение состояния определяется неединственным образом. Можно показать, что по всякому недетерминированному - 31 - автомату можно построить эквивалентный ему (то есть, допускаю- щий тот же язык) детерминированный автомат. 2Определение. 0Входная цепочка допускается недетерминиро- ванным конечным автоматом, если существует такой порядок при- менения отображения D, при котором по окончанию входной цепоч- ки последнее состояние является заключительным. В противном случае говорят, что автомат не допускает входную цепочку. Приведем пример конечного автомата для распознавания идентификатора с возможными начальными пробелами, которые обозначим через ' '. Для этого определим все составные части автомата: 1) K = {0,1} 2) A = {a, b, ..., z, 0, 1, ..., 9, ' '} 3) S = 0 4) F = {1} 5) Функцию переходов зададим таблично (см. табл. 1). Си- туацию недопустимого символа обозначим словом fail. 2Таблица 1 2Таблица переходов ш1 ┌─────┬─────────┬─────────┬─────┐ │K \ A│ a,...,z │ 0,...,9 │ ' ' │ ├─────┼─────────┼─────────┼─────┤ │ 0 │ 1 │ fail │ 0 │ ├─────┼─────────┼─────────┼─────┤ │ 1 │ 1 │ 1 │fail │ └─────┴─────────┴─────────┴─────┘ ш0 Удобно задавать конечный автомат графом (диаграммой пере- ходов). В этом случае узлы графа соответствуют состояниям, а направленные дуги помечаются символами. Для предыдущего приме- ра граф представлен на рисунке 8. ш1 ┌───┐ a,b, ..., z ┌───┐ ┌─────>│ 0 ├──────────────────>│ 1 │<──────────┐ │ └─┬─┘ └─┬─┘ │ │ │ │ │ │ ' ' │ │ 0, ..., 9 │ └────────┘ │ a, ..., z │ └─────────────┘ ш0 Рис. 8. Пример графа переходов - 32 - Можно показать, что по любому недетерминированному конеч- ному автомату строится детерминированный автомат, распознающий (допускающий) тот же язык. 2Упражнение. 0Покажите эквивалентность способов задания ре- гулярного языка: лево- и право- автоматные грамматики, детер- минированный и недетерминированный конечные автоматы, регуляр- ные выражения и грамматики (то есть то, что любой язык из класса регулярных языков можно задать каждым из перечисленных способов). 24.3. Лексический анализатор Написание лексического анализатора заключается в модели- ровании различных автоматов для распознавания различных симво- лов. В качестве примера рассмотрим задачу распознавания ве- щественного числа в форме без порядка. Соответствующий конеч- ный автомат представлен диаграммой (графом) переходов на рисунке 9. Под стрелками указаны допустимые символы. Вещест- венное число считается принятым конечным автоматом, если авто- мат перейдет в четвертое состояние. Символ d обозначает как и прежде произвольную цифру. Например, строка "314.1Е-02" считается правильной записью вещественной константы до момента чтения символа "Е" (автомат последовательно находится в состояниях: 0-2-2-2-3-4), но так как при этом строка не исчерпана, то полная запись "314.1Е-02" с точки зрения данного автомата считается некорректной. Второй пример: строка "+.343" считается некорректной, так как символ "." недопустим после знака "+". ш1 ┌─────────────────┐ │ │ ┌───┴───┐ ┌───────┐│d ┌───────┐ ┌───────┐ ┌───────┐ │ 0 ├───>│ 1 │└──>│ 2 ├───>│ 3 ├───>│4(закл)│ │началь-│+/- │чтение ├───>│чтение │ . │чтение │ d │чтение │ │ное со-│ │знака │ d │целой │ │точки │ │дробной│ │стояние│ │числа │┌──>│части │ │ │┌──>│части │ └───────┘ └───────┘│ └───┬───┘ └───────┘│ └───┬───┘ │ d │ │ d │ └───────┘ └───────┘ ш0 Рис. 9. Граф переходов (пример вещественного числа) - 33 - Ниже приведен текст процедуры-функции, реализующей распознавание числа. function Read_Real:boolean; const final=[4]; var s : 0..4; ch : char; { Error - внешняя процедура обработки ошибок } begin s:=0; while not eoln do begin read(ch); if ch in ['+','-','0'..'9','.'] then case s of 0 : if (ch='+') or (ch='-') then s:=1 else if ch in ['0'..'9'] then s:=2 else Error; 1 : if ch in ['0'..'9'] then s:=2 else Error; 2 : if ch='.' then s:=3 else if not(ch in ['0'..'9']) then Error; 3 : if ch in ['0'..'9'] then s:=4 else Error; 4 : if not(ch in ['0'..'9']) then Error; end end; Read_Real:= (s in final) end; Обратите внимание, что приведенная программа "дословно" соответствует диаграмме переходов, то есть наличие диаграммы существенно облегчает процесс написания программы. В приложении 1 приведен текст программы, включающей ска- нер для распознавания лексем: целое число (возможно со зна- ком), знак операции, конец строки. . - 34 - 24.4. Пример сканера для языка PL/0 В качестве примера лексического анализатора рассмотрим сканер Вирта [3], предназначенный для распознавания лексем специального учебного языка PL/0. В приложении 2 приведены синтаксические диаграммы этого языка. Сканер оформлен в виде процедуры Getsym и выполняет сле- дующие действия: 1) пропускает пробелы, 2) распознает разделители, 3) распознает служебные слова, 4) распознает незарезервированные слова как идентификато- ры, 5) распознает последовательности цифр в качестве целых чисел (значение числа присваивается переменной num), 6) распознает знак присваивания ':='. |
Похожие:
 | Конспект лекций Владимира Климентьева по истории философии, отредактированный... Рекомендовано Министерством общего и профессионального образования Российской федерации в качестве учебника для студентов высших... | | Курс лекций 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 частях. Часть М.: Айрис-пресс,... Баранова Е. С., Васильева Н. В., Федотов В. Л. Практическое пособие по высшей математике. Типовые расчеты. Учебное пособие. — Спб:... |
