Обычная форма Грейбаха

На формальном языке теория, контекстно-свободная грамматика находится в нормальной форме Грейбаха (GNF), если правые части всех производственных правил начинаются с терминала символ, за которым могут следовать некоторые переменные. Нестрогая форма допускает одно исключение из этого ограничения формата, позволяющее пустому слову (epsilon, ε) быть членом описываемого языка. Нормальная форма была установлена ​​Шейлой Грейбах и носит ее имя.

Точнее, контекстно-свободная грамматика находится в нормальной форме Грейбаха, если все продукционные правила имеют вид:

$A\; \to \; a\; A\; 1\; A\; 2\; \cdots \; A\; n\; \{\backslash \; displaystyle\; A\; \backslash \; to\; aA\_\; \{\; 1\}\; A\_\; \{2\}\; \backslash \; cdots\; A\_\; \{n\}\}$

или

$S\; \to \; \epsilon \; \{\backslash \; displaystyle\; S\; \backslash \; to\; \backslash \; varepsilon\}$

, где $A\; \{\backslash \; displaystyle\; A\}$- это нетерминальный символ, $a\; \{\backslash \; displaystyle\; a\}$- конечный символ, $A\; 1\; A\; 2\dots \; A\; n\; \{\backslash \; displaystyle\; A\_\; \{1\}\; A\_\; \{2\}\; \backslash \; ldots\; A\_\; \{n\}\}$- это (возможно, пустая) последовательность нетерминальных символов, не включая начальный символ, $S\; \{\backslash \; displaystyle\; S\}$- начало символ, а ε - пустое слово.

Обратите внимание, что грамматика не имеет левой рекурсии.

Каждая контекстно-свободная грамматика может быть преобразована в эквивалентную грамматику в нормальной форме Грейбаха. Существуют различные конструкции. Некоторые не допускают вторую форму правила и не могут преобразовывать контекстно-свободные грамматики, которые могут генерировать пустое слово. Для одной такой конструкции размер построенной грамматики составляет O (n) в общем случае и O (n), если никакой вывод исходной грамматики не состоит из одного нетерминального символа, где n- размер исходной грамматики. Это преобразование можно использовать для доказательства того, что каждый контекстно-свободный язык может быть принят (недетерминированным) автоматом выталкивания вниз в реальном времени, т. Е. Автомат читает букву из своего вводите каждый шаг.

Учитывая грамматику в GNF и выводимую строку в грамматике с длиной n, любой нисходящий синтаксический анализатор остановится на глубине n.

• Форма Бэкуса-Наура
• нормальная форма Хомского
• нормальная форма Курода

1. ^Хопкрофт, Джон Э.; Ульман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления. Ридинг, Массачусетс: издательство Addison-Wesley Publishing. п. 95. ISBN 0-201-02988-X.
2. ^Грейбах, Шейла (январь 1965 г.). «Новая теорема о нормальной форме для грамматик контекстно-свободных фраз». Журнал ACM. 12 (1). doi : 10.1145 / 321250.321254.
3. ^Блюм, Норберт; Кох, Роберт (1999). «Возвращение к преобразованию нормальной формы Грейбаха». Информация и вычисления. 150 (1): 112–118. CiteSeerX 10.1.1.47.460. doi : 10.1006 / inco.1998.2772.

• Александр Медуна (6 декабря 2012 г.). Автоматы и языки: теория и приложения. Springer Science Business Media. ISBN 978-1-4471-0501-5.
• Дьёрдь Э. Ревес (17 марта 2015 г.). Введение в формальные языки. Курьерская корпорация. ISBN 978-0-486-16937-8.