Конспект лекций Рекомендовано Учебно-методи
Скачать 1.01 Mb.
|
| часть прочитанной цепочки с правой частью какого-либо правила вывода [11]. Тогда выполняется свертка этой цепочки с заменой ее на нетерминал левой части. Далее анализ продолжается до тех пор, пока входная цепочка не будет исчерпана. В стеке к этому времени должен находиться начальный символ грамматики. Рассмотрим идею восходящего анализа подробнее на следующем примере. Некоторые тонкости будут обсуждаться дополнительно. 2Пример. 0 Пусть задана следующая КС-грамматика: 1) S -> real Idlist 2) Idlist -> Idlist , Id 3) Idlist -> Id 4) Id -> a │ b │ c │ d Здесь большими буквами выделены нетерминальные символы, а с малой буквы начинаются терминалы. Будем считать, что у нас имеется сканер, который читает из входной цепочки терминальные символы предложения. Пусть на вход подается следующее предло- жение: "real a,b,c". Для работы анализатора потребуется стек, где будет храниться будущая правая часть правила вывода. В таблице 3 приведен пример анализа (в последнем столбце указы- вается выполняемая операция: или сдвиг символа в стек, или свертка подцепочки к нетерминалу). . - 54 - ш1 2Таблица 3 2Пример восходящего разбора ┌─────┬────────┬────────┬──────────────────────┐ │номер│читаемый│операция│содержимое стека после│ │шага │символ │ │выполнения операции │ ├─────┼────────┼────────┼──────────────────────┤ │ 1 │real │сдвиг │real │ │ 2 │a │сдвиг │real a │ │ 3 │ │свертка │real Id │ │ 4 │ │свертка │real Idlist │ │ 5 │, │сдвиг │real Idlist , │ │ 6 │b │сдвиг │real Idlist , b │ │ 7 │ │свертка │real Idlist , Id │ │ 8 │ │свертка │real Idlist │ │ 9 │, │сдвиг │real Idlist , │ │ 10 │c │сдвиг │real Idlist , c │ │ 11 │ │свертка │real Idlist , Id │ │ 12 │ │свертка │real Idlist │ │ 13 │ │свертка │S │ └─────┴────────┴────────┴──────────────────────┘ ш0 Наш разбор считается успешным, так как в стеке располага- ется только начальный символ и входная цепочка исчерпана. Итак, в процессе анализа мы применяли два типа действий: сдвиг и свертка (приведение). При этом выбор действия нами ни- как не комментировался. А, желательно, чтобы на каждом шаге однозначно определялось нужное действие. Далее при выполнении свертки может оказаться, что это действие возможно по несколь- ким сразу правилам вывода. Последнее означало бы, что придется организовывать перебор различных вариантов свертки при попада- нии в тупик. 2Определение. 0 Грамматики, допускающие безвозвратный анализ по принципу снизу вверх при "заглядывании" на k символов впе- ред (слева направо), называются LR(k)-грамматиками. В обозначении LR первая буква L обозначает, что разбирае- мое предложение читается слева направо. Вторая буква R обозна- чает, что строится правосторонний разбор. Позже будет показа- но, что определение LR-грамматик, так же как и LL-грамматик связано с определенными ограничениями. В случае LR-грамматик это ограничение касается однозначности каждой клетки специаль- ной таблицы разбора. На практике чаще всего рассматривают LR(0)- и LR(1)-грам- матики. На самом деле, справедливо следующее утверждение. 2Теорема. 0Если некоторый язык относится к классу LR(k)-языков при некотором k (то есть существует порождающая - 55 - его LR(k)-грамматика), то он является LR(k)-языком с любым значением k (k>=0), в том числе и при k=0 и k=1. Упомянем еще один интересный теоретический результат. Если некоторый язык может быть разобран детерминированно, то он относится к классу LR-языков. Например, любой LL(1)-язык является LR-языком. Действительно, принятие решения в LR-ана- лизаторе откладывается до полного прочтения правой части пра- вила вывода, в то время как для LL(1)-языка гарантирован выбор правила вывода уже по одному символу. Следовательно, в LR-раз- боре информации уж никак не меньше. В заключение перечислим достоинства LR-грамматик. 1) По заданной грамматике можно определить, является ли она LR-грамматикой (так же как и для LL-грамматик). 2) Для LR-анализатора гораздо реже приходится преобразо- вывать исходную грамматику (по сравнению с LL-анализатором). 28.2. LR-таблицы разбора На практике LR-анализатор обычно выполняет разбор, руко- водствуясь специальной управляющей таблицей. В этой таблице для каждого возможного состояния анализатора и каждого очеред- ного входного символа (терминального или нетерминального!) предусмотрено необходимое действие, задающее сдвиг и новое состояние или свертку по некоторому правилу. В первом случае будем записывать в клетке таблицы сочетание "Sn", где S - опе- рация сдвига, а n - номер нового состояние анализатора. Во втором случае будем указывать сочетание "Rn", где R - операция свертки (приведения), а n - указание номера правила, по кото- рому осуществляется свертка. Анализатор будет использовать два стека. Первый - для хранения формируемой правой части какого-либо правила вывода, а второй - для хранения состояний. Текущим состоянием анализа- тора является верхнее значение в стеке состояний. Условимся, что начальное состояние равно 1. При выполнении операции сдвига анализатор помещает в стек символов очередной символ и переходит в новое состояние, кото- рое записывается также в стек состояний. . - 56 - При выполнении операции свертки определяется длина правой части правила вывода (обозначим эту длину через l) и из каждо- го стека удаляется по l элементов. Нетерминал левой части пра- вила вывода, по которому осуществлялась свертка, становится текущим входным символом. Обратите внимание: символ, который вызвал свертку, не считается обработанным и возвращается об- ратно во входную строку! 2Упражнение. 0Докажите, что нетерминальный символ, появив- шийся после свертки, на следующем шаге будет помещен в стек. 2Пример. 0В таблице 4 приводится пример LR-таблицы для грамматики из предыдущего примера. Символ "#" является марке- ром конца входной цепочки. Незаполненные клетки таблицы соот- ветствуют ошибочным ситуациям. В клетке 1/S указано слово "halt", обозначающее конец работы анализатора. 2Пример. 0 Рассмотрим работу анализатора по таблице из пре- дыдущего примера. Пусть на вход подается цепочка "real a,b,c#". Первоначально стек символов пуст, в стеке состояний записано начальное состояние 1. В таблице 5 приводится пример трассировки алгоритма LR-разбора. ш1 2Таблица 4 2Пример управляющей таблицы LR-анализатора ┌──────────┬─────┬──────┬─────┬──────┬───────┬───────┬─────┐ │\ Символ │ │ │ │ │ │ a b │ │ │ ──────── │ S │Idlist│ Id │ real │ , │ c d │ # │ │Состояние\│ │ │ │ │ │ │ │ ├──────────┼─────┼──────┼─────┼──────┼───────┼───────┼─────┤ │ 1 │halt │ │ │ S2 │ │ │ │ ├──────────┼─────┼──────┼─────┼──────┼───────┼───────┼─────┤ │ 2 │ │ S5 │ S4 │ │ │ S3 │ │ ├──────────┼─────┼──────┼─────┼──────┼───────┼───────┼─────┤ │ 3 │ │ │ │ │ R4 │ │ R4 │ ├──────────┼─────┼──────┼─────┼──────┼───────┼───────┼─────┤ │ 4 │ │ │ │ │ R3 │ │ R3 │ ├──────────┼─────┼──────┼─────┼──────┼───────┼───────┼─────┤ │ 5 │ │ │ │ │ S6 │ │ R1 │ ├──────────┼─────┼──────┼─────┼──────┼───────┼───────┼─────┤ │ 6 │ │ │ S7 │ │ │ S3 │ │ ├──────────┼─────┼──────┼─────┼──────┼───────┼───────┼─────┤ │ 7 │ │ │ │ │ R2 │ │ R2 │ └──────────┴─────┴──────┴─────┴──────┴───────┴───────┴─────┘ ш0 В приложении 1 приведен пример программы, реализующей анализ по LR-таблице. . - 57 - ш1 2Таблица 5 2Пример трассировки алгоритма LR-разбора ┌───────┬──────┬────────┬────────────────────────────────────┐ │Очеред.│Текущ.│Выполня-│Содержимое после выполнения действия│ │символ │состо-│емое ├─────────────────┬──────────────────┤ │ │яние │действие│ стека символов │ стека состояний │ ├───────┼──────┼────────┼─────────────────┼──────────────────┤ │ │ │ │стек пуст │ 1 │ │ real │ 1 │ S2 │real │ 1 2 │ │ a │ 2 │ S3 │real a │ 1 2 3 │ │ , │ 3 │ R4 │real │ 1 2 │ │ Id │ 2 │ S4 │real Id │ 1 2 4 │ │ , │ 4 │ R3 │real │ 1 2 │ │ Idlist│ 2 │ S5 │real Idlist │ 1 2 5 │ │ , │ 5 │ S6 │real Idlist , │ 1 2 5 6 │ │ b │ 6 │ S3 │real Idlist , b │ 1 2 5 6 3 │ │ , │ 3 │ R4 │real Idlist , │ 1 2 5 6 │ │ Id │ 6 │ S7 │real Idlist , Id │ 1 2 5 6 7 │ │ , │ 7 │ R2 │real │ 1 2 │ │ Idlist│ 2 │ S5 │real Idlist │ 1 2 5 │ │ , │ 5 │ S6 │real Idlist , │ 1 2 5 6 │ │ c │ 6 │ S3 │real Idlist , c │ 1 2 5 6 3 │ │ # │ 3 │ R4 │real Idlist , │ 1 2 5 6 │ │ Id │ 6 │ S7 │real Idlist , Id │ 1 2 5 6 7 │ │ # │ 7 │ R2 │real │ 1 2 │ │ Idlist│ 2 │ S5 │real Idlist │ 1 2 5 │ │ # │ 5 │ R1 │стек пуст │ 1 │ │ S │ halt │ │ │ │ └───────┴──────┴────────┴─────────────────┴──────────────────┘ ш0 28.3. Грамматики простого предшествования К числу восходящих методов разбора относится анализ по таблице предшествования для грамматики называемых грамматиками предшествования [8]. Рассмотрим такие грамматики. Прежде всего определим на множестве терминальных и нетер- минальных символов отношения предшествования. Используемые ни- же символы R и S берутся из такого множества. 2Определение 1. 0 Два символа находятся в отношении не- посредственного следования, если они непосредственно следуют друг за другом в правой части какого-либо правила вывода грам- матики. Через R=.S будем обозначать отношение непосредственно- го следования символа S за символом R. Здесь символы R и S мо- гут быть как терминальными, так и нетерминальными в любой ком- бинации. 2Определение 2. 0 Символ R находится в отношении не- посредственного предшествования к символу S, если существует - 58 - нетерминальный символ G, такой что R=.G и из G выводима цепоч- ка, начинающаяся с S (обозначение: R<.S). Здесь символы R и S также могут быть как терминальными, так и нетерминальными. 2Определение 3а. 0 Терминальный символ R находится в отноше- нии непосредственного послеследования к символу S (терминаль- ному или нетерминальному), если существует нетерминальный сим- вол G, такой что G=.R и из G выводима цепочка, заканчивающаяся символом S (обозначение: S.>R). 2Определение 3б. 0 Терминальный символ R находится в отноше- нии непосредственного послеследования к символу S (терминаль- ному или нетерминальному), если существуют нетерминальные сим- волы G и Q, такие что G=.Q и из G выводима цепочка, заканчива- ющаяся символом S, а из Q выводима цепочка, начинающаяся с символа R (обозначение такое же: S.>R). 2Пример. 0 Рассмотрим следующую грамматику: 1) S -> bMb 2) M -> (L 3) M -> a 4) L -> Ma) Подумайте, какой язык порождается этой грамматикой? Ниже в таблице 6 приводятся отношения предшествования для объеди- ненного алфавита терминальных и нетерминальных символов. ш1 2Таблица 6 2Пример таблицы предшествования ┌──────────────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐ │\Второй символ│ │ │ │ │ │ │ │ │ ──────────── │ S │ M │ L │ a │ b │ ( │ ) │ │Первый символ\│ │ │ │ │ │ │ │ ├──────────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤ │ S │ │ │ │ │ │ │ │ ├──────────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤ │ M │ │ │ │ =. │ =. │ │ │ ├──────────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤ │ L │ │ │ │ .> │ .> │ │ │ ├──────────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤ │ a │ │ │ │ .> │ .> │ │ =. │ ├──────────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤ │ b │ │ =. │ │ <. │ │ <. │ │ ├──────────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤ │ ( │ │ <. │ =. │ <. │ │ <. │ │ ├──────────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤ │ ) │ │ │ │ .> │ .> │ │ │ └──────────────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘ ш0 2Определение 4. 0 Грамматика называется грамматикой простого предшествования, если в ней нет правил вывода с одинаковыми правыми частями и для каждой пары символов определено не более одного отношения предшествования. - 59 - Грамматика из предыдущего примера является грамматикой простого предшествования (см. таблицу 6). 28.4. Анализатор предшествования Рассмотрим алгоритм анализа входной цепочки по некоторой таблице предшествования. Дополним множество терминальных сим- волов терминальным символом "#". Будем считать, что для любого символа R верны отношения предшествования: R.># и #<.R. Для анализа (как и всегда при восходящем разборе) нам потребуется стек, где будет накапливаться будущая правая часть правила вывода. При анализе очередного символа по таблице предшествования определяется , в каком отношении находятся верхний символ стека и очередной входной символ. Если символы находятся в отношении непосредственного сле- дования, то входной символ записывается в стек. Если символы находятся в отношении непосредственного предшествования, то в стек записывается и знак предшествова- ния, и входной символ. Если символы находятся в отношении непосредственного послеследования, то производится свертка в стеке правой части правила вывода (выделенной самым верхним отношением в стеке из всех отношений непосредственного предшествования). Очередным входным символом становится нетерминал левой части свернутого правила. Если же свертка невозможна (то есть не существует правой части правила вывода, совпадающей с выделенной цепоч- кой), то значит обнаружена ошибка. Если обнаружится, что для текущих символов отношение предшествования неопределено, то значит обнаружена ошибка. Анализатор заканчивает работу успешно, если входная це- почка исчерпана, а в стеке находится начальный символ грамма- тики. 2Пример. 0 Рассмотрим работу анализатора по предыдущей таб- лице предшествования. Пусть на вход подается цепочка "b(aa)b#". Первоначально в стек записывается маркер конца. Ни- же в таблице 7 приводится пример работы анализатора. . - 60 - ш1 2Таблица 7 2Пример работы анализатора предшествования ┌──────────────────┬────────────┬─────────────────────────┐ │ Оставшаяся часть │ Отношение │ Содержимое стека после │ |
Похожие:
 | Конспект лекций Владимира Климентьева по истории философии, отредактированный... Рекомендовано Министерством общего и профессионального образования Российской федерации в качестве учебника для студентов высших... | | Курс лекций 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 частях. Часть М.: Айрис-пресс,... Баранова Е. С., Васильева Н. В., Федотов В. Л. Практическое пособие по высшей математике. Типовые расчеты. Учебное пособие. — Спб:... |
