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

Скачать 0.69 Mb.

Название	Конспект лекций доцента и. А. Волковой по курсу «системы программирования»
страница	7/20
Дата публикации	24.05.2014
Размер	0.69 Mb.
Тип	Конспект

literature-edu.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 = {aⁱb^jc^k | 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

Похожие:

	Республики Беларусь Учреждение образования «белорусский государственный... Конспект лекций по курсу «Основы алгоритмизации и программирования» для студентов всех специальностей и всех форм обучения. Мн.:...		Конспект лекций «Логистика. Конспект лекций» Конспект лекций соответствует требованиям Государственного образовательного стандарта высшего профессионального образования
	Конспект лекций по курсу "Информатика и использование компьютерных... Конспект лекций предназначен для студентов филологического факультета и факультета гуманитарных и социальных наук рудн. Конспект...		Рабочая программа по курсу «основы Программирования на языке ассемблер» Программа предназначена для обучения основам программирования на языке низкого уровня Ассемблере учащихся средних школ, учреждений...
	Основы информатики и вычислительной техники системы программирования Рассматриваются основные понятия языков программирования. Излагаются процедурный и объектный подходы в программировании. Более подробно...		Конспект лекций для студентов специальности 1-25 01 04 «Финансы и... ...
	Конспект лекций для студентов специальности 1-54 01 01-04 «Метрология,... Конспект лекций предназначен для студентов специальности 1-54 01 01-04 «Метрология, стандартизация и сертификация (лёгкая промышленность)»...		Автор: Медведева Г. В Курс лекций содержит основные разделы языка программирования t-pascal, предусмотренные образовательным стандартом
	Конспект лекций для студентов пятого курса специальности 220400 Программное... Данный конспект лекций составлен для студентов четвёртого курса специальности “Программное обеспечение вычислительной техники и автоматизированных...		Учебник Толубеевой Т. И., доцента кафедры пти «Основы проектирования крупноузорчатых тканей» Особенность Декады – 25- летие выхода в свет стандартов исо серии 9000 на системы менеджмента качества

Литература