Перечитываю PT:APG

[thesz]

Parsing Techniques: A Practical Guide

Там есть применение регулярных грамматик к разбору контекстно-свободных грамматик, в районе страницы 106.

И, надо отметить, авторы не утруждают себя сколько-нибудь сложными подходами. Если у нас есть что-то типа L ::= Q L | ε, то вот вам регулярная часть. Алгоритмов сведения произвольных грамматик к виду выше

Comments

[ivvl]

> Алгоритмов сведения произвольных грамматик к виду выше я, что-то, не увидел.

А они сводятся? Выше задана грамматика, которая считывает из потока термы Q, пока они не закончатся. Тупо конечный автомат без стека. Он может задать только регулярный язык (читай, регулярная грамматика), более сложные грамматики идут лесом.

[thesz]

Страница 106 книжки выше.

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

Те же выражения в C или Паскале:

expr ::= sum
sum ::= ('+'|'-'|) prod (('+'|'-')prod)*
prod ::= factor (('*'|'/') factor)*
factor ::= variable | ('(' expr ')')

expr контекстно-свободная из-за expr внутри скобок, sum и prod это её регулярные части.

Регулярная часть грамматики может обрабатывать упрощённым способом в обычном последовательном разборе и должна обрабатываться специальным образом при параллельном разборе. При параллельном разборе с помощью CYK или алгоритма Валианта (любой табличный вариант алгоритма разбора), обычный подход даст квадратичное распухание промежуточных данных в регулярных частых грамматик и сведёт на нет всю параллельность.

[ivvl]

> обычный подход даст квадратичное распухание промежуточных данных в регулярных частых грамматик

Ещё бросился в глаза этот фрагмент, кэширование промежуточных термов крайне важно, но с этим проблемы. Можно рекомендовать разве что hash consing.