Цепочка (слово)

Алфавит (словарь)

Способы определения языков

V. Введение в теорию формальных языков

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

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

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

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

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

Неформально язык L – это множество цепочек конечной длины в алфавите T.

Механизм порождения позволяет описать языки с помощью системы правил, называемой грамматикой, которая представляет собой наиболее распространенный класс описаний языков.

При описании грамматики необходимо определить алфавита языка, который задается как набор допустимых – терминальных символов (терминалов). Затем необходимо определить набор правил вывода вида α→β, в соответствии с которыми строятся цепочки (предложения) языка. В левой и правой частях правил могут встречаться специальные – нетерминальные символы (нетерминалы), которые в процессе вывода заменяются с помощью соответствующих правил до полной замены на соответствующие терминалы. Кроме того, грамматика должна включать в себя начальный символ(аксиому), с которого начинается получение любого предложения языка.

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

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

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

Конечное множество символов, неделимых в данном рассмотрении, называется алфавитом (словарем), а символы, входящие во множество, называются буквами алфавита.

Например, алфавит A = {a, b, c, +,!} содержит 5 букв;

алфавит B = {00, 01, 10, 11} одержит 4 буквы, каждая из которых состоит из двух символов.

Конечная последовательность символов (букв) алфавита называется цепочкой (словом) в этом алфавите.

Пустая цепочка – это цепочка, которая не содержит ни одного символа (для обозначения используется символы ε или $).

Длина цепочки (слова) – число символов (букв), входящих в цепочку (слово).

Например, слово a=ab+!c в алфавите A имеет длину l(a) = 5 или | а |=5;

слово b=00110010 в алфавите B имеет длину l(b) = 4;

если α = abcdefg, то длина α равна 7 — l(α)=7 или | α|=7;

длина ε равна 0 — l(ε)=0 или |ε|=0.

Конкатенация (сцепление) цепочек – это цепочка αβ, если α и β – цепочки.

Если α = ab и β = cd, то αβ = abcd

Для любой цепочки α всегда αε = εα = α.

Обращение (реверс) цепочки α – это цепочка α^R, символы которой записаны в обратном порядке.

Если α = abcdef, то α^R = fedcba

Для пустой цепочки: ε = ε^R.

Cтепень цепочки α – это конкатенация n цепочек α:

α⁰ = ε;

αⁿ = αα^n-1 = α^n-1α

Дата добавления: 2014-01-11