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




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

Лекция 3. 27/02/2004.




Формальные грамматики языков.


(рекомендуется использовать учебное пособие)
Цепочка символов в алфавите V={a,b,c,…} – любая конечная последовательность символов этого алфавита.
В серьёзных языках программирования, в отличие от простых, алфавит состоит из слов – некоторых наборов символов.
При написании языка программирования используется 2 языка:

  • язык для написания лексем

  • сам язык, где алфавит составляют эти лексемы


Например, символ @, не является лексемой и не входит в алфавит.

Совокупность символов _1а_ не является лексемой, но правильна с точки зрения алфавита.
Пустая цепочка (обозначается ε) – цепочка, не содержащая символов.
α = ab V = {1,a,b,c,d,e}

β = cde

αβ = abcde

αε = εα = α
Обращение к цепочке α (обозначается αR) – цепочка, в которой символы расположены в обратном порядке по отношению к цепочке α, т.е. αR = ba.
αn – n-ая степень цепочки α – конкатенация n цепочек α.

Например, α3 = ababab.

По определению α0 = ε.
Длина цепочки – количество символов, составляющих цепочку.

Обозначается |β|, по аналогии с длиной вектора.

В нашем примере |β|=3.
Язык (в алфавите V) – подмножество цепочек конечной длины в заданном пространстве.
V* - множество всевозможных цепочек алфавита V, включая пустую цепочку.
Если V = {0,1}, то V* = {ε,0,1,001,010,…}

Это множество бесконечное.
Язык тоже может быть конечным и бесконечным.
V+ - множество, содержащее все цепочки в алфавите V, исключая пустую цепочку ε.

В нашем примере V+ = {0,1,00,11,01,10,000,…}.
V* = V+ U {ε}
Язык – подмножество множества V* (в частности, они могут совпадать).

Механизмы описания языков.


  • распознавание – схематизированный алгоритм, определяющий множество цепочек. Примеры распознавателей – конечный автомат, машина Тьюринга (но существуют языки, которые нельзя задать машиной Тьюринга).

  • порождающая грамматика (пример – грамматика Хомского).

Обычно используется обозначение G – четвёрка из множеств:

G = (VT, VN, P, S)

VT – алфавит терминальных символов, т.е. алфавит символов, из которых состоят цепочки языка.

VN – нетерминальные символы, т.е. вспомогательные символы, не входящие в слова, но участвующие в грамматике. Они нужны для порождения процесса.

P – конечное подмножество множества (VT U VN)+ X (VN U VN)*, где X – декартово произведение, α принадлежит (VT U VN)+, β принадлежит (VN U VN)*.

α -> β - правило вывода в грамматике.

α не пустое (следует из определения), содержит хотя бы один нетерминальный символ.

β – произвольная цепочка из алфавита (VT U VN).

S, принадлежащий VN, - начальный символ (цель) грамматики.

Соглашения. (используются для удобства)


  • нетерминальные символы обозначаются большими латинскими буквами.

  • цепочки символов обозначаются малыми греческими буквами.

  • если в множестве из α выводятся β12,...,βn : α->β1, α->β2, ..., α->βn; обозначаем это правило α -> β1 | β2 | ... | βn

βi называем альтернативами правила вывода.

Пример грамматики.

G1 = ({0,1}, {A,S}, P, S)

P: S->0A1

0A->00A1

A->ε

P – это набор правил, достаточно задавать его, не задавая алфавит.
Цепочка β называется непосредственно выводимой из цепочки α, если она получается из α с помощью одного правила вывода.

Например, 0A1 -> 00A11

α β
α = S -> 0A1 -> 00A11 -> 0011 = β

Длина вывода – количество применённых правил. Здесь длина вывода равна 3.
Если β выводима из α (т.е. >1 правила вывода), обозначается α => β.
Грамматика L(G1) = {0n1n | n>=1}.

0n1n – перечисление цепочек, n>=1 – ограничение на переменные, неопределённые символы, которые введены в языке.

Чем меньше ограничений, тем тяжелее работать.
Язык порождаемой грамматики – множество L(G) терминальных цепочек, выводимых из начального символа грамматики.

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

=> Язык – множество терминальных сентенциальных формул в заданной грамматике.

Эквивалентность грамматик – если они порождают один и тот же язык.

Пример. G2 = ({0,1},{S},P,S)

P: S->0S1 | 01

L(g2) = {0n1n | n>=1}
Грамматики называются почти эквивалентными, если они отличаются на ε (пустую цепочку)
Пример. G3 = ({0,1},{S},P,S)

P: 0S1 | ε

L(G3) = {0n1n | n>=0}

Т.о. L(G1) U {ε} = L(G3) U {ε}

1   2   3   4   5   6   7   8   9   ...   20

Похожие:

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconРеспублики Беларусь Учреждение образования «белорусский государственный...
Конспект лекций по курсу «Основы алгоритмизации и программирования» для студентов всех специальностей и всех форм обучения. Мн.:...

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

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

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

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

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconКонспект лекций для студентов специальности 1-25 01 04 «Финансы и...
...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconКонспект лекций для студентов специальности 1-54 01 01-04 «Метрология,...
Конспект лекций предназначен для студентов специальности 1-54 01 01-04 «Метрология, стандартизация и сертификация (лёгкая промышленность)»...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconАвтор: Медведева Г. В
Курс лекций содержит основные разделы языка программирования t-pascal, предусмотренные образовательным стандартом

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconКонспект лекций для студентов пятого курса специальности 220400 Программное...
Данный конспект лекций составлен для студентов четвёртого курса специальности “Программное обеспечение вычислительной техники и автоматизированных...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconУчебник Толубеевой Т. И., доцента кафедры пти «Основы проектирования крупноузорчатых тканей»
Особенность Декады – 25- летие выхода в свет стандартов исо серии 9000 на системы менеджмента качества

Литература


При копировании материала укажите ссылку © 2015
контакты
literature-edu.ru
Поиск на сайте

Главная страница  Литература  Доклады  Рефераты  Курсовая работа  Лекции