Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 33 стр.

UptoLike

Составители: 

4.5.5. Удаление правил с терминальной правой частью
Пусть в грамматике G имеется с терминальной правой частью A→β, где β V
*
T
. Тогда
любой вывод с использованием этого правила имеет вид: S
*
xAy xβy. Здесь
нетерминал А в сентенциальной форме xAy появился на предыдущем шаге вывода B uAv.
Если в это правило вместо А подставить β, получим правило B uβv. Тогда длина вывода
некоторой цепочки сократится на один шаг. Следовательно, для того чтобы удалить
терминальное правило грамматики A→β, необходимо учесть следующие правила:
а) если для нетерминала А больше нет правил, тогда во всех правых частях А заменяется
на β;
б) если для нетерминала А есть другие правила, тогда добавляются новые правила, в
которых А заменяется на β.
Пример. Пусть дана КС-грамматика G:
S aSb | bAa | B; A ABa | b | ε; B ab | ba.
Удалим правила для нетерминала В. Тогда эквивалентная грамматика G
1
будет включать
следующие правила:
S aSb | bAa | ab | ba; A Aaba | Abaa| b | ε.
4.5.6. Построение эквивалентной праворекурсивной КС-грамматики
Некоторые специальные методы грамматического разбора неприменимы к
леворекурсивным или праворекурсивным грамматикам, поэтому рассмотрим устранение
левой или правой рекурсии. В общем случае избавиться от рекурсии в правилах грамматики
невозможно, т.к. бесконечные языки порождаются грамматиками с конечным числом правил
только благодаря рекурсии. Поэтому можно говорить лишь о преобразовании одного вида
рекурсии в другой. Рассмотрим, как для любой леворекурсивной КС-грамматики построить
эквивалентную праворекурсивную КС-грамматику.
Пусть нетерминал А - леворекурсивен, т.е. для него имеются правила следующего вида:
A Ax
1
| Ax
2
| . . . | Ax
p
| w
1
| . . . | w
k
, где x
i
и w
j
- цепочки над множеством V
T
V
N
.
Введем дополнительные нетерминалы B и D и указанные правила заменим на
эквивалентные им:
A AB
| D;
B x
1
| x
2
| . . . | x
p
;
D w
1
| w
2
| . . . | w
k
.
В результате замены получим вывод, который имеет вид:
A AB ABB ABBB . . . AB
*
DB
*
.
Таким образом, для нетерминала А можно определить эквивалентные правила:
A DK;
K BK | ε.
Выполняя подстановку D и B в эти правила, получим следующие праворекурсивные
правила:
A w
1
K| w
2
K | . . . | w
k
K;
K x
1
K
| x
2
K
| . . . | x
p
K | ε.
Пример. Пусть задана грамматика G со следующими правилами вывода: S Sa | ba.
Требуется построить эквивалентную ей праворекурсивную грамматику.
Для решения задачи воспользуемся рассмотренным выше алгоритмом. В исходной
грамматике один леворекурсивный нетерминал S. Построим для него вывод:
S SB | D;
B a; D ba. Вывод из S имеет вид: S SB SBB . . . DB
*
.
Запишем эквивалентные правила для S: