Пред.Страница  След.Страница   Раздел   Содержание

1.3.6. Синтаксический разбор

Вывод цепочки с помощью правил грамматики может быть задан не только в виде синтаксического дерева. Если пронумеровать правила грамматики, то последовательность номеров используемых правил также задает вывод.

Например, в следующей грамматике
Г_{1. 9}:
V_т = { i, +, * , (, ) }, V_a = {<E>, <T>, <P>}
R ={ (1) <E> ®<E> +<T>,
(2) <E> ®<T>,
(3) <T> ®<T> *<P>,
(4) <T> ®<P>,
(5) <P> ®(E),
(6) <P> ® i },
правила которой пронумерованы, вывод
 
<E> Ю <E> +<T> Ю <T> +<T> Ю <T> *<P> +<T> Ю
<P> *<P> +<T> Ю i * <P> +<T> Ю i * i +<T> Ю
i * i +<P> Ю i * i + i
 
имеет синтаксический разбор [1,2,3,4,6,6,4,6].

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

Например, вывод цепочки i + i в грамматике Г_{1. 9} может быть получен десятью различными способами.
 

Пред.Страница  След.Страница   Раздел   Содержание