Машинно- независимая оптимизация кода.
Предполагает :
1. Одним из важнейших источников оптимизации кода является удаление общих подвыражений, т.е. подвыражений, которые встречаются в нескольких местах программы и вычисляют одно и то же выражение.
2. Другим источником оптимизации кода является удаление инвариантов цикла. Так называются подвыражения внутри цикла, результирующие значения которых не изменяются внутри цикла при переходе от одной итерации к другой. Поскольку для большинства программ основное время работы приходится на выполнение циклов, экономия времени от подобной оптимизации может быть весьма существенной.
3. Еще один источник оптимизации кода состоит в замене менее эффективных операций на более эффективные.
Синтаксический анализ: задачи, виды, преимущества использования грамматик.
Синт анализатор - цель проверка входной строки на соответстиве грамматики.
Мн-во терм символов - (ab+-12 и тд)
набор нетерм символов - A B C
продукции - A->Bc|Ad
начальный нетерминал
Лекс А->Синт А->Дерево разбора->Семант А
_____________________________________________________________
Синтаксическая диаграмма графически изображает структуру конструкций алгоритмического языка. Отдельными элементами диаграммы могут быть основные символы или понятие языка. Из каждого элемента выходит одна или несколько стрелок, указывающих на те элементы, которые могут непосредственно следовать за данным элементом (то есть стрелки указывают возможных преемников каждого из элементов диаграммы). Стрелка, не выходящая из какого-либо элемента, является входом в диаграмму, а стрелка, не ведущая к какому-либо элементу, означает выход из диаграммы, то есть конец синтаксического определения. Чтобы легче было отличить в диаграммах основные символы (терминальные) от понятий (нетерминальных символов) их выделяют каким-либо способом, например, заключают основные символы в кружки или овалы, а понятия – в прямоугольники. Однако, это не совсем удобно при подготовке печатных документов.
Поэтому сохраним для понятий символику БНФ, то есть понятия будут заключаться в угловые скобки, а терминальные символы будут без скобок.
Например, определение идентификатора в БНФ имеет вид:
1.<идентификатор>::=<буква><продолжение идентификатора>
2. <продолжение идентификатора> ::= <буква><продолжение идентификатора> |
<цифра><продолжение идентификатора> |
<пусто>
Синтаксическая диаграмма для этого определения будет выглядеть, как показано на Рисунке 2.1.
Рисунок 2.1 Синтаксическая диаграмма идентификатора
Достоинством синтаксических диаграмм является наглядность и простота для понимания. Кроме того, от синтаксической диаграммы просто перейти к блок-схеме алгоритма грамматического разбора.
Для данного примера диаграммы блок-схема приведена на Рисунке 2.2. (указанные в блок-схеме подпрограммы вырабатывают признак U=True, если символ входной строки соответствует проверяемому понятию, и U=False – в противном случае). Подпрограммы «буква» и «цифра» выполняют соответственно проверку очередного символа входной строки на принадлежность множеству букв и цифр.
Общим недостатком формальных методов является отсутствие средств для задания смысловых правил синтаксиса языка. Примером такого вида правил является требование, чтобы все объекты в PASCAL-программе были описаны. Однако при переходе к алгоритмическому заданию синтаксиса (например, в виде блок-схемы) эта трудность преодолима. Пусть в рассмотренном примере требуется, чтобы количество символов в идентификаторе не превышало 5. Если обозначить счетчик символов как COUNT, то можно изменить приведенную на Рисунке 2.2 блок-схему так, как показано на Рисунке 2.3.
Задача синтаксического анализа упрощается, если программа предварительно обработана лексическим анализатором и поступает на вход синтаксического анализатора в форме последовательности кодов лексем. Тогда любой модуль блок-схемы, соответствующий элементу диаграммы, в начале по коду таблицы определяет допустимость данного вида лексем в структуре предложения и если допустим, тогда по спецификатору проверяется допустимость лексемы.