Интерпретаторы и компиляторы. Part 3.

В этой части мы сосредоточимся на грамматиках и иерархии Хомского.

Грамматику, по Хантеру, можно рассмотреть как следующую структуру:

(V_T, V_N, P, S)

V_T – алфавит терминалов,

V_N – алфавит нетерминалов,

Необходимо отметить, что множества V_T и V_N не пересекаются, а их объединение будем обозначать V.

P – множество правил. Каждое правило состоит из левой и правой частей и записывается так: q → r.

S – аксиома грамматики. С неё начинается генерация строк языка с данной грамматикой.

Теперь мне бы хотелось процитировать Хантера: “Грамматика используется для генерации последовательностей символов составляющих строки языка, начиная с аксиомы и последовательно заменяя её с помощью одного из порождений грамматики”.

Пример так же возьмем из Хантера. Его мы рассматривали в прошлый раз в самом конце:

{aⁿbⁿ | n>0}

Для такого языка грамматика будет выглядеть следующим образом:

G = ({a, b}, {S}, P, S}

P = {S → aSb, S → ab}

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

Теперь перейдём к иерархии Хомского (Chomsky hierarchy).

Господин Хомский выделил четыре класса грамматик, при этом каждая следующая является частным случаем предыдущей.

0-го типа.

Первая грамматика является наиболее общей, и она называется грамматика 0-го типа. Другое её название – рекурсивно перечислимая. К таким относятся грамматики, попадающие под определение данное Хантером и не имеющие ограничений на типы продукций.

1-го типа.

Для данной грамматики вводится следующее ограничение на продукцию: для продукции q → r количество символов в левой части, не должно быть больше чем в правой (|q| → |r|). Другое название – контекстно-зависимые грамматики.

2-го типа.

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

3-го типа.

Грамматика 2-го типа является регулярной грамматикой. Т.е. может быть представлена как праволинейная или леволиненейная.

Продукция праволинейной грамматики может иметь один из следующих видов:

S → a

S → aB

Соответственно леволинейная:

S → a

S → Ba

Если в грамматики продукции чередуются, т.е. существуют как право- так и леволинейные, то это уже не регулярная грамматика.

На практике, как правило, используются грамматики 2-го и 3-го типов.

Наиболее простой с точки зрения реализации язык – это язык, построенный грамматикой 3-го типа, поэтому по возможности она и используется. Как мы отмечали выше, грамматика 3-го типа, является подмножеством грамматики 2-го типа. Поэтому при невозможности описать структуру с помощью регулярной грамматики используется контекстно-свободная.

Указанное выше положение приводит к необходимости создания способа для определения, подходит ли к данной задачи регулярная грамматика или нет.

Предварительно нужно ввести понятие рекурсии в грамматике.

Рекурсия рассматривается для продукций, и такие продукции имеют вид:

A → Aa

A → aA

A → bAa

Первая называется левой рекурсией (нетерминал находится в левой части), вторая – правой и последняя – средней, соответственно.

Есть такая теорема: “Если грамматика не содержит средней рекурсии, то генерируемый ею язык является регулярным”.

Вот в принципе и всё, что нужно знать, для определения регулярности языка.

Как показывает практика, для задачи лексического анализа почти всегда используется грамматика 3-го типа, для синтаксического – грамматика 2-го типа.

Например, для любого скобочного выражения невозможно применить грамматику 3-го типа, т.к. в ней имеется средняя рекурсия. Для такого выражения, список продукций будет таким:

A → (A)

A → AA

A → e

P.S.

Тема “интерпретаторы и компиляторы” является для меня экспериментальной, поэтому повествование идет исходя из следующей схемы: Изучил → Осмыслил → Написал. Т.е. я хочу сказать, что не являюсь экспертом в этой области, мне просто интересен этот предмет. И для большего понимания я пишу о нём здесь. Постепенно, изучив теорию и разобравшись с инструментами и подходами, мы создадим свой интерпретатор языка.