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

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

Они используют модификации алгоритма с подбором альтернатив. При их создании применяется метод, который позволяет однозначно выбрать одну и только одну альтернативу на каждом шаге работы МП-автомата (шаг «выброс» в этом автомате всегда выполняется однозначно).

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

Восходящие распознаватели используют модификации алгоритма «сдвиг-свертка» (или «перенос-свертка», что то же самое). При их создании применяются методы, которые позволяют однозначно выбрать между выполнением «сдвига» («переноса») или «свертки» на каждом шаге работы расширенного МП-автомата, а при выполнении свертки однозначно выбрать правило, по которому будет производиться свертка. Алгоритм «сдвиг-свертка».

Задаётся формулой ${\displaystyle L=\{w\in \Sigma ^{*}|w=w^{R}\}}$

• Терминалы: буквы алфавита ${\displaystyle \Sigma }$;
• Нетерминал: ${\displaystyle S}$;
• Продукции: ${\displaystyle S\rightarrow \alpha S\alpha \,|\,\alpha \,|\,\varepsilon ,\alpha \in \Sigma }$
• Начальный нетерминал — ${\displaystyle S}$.

• Терминалы: ${\displaystyle (}$ и ${\displaystyle )}$;
• нетерминал: ${\displaystyle S}$;
• продукции: ${\displaystyle S\rightarrow (S)\mid \varepsilon }$;
• начальный нетерминал — ${\displaystyle S}$.

Этой грамматикой задаётся язык вложенных скобок ${\displaystyle \{\left(^{n}\right)^{n}\mid n\geq 0\}}$.

• Терминалы: '+', '-', '*', '/', '(', ')', 'x'
• нетерминалы: <выражение>, <слагаемое>, <множитель>
• продукции:

<выражение> → <выражение> + <слагаемое>,
<выражение> → <выражение> - <слагаемое>,
<выражение> → <слагаемое>,
<слагаемое> → <слагаемое> * <множитель>,
<слагаемое> → <слагаемое> / <множитель>,
<слагаемое> → <множитель>,
<множитель> → ( <выражение> ),
<множитель> → x,

• начальный нетерминал: <выражение>.

Этой грамматикой задаётся арифметическое выражение, содержащее простейшие арифметические действия над переменной x. Если заменить терминал 'x' на нетерминал <число>, то получится грамматика, задающая арифметическое выражение, состоящее из операций сложения, вычитания, умножения и деления над целыми числами.