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




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

Теория трансляции.



Лексический анализатор проверяет правильность ввода, выполняет анализ символов некоторого языка. Для описания лексического анализатора достаточно самых простых грамматик.

Не ограничивая общности, рассмотрим леволинейную грамматику

( A -> t

A -> Bt)

Нет пустых цепочек (это УКС).

а1……аn &
Примечание автора:

& - так будем обозначать признак конца цепочки. На самом деле он обозначается значком перпендикулярности, но, т.к. на клавиатуре такой значок не реализуется, во избежание путаницы договоримся обозначать его &, тем более, что в дальнейшем (а точнее, в лексическом анализаторе) мы столкнёмся именно с таким обозначением этого символа.
Алгоритм разбора снизу вверх:

а1……аn

Просматриваем цепочку слева направо, берём ‘a1’, ищем правило вида ‘A -> а1’ , берём ‘a2’, ищем ‘A -> Ba2’ и т.д., пока не дойдём до признака конца и не прочитаем S при последней свёртке.


  • Если на шаге существует более 1 правила, удовлетворяет условию недетерминированности разбора, если существует единственное правило, приходим к S, то α є V.

  • Если на к.-л. шаге не нашли правила, цепочка не принадлежит языку.

  • Если свернули к нетерминальному символу, отличному от S, цепочка не принадлежит языку.


^

Лекция 5. 05/03/2004.




Диаграммы состояний.



Диаграмма состояний – все возможные свертки.

Рассмотрим регулярную грамматику. (A -> t , A -> Bt)

S -> C &

C -> Ab|Ba

A -> a|Ca

B -> b|Cb
A

a b

H a

b b C

B a &

S

ER
Н – начальное состояние

Анализ цепочки начинается из состояния Н.

Любое правило вида A -> t представляется стрелкой к символу, стоящему в левой части (от Н к А). Все остальные правила A -> Bt, стрелка от В к А.

Правило A -> Bt означает, что, находясь в состоянии В, читая терминальный символ t, попадаем в состояние А.

Диаграмма состояний – ориентированный помеченный граф.
Пример. Найти цепочку abba.

Проходим через состояния H -> A -> C -> B -> C. Мы не пришли в заключительное состояние S. Значит, цепочка abba не принадлежит языку. Однако, признак конца цепочки S формальный, его можно добавить к цепочке. abba&
Каждая стрелка в диаграмме соответствует одному правилу вывода.
Пример. Задача 4.а

L = {anbm&| n,m>=1}

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

a b &

H A B S

//(из В в В по b)

(a) (b)
Первым символом может быть только ‘a’, поэтому из Н выходим через символ ‘a’.

S -> B&

B -> Bb | Ab

A -> Aa | a

По диаграмме состояния можно легко построить грамматику.
L = {anbm& | n>=0 ,m>=1}

Язык остался регулярным, минимальная цепочка – b.

a b

a b &

H A B S
Грамматика. S -> B&

B -> Bb | Ab | b

A -> Aa | a
Если L = {anbm& | n>=0 ,m>=0}
&

a b

a b &

H A B S

b &


Грамматика. S -> B& | &

B -> Bb | Ab | b

A -> Aa | a
ЕР – ошибочное состояние.
Рассмотрим конечный автомат (КА).

ΚΑ = (Κ, VT, F, H, S)

F – функция перехода.

Приняты соглашения для укорачивания записи:

a1

1) Вместо A … B пишется A a1, …, an B

an

2) a1, …, an

A B

b C

D
Если стрелка не помечена, это соответствует всем остальным случаям.
В состояние ЕR ведут стрелки из каждого состояния, кроме S, не помеченные.
F – функция переходов конечного автомата.

F (A,b) = C – означает, что, читая символ ‘b’, переходим из состояния A в состояние C/
Вообще говоря, начальных состояний может быть несколько, но они сводятся в одно.

Заключительное состояние единственно.
^ Язык конечного автомата - множество цепочек, допускаемых автоматом.

Конечный автомат допускает цепочку а1……аn , если

F(H,a1) = A1, F(A1,a2) = A2,…., F(An-1,an) = S.

Т.е. находясь в начальном состоянии, читая символ, попадаем в следующее состояние, и т.д., в итоге попадаем в S.
Анализатор для грамматики:
#include

int c;

void gc( ) { cin >> c;} // gc считывает символы во входную цепочку

bool scan_G( ) {

enum state {H,A,B,C,S,ER}; // - все состояния

state CS = H; // - встали в начальное состояние

gc ( ); // - считали первый символ

do {switch (CS) {

case H: if (c==’a’) {gc( ); CS = A;}

else if (c==’b’) {gc( ); CS = B;}

else CS =ER; break;

case A: if (c==’b’) {gc( ); CS = C;} // находясь в состоянии А,

else CS = ER; break; // можно перейти только в В

case B: …………………………………

case C: …………………………………

} while (SS != S && CS != ER);

if (CS == ER) return false else return true;

}
Перебор «в лоб» всех вариантов по стрелкам приемлем только для простых грамматик. Вообще он неприемлем из-за недетерминированности по времени.
Пример. P: S -> A&

A -> a | Bb

B -> b | Bb

b

b b &

H B A S

a
Рассмотрим недетерминированный конечный автомат.

НКА = (K, VT, F, H, S)
Отличия между КА и НКА:

KA K x VT -> K F (A,t) = B

НКА K x VT -> множество подмножеств F (A,t) = {B1……Bn} – переходим

в множество состояний.
^ Упрощенный механизм построения КА по НКА:

(для предыдущего примера)

НКА: F (H,b) = B KA: F (H,b) = B

F (H,a) = A F (H,a) = A

F (B,b) = B F (B,b) = AB

F (B,b) = A F (AB,b) = AB // включаем к названию те состояния,

F (A,&) = S F (AB,&) = S // куда можно перейти по a (нельзя), b...

F (A,&) = S
Для КА напишем диаграмму состояний.

b B b AB b

H a &

A & S
Пусть задан НКА: F (H,1) = B

F (A,1) = B

F (B,0) = A

F (A,1) = S

Η 1 Β

1 0

Α 1 S

L = {1(01)n | n>=1}
КА: F (H,1) = B

F (B,0) = A

F (A,1) = BS

F (BS,0) = A

1 0 1

H B A BS

0

При построении детерминированного КА по НКА возможна потеря конечного состояния грамматики. Тогда заключительным считается состояние, содержащее букву S. Состояние BS можно свести к S с помощью символа &. Если таких состояний с буквой S несколько, все заключительные состояния необходимо сводить в одно состояние S с помощью символа &.
Необходимо уметь:

  1. строить диаграмму состояний по грамматике и наоборот

  2. приводить НКА к КА.


1   ...   4   5   6   7   8   9   10   11   ...   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
главная страница