Теория трансляции.
Лексический анализатор проверяет правильность ввода, выполняет анализ символов некоторого языка. Для описания лексического анализатора достаточно самых простых грамматик.
Не ограничивая общности, рассмотрим леволинейную грамматику
( 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 с помощью символа &.
Необходимо уметь:
-
строить диаграмму состояний по грамматике и наоборот
-
приводить НКА к КА.
|