Рис1. Частичное синтаксическое дерево для программы CopyChar

В отличие от обычных деревьев, синтаксические деревья растут сверху вниз. В данном случае, корнем дерева является элемент < программа>, конечные узлы дерева называются листьями.

Данное дерево не показывает нам подробности строения < идентификатора>, но результат его построения показывается присоединенным пунктирной линией, сигнализируя о том, что результаты были сокращены.

Проходя по листьям дерева слева направо, мы получаем следующее:

PROGRAM CopyChar(INPUT, OUTPUT); < блок>.

Это законченная программа, за исключением элемента < блок>, синтаксическое правило которого еще не было дано и поэтому не может быть заполнено.

На рисунке 2 показано полное построение < идентификатора> Copy1

Рис. 2. Синтаксическое дерево для < идентификатора> Copy1

Когда синтаксическое дерево построено с использование всех необходимых правил синтаксиса, листья этого дерева должны явно присутствовать в программе. Когда мы проходим слева направо по листьям дерева, вставляя где положено пробелы, они как бы проговаривают нам элемент программы, название которого находится в корне дерева. Например, часть рисунка 1, изображенная на рисунке 3, показывает, что дерево с корнем < заголовок>, может построить следующее:

PROGRAM CopyChar(INPUT, OUTPUT)

Рис 3. Синтаксическое дерево < заголовок>

Иными словами

PROGRAM CopyChar (INPUT, OUTPUT)

является < заголовком>. Когда мы говорим о < заголовке>, мы имеем в виду эту строку. Но обычно значение идентификатора не имеет большого значения, и ссылка на < заголовок> обозначает любую строку, которая может быть таким образом построена. В данном случае единственная часть дерева, которая может меняться – это < идентификатор>.

Синтаксические деревья могут быть использованы для доказательства корректности любой последовательности символов являющейся элементом программы. Начиная с синтаксического правила, имеющего этот элемент слева от знака:: =, дерево строится по этому и другим синтаксическим правилам. Синтаксис последовательности символов считается корректным, если он формируется из листьев дерева путем вставки соответствующих пробелов. Основное правило вставки идентификаторов гласит:

1. Пробелы не могут быть помещены внутрь < идентификатора>

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

3. Там, где может быть помещен один пробел, там может быть помещено любое их количество.

4. Разрыв строки может быть помещен в любом месте, где может быть помещен пробел. Однако разрыв строки не заменяет пробел в пункте 2.

Например, дерево < заголовок> рассмотренное выше, показывает, что

PROGRAM CopyChar (INPUT, OUTPUT)

является < заголовком>, как и

PROGRAM

CopyChar

(INPUT, OUTPUT)

показывая различные случаи расстановки пробелов и разрывов строк. В некоторых Паскаль-машинах разрыв строки игнорируется. В других – он заменяет пробел. Правило 4 является консервативным и безопасным при любых обстоятельствах.

В качестве проверки правильного построения синтаксического дера\ева, номера синтаксических правил, используемые при построении, могут быть приписаны к каждому узлу, как показано на рисунке 4 для < идентификатора> B4U

Рис 4. Синтаксическое дерево для < идентификатора> B4U

По мере накопления опыта доказательство корректности синтаксиса станет для вас простым. Вы станете делать это на полном автоматизме. Как только вы прочувствуете идею, очень редко вам придется рисовать синтаксические деревья.