Системы программирования (1119744), страница 8
Текст из файла (страница 8)
Заметим, что могут быть случаи и хуже:
Для цепочки B┴ нет подходящей свертки, так что предложенная нам цепочка языку не принадлежит. Другой случай:
Цепочка уже закончилась, и дерево успешно построено, однако его корень не помечен S. Значит, и эта цепочка не принадлежит порождаемому нашей грамматикой языку.
Однако список проблем на этом не заканчивается. Заменим последнюю группу правил в грамматике на такую:
B -> Aa | b
или другую:
B -> Aa | Bb
Что же мы видим? У разных нетерминалов появляются одинаковые альтернативы, а значит, казавшийся нам столь простым алгоритм нужно для таких грамматик модифицировать, обходя в процессе работы целое дерево вложенных вариантов (с откатами назад). Обратим особое внимание на важный факт: анализ получается недетерминированным, хотя рассматриваемая грамматика однозначна! Запомним это и отметим также справедливость следующего утверждения: любой язык, который можно описать регулярной грамматикой, можно описать регулярной грамматикой «без одинаковых правых частей».
Конечные автоматы
Определение конечного автомата из дискретной математики, безусловно, хорошо известно всем. Однако мы будет рассматривать конечные автоматы в первую очередь как «распознаватели» языков, поэтому дадим более узкое, удобное нам определение.
Недетерминированный конечный автомат (НКА) – это пятерка (K, VT, F, H, S), где:
K – конечное множество состояний автомата,
VT – конечное множество входных символов,
F – функция переходов: F: K x VT → P(K) (последним символом обозначено множество всех подмножеств K),
HK – начальное состояние,
SK – множество заключительных состояний.
Определим еще несколько понятий. Будем говорить, что НКА допускает цепочку α=a1...an, если F(H,a1) = A1, F(A1,a2) = A2, ..., F(An-1,an) = An S (символы равенства следует понимать здесь следующим образом: найдутся элементы A1, ..., An множества K такие, что A1 – элемент F(H,a1), A2 – элемент F(A1,a2), ..., An – элемент F(An-1,an)). Язык, допускаемый (определяемый, распознаваемый) НКА – это множество всех допускаемых этим НКА цепочек.
Диаграмма состояний (ДС) НКА – это помеченный ориентированный граф такой, что:
-
его вершины помечены символами состояний из K,
-
вершины A и B соединяются дугой (от A к B), если a VT: F(A,a) = B, при этом дуга помечается всеми такими a.
Сформулируем без доказательства две теоремы.
Теорема 1. Для L = L(НКА) всегда найдется регулярная грамматика G: L(G) = L.
Теорема 2. Для L = L(G), где G – регулярная грамматика, всегда найдется НКА: L = L(НКА).
Из доказательств этих теорем извлечем лишь правила получения G из НКА и НКА из G соответственно.
-
НКА -> G (регулярная леволинейная)
-
Регулярная леволинейная G -> НКА
Пример.
НКА = ( {H,A,B,S}, {a,b,+,-}, F, H, {S} )
F: F(H,a)=A, F(H,b)=A;
F(A,+)=B, F(A,-)=B;
F(B,a)=A, F(B,b)=A;
F(A, ┴)=S (маркер конца обыкновенно не указывают явно в VT),
а для остальных пар F =
ДС:
ДС весьма удобна: язык «виден» читателю. Будем теперь строить грамматику:
S -> A┴
A -> Ba | Bb | a | b
B -> A+ | A-
Обратный пример.
S -> A┴
A -> Ab | Bb | b
B -> Aa
Строим НКА:
Получена, по сути дела, блок схема алгоритма разбора цепочки. На плюсах это может выглядеть примерно так:
class Scan // реализация НКА
{
enum State {H, A, B, S};
State cs; // current state
FILE *fp; // input file
char c;
public:
Scan(const char *data);
~Scan();
bool analyze();
};
Scan::Scan(const char *data)
{
fp = fopen(data, "r");
if (!fp) throw data;
cs = H;
c = fgetc(fp);
}
Scan::~Scan()
{
fclose(fp); // если файл не был открыт, то объект
// не был создан => вызова не будет
}
bool Scan::analyze()
{
try
{
do
{
switch(cs)
{
case H:
if (c == 'b')
{
c = fgetc(fp); cs = A;
}
else
throw c; // упрощенно
break;
case A:
if (c == 'a')
{
c = fgetc(fp); cs = B;
}
else if (c == 'b')
{
c = fgetc(fp); // cs уже == B
}
else if (c == '┴')
{
cs = S; // end
}
else
throw c;
case B:
if (c == 'b')
{
c = fgetc(fp); cs = A;
}
else
throw c;
} //switch
} while (cs != S); //do
} //try
catch(char c)
{
cout << "..." << c << endl;
return false;
}
return true;
}//analyze()
int main()
{
bool res;
try
{
Scan E("test.txt");
res = E.analyze();
cout << "Result is " << res << endl;
}
catch(const char *file)
{
cout << "Error opening file " << file << endl;
}
return 0;
}
Сделаем еще несколько замечаний. Во-первых, мы работали с очень удобной грамматикой: S в правилах вывода встречается только слева (ясно, что этого можно добиться всегда). Во-вторых, в приведенном коде нет проверки на наличие символов после '┴' (вообще говоря, мы не слишком-то заботились о содержимом входного файла, считая, что '┴' там обязательно-обязательно встретится). Далее, в нашем примере анализ детерминирован, хотя, как уже отмечалось ранее, это не всегда справедливо (опять же ограничимся замечанием, что построить детерминированный конечный автомат, тем не менее, возможно).
Кроме того (а мы уже почти вплотную приблизились к построению лексического анализатора!) обратим внимание на то, что нашу схему очень легко модифицировать для решения родственных задач (рано или поздно нам придется «выдавать» на выход лексемы). Продолжим для иллюстрации этого утверждения рассмотрение нашего примера.
Зададимся вопросом: а какой язык распознает построенный нами НКА (и – по нему – алгоритм)? Ответом будет L = {b┴, bαb┴, α{a,b}*, где нет двух a подряд}. Поставим теперь задачу определить длину максимальной последовательности подряд идущих b (не «разорванных» ни одной a). Решением можно считать несколько измененную диаграмму состояний:
Здесь дуги, кроме терминальных символов, инициирующих переходы, помечены также дополнительными действиями – то бишь соответствующими фрагментами кода. Достаточно перенести их в надлежащее место в программе, и программа наряду с проверкой на принадлежность цепочки нашему языку будет решать описанную задачу. Заметим, что алгоритмическая сложность по сравнению с общей схемой остается прежней.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
