Синтаксис и семантика языков программирования. Формальные грамматики.

Синтаксис языка программирования – правила образования строк или цепочек символов языка программирования. Их значение или эффект который они дают, называется семантикой.

Формальная грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита.

Словами языка, заданного грамматикой, являются все последовательности терминалов, выводимые (порождаемые) из начального нетерминала по правилам вывода.

Терминал (терминальный символ) — объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»).

Нетерминал (нетерминальный символ) — объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.

Чтобы задать грамматику, требуется задать алфавиты терминалов и нетерминалов, набор правил вывода, а также выделить в множестве нетерминалов начальный.

Итак, грамматика определяется следующими характеристиками:

§ V_T — набор (алфавит) терминальных символов;

§ V_N — набор (алфавит) нетерминальных символов;

§ P — набор правил (продукций) вида: «левая часть» → «правая часть», где «левая часть» – непустая последовательность терминалов и нетерминалов, содержащая хотя бы один нетерминал, «правая часть» – любая последовательность терминалов и нетерминалов, «→» – знак продукции;

§ S — стартовый (начальный) символ из набора нетерминалов.

Множества терминалов и нетерминалов не пересекаются, а их совокупность составляет алфавит языка.

Правила образования строк языка:

1. Начать со стартового нетерминального символа и заменить его строкой, расположенной справа от знака продукции соответствующего правила.

2. Если полученная строка больше не содержит нетерминальных символов, то она принадлежит языку и называется предложением языка.

3. В противном случае заменить один нетерминальный символ строкой, расположенной справа от знака продукции соответствующего правила и перейти к шагу 2.

Эта последовательность шагов для получения строки с использованием продукций называется порождением.

Типы грамматик по иерархии Хомского:

§ Тип 0 — неограниченные.

К типу 0 по классификации Хомского относятся неограниченные грамматики (также известные как грамматики с фразовой структурой). Это — все без исключения формальные грамматики. Для грамматики G(V_T,V_N,P, S), V=V_TUV_N все правила имеют вид:

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

Практического применения в силу своей сложности такие грамматики не имеют.

§ Тип 1 — контекстно-зависимые.

К этому типу относятся контекстно-зависимые (КЗ) грамматики и неукорачивающие грамматики. Для грамматики G(V_T,V_N,P, S), V=V_TUV_N все правила имеют вид:

o αAβ→αγβ, где α, β V^*, γ V⁺, A V_N. Такие грамматики относят к контекстно-зависимым.

o , где α,β V⁺, |α|≤|β|. Такие грамматики относят к неукорачивающим.

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

§ Тип 2 — контекстно-свободные.

К этому типу относятся контекстно-свободные (КС) грамматики. Для грамматики G(V_T,V_N,P, S), V=V_TUV_N все правила имеют вид:

A→β, где β V⁺ (для неукорачивающих КС-грамматик, β V^* для укорачивающих), A V_N. То есть грамматика допускает появление в левой части правила только нетерминального символа.

КС-грамматики широко применяются для описания синтаксиса компьютерных языков.

§ Тип 3 — регулярные.

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

Все регулярные грамматики могут быть разделены на два эквивалентных класса, которые для грамматики вида III будут иметь правила следующего вида:

o A→Bγ или A→γ, где γ , A, B V_N (для леволинейных грамматик).

o A→γB; или A→γ, где γ , A, B V_N (для праволинейных грамматик).

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