🗊Презентация Конечные автоматы. (Лекция 5)

Лекция 05. Конечные автоматы

В основе лексических анализаторов лежат регулярные грамматики Соглашение: в дальнейшем, если особо не оговорено, под регулярной грамматикой будем понимать леволинейную грамматику. Напомним, что грамматика G = (VT, VN, P, S) называется леволинейной, если каждое правило из Р имеет вид A  Bt либо A  t, где A  VN, B  VN, t  VT. Соглашение: предположим, что анализируемая цепочка заканчивается специальным символом  - признаком конца цепочки.

Алгоритм разбора для леволинейных грамматик (принадлежит ли цепочка a1a2...an языку грамматики) первый символ исходной цепочки a1a2...an заменяем нетерминалом A, для которого в грамматике есть правило вывода A  a1 ("свертка" терминала a1 к нетерминалу A) многократно (до тех пор, пока не считаем признак конца) выполняем: полученный на предыдущем шаге нетерминал A и расположенный непосредственно справа от него очередной терминал ai исходной цепочки заменяем нетерминалом B, для которого есть правило вывода B  Aai (i = 2, 3,.., n); Это эквивалентно построению дерева разбора методом "снизу-вверх": на каждом шаге алгоритма строим один из уровней в дереве разбора, "поднимаясь" от листьев к корню.

При работе алгоритма возможны следующие ситуации: прочитана вся цепочка; на последнем шаге свертка произошла к символу S.  a1a2...an  L(G). прочитана вся цепочка; на последнем шаге свертка произошла к символу, отличному от S.  a1a2...an  L(G). на некотором шаге не нашлось нужной свертки, т.е. для нетерминала A и очередного терминала ai исходной цепочки не нашлось нетерминала B, для которого было бы правило вывода B  Aai.  a1a2...an  L(G). на некотором шаге работы алгоритма оказалось, что есть более одной подходящей свертки. Это говорит о недетерминированности разбора.

Пример реализации алгоритма Построим таблицу возможных сверток для грамматики

Пример реализации алгоритма Или диаграмму состояний

Правила построения диаграммы строим вершины графа, помеченные нетерминалами грамматики (для каждого нетерминала - одну вершину), и еще одну вершину, помеченную символом, отличным от нетерминальных (например, H). Эти вершины будем называть состояниями. H - начальное состояние. соединяем эти состояния дугами по правилам: для каждого правила грамматики вида W  t соединяем дугой состояния H и W (от H к W) и помечаем дугу символом t; для каждого правила W  Vt соединяем дугой состояния V и W (от V к W) и помечаем дугу символом t;

Детерминированный конечный автомат (КА) Определение: конечный автомат (КА) - это пятерка (K, VT, F, H, S), где K - конечное множество состояний; VT - конечное множество допустимых входных символов; F - отображение множества K  VT  K, определяющее поведение автомата; F - функция переходов; H  K - начальное состояние; S  K - заключительное состояние (либо конечное множество заключительных состояний). F(A, t) = B означает, что из состояния A по символу t автомат переходит в состояние B.

О недетерминированном разборе Для грамматики G = ({a,b, }, {S,A,B}, P, S), где P: S  A A  a | Bb B  b | Bb разбор будет недетерминированным (т.к. у нетерминалов A и B есть одинаковые правые части - Bb). Такой грамматике будет соответствовать недетерминированный конечный автомат.

Недетерминированный конечный автомат (НКА) Определение: недетерминированный конечный автомат (НКА) - это пятерка (K, VT, F, H, S), где K - конечное множество состояний; VT - конечное множество допустимых входных символов; F - отображение множества K  VT в множество подмножеств K; H  K - конечное множество начальных состояний; S  K - конечное множество заключительных состояний.

Следующая тема: «Построение сканера»