Леволинейные и праволинейные грамматики. автоматные грамматики

К регулярным относятся два типа грамматик: леволинейные и праволинейные.

Леволинейные грамматики G(VT,VN,P,S), V = VNVT могут иметь правила двух видов: АВ? или А?, где A,BVN, ?VT*.

В свою очередь, праволинейные грамматики G(VT,VN,P,S), V= VNVT могут иметь правила также двух видов: А?В или А?, где А,ВVN, ?VT*.

Доказано, что эти два класса грамматик эквивалентны. Для любого регулярного языка, заданного праволинейной грамматикой, может быть построена леволинейная грамматика, определяющая эквивалентный язык; и наоборот – для любого регулярного языка, заданного леволинейной грамматикой, может быть построена праволинейная грамматика, задающая эквивалентный язык.

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

Среди всех регулярных грамматик можно выделить отдельный класс – автоматные грамматики. Они также могут быть леволинейными и праволинейными.

Леволинейные автоматные грамматики G(VT,VN,P,S), V = VNVT могут иметь правила двух видов: ABt или At, где A,BVN, tVT.

Праволинейные автоматные грамматики G(VT,VN,P,S), V = VNVT могут иметь правила двух видов: AtB или At, где A,BVN, tVT.

Разница между автоматными грамматиками и обычными регулярными грамматиками заключается в следующем: там, где в правилах обычных регулярных грамматик может присутствовать цепочка терминальных символов, в автоматных грамматиках может присутствовать только один терминальный символ. Любая автоматная грамматика является регулярной, но не наоборот – не всякая регулярная грамматика является автоматной.

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

Чтобы классы автоматных и регулярных грамматик были полностью эквивалентны, в автоматных грамматиках разрешается дополнительное правило вида S, где S – целевой символ грамматики. При этом символ S не должен встречаться в правых частях других правил грамматики. Тогда язык, заданный автоматной грамматикой G, может включать в себя пустую цепочку: L(G). В таком случае автоматные леволинейные и праволинейные грамматики, так же как обычные леволинейные и праволинейные грамматики, задают регулярные языки. Поскольку реально используемые языки, как правило, не содержат пустую цепочку символов, разница на пустую цепочку между этими двумя типами грамматик значения не имеет и правила вида S далее рассматриваться не будут.

Существует алгоритм, который позволяет преобразовать произвольную регулярную грамматику к автоматному виду – то есть построить эквивалентную ей автоматную грамматику. Этот алгоритм рассмотрен ниже. Он является исключительно полезным, поскольку позволяет существенно облегчить построение распознавателей для регулярных грамматик.

2.1.2. Алгоритм преобразования регулярной грамматики
к автоматному виду

Имеется регулярная грамматика G(VT,VN,P,S), необходимо преобразовать ее в почти эквивалентную автоматную грамматику G’(VT,VN’,P’,S’). Для определенности будем рассматривать леволинейные грамматики, как уже было сказано выше (для праволинейных грамматик можно легко построить аналогичный алгоритм).

Алгоритм преобразования прост и заключается он в следующей последовательности действий:

Шаг 1. Все нетерминальные символы из множества VN грамматики G переносятся во множество VN’ грамматики G’.

Шаг 2. Необходимо просматривать все множество правил Р грамматики G.

Если встречаются правила вида ABa1, А,ВVN, а1VT или вида Aa1, AVN, a1VT, то они переносятся во множество Р’ правил грамматики G’ без изменений.

Если встречаются правила вида АВа1а2…аn, n1, A,BVN, ni0: aiVT, то во множество нетерминальных символов VN’ грамматики G’ добавляются символы A1, A2, …, An-1, а во множество правил Р’ грамматики G’ добавляются правила:

ААn-1аn

Аn-1Аn-2аn-1

…

А2А1а2

А1Bа1

Если встречаются правила вида Аа1а2…аn, n1, AVN, ni0: aiVT, то во множество нетерминальных символов VN’ грамматики G’ добавляются символы A1, A2, …, An-1, а во множество правил Р’ грамматики G’ добавляются правила:

ААn-1аn

Аn-1Аn-2аn-1

…

А2А1а2

А1а1

Если встречаются правила вида АВ или вида А, то они переносятся во множество правил Р’ грамматики G’ без изменений.

Шаг 3. Просматривается множество правил Р’ грамматики G’. В нем ищутся правила вида АВ или вида А.

Если находится правило вида АВ, то просматривается множество правил Р’ грамматики G’. Если в нем присутствуют правила вида ВС, ВСа, Ва или В, то в него добавляются правила вида АС, АСа, Аа и А соответственно, A,B,CVN’, aVT’ (при этом следует учитывать, что в грамматике не должно быть совпадающих правил, и если какое-то правило уже присутствует в грамматике G’, то повторно его туда добавлять не следует). Правило АВ удаляется из множества правил Р’.

Если находится правило вида А, то просматривается множество правил Р’ грамматики G’. Если в нем присутствует правило вида ВА или ВАа, то в него добавляются правила вида В и Ва соответственно, A,BVN’, aVT’ (при этом следует учитывать, что в грамматике не должно быть совпадающих правил, и если какое-то правило уже присутствует в грамматике G’, то повторно его туда добавлять не следует). Правило А удаляется из множества правил Р’.

Шаг 4. Если на шаге 3 было найдено хотя бы одно правило вида АВ или А во множестве правил Р’ грамматики G’, то надо повторить шаг 3, иначе перейти к шагу 5.

Шаг 5. Целевым символом S’ грамматики G’ становится символ S.

Шаги 3 и 4 алгоритма в принципе можно не выполнять, если грамматика не содержит правил вида АВ (такие правила называются цепными) или вида А (такие правила называются -правилами). Реальные регулярные грамматики обычно не содержат правил такого вида. Тогда алгоритм преобразования грамматики к автоматному виду существенно упрощается.

Конечные автоматы

Леволинейные и праволинейные грамматики. автоматные грамматики

Статьи к прочтению:

Лекция 2 | Формальные языки и синтаксический анализ | Александр Охотин | Лекториум

Похожие статьи: