Роль и место формальных грамматик в синтаксическом анализе

Формальные грамматики (ФГ) как математический аппарат появились именно по «производственной необходимости» представления синтаксиса в трансляторах и автоматизации синтаксического анализа (СА). В отличие от лексики и семантики, которые можно в принципе реализовать, использую только содержательные (неформальные) средства, синтаксический анализатор почти невозможно сделать, руководствуясь «здравым смыслом» и очевидностью. Необходим некоторый промежуточный уровень между синтаксисом языка и программной системой, его распознающей. Таковым уровнем и является ФГ.

ФГ является не только средством представления синтаксиса, на ее основе создается инструментарий СА. Самая общая схема синтаксического анализатора, построенного на основе формальных методов, выглядит следующим образом:

1. Описание синтаксиса языка дается исключительно средствами ФГ.

2. Формальный метод СА устанавливает свойства ФГ (множества символов и отношения между ними), которые определяются, исходя из правил, составляющих ФГ.

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

4. Распознаватель представляет собой алгоритм (управляющий автомат), который наряду со строкой исходного текста программы (со «снятой» лексикой) в качестве обязательного элемента использует стек. Необходимость стека и качественные характеристики такой стековой машины будут рассмотрены в конце параграфа.

5. Распознаватель, используя данные, «извлеченные» из ФГ, выполняет действия, которые соответствуют синтаксической структуре предъявляемого ему текста (например, отрабатывает последовательность действий, соответствующих обходу синтаксического дерева).

Напрашивается очевидная аналогия. Стековая машина является процессором (интерпретатором) определенного набора действий, соответствующих синтаксическому анализу, полученные формальным методом табличные данные являются программой его работы, а описание синтаксиса в виде ФГ – ее исходным текстом. Проще говоря, ФГ – это язык программирования синтаксиса.