Контекстно-свободные грамматики и языки

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

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

Левосторонние и правосторонние выводы в КС-грамматике

Рассмотрим (однозначную) грамматику G₈, задающую синтаксис арифметических выражений.

G₈: E®T| E+T | E-T

T® M | T*M | T/M

M®a | b | c | (Е)

Построим два различных вывода цепочки а + b*св этой грамматике.

В первом случае, если сентенциальная форма содержит более одного нетерминала, будем выполнять подстановку (замену нетерминала правой частью одного из правил) для самого левого нетерминала этой сентенциальной формы:

ЕÞЕ+ТÞТ+ТÞМ+ТÞа+ТÞа+T*МÞа+М*МÞ

а + b*МÞа + b*с.

Такой вывод называется левосторонним.

Аналогично, вывод, в ходе которого замене всегда подвергается самый правый нетерминал сентенциальной формы, называется правосторонним. Для цепочки а+b*с в грамматике G₈ он будет таким:

ЕÞЕ+ ТÞ Е + T*М ÞЕ + Т*с Þ Е + М*с Þ

Е + b*с Þ T+ b*с Þ М + b*с Þ а + b*с.

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

Для цепочки а + b*с в грамматике G₈ и левосторонний, и правосторонний выводы строятся однозначно. Это же справедливо и для любой другой цепочки, порождаемой G₈.

КС-грамматика называется однозначной, если для каждого предложения языка, порождаемого этой грамматикой, существует единственный левосторонний вывод.