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




НазваниеКонспект лекций доцента и. А. Волковой по курсу «системы программирования»
страница5/20
Дата публикации28.06.2013
Размер0.69 Mb.
ТипКонспект
lit-yaz.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Конспект лекций по курсу «Объектно-ориентированное программирование»
Б. Страуструп. Язык программирования C++, 3-е изд./Пер с англ. – Спб.; М.: «Невский диалект» – «Издательство бином», 1999 г. – 991...

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

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

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

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

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

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

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

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

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



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



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