Изменение направления рекурсии

Для построения распознавателей в правилах грамматики не должно быть левосторонней рекурсии, т.е. правил вида A -> Ax. Пусть в исходной грамматике есть следующее правило: A -> Ax1¦ Ax2¦...¦Axk¦y1¦y2¦....¦ys (знак ¦ означает "или", т.е. в этом правиле объединено несколько правил с одинаковыми левыми частями; xi,yi цепочки терминалов и нетерминалов и yi не начинаются с А). Исходная грамматика не содержит нетерминала В. Тогда возможна эквивалентная замена такого составного правила на два не содержащих левосторонней рекурсии:

A -> y1¦y2¦....¦ys¦y1B¦y2B¦....¦ysB

B -> x1¦x2¦....¦xk¦x1B¦x2B¦....¦xkB

Пример: Пусть в исходной грамматике G имеется правило с левосторонней рекурсией A -> Abc ¦ b. Устраним левостороннюю рекурсию.

Введем обозначения: х1=bc; y1=b. После замены получим:

A -> b ¦ bB;

B -> bc ¦ bcB.

Тема № 8 Построение распознавателей для грамматик

План

8.1 Построение КА для распознания автоматных грамматик.

8.2 Построение КА-распознавателей для праволинейных грамматик

8.3 Построение МП-распознавателей для S-грамматик

8.4 Построение МП-распознавателей для q-грамматик.

8.5 Задачи преобразование грамматик и построение МП-распознавателей................................

Построение конечных автоматов для распознания регулярных множеств, особенно таких, для распознания которых необходимо построение МП-автоматов, процесс творческий и плохо поддающийся формализации. Такие задачи значительно упрощаются и формализуются, если удается построить грамматики, порождающие такие множества. Рассмотрим ряд частных случаев построения автоматов-распознавателей для гамматик второго и третьего типов.