Контекстно-свободные грамматики являются формальной системой, описывающей язык, определяя, каким образом любые допустимые тексты могут быть выведены из известного символа, называемого аксиомой, символом предложения. Он состоит из целого ряда продукций, каждая из которых утверждает, что данный символ может быть заменен последовательностью символов. Для получения допустимого текста, грамматика используется как данные по следующему алгоритму :
1. Пусть текст расположен отдельно от аксиомы.
2. Если нет продукций, согласно которым в настоящее время символ текста может быть заменен некоторой последовательностью символов, тогда остановиться.3. Изменить текст, заменив один из его символов в последовательности согласно некоторым продукциям.
4. Перейти к шагу (2).
Когда алгоритм заканчивается, текст является допустимым текстом языка. Структура фразы текста – это иерархия последовательностей, используемых в его словообразовании.
Каждая продукция контекстно-свободной грамматики ,состоящая из символа будет заменена соответствующей ему последовательностью. Правила замены выглядят следующим образом:
Назначение : Переменная ': =' Выражение.
СписокУтверждений: .
Утверждение : "если" Выражение ", тогда" Заявление "иначе" Заявление.
Первая продукция утверждает, что символ Назначение можно заменить на последовательность состоит из трех символов переменной , ': =' и выражение. Любой символ из СписокУтверждений может быть заменен пустой последовательностью согласно второй продукции.В третьей продукции, вы увидите, что новые линии можно использовать в качестве разделителей в описании продукции..Это обозначение обычно называют формы Бэкоса-Наура, или просто БНФ.
Символы, которые должны быть заменены называются синтермами, и они всегда представлены идентификаторами.(Идентификатор - это последовательность букв и цифр, первый симвод последовательности - буква.) Каждый синтерм расположен перед двоеточием по крайней мере в одной продукции. Аксиомы является синтермами, расположенными перед двоеточием в только одонй продукции, и не появляются между двоеточием и последовательностью в любой продукции. Должен быть только 1 синтерм, удовлетворяющий требованиям для аксиомы.
Символы, которые не могут быть заменены называются терминалы, и могут быть представлены идентификаторами или литералами. (Литерал - это последовательность символов, ограниченной апострофами ( '). Синтерм может располагаться перед двоеточием в любой продукции