4.2. Формальные языки и грамматики
Компьютерные языки являются подмножеством формальных языков.
Формальный язык состоит из множества строк конечной длины, называемых словами. Слова состоят из символов, а символы содержатся в алфавите – конечном множестве символов.
В этом определении предполагается, что для установления принадлежности некоторой строки формальному языку необходимо сначала перечислить все возможные строки на этом языке, что, разумеется, является непрактичным подходом.
Рассмотрим иной способ определения языка. Регулярный язык, являющийся теоретической основой регулярных выражений, может быть описан следующим образом:
- Пустая строка ε или одиночный символ из алфавита являются регулярным языком.
- Если \(A\) это регулярный язык, то \(A^{*}\) также является регулярным языком. Операция \(A^{*}\) обозначает повторение \(R\) 0 или более раз.
- Если \(A\) и \(B\) – регулярные языки, то \(A | B\) тоже является регулярным языком. Операция \(A | B\) обозначает выбор из \(A\) или \(B\).
- Если \(A\) и \(B\) – регулярные языки, то \(A B\) тоже является регулярным языком. Операция \(A B\) обозначает последовательность: \(A\), за которым следует \(B\).
Введенных базовых операций достаточно, чтобы определить дополнительные конструкции, использующиеся в регулярных выражениях. Например, конструкцию A+ можно определить, как AA*, а конструкция A? заменяется конструкцией A|ε.
Мощности регулярных языков, тем не менее, не хватает для описания многих важных компьютерных языков. В частности, с помощью регулярного языка невозможно описать конструкции произвольной вложенности. Это, в том числе, касается разбора и HTML-кода, и даже простого выражения, в котором присутствуют лишь правильно расставленные скобки с произвольной глубиной вложенности.
Другой способ определения формального языка – формальная грамматика, задающая общие правила построения языка. Этот способ используется для определения синтаксиса компьютерных языков. Формальная грамматика – метаязык, то есть язык, который определяет язык. В частности, для описания регулярных языков может быть задана регулярная грамматика.
Формальные грамматики на практике используются для следующих целей:
- лексический и синтаксический разбор компьютерного языка;
- порождение случайных фраз на компьютерном языке, например, для задач тестирования.
Более мощным, чем регулярные языки, формализмом описания компьютерных языков является контекстно-свободная грамматика.
Контекстно-свободную грамматику можно представить себе в виде программы на ограниченном языке программирования. В этом языке есть «имена функций» (нетерминалы, имена правил) и «определения функций» (тела правил). В определениях содержатся «вызовы функций» и «вывод символов» определяемого языка (терминалов). Работа программы начинается с «главной функции», называемой начальным нетерминалом.
Благодаря возможности использования рекурсии в грамматических правилах контекстно-свободные грамматики широко используются для определения синтаксиса компьютерных языков.
Контекстно-свободную грамматику можно представить в форме так называемой железнодорожной или синтаксической диаграммы.
На рис. 31 показан пример грамматики арифметического выражения.
В текстовой форме контекстно-свободная грамматика определяется с помощью формы Бэкуса-Наура (БНФ). На практике, в БНФ часто добавляются конструкции регулярных выражений для упрощения описания синтаксиса.
Ниже представлен пример грамматики арифметического выражения в БНФ:
<Значение> ::= <Число> | <Переменная>
<Операция> ::= "+" | "-" | "*" | "/"
<Выражение> ::= <Значение> | <Выражение> <Операция> <Выражение> | "(" <Выражение> ")"
Для автоматизации задач лексического (уровень базовых лексических единиц) и синтаксического (уровень иерархических конструкций) разбора существуют специальные инструменты. Примерами таких инструментов являются ANTLR [42] для Java, SLY [43] для Python и Flex/Bison для C++.