Методы и средства лексического анализа

Рассмотрим методы и средства, которые обычно используются при построении лексических анализаторов. В основе таких анализаторов лежат регулярные грамматики, поэтому рассмотрим грамматики этого класса более подробно.

Соглашения:

- в дальнейшем, если особо не оговорено, под регулярной грамматикой будем понимать леволинейную грамматику;

- предположим, что анализируемая цепочка заканчивается специальным символом ^ - признаком конца цепочки.

Для регулярных грамматик существует алгоритм определения того, принадлежит ли анализируемая цепочка языку, порождаемому этой грамматикой (алгоритм разбора):

(1) первый символ исходной цепочки a₁a₂...a_n^ заменяем нетерминалом A, для которого в грамматике есть правило вывода A ® a₁ (другими словами, производим "свертку" терминала a₁ к нетерминалу A)

(2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: полученный на предыдущем шаге нетерминал A и расположенный непосредственно справа от него очередной терминал a_i исходной цепочки заменяем нетерминалом B, для которого в грамматике есть правило вывода B ® Aa_i (i = 2, 3,.., n);

Данный алгоритм эквивалентен алгоритму построения дерева разбора методом "снизу-вверх": на каждом шаге алгоритма строим один из уровней в дереве разбора, "поднимаясь" от листьев к корню.

При работе этого алгоритма возможны следующие ситуации:

1) прочитана вся цепочка; на каждом шаге находилась единственная нужная "свертка"; на последнем шаге свертка произошла к символу S. Это означает, что исходная цепочка a₁a₂...a_n^ Î L(G).

2) прочитана вся цепочка; на каждом шаге находилась единственная нужная "свертка"; на последнем шаге свертка произошла к символу, отличному от S. Это означает, что исходная цепочка a₁a₂...a_n^ Ï L(G).

3) на некотором шаге не нашлось нужной свертки, то есть для полученного на предыдущем шаге нетерминала A и расположенного непосредственно справа от него очередного терминала a_i исходной цепочки не нашлось нетерминала B, для которого в грамматике было бы правило вывода B ® Aa_i. Это означает, что исходная цепочка a₁a₂...a_n^ Ï L(G).

4) на некотором шаге работы алгоритма оказалось, что есть более одной подходящей свертки, то есть в грамматике разные нетерминалы имеют правила вывода с одинаковыми правыми частями, и поэтому непонятно, к какому из них производить свертку. Это говорит онедетерминированности разбора. Анализ этой ситуации будет дан ниже.