Пред.Страница След.Страница Раздел Содержание
1.3.6. Синтаксический разбор
Вывод цепочки с помощью правил грамматики может быть задан не только в виде синтаксического дерева. Если пронумеровать правила грамматики, то последовательность номеров используемых правил также задает вывод.
Определение. Последовательность номеров правил грамматики Г, применение которых позволяет построить вывод рассматриваемой цепочки s из начального символа грамматики, называется синтаксическим разбором s. |
Например, в следующей грамматике
Г1. 9:
Vт = { i, +, * , (, ) }, Va = {<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
может быть получен десятью различными способами.