Конспект лекций Рекомендовано Учебно-методи
Скачать 1.01 Mb.
|
5) разработка компилятора с широкими возможностями по об- наружению, локализации и диагностированию ошибок; 6) обеспечение надежности компилятора; 7) быстрая разработка компилятора; 8) требование пакетной обработки программ; 9) ориентация на диалоговое применение компилятора. Как зачастую бывает, эти цели могут оказаться взаимно противоречивыми. Выбор приоритетных целей во многом определяет и выбор языка реализации. Как уже указывалось, в качестве языка реали- зации может выбираться и язык высокого уровня. В таком случае можно создавать переносимые ( с машины на машину) компиляторы. - 18 - Прежде чем перейти к следующему материалу, уточним поня- тия синтаксиса и семантики языка программирования. Правила, описывающие структуру входящих в язык программи- рования текстов программ, называются 2синтаксисом 0, а правила, определяющие смысловую сторону этих текстов (то есть приписы- вающие им определенные смысловые значения), - 2семантикой 0дан- ного языка. 22. ФОРМАЛЬНЫЕ МЕТОДЫ ОПИСАНИЯ ЯЗЫКОВ Наиболее известны и хорошо описаны следующие формальные методы описания языков: Нормальные Формы Бэкуса - Наура ( 2БНФ 0), 2синтаксические диаграммы 0Вирта и 2порождающие грамматики 0. БНФ были первой, получившей широкое распространение, формальной системой обозначений для описания синтаксиса языков программи- рования. Впервые БНФ были применены для описания синтаксиса языка Алгол-60. Позже появились синтаксические диаграммы, описывающие синтаксис в графическом виде (см. приложение 2). Но в теоретических исследованиях удобнее пользоваться аппара- том формальных грамматик, на нем мы и остановимся поподробнее. 22.1. Определения и общие свойства порождающих грамматик Упомянутые выше нормальные формы Бэкуса и синтаксические диаграммы Вирта используются для представления синтаксиса и, отчасти, семантики. Приведем пример описания понятия "иденти- фикатор" с использованием формализма БНФ: <идентификатор> ::= <буква> │ <буква> <буквы и цифры> <буквы и цифры> ::= <буква> │ <цифра> │ <буква> <буквы и цифры> │ <цифра> <буквы и цифры> <буква> ::= a │ b │ c │ d │ e │ f │ g │ h │ i │ j │ k │ l │ m │ n │ o │ p │ q │ r │ s │ t │ u │ v │ w │ x │ y │ z <цифра> ::= 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 - 19 - Приведенные в угловых скобках обозначения называются ме- талингвистическими переменными или нетерминальными символами. В этих обозначениях проявляется семантика конструкций языка программирования. Запись вида "::=" читается как "это есть". Вертикальная черта задает перечисление альтернативных определений данного понятия. Оставшиеся символы называются терминальными. Позже стали использоваться так называемые расширенные БНФ (РБНФ). Их отличие в том, что в правых частях правил было раз- решено использовать квадратные и фигурные скобки, не являющи- еся терминальными. Квадратные скобки обозначают необязательный элемент, а фигурные задают возможное повторение нуль или более раз. Приведенный выше пример на РБНФ выглядит так: <идентификатор> ::= <буква> {<буква или цифра>} <буква или цифра> ::= <буква> │ <цифра> <буква> ::= a │ b │ c │ d │ e │ f │ g │ h │ i │ j │ k │ l │ m │ n │ o │ p │ q │ r │ s │ t │ u │ v │ w │ x │ y │ z <цифра> ::= 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 В синтаксических диаграммах терминальные и нетерминальные символы различаются внешним видом контура: терминальные эле- менты размещаются в овалах или кружках, а нетерминальные - в прямоугольниках. В данном тексте терминальные символы будут записываться в синтаксических диаграммах без контура. Название диаграммы соответствует определяемому нетерминальному символу. Пути, ведущие от начала диаграммы к ее концу задают все син- таксически корректные варианты. На рисунке 5 приведены диаг- раммы понятий "идентификатор", "буква" и "цифра". Нормальные формы Бэкуса, а вместе с ними и синтаксические диаграммы Вирта, легко трансформируются в порождающие грамма- тики. Для этого металингвистические переменные заменяются не- терминальными символами грамматики, комбинация "::=" заменя- ется стрелкой, терминальные символы остаются неизменными, а каждой альтернативе соответствует свое правило грамматики. - 20 - ш1 ┌─────┐ ┌<─┤буква├─┐ Идентификатор ┌─────┐ │ └─────┘ │ ─────────────>│буква├──┼──────────┼───────────────> └─────┘ │ ┌─────┐ │ └<─┤цифра├─┘ └─────┘ ┌──── a ────┐ ┌──── 0 ────┐ │ │ │ │ ├──── b ────┤ ├──── 1 ────┤ │ │ │ │ Буква │. . . . . .│ Цифра │. . . . . .│ ─────────┤ ├────> ───────┤ ├────> │ │ │ │ └──── z ────┘ └──── 9 ────┘ Рис. 5. Пример синтаксических диаграмм ш0 Дадим формальное определение грамматики [2]. 2Определение 0. Порождающей грамматикой G называется четверка объектов: Vt - конечное множество терминальных символов; Vn - конечное множество нетерминальных символов, причем множества Vt и Vn не пересекаются; S - начальный символ грамматики, принадлежащий множеству Vn; P - множество правил вывода вида x -> y, где x и y цепоч- ки терминальных и нетерминальных символов. Здесь и в дальнейшем будем придерживаться следующих обоз- начений: малые латинские буквы из начала алфавита будут обоз- начать терминальные символы, малые латинские буквы из конца алфавита будут обозначать цепочки как терминальных, так и не- терминальных символов, большие латинские буквы будут обозна- чать нетерминальные символы. При всех буквах допустимо указы- вать индексы. 2Определение 0. Говорят, что цепочка x1 непосредственно вы- водима из цепочки x0 в грамматике G (записывается так: x0->/G/->x1 ), если цепочки x0, x1 представимы в виде x0=w1yw2, x1=w1zw2, и среди правил вывода есть правило y->z. 2Определение 0. Если в грамматике G есть непосредственная выводимость x[0]->x[1], x[1]->x[2], ..., x[n-1]->x[n], то го- ворят, что цепочка x[n] выводима из x[0] в грамматике G (за- писывается так: x[0]->/+G/->x[n]). Символ грамматики можно опускать или писать его под знаком выводимости. - 21 - В частных случаях, x[0] может быть нетерминалом или тер- минальной цепочкой, что позволяет определять выводимость из нетерминала, выводимость терминальной цепочки. 2Определение 0. Множество терминальных цепочек, выводимых в грамматике G из начального символа, называется языком, порож- даемым этой грамматикой, и обозначается L(G). 2Пример. 0Рассмотрим следующую грамматику G: 1) Vt = { a, b, c, 0, 1, 2 }, 2) Vn = { A, B, C, D }, 3) начальный символ грамматики - A, 4) правила вывода S = { A -> BC; B -> a; B -> b; B -> c; C -> B; C ->D; C -> CC; D -> 0; D -> 1; D -> 2 }. В язык L(G), порождаемый данной грамматикой G, входят це- почки, начинающиеся с одной из букв: a, b или c. Далее следуют один или несколько буквенных (a, b, c), или цифровых (0, 1, 2) символов. Покажем, как, например, выводится цепочка ab0с: A -> BC -> aC -> aCC -> aCCC -> aBCC -> abCC -> abDC -> ab0C -> ab0c. Перечислить все цепочки языка невозможно, так как их количество бесконечно. Одной из основных проблем, связанных с практическим при- менением порождающих грамматик, является проблема распознава- ния. Для конкретной грамматики алгоритмическая разрешимость проблемы распознавания означает, что можно за конечное число шагов проверить принадлежность произвольной терминальной це- почки языку, порождаемому данной грамматикой. Очевидно, что интерес представляют в первую очередь распознаваемые языки, но существуют и нераспознаваемые языки. Описанный выше язык L(G) является распознаваемым. Действительно, рассмотрим произвольную цепочку символов над терминальным алфавитом Vt. Пусть ее длина равна l. Если l<2, то цепочка заведомо не принадлежит языку. Пусть l>=2, тогда применим к начальному символу правило вывода A -> BC. Далее применим (l-1) раз правило C -> CC. В результате получим цепочку нетерминалов: BCC...C. Принадлеж- ность цепочки языку определяется выводимостью каждого из ее символов из соответствующего нетерминала. Последнее легко про- верить полным перебором правил вывода. 2Определение 0. Количество символов, составляющих цепочку, называется длиной цепочки (обозначение: l(x) или │x│ ). Если - 22 - l(x)=0, то цепочка называется пустой. Будем обозначать пустую цепочку символом - 7e 0. 2Определение 0. Грамматика называется неукорачивающей, если для любого правила вывода левая часть не длиннее правой. 2Теорема 0. Пусть G - неукорачивающая грамматика, тогда L(G) - легко распознаваемый язык, то есть число шагов алгоритма распознавания есть функция длины цепочки [2]. 2Указание 0. Доказательство основывается на полном переборе бесповторных выводов. Неукорачивающие грамматики довольно громоздки и неудобны, так как в них допускается замена терминальных цепочек, что приводит к потере естественной интерпретации нетерминальных символов как обозначений (имен) синтаксических конструкций. 22.2. Классификация грамматик Существует несколько вариантов классификации порождающих грамматик. Ниже приводится вариант классификации по Хомскому [11]. Грамматики перечисляются в следующем порядке: произволь- ные грамматики, неукорачивающие грамматики, грамматики не- посредственных составляющих, контекстно-свободные грамматики, укорачивающие контекстно-свободные грамматики, автоматные грамматики. 1) 2Произвольные грамматики 0 - по Хомскому - 2тип 0 0. 2) 2Неукорачивающие грамматики 0 - 2тип 1 0. 3) 2НС - грамматики 0 (вид правил: xAy -> xty, t<> 7e 0 ). Класс НС-грамматик эквивалентен классу неукорачивающих грамматик (следовательно, по Хомскому тоже 2тип 1 0). Другое наз- вание НС-грамматик - контекстно зависимые грамматики. 4) 2КС - грамматики 0(вид правил: A -> x, x<> 7e 0) - по Хомскому - 2тип 2 0. Класс КС-языков уже класса НС-языков. 5) 2УКС - грамматики 0(вид правил: A -> x, где x , возмож- но, пустая цепочка). По любой УКС-грамматике можно построить - 23 - почти эквивалентную ей КС-грамматику (тот же язык за исключе- нием, возможно, пустой цепочки). 6) 2А - грамматики. 0 Лево и правоавтоматные или иначе - ре- гулярные грамматики (вид правил: A -> aB, A -> a). По Хомскому - 2тип 3 0. 2Упражнение. 0 L={xbx}. (В терминальной цепочке "x" терминал "b" не присутствует.) Показать, что это НС-язык. (Ответ: I->b; I->IA[i]a[i]; a[i]A[j]->A[j]a[i]; bA[i]->a[i]b) 2Пример. 0Рассмотрим скобочный язык. Он состоит из беско- нечного множества цепочек, представленных правильной скобочной структурой. Порождающая его грамматика очень проста: 1) E -> ( ) 2) E -> ( E ) 3) E -> E E Судя по грамматике, язык является контекстно свободным. Однако, пример КС-грамматики не означает, что не существует грамматики с более жесткими ограничениями (в данном случае - регулярной). Докажем, что скобочный язык действительно не является ре- гулярным. Предположим противное: пусть существует регулярная грам- матика (например, левоавтоматная). Тогда, правила вывода имеют вид: A -> a, A -> aB. В качестве терминальных символов будут выступать левые и правые скобки. Предположим в искомой грамматике имеется k нетерминальных символов. Рассмотрим скобочную цепочку, состоящую из k левых скобок, за которыми следуют k правых скобок. Это правильная скобочная цепочка. Построим вывод этой цепочки в нашей гипоте- тической грамматике. На каждом шаге вывода порождается один терминальный сим- вол, поэтому всего будет 2k шагов. При этом, на каждом шаге в получаемой цепочке будет присутствовать ровно один нетерминал. Рассмотрим первую половину этого вывода (порождение k левых скобок). Очевидно, что среди использованных в этой части выво- да нетерминалов найдутся хотя бы два совпадающих, то есть: E => ... => x 2Z 0 => ... => y 2Z 0 => t - 24 - Здесь x и y некоторые терминальные цепочки, а t - результирую- щая цепочка. Пусть выделенная часть вывода содержит m шагов, тогда цепочка y получается из цепочки x приписыванием m левых скобок. Понятно, что мы в рамках нашей грамматики можем построить другой вывод, отличающийся от исходного тем, что в первой его части будет выброшена выделенная ранее часть. И, следователь- но, нашему языку будет принадлежать цепочка из (k-m) левых скобок и k правых скобок. А это запрещено. Полученное противо- речие означает, что не может существовать регулярная граммати- ка, порождающая скобочный язык. 23. ВЫВОД ЦЕПОЧЕК 23.1. Задача разбора Мы рассмотрели задачу порождения цепочек языка. Однако, для компилятора важно уметь распознавать цепочки и устанавли- вать их структуру. Эта задача называется задачей разбора. Структура цепочки может быть задана графически в виде дерева. В программе часто применяют иной способ - линейно скобочная запись. 2Пример. 0 Пусть даны правила вывода порождающей грамматики G с начальным символом E: 1) E -> E + T 2) E -> T 3) T -> T * F 4) T -> F 5) F -> ( E ) 6) F -> a 7) F -> b Здесь E - арифметическое выражение; T - терм; F - множи- тель. Рассмотрим цепочку (a+b)*a . Очевидно, что она принадле- жит языку L(G). Попробуем построить вывод этой цепочки из на- чального символа: E -> T -> T*F. На этом шаге возникает неоп- ределенность: к какому нетерминалу применять следующее правило - 25 - вывода. Будем придерживаться принципа - правило вывода всякий раз применяется к самому левому вхождению нетерминала. Тогда последовательность вывода имеет вид: E -> T -> T*F -> F*F -> (E)*F -> (E+T)*F -> (T+T)*F -> -> (F+T)*F -> (a+T)*F -> (a+F)*F -> (a+b)*F -> (a+b)*a Мы осуществили так называемый левосторонний вывод. Пе- речиcлим номера правил: 2,3,4,5,1,2,4,6,4,7,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 частях. Часть М.: Айрис-пресс,... Баранова Е. С., Васильева Н. В., Федотов В. Л. Практическое пособие по высшей математике. Типовые расчеты. Учебное пособие. — Спб:... |
