Конспект лекций доцента и. А. Волковой по курсу «системы программирования»




НазваниеКонспект лекций доцента и. А. Волковой по курсу «системы программирования»
страница7/20
Дата публикации28.06.2013
Размер0.69 Mb.
ТипКонспект
lit-yaz.ru > Информатика > Конспект
1   2   3   4   5   6   7   8   9   10   ...   20
^

Разбор цепочки



Разбор цепочки – процесс построения вывода цепочки α из цели некоторой грамматики G = (VT, VN, P, S).
Примечание.

В дальнейшем будем считать, что КС = УКС тождественно. (=> по опр. КС грамматики) Множества языков, порождающих КС и УКС, отличаются только наличием ε (см. предыдущую лекцию).
Порождающей мощности КС грамматики достаточно для описания языков большинства существующих языков программирования.
Далее на лекциях будем рассматривать только КС грамматики.

^

Левый и правый выводы.


Вывод цепочки α из цели S некоторой грамматики G называется левым (или левосторонним), если на каждом шаге применяются правила, раскрывающие самый левый нетерминальный символ.

Вывод называется правым (правосторонним), если каждая сентенциальная форма получается из предыдущей заменой каждого правого нетерминального символа.
Пример.

S -> Τ|Τ+S

S -> T+S -> T+(T+S) -> a+T+S -> a+b+S -> a+b+T -> a+b+a

Этот вывод не является ни левосторонним, ни правосторонним. Но левый или правый выводы из него можно легко получить.

^

Дерево вывода (дерево разбора).


Построим дерево вывода для этого примера.
S




T + S



a T + S



b a
Вершина дерева – начальный символ, листья – терминальные символы. Стрелками обозначаются правила грамматики.

Если из к.-л. А -> a1a2…ak, то это правило существует в грамматике.

Если есть правило a -> ε, то оно тоже принадлежит грамматике.
Способы построения дерева: восходящий и нисходящий. При восходящем способе берём цепочку и пытаемся свернуть к нетерминальным символам грамматики. В итоге нужно прийти к S.
S




S




S




T T T




a + b + a
Два вывода эквивалентны, если при любом способе построения получается одно и то же дерево.

^

Неоднозначность грамматики



КС грамматика G называется неоднозначной, если есть хотя бы 1 цепочка α, принадлежащая языку, порождаемому грамматикой, для которой можно построить 2 или более деревьев вывода.

В противном случае грамматика однозначная.

Проблема определения однозначности грамматики алгоритмически неразрешима.
^ Язык неоднозначен, если нет однозначной грамматики, описывающей этот язык.
Пример неоднозначной грамматики.

G = ({if, then, else, a, b}, {S}, P, S)

P: S -> if b then S else S | if b then S | a

Для выражения ‘if b then if b then a else a’ построим дерево вывода.

1-ый способ.

S
if b then S
if b then S else S




a a


2-ой способ.

S
if b then S else S
if b then S a
a

Т.к. существует более одного способа построения, грамматика неоднозначная.
Неоднозначный язык:

L = {aibjck | i=j или j=k}
S -> if b then S|Τ -

T -> if b then T else S|a - эти правила описывают однозначную грамматику Pascal.
Если в грамматике существует правило некоторого вида, то грамматика неоднозначна.
Примеры неоднозначных грамматик (в скобках указаны преобразования, делающие их однозначными):

1. A -> AA|α (Α -> αΑ|α)

2. Α -> ΑαΑ|β (Α -> βαΑ|β)

3. Α -> αΑ|Αβ|γ (Α -> αΑ|Β Β не принадлежит VN.

Β -> Ββ|γ)

4. A -> aA|αΑβΑ|γ (Α -> αΑ|Β Β не принадлежит VN.

Β -> αΒβΑ|γ)

Если, как в 1-ом примере, существует правило А -> AA , то следующий шаг – из левого или правого А, симметрия не учитывается, это разная структура.
Доказать, что грамматика неоднозначная, значит, найти цепочку с двумя деревьями вывода.
Предлагается подумать дома:

  • βαβαβ – доказать, что грамматика не однозначна.

  • Попробовать показать, что эти начальные правила приводят к неоднозначным грамматикам

  • Показать, что новые правила описывают тот же язык.


Грамматики должны быть однозначными, чтобы программа делала то, что должна.
Рассмотрим другие преобразования грамматик.

Пример.

S -> Α|a По определению эта грамматика может существовать.

B -> b Но очевидно, что 2-ое правило лишнее, В и b недостижимы.

Порождаемый язык – а.
^ Символ недостижим, если он не получается ни в одной сентенциальной форме.

Символ бесплодный, если из него в итоге не выводится ни одна терминальная цепочка.

Недостижимые и бесплодные символы лишние, они замедляют компиляцию.

^ Приведённая грамматика – грамматика без недостижимых и бесплодных символов.

Чтобы сделать грамматику приведённой, надо удалить все бесплодные символы, затем удалить все недостижимые символы. (именно в этом порядке!)
Пример.

S -> AB | a (1) удаляем (бесплодный) S -> AB

A -> b (3) удаляем (недостижимый)

B -> BA (2) удаляем (бесплодный)

Остаётся S -> a.

Если удалять в другом порядке, в начале нет недостижимых символов, они появляются только после удаления бесплодных.

В языках программирования используются однозначные приведённые грамматики.
1   2   3   4   5   6   7   8   9   10   ...   20

Похожие:

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconКонспект лекций по курсу «Объектно-ориентированное программирование»
Б. Страуструп. Язык программирования C++, 3-е изд./Пер с англ. – Спб.; М.: «Невский диалект» – «Издательство бином», 1999 г. – 991...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconКонспект лекций «Логистика. Конспект лекций»
Конспект лекций соответствует требованиям Государственного образовательного стандарта высшего профессионального образования

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconВ. Г. Баула Введение в архитектуру ЭВМ и системы программирования
Мгу им. М. В. Ломоносова. По данному курсу существует достаточно обширная литература, посвящённая программированию на Ассемблере,...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconРабочая программа по курсу «основы программирования на с++»
Программа предназначена для обучения программирования на языке С++ учреждений начального профессионального образования для овладения...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconМетодические указания к курсовой работе по дисциплине " системы программирования " Киев -2002
Целью курсовой работы по дисциплине "Системы программирования" является закрепление теоретического материала и приобретение практических...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconРабочая программа по курсу «основы Программирования на языке ассемблер»
Программа предназначена для обучения основам программирования на языке низкого уровня Ассемблере учащихся средних школ, учреждений...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconСистемы сбора информации на железнодорожном транспорте хабаровск
Конспект лекций предназначен для студентов дневной формы обучения специальности 0719 ²Информационные системы на ж д транспорте²,...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconУчебная программа курса или дисциплины «Основы программирования»
В частности, в курсе рассматриваются основные конструкции языков программирования, анализируются основные типы и структуры данных,...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconКонспект лекций по дисциплине вгипу, 2009 Конспект лекций по дисциплине «Управление персоналом»
Крупица В. В., Яшкова Е. В., Егоров Е. Е. Управление персоналом: Конспект лекций по дисциплине – вгипу, 2009

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconКонспект лекций. (Электронный учебник) Минск: бгэу, 2010. Тема 1...
Короленок Г. А. Менеджмент в торговле. Конспект лекций. (Электронный учебник) Минск: бгэу, 2010



Образовательный материал



При копировании материала укажите ссылку © 2013
контакты
lit-yaz.ru
главная страница