Для того чтобы быстрее находить правило с подходящей правой частью, зафиксируем все возможные свертки. Информацию о возможных свертках чаще представляют в виде диаграммы состояний(ДС)- неупорядоченного ориентированного помеченного графа, который строится следующим образом:
1) строят вершины графа, помеченные нетерминалами грамматики (для каждого нетерминала - одну вершину), и еще одну вершину, помеченную символом, отличным от нетерминальных (например, H). Эти вершины будем называть состояниями.H - начальное состояние;
2) соединяем эти состояния дугами по следующим правилам:
- для каждого правила грамматики вида А ® t соединяем дугой состояния H и А (направление указываем стрелкой: от H к А) и помечаем дугу символом t;
- для каждого правила А ® Вt соединяем дугой состояния В и А (от В к А) и помечаем дугу символом t;
4) S (целевой символ грамматики) – конечное состояние.
Для более удобной работы с диаграммами состояний введем несколько соглашений:
- если из одного состояния в другое выходит несколько дуг, помеченных разными символами, то будем изображать одну дугу, помеченную всеми этими символами;
- непомеченная дуга будет соответствовать переходу при любом символе, кроме тех, которыми помечены другие дуги, выходящие из этого состояния;
- чтобы исключить ситуации, для которых нет переходов по входным символам, введем состояние ошибки (ER). На это состояние замыкают все неопределенные переходы, а все переходы из самого состояния ER замыкают на него же. Переход в это состояние будет означать, что исходная цепочка языку не принадлежит.
Алгоритм разбора по диаграмме состояний:
(1) объявляем текущим состояние H;
(2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: считываем очередной символ исходной цепочки и переходим из текущего состояния в другое состояние по дуге, помеченной этим символом. Состояние, в которое мы при этом попадаем, становится текущим.
При работе этого алгоритма возможны следующие ситуации (аналогичные ситуациям, которые возникают при разборе непосредственно по регулярной грамматике):
(1) прочитана вся цепочка; на каждом шаге находилась единственная дуга, помеченная очередным символом анализируемой цепочки; в результате последнего перехода оказались в состоянии S. Это означает, что исходная цепочка принадлежит L(G).
(2) прочитана вся цепочка; на каждом шаге находилась единственная "нужная" дуга; в результате последнего шага оказались в состоянии, отличном от S. Это означает, что исходная цепочка не принадлежит L(G).
(3) на некотором шаге не нашлось дуги, выходящей из текущего состояния и помеченной очередным анализируемым символом. Это означает, что исходная цепочка не принадлежит L(G).
(4) на некотором шаге работы алгоритма оказалось, что есть несколько дуг, выходящих из текущего состояния, помеченных очередным анализируемым символом, но ведущих в разные состояния. Это говорит онедетерминированности разбора. Анализ этой ситуации будет приведен ниже.
Пример 3.1
Построим диаграмму состояний для регулярной грамматики
G = ({0, 1, . }, {S, F, D}, P, S) со следующими правилами
P: S à S0 | S1 | F0 | F1
F à D .
D à 0 | 1 | D0 | D1
Рис. 3.4. Диаграмма состояний
Произведем разбор цепочек по диаграмме состояний.
11.010 : H à D à D à F à S à S à S(цепочка принадлежит языку)
0.1 : H à D à F à S (цепочка принадлежит языку)
01. : H à D à D à F (цепочка не принадлежит языку)
100 : H à D à D à D (цепочка не принадлежит языку)
Грамматика G порождает язык
L(G) = {(0 | 1)n(.)k(0 | 1)m|n > 0, m > 0, k = 1}
Пример 3.2
Дана диаграмма состояний.
Рис. 3.5. Диаграмма состояний
Требуется восстановить по данной диаграмме состояний регулярную грамматику. Применим для решения задачи алгоритм построения диаграммы состояний.
Р={ A à 0 | 1 | A1 | A0 | B0 | B1, B à A+ | A- , S à A^ }
Произведем разбор цепочек по диаграмме состояний.
1011^ : H à A à A à A à A à S
10+011^ : H à A à A à B à A à A à A à S
0-101+1^ : H à A à B à A à A à A à B à A à S
Данная грамматика порождает язык
L = {(0 | 1)n ((+ | -)k (0 | 1)m)p | n > 0, m > 0, p ≥ 0, 0 ≤ k ≤ 1 }
Диаграмма состояний (ДС) представляет собой граф переходов конечного автомата, построенного по регулярной грамматике, который допускает множество цепочек, составляющих язык, определяемый этой грамматикой. Состояния и дуги ДС - это графическое изображение функции переходов конечного автомата из состояния в состояние при условии, что очередной анализируемый символ совпадает с символом-меткой дуги. Среди всех состояний выделяется начальное (считается, что в начальный момент своей работы автомат находится в этом состоянии) и конечное (если автомат завершает работу переходом в это состояние, то анализируемая цепочка им допускается).
Конечный автомат(КА) - это пятерка (K, V, F, H, S), где
K - конечное множество состояний автомата;
V - конечное множество допустимых входных символов (алфавит автомата);
F - отображение множества K ´ V ® K, определяющее поведение автомата; отображение F часто называют функцией переходов;
H Î K - начальное состояние;
S Î K - заключительное состояние (либо конечное множество заключительных состояний).
Работа конечного автомата представляет собой некоторую последовательность шагов (или тактов). На каждом шаге работы автомат находится в одном из своих состояний К (текущем состоянии). То, в какое состояние он перейдет на следующем шаге работы, определяется функцией переходов F, которая зависит от текущего состояния и от символа алфавита V, поступающего на вход автомата (рис. 3.6). На следующем шаге автомат может перейти в другое состояние или остаться в текущем состоянии. Если функция переходов допускает переход автомата из текущего состояния в несколько следующих состояний, то конечный автомат может перейти в любое из этих состояний. В начале работы КА всегда находится в начальном состоянии Н. Работа КА продолжается до тех пор, пока на его вход поступают символы входной цепочки wÎV+.
Рис. 3.6. Принцип работы конечного автомата
Конфигурацией автомата M = (K, V, F, H, S) называется пара (h, w) Î K ´ VT *, где h – текущее состояние управляющего устройства, а w – цепочка символов на входной ленте, состоящая из символа под головкой и всех символов справа от него.
Конфигурация (H, w) называется начальной;
конфигурация (h, ε), где hÎS – заключительной (или допускающей).
F(A, t) = B означает, что из состояния A по входному символу t происходит переход в состояние B.
Будем говорить, что конечный автомат допускает цепочку a1a2...an, если F(H,a1) = A1; F(A1,a2) = A2; . . . ; F(An-2,an-1) = An-1; F(An-1,an) = S, где ai Î V, Aj Î K, j = 1, 2 , ... , n-1; i = 1, 2, ... , n; H - начальное состояние, S - одно из заключительных состояний. Другими словами, КА допускает цепочку символов, если, получив на вход эту цепочку, автомат из начального состояния может перейти в одно из заключительных состояний.
КА называют полностью определенным, если в каждом его состоянии существует функция перехода для всех возможных входных символов.
Конечный автомат, граф переходов которого соответствует диаграмме состояний, представленной выше на рис. 3.5, формально может быть определен таким образом:
M = ({H, A, B, ER, S}, {0, 1, +, -, ^}, F, H, {S}), где
Во множество состояний этого конечного автомата включено состояние ER (ошибка), на которое замыкаются все неопределенные переходы, следовательно рассматриваемый конечный автомат приведен к полностью определенному виду.
Множество цепочек, допускаемых конечным автоматом, составляет определяемый им язык.
Обычно перед лексическим анализатором стоит более сложная задача, чем просто ответ на вопрос, принадлежит ли входная цепочка символов заданному языку. Сканер должен не только выделить в исходном тексте лексему, но и записать ее в таблицу лексем. Также сканеру необходимо уметь работать с таблицей идентификаторов: осуществлять поиск идентификатора в таблице и запись в нее нового идентификатора. Обычно эти действия выполняются сканером сразу же по обнаружению конца распознаваемой лексемы. На графе переходов конечного автомата сканера (или на диаграмме состояний) эти действия отображаются достаточно просто: на дугах вводится дополнительный вид пометок - пометки-действия. Теперь каждая дуга в ДС может выглядеть так, как показано на рис. 3.7:
Рис. 3.7. Диаграмма состояний с пометками-действиями
Если в состоянии A очередной анализируемый символ совпадает с символом ti для какого-либо i = 1, 2 ,... n, то осуществляется переход в состояние B; при этом необходимо выполнить действия D1, D2, ... ,Dm.
После построения графа переходов конечного автомата (или диаграммы состояний) несложно написать программу, моделирующую работу этого автомата, которая и будет представлять собой сканер, распознающий цепочки входного языка, заданного этим конечным автоматом.
Пример 3.3
Рассмотрим грамматику G = ({a,b, ^}, {S,A,B,C}, P, S), где
P={ S ® C^, С ® Ab | Ba, A ® a | Ca, B ® b | Cb}
Диаграмма состояний грамматики G представлена на рис. 3.8.
В листинге 3.1 приводится текст функции scan_G(), написанной на языке программирования С, которая представляет собой лексический анализатор для языка, заданного грамматикой G (или конечным автоматом, где диаграмма состояний на рис. 3.8 - граф переходов этого КА). Функция scan_G() завершает свою работу, как только произойдет переход в заключительное состояние или состояние ER. Анализируемый исходный текст расположен в файле data.txt . Если цепочка принадлежит языку, заданному грамматикой G, то функция scan_G() возвращает значение 0, в противном случае функция возвращает значение -1.
Рис. 3.8. Диаграмма состояний
Листинг 3.1
#include <stdio.h>
// Функция – лексический анализатор
int scan_G(){
enum state {H, A, B, C, S, ER}; // Множество состояний конечного автомата
state CS; // CS - текущее состояние
FILE *fp; // Указатель на файл, в котором находится анализируемая цепочка
int c; // Переменная для хранения очередного считанного символа
CS=H; // В качестве текущего состояния устанавливается начальное состояние Н
fp=fopen("data.txt","r"); // Открытие файла для чтения
c=fgetc (fp); // Считывание символа из файла
// Основной цикл: распознавание лексемы
do {switch(CS) {
case H: if (c=='a') {c=fgetc(fp); CS=A;}
else if (c=='b'){c=fgetc(fp); CS=B;}
else CS=ER;
break;
case A: if (c=='b') {c=fgetc(fp); CS=C;}
else CS=ER;
break;
case B: if (c=='a') {c=fgetc(fp); CS=C;}
else CS=ER;
break;
case C: if (c=='a') {c=fgetc(fp); CS=A;}
else if (c=='b') {c=fgetc(fp); CS=B;}
else if (c=='^') CS=S;
else CS=ER;
break;
}
// Выход из цикла по достижению заключительного состояния или состояния ER
D à 0 | 1 | D0 | D1
