Синтаксический анализ

Иерархический анализ называется разбором (parsing), или синтаксическим анализом, который включает группирование токенов исходной программы в грамматические фра­зы, используемые компилятором для синтеза вывода. Обычно грамматические фразы ис­ходной программы представляются в виде дерева, пример которого показан на рис. 1.4.

В выражении initial+rate*60 фраза rate*60 является логической единицей, поскольку обычные соглашения о приоритете арифметических операций гласят, что ум­ножение выполняется до сложения. Поскольку после выражения initial+rate следу­ет знак умножения *, само по себе оно не группируется в единую фразу на рис. 1.4.

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

1. Любой идентификатор (identifier) есть выражение (expression).

2. Любое число (number) есть выражение (expression).

3. Если expression₁ и expression₂ являются выражениями, то выражениями являются и expression₁ + expression₂

expression₁ * expression₂ (expression₁).

Инструкция присвоения

: =

Идентификатор

position

rate

initial

Выражение

Число

Выражение

Выражение

Идентификатор

Идентификатор

Выражение

Выражение

*

+

Рис. 1.4. Дерево разбора для выражения position: =initial+rate*60

Правила (1) и (2) являются базовыми (нерекурсивными), в то время как (3) определя­ет выражения с помощью операторов, применяемых к другим выражениям. Согласно правилу (1), initial и rate представляют собой выражения; правило (2) гласит, что 60 также является выражением. Таким образом, из (3) можно сначала сделать вывод, что rate*60 — выражение, а затем — что выражением является и initial+rate*60.

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

1. Если identifier₁ является идентификатором, a expression₂ — выражением, то identifier₁:= expression₂

есть инструкция.

2. Если expression₁ — выражение, a statement₂ — инструкция, то

while ( expression₁ ) do statement₂

if ( expression₁ ) then statement₂

являются инструкциями[2].

Разделение анализа на лексический и синтаксический достаточно произвольно. Обычно оно используется для упрощения анализа в целом. Одним из факторов, опреде­ляющих данное разделение, является использование рекурсии в правилах анализа. Лек­сические конструкции не требуют рекурсии, в то время как синтаксические редко обхо­дятся без нее. Контекстно-свободные грамматики представляют собой формализацию рекурсивных правил, используемых при синтаксическом анализе. Данные грамматики рассматриваются в главе 2 и подробно изучаются в главе 4.

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

Однако такое линейное сканирование недостаточно для анализа выражений или ин­струкций. Например, мы не можем проверить соответствие скобок в выражениях или ключевых слов begin и end в инструкциях без наложения некоторой иерархической или вложенной структуры на вводимые данные.

: =

position

+

initial

rate

*

: =

position

+

initial

rate

*

inttoreal

a) б)

Рис. 1.5. Семантический анализ добавляет преобразование из целого числа в действительное

Дерево разбора, показанное на рис. 1.4, описывает синтаксическую структуру посту­пающей информации. Более общее внутреннее представление этой синтаксической струк­туры представлено на рис. 1.5а. Синтаксическое дерево — это "сжатое" дерево разбора, в котором операторы размещены во внутренних узлах, а операнды оператора представлены дочерними ветвями узла, представляющего этот оператор. Построение подобных деревьев (рис. 1.5а) обсуждается в разделе 5.2. В главе 2, "Простой однопроходный компилятор", мы приступим к рассмотрению синтаксически управляемой трансляции (syntax-directed translation), а в главе 5, "Синтаксически управляемая трансляция", изучим ее подробнее. При синтаксически управляемой трансляции для построения вывода компилятор использу­ет иерархическую структуру вводимой информации.

Дата добавления: 2015-11-30