Определение разбора

Мы говорим, что для некоторой КС-грамматики цепочка разобрана, или проанализирована, если известно одно (или, быть может, все) из ее деревьев выводов. При трансляции такое дерево можно «физически» построить в памяти машины, но вероятнее, что будет использован какой-нибудь более искусный способ представления. Прослеживая шаг за шагом работу синтаксического анализатора, можно получить дерево разбора, хотя связь между этими процессами едва ли сразу очевидна.

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

Определение: Пусть дана КС-грамматика и в этой грамматике правила пронумерованы целыми числами . Пусть . Тогда

1. левым разбором цепочки называется последовательность правил, примененных при левом выводе цепочки из ;

2. правым разбором цепочки называется обращение последовательности правил, примененных при правом выводе цепочки из .

Эти разборы можно представить в виде последовательности номеров из множества .

Пример:

Рассмотрим грамматику с такой нумерацией правил:

1.

2.

3.

4.

5.

6. .

Требуется построить левый и правый разбор цепочки .

Решение:

Левый разбор

.

Правый разбор

.

Дата добавления: 2014-01-07