Нисходящие анализаторы

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

Восходящий и нисходящий синтаксический анализ

Алгоритм получения обратной польской записи.

Прямые методы трансляции

VI. Основы построения компиляторов

Просмотр и редактирование индексов

1 Откройте таблицу в режиме конструктора.

2 На панели инструментов нажмите кнопку Индексы.

3 Внесите необходимые изменения в индексы или их свойства. Для удаления индекса удалите соответствующую строку в окне индексов. При этом будет удален только индекс, но не поле.

(продолжение)

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

Известно несколько методов получения обратной польской записи. Один из наиболее эффективных методов предложен в 1960 г. голландским ученым Е. В. Дейкстрой.

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

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

Для любой контекстно-свободной грамматики может быть построен анализатор, сложность которого не превышает O(n³) для входной строки длины n, но в большинстве случаев по заданному языку программирования можно построить такую грамматику, которая позволит сконструировать и более быстрый анализатор.

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

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

Выход синтаксического анализатора – это дерево разбора и таблицы, например, таблица идентификаторов и таблица типов, которые являются входом для следующего просмотра компилятора (например, просмотр, осуществляющий контроль типов).

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

Большинство известных методов анализа принадлежат одному из двух классов, один из которых объединяет нисходящие (top-down) алгоритмы, а другой – восходящие (bottom-up) алгоритмы. Происхождение этих терминов связано с тем, каким образом строятся узлы синтаксического дерева: либо от корня (аксиомы грамматики) к листьям (терминальным символам), либо от листьев к корню.

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

· они могут быть проанализированы без возвратов;

· первая буква L означает, что просматриваем входную цепочку слева направо (left-to-right scan);

· вторая буква L означает, что строится левый вывод цепочки (leftmost derivation).

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

Кроме того, LL-грамматики легко обобщаются: грамматики, не являющиеся LL-грамматиками, обычно могут быть проанализированы методом рекурсивного спуска с возвратами.

9.1.1. Метод рекурсивного спуска(recursive descent method) — один из наиболее простых методов нисходящего синтаксического анализа.

Рассмотрим задачу вычисления значений арифметических формул, состоящих из целочисленных значений, бинарных операций сложения (+), вычитания (–), умножения (*), деления нацело (/) и круглых скобок.

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

Операции + и – называются операциями типа сложения, а операции * и / – операциями типа умножения. Круглые скобки используются для изменения стандартного порядка выполнения операций.

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

T₁+T₂+…+T_n

T_i – это формула вида F_1i*F_2i*…*F_mi

F_ji – это либо число, либо произвольная формула, заключенная в круглые скобки.

Процесс вычисления значения формулы можно представить следующим образом: вначале вычисляется F₁₁; далее выясняется, какая операция следует за F₁₁: если это – операция типа умножения, то, зная ее левый операнд, вычисляется правый операнд и выполняется операция – получаем левый операнд для возможных следующих операций типа умножения; когда закончится вычисление формулы F₁*F₂*…*F_n, то, возможно, далее следует операция типа сложения, и процесс вычисления такой формулы будет аналогичен уже описанному процессу.

9.1.2. Классы формул:

· простейшие формулы: числа и произвольные формулы, заключенные в круглые скобки, например, 354, (17+3–18);

· формулы, содержащие операции типа умножения, т. е. умножение и деление, например, 18*2*(35+2)*7;

· формулы, содержащие операции типа сложения, т. е. сложение и вычитание, например, 18*2*(35+2)*7+354+ (17+3-18)*(12–7).

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

Expression (Term (Factor ()))

Factor – процедура вычисления простейшей формулы, являющейся либо числом, либо произвольной формулой, заключенной в круглые скобки

Term – процедура вычисления значения формулы, содержащей операции типа умножения

Expression – процедура вычисления значения формулы, содержащей операции типа сложения

Формула, содержащая операции типа умножения:

F₁*F₂*…* F_n

Обрабатывать такие формулы может процедура Term, параметром которой является целочисленное значение, представляющее левый операнд формулы F₁*F₂, т. е. F₁. Для того, чтобы вычислить значение такой формулы, необходимо выбрать ее правый операнд, который может быть простейшей формулой, а затем выполнить операцию.

Формула, содержащая операции типа сложения:

T₁+T₂+…+ T_n

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

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