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

Date: 2015-10-07; view: 393.

1. Способы определения языков(продолжение)

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

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

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