Интерпретация управления сканированием входного потока

Lexer:

//Init

inputStream.Open();

tokenStream. Open ();

q = 0;

s = ””;

while(true)

{

if( inputStream.Eof()) {

//текущее состояние q in Active

a =’#’;

b = [a];

f[q,b]();

//выход

tokenStream.Close();

inputStream.Close();

exit;

}

else

{

//текущее состояние q in Active и //не конец входного потока inputStream

a=inputStream.ReadChar();

b=[a];

f[q,b]();

//по (q, b) выполнить процедуру f(q,b) in P, т.е. проинтерпретировать //символ f(q,b) с помощью базисной функции f[q,b](), другими словами,  //выполнить инструкцию (команду) f(q,b)

}

}

Простой метод вычисления декартова произведения

Пусть L_i = L(M_i) – не пустые и -свободные регулярные языки над общим алфавитом B, допускаемые ДКА M_i = (Q_i, B , g_i, q_i⁰, F_i) для всех i [1, n], n > 1. На множестве всех слов B* для целого числа k  0 однозначно определена функция first_k(w). По определению эта функция каждому слову w ставит в соответствие префикс v: v = w, если |w| < k и, если |w| > k, тогда v = x, где слово x такое, что w = xy и |x| = k, y B*.

Для любого языка L  B* определено конечное множество FIRST_k(L) = {first_k(w)| w L}.

Не пустые языки L, L  B* называются разделенными, если существует k > 0, что справедливо FIRST_k(L)  FIRST_k(L) = .

Если не пустой и -свободный язык L допускается ДКА, то очевидно FIRST₁(L) = {b| g(q₀, b)  Active}.

Пусть любая пара языков L_i и L_j , 1 i  j  n, разделена при k = 1. Тогда автомат M = (Q, B , g, q₀, F), изоморфный декартову произведению автоматов M₁  M₂ … M_n , определяется следующим образом:

Q = {q₀}  Active₁  …  Active_n  {q_error}; F = F₁  …  F_n; g(q₀, b) = q, если g_i(q_i⁰, b) = q  Active_i , i [1, n], n > 1;

g(q₀, b) = q_error для всех b  (FIRST₁(L₁)  …  FIRST₁(L_n));

для всех qActive_i g(q, b) = q_error , если g_i(q, b) = q  Error_i , i [1, n], n > 1;

g(q_error, b) = q_error для всех bB;

g(q, b) = q, если g_i(q, b) = q , где q, q  Active_i , i [1, n], n > 1;

На языке диаграмм (орграфов) диаграмма переходов D автомата M конструируется, как описано ниже.

Пусть D_i – диаграмма автомата M_i. Через D_1-n = D₁  D₂ … D_n обозначим объединение диаграмм. Определим отображение : Q₁  Q₂ … Q_n Q :

( q_i⁰) = q₀ и ( q) = q_error , где q  Error_i , для всех i [1, n];

( q) = q, где q  Active _i , для всех i [1, n];

( (q, b, q)) = (( q), b, ( q)), если (q, b, q) – дуга диаграммы D_1-n.

Отображение   гомоморфизм диаграмм и образ D = ( D_1-n) изоморфен диаграмме автомата M.

Графически выполнить построение диаграммы D = ( D_1-n) значит

отождествить (топологически) начала всех дуг (q_i⁰, b, q) с вершиной q₀ и концы всех дуг (q, b, q) с вершиной q_error при условии, что q  Error_i , i [1, n]. Такой метод называется «слиянием диаграмм».

В случае табличного представления автоматов M_i , i [1, n], метод построения таблицы автомата M, изоморфного автомату M₁M₂…M_n , подобен методу «слияния диаграмм», и хорошо подходит для программной реализации.

Пример 1. FIRST₁(L₁) = {a, l, u}; FIRST₁(L₂) = {0}; FIRST₁(L₃) = {s, t}. Следовательно, автомат M= M₁ x M₂ x M₃ допускает конструирование методом «слияния диаграмм».