Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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




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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

T1+T2+…+Tn

 

Ti – это формула вида F1i*F2i*…*Fmi

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

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

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 – процедура вычисления значения формулы, содержащей операции типа сложения

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

F1*F2*…* Fn

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

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

T1+T2+…+ Tn

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




Поделиться с друзьями:


Дата добавления: 2014-01-11; Просмотров: 1127; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.016 сек.