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




Скачать 0.69 Mb.
Название Конспект лекций доцента и. А. Волковой по курсу «системы программирования»
страница 8/20
Дата публикации 24.05.2014
Размер 0.69 Mb.
Тип Конспект
literature-edu.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 &

HA 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 &

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

B -> Bb | Ab | b

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

a b

a b &

HA 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 &

HB 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

Ha &

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

HB A BS

0

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

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

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


1   ...   4   5   6   7   8   9   10   11   ...   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
Поиск на сайте

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