4.Лексический анализ. Основные понятия.(50)

Лексический анализ выполняет формирование символов языка на основе так называемых лексем , к числу которых принадлежат следующие элементы языка.

1) Ключевые слова языка (if, then, else, while, do, var, integer и т.п).

2) Идентификаторы ( custom, x1 ,y1 , name и т.п)

3) Константы (14 , 13.06 , 'abc' и т.п.).

4) Последовательности знаков (<= , <> ,>=, и т.п.).

Знаки пунктуации ( { } [ ] … , ; и т.п ).

Лексемы преобразуются в неделимые символы языка , которые в дальнейшем используются на фазах синтаксического и семантического анализов. Кроме этого лексический анализатор осуществляет обработку пробелов, удаление комментариев и некоторые другие действия , необходимые для подготовки текста программы к последующим фазам. При формировании символов языка лексический анализатор не учитывает их последовательность , то есть как правило не работает с контекстом . Например, если в программе на языке PASCAL появится некорректная конструкция вида if b while P вместо if b then P , лексический анализатор не обнаружит никакой ошибки .

Для фазы лексического анализа наиболее удобным средством описания символов являются регулярные выражения. Например , идентификатор можно представить в виде буква(буква | цифра)^* .

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

ключевые слова разрешено использовать в качестве идентификаторов;

интерпретация некоторых последовательностей лексем носит контекстно-зависимый характер.

Например, в языке FORTRAN можно использовать конструкцию вида IF(K) =1 , которую можно интерпретировать как присвоение значения K-ому элементу массива с именем IF. Однако распознавание именно такой интерпретации может быть выполнено только по достижению конца строки, поскольку может появиться конструкция IF(K) 1,2,3, интерпретируемая как оператор IF. Другим неудобством языка FORTRAN с точки зрения лексического анализа является возможность использования внутренних пробелов при обозначении идентификаторов. Конструкция DO 7 K=1,5 определяет оператор цикла. В то же время, пока не считан символ запятой , начало строки можно спутать с идентификатором DO 7 K. Для устранения подобных неоднозначностей используют предварительный просмотр текста и приведение к некоторому каноническому виду, который уже лексическим анализатором воспринимается однозначным

образом.

5.Задачи синтаксического анализа. Основные понятия, канонические формы, используемые в синтаксическом анализе (Префиксная и постфиксная записи выражений.) (58)

Первоочередной задачей синтаксического анализа является нахождение порождения (если оно существует) конкретного предложения языка с использованием данной грамматики.

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

Если анализируемое предложение не принадлежит языку, компилятор не должен прекращать свою работу, ограничившись сообщением об ошибке. В этом случае, как правило, компилятор сообщает об ошибке и указывает на последний символ, после которого возникла ошибка. Затем после соответствующей локализации ошибки процесс анализа продолжается. Далее строится синтаксическое дерево, вершина которого соответствует символу предложения, соединяемого с анализируемым предложением через поддеревья, соответствующие продукциям грамматики. Существует несколько подходов к построению синтаксического дерева:

Нисходящий синтаксический анализ (top-down parsing) предусматривает построение синтаксического дерева, начиная с вершины (символа предложения) с развертыванием дерева в направлении предложения языка. Примера язык вида {x ^m y ⁿ |m, n > 0}, определяемый следующими продукциями:

S -> XY X -> xX X -> x Y - >yY Y -> y

Восходящий синтаксический анализ (bottom-up parsing) предусматривает построение синтаксического дерева, начиная с предложения языка, сворачивая его до получения символа предложения. Нисходящий синтаксический анализ обладает большей степенью наглядности , чем восходящий . Однако на практике большее распространение получил восходящий синтаксический анализ, обладающий большей общностью и более совершенным аппаратом инструментальной поддержки . В ряде компиляторов сочетаются оба эти подхода. В отличие от нисходящего, при восходящем синтаксическом анализе этапы порождения определяются в противоположном порядке, то есть:xxxyy=> xxX yy=> xXyy=> Xyy=> XyY=> XY=> S .

Префиксная и постфиксная записи выражений.

Классическим способом представления выражений для анализа перед генерацией кода являются префиксная и постфиксная записи.

Для пояснения рассмотрим выражение вида a+b*c+d/e-f. Такая запись выражения называется инфиксной, что означает расположение

знака бинарной операции между операндами. Интерпретация и соответственно анализ такого выражения в общем случае носит

неоднозначный характер. Для устранения неоднозначности используется приоритет операций. Каждая промежуточная вершина

этого дерева помечена знаком. Анализ основывается на представлении выражения в древовидной форме следующего вида:

-

+ f

+ /

a * d e

b c

Рис. 3.4.4-1. Пример древовидного представления выражения.

соответствующей операции, а дуги, исходящие из данной вершины, ведут к операндам. Теперь, начиная с вершины (сверху вниз)

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

В результате получим выражение вида - + + a * b c / d e f , представляющее префиксную запись. Отличительная особенность

префиксной записи заключается в том, что каждый знак операции предшествует своим операндам. Постфиксная запись получается

"зеркальным отображением " соответствующей префиксной записи. Таким образом, для указанного выше выражения постфиксная запись

имеет вид f e d / c b * a + + -. Отличительной особенностью постфиксной записи является то, что каждый знак операции

записывается после операндов. Постфиксная запись является очень удобной для вычисления выражений, поскольку в ней все знаки

выполняемых операций располагаются в порядке убывания приоритетов.