Расширения грамматики

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

Нотации

Самая простая запись здесь называется канонической. Правило определяется нетерминальным символом в левой части и последовательностью символов в правой. В качестве разделителя используют стрелку.

S -> a B C d
B -> b

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

Backus-Naur form

Форма Бэкуса-Наура (Backus-Naur form, BNF) — это нотация для описания синтаксиса формального языка.

По сравнению с канонической, она имеет ряд удобных расширений:

• возможность задать альтернативы (оператор "или"), для этого используется символ |
• для терминальных символов с постоянной лексемой можно указать значение этой лексемы в кавычках

В качестве разделителя левой и правой части правила используется ::=.

expr ::= expr '+' expr | number

Extended Backus-Naur form

Расширенная форма Бэкуса-Наура (EBNF) добавляет ещё ряд новых возможностей для описания синтаксиса.

Запись	Значение
=	разделитель левой и правой части
,	конкатенация
;	окончание правила
|	альтернатива
(...)	группировка
[...]	опциональная часть
{...}	повторение 0 или более раз
'...' или "..."	терминальная строка
(* ... *)	комментарий

Пример:

parameters = '(' , parameter , { ',' , parameter } , [ ',' ], ')' ;
parameter  = expression | Identifier , '=' , expression ;

Приведение к каноничному виду

TODO.

Альтернативы

$$\begin{align*} A \to B | C \rArr \begin{cases} A \to B \\ A \to C \space\space \end{cases} \\ A \to B(x | y) \rArr \begin{cases} A \to Bx \\ A \to By \end{cases} \end{align*}$$

Квантификаторы

• $A^?$ — 0 или одно повторение
• $A^*$ — 0 или более повторений
• $A^+$ — 1 или более повторений

$$\begin{align*} A \to B^? \rArr \begin{cases} A \to B \space\space\space \\ A \to \epsilon \end{cases} \\ A \to B^* \rArr \begin{cases} A \to BA \\ A \to \epsilon \end{cases} \\ A \to B^+ \rArr \begin{cases} A \to BA \\ A \to B \end{cases} \end{align*}$$

Часто можно избавиться от пустых строк:

$$\begin{align*} A \to B^? \gamma \rArr \begin{cases} A \to B \gamma \space\space \\ A \to \gamma \end{cases} \\ A \to \gamma C^* \rArr \begin{cases} A \to \gamma \\ A \to \gamma C^+ \end{cases} \end{align*}$$

Пример

$$S \to n(+ n)^* \rArr \begin{cases} S \to n \\ S \to n(+n)^+ \end{cases} \rArr \\ \rArr \begin{cases} S \to n \\ S \to nG \\ G \to (+n)^+ \end{cases} \rArr \begin{cases} S \to n \\ S \to nG \\ G \to +nG \\ G \to +n \end{cases}$$