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

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

Вторая фаза компилятора — синтаксический анализ или разбор (parsing). Ана­лизатор использует первые компоненты токенов, полученных при лексическом анализе, для создания древовидного промежуточного представления, которое опи­сывает грамматическую структуру потока токенов. Типичным представлением яв­ляется синтаксическое дерево, в котором каждый внутренний узел представляет операцию, а дочерние узлы — аргументы этой операции. Синтаксическое дере­во для потока токенов (1.2)показано на выходе синтаксического анализатора на рис. 1.7.

Технически говоря, для лексемы 60 мы должны создать токен наподобие (number, 4), где указывает на запись таблицы символов для внутреннего представления целого числа 60.

Это дерево указывает порядок, в котором выполняются операции в присваи­вании

position = initial + rate * 60

Дерево имеет внутренний узел, помеченный *, левым дочерним узлом которого является (id, 3), а правым — 60. Узел (id, 3) представляет идентификатор rate. Узел, помеченный *, явно указывает, что сначала мы должны умножить значение rate на 60. Узел, помеченный +, указывает, что мы должны прибавить результат умножения к значению initial. Корень дерева с меткой = говорит о том, что следует присвоить результат этого сложения в позиции памяти, отведенной иден­тификатору position. Порядок операций согласуется с обычными арифметиче­скими правилами, которые говорят о том, что умножение имеет более высокий приоритет, чем сложение, и должно быть выполнено до сложения.

Последующие фазы компилятора используют грамматическую структуру, ко­торая помогает проанализировать исходную и сгенерировать целевую программу. В главе 4 мы будем использовать контекстно-свободные грамматики для опреде­ления грамматической структуры языков программирования и рассмотрим алго­ритмы автоматического построения эффективных синтаксических анализаторов для определенных классов грамматик. Из глав 2 и 5 вы узнаете, что синтаксиче­ски управляемые определения могут помочь уточнить трансляцию конструкций языка программирования.

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

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

Важной частью семантического анализа является проверка типов, когда ком­пилятор проверяет, имеет ли каждый оператор операнды соответствующего типа. Например, многие определения языков программирования требуют, чтобы ин­декс массива был целым числом; компилятор должен сообщить об ошибке, если в качестве индекса массива используется число с плавающей точкой.

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

Такое приведение показано на рис. 1.7. Предположим, что position, initial и rate были объявлены как числа с плавающей точкой и что лексема 60 образует целое число. Проверка типов в семантическом анализаторе на рис. 1.7 определяет, что оператор * применяется к числу с плавающей точкой rate и це­лому числу 60. В этом случае целое число может быть преобразовано в число с плавающей точкой. Обратите внимание, что на рис. 1.7 в синтаксическом дере­ве, полученном на выходе семантического анализатора, имеется дополнительный узел для оператора inttofloat, который явным образом преобразует свой целый аргумент в число с плавающей точкой.