Основные определения. Описание языков программирования во многом опирается на теорию формальных языков

Языки и грамматики

Описание языков программирования во многом опирается на теорию формальных языков. Эта теория является фундаментом для организации синтаксического анализа и перевода.

Существует два основных способа определения языков:

· механизм порождения или генератор;

· механизм распознавания или распознаватель.

Порождающая грамматика состоит из четырех компонент: Г = ( V, W, J, R), где V и W - непересекающиеся конечные множества, называющиеся основным и вспомогательным алфавитами (или словарями). Элементы этих множеств называются соответственно основными (или терминальными) и вспомогательными (или нетерминальными) символами; J - выделенный вспомогательный символ, называемый начальным символом; R - конечный набор правил вывода, имеющих вид j (r) y, где j и y - цепочки, состоящие из основных и вспомогательных символов.

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

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

Неформально язык L - это множество цепочек конечной длины в алфавите T. Механизм порождения позволяет описать языки с помощью системы правил, называемой грамматикой. Цепочки (предложения) языка строятся в соответствии с этими правилами. Достоинство определения языка с помощью грамматик в том, что операции, производимые в ходе синтаксического анализа и перевода, можно делать проще, если воспользоваться структурой, предписываемой цепочкам с помощью этих грамматик.

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