20616

Фазы трансляции

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

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

Русский

2013-07-31

328 KB

1 чел.

Лекция № 1.

Фазы трансляции.

  1.  Написание кода
  2.  Обработка препроцессором
  3.  Модель анализа-синтеза

Компиляция состоит из двух частей: анализа и синтеза.

Анализ — это разбиение исходной программы на составные части и создание ее промежуточного представления.

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

Группы символов, соответствующие элементам языка называются токенами.

Position:=initial + rate*50.

Токены:

1. Идентификаторы id1 position 

2. Операция op1:=      

3. id2 initial      

4. op2 +

5. id3 rate       

6. op3 *

7. num1 50

Трансляция инструкции

position:=initial + rate*50

id1:= id2 + id3 * 50

Генерация промежуточного кода

temp1:= inttoreal(50);

temp2:= id3 * temp1;

temp3:= id2 + temp2;

id1:= temp3;

 

Оптимизация

temp1:= id3 * 50;

id1:= id2 + temp1;

Генерация исполнительного кода

mov id3, R2

mulf #50, R2

movf id2, R1

addf R2, R1

movf R2, id1

 Язык определяется синтаксисом и семантикой (как должна выглядеть и что должна делать). Для определения синтаксиса языка используется специальная форма записи, которая называется контекстно – свободная грамматика (BNF).

Для определения семантики используется неформальное описание и примеры. Для лексики используются применения возможных токенов и правила для выделения основных.

 If (выражение) инструкция else инструкция;

Stmt if (expr) stmt else stmt;

 В продукции лексические элементы называются токенами. Переменные типа expr и stmt являются последовательностью токенов и называются нетерминальными символами.

Контекстно-свободная грамматика имеет 4 компоненты:

  1.  множество токенов (терминальных символов)
  2.  множество нетерминальных символов
  3.  множество продукций, где слева всегда нетерминал, а справа последовательность терминалов (нетерминалов)
  4.  указание одного из нетерминалов в качестве стартового символа грамматики.

Begin blockbegin opt_stmts end

…….; opt_stmtsstmt_list|e

…….; stmt_liststmts_list;

…….; stmt|stmt;

End stmt…

 Правила соотношения продукции и дерева

  1.  в корне дерева стартовый символ
  2.  каждый лист помечен токеном или e (пустой)
  3.  каждый внутренний узел нетерминальный
  4.  если А – нетерминал или помечает некоторый внутренний узел, а Х1, Х2, Х3…Хn – отметки его дочерних узлов, то существует продукция следующего вида: АХ1Х2…Хn – могут быть как терминальными, так и нетерминальными. Ае

red (apple)

red (X):-not green (X)

stmt  rule | fact | question

fact  property (object)

rule  property (X):-rule1

rule1  property (X) | property (X), rule1

Лексический анализ

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

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

Формальной основой для построения лексического анализатора являются детерминированные конечные автоматы.

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

Кроме того, автомат определяется начальным состоянием, в котором он находится на момент начала работы.

Алгоритм работы описывается с помощью диаграммы переходов.

a

e

f

ab

ec

fa

ab

ecd

fha

acd

f(h)a

Пример:

Выделение идентификаторов, целое со знаком, вещественное со знаком, другое.

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

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

hush

id

link

**

ab

***

***

ba

****

****

de

Методы синтаксического анализа

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

xAyxBy

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

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

Прямое рекурсивное правило – правило, в правой части которого содержится его левая часть: AxAy

 Непрямая рекурсия – содержит неявным образом: BxC; CyB.

Грамматики подразделяются (классы грамматик):

  1.  Контекстно-свободные грамматики.

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

  1.  Контекстно–зависимые грамматики.

В левой части содержится терминал. Данный класс является очень сложным, однако позволяет описать тонкие нюансы.

  1.  Регулярные грамматики.

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

По структуре является достаточно простым, для синтаксического анализа не используется. Используется при описании синтаксических анализаторов.

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

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

Пример:

Описать грамматику сложения-вычитания целых от 0 до 9.

Произвести синтаксический разбор предложения: 9+5-3

Число: 0…9; оператор: +,-

Slist    Нисходящий анализ:

listlist+dig   Slist

listlist-dig   listlist+block

listdig    listlist-block

dig0|1|…|9   list(list)

    block(dig)

    blockdig

     dig0|1|…|9


 

А также другие работы, которые могут Вас заинтересовать

45502. CASE-средства. Общая характеристика и классификация 51 KB
  Общая характеристика и классификация Современные CSEсредства охватывают обширную область поддержки многочисленных технологий проектирования ИС: от простых средств анализа и документирования до полномасштабных средств автоматизации покрывающих весь жизненный цикл ПО. Наиболее трудоемкими этапами разработки ИС являются этапы анализа и проектирования в процессе которых CSEсредства обеспечивают качество принимаемых технических решений и подготовку проектной документации. Графические средства моделирования предметной области позволяют...
45503. Типизация проектных решений АСОИУ. Использование коробочных продуктов и адаптируемых интегрированных систем. Подходы к созданию автоматизированной системы 58 KB
  Подходы к созданию автоматизированной системы В настоящее время существуют различные подходs к построению АСОИП отличающиеся признаками положенными в основу классификации. Полученная таким образом схема классификации подходов к построению АСОИП приведена на рис. В соответствии с этой схемой при выборе подхода к построению АСОИП решается вопрос о возможности использования существующих на рынке тиражируемых систем или необходимости создавать уникальную систему полностью ориентированную только на задачи конкретного предприятия. Подходы к...
45504. Графические средства представления проектных решений АСОИУ (IDEF, DFD, UML, ERD и т.п.) 36 KB
  DFD диаграммы потоков данных являются основным средством моделирования функциональных требований к проектируемой системе. Первый шаг моделирования – извлечение информации из интервью и выделение сущностей. Второй шаг моделирования – идентификация связей. Язык UML находится в процессе стандартизации проводимом OMG – организацией по стандартизации в области ОО методов и технологий в настоящее время принят в качестве стандартного языка моделирования и получил широкую поддержку в индустрии ПО.
45505. Анализ и оценка производительности АСОИУ 23 KB
  В основе такой оценки лежит понятие производительности. Есть 2 показателя производительности процессов по чистому времени: показатель производительности процессоров на операциях с данными целочисленного типа MIPS – отношение числа команд в программе к времени ее выполнения показатель производительности процессоров на операциях с данными вещественного типа при все кажущейся простоте критерия оценки чем MIPS тем быстрее выполняется программа его использование затруднено вследствие нескольких причин: процессоры разной архитектуры...
45506. Общая характеристика процесса проектирования АСОИУ. Цели и этапы разработки консалтинговых проектов 41 KB
  Проект проектноконструкторская и технологическая документация в которой представлено описание проектных решений по созданию и эксплуатации системы в конкретной программнотехнической среде. Проектирование системы процесс преобразования входной информации об объекте проектирования о методах проектирования и об опыте проектирования объектов аналогичного назначения в соответствии с ГОСТом в проект АСОИУ. Проектирование АСОИУ сводится к последовательной формализации проектных решений на различных стадиях жизненного цикла системы....
45507. Структурный подход к проектированию ИС. Функциональная модель АСОИУ 72.5 KB
  Сущность структурного подхода к разработке ИС заключается в ее декомпозиции на автоматизированные функции. Основные элементы этой методологии основываются на следующих концепциях: графическое представление блочного моделирования – функции изображаются в виде блока интерфейсы – дуг входящих и выходящих взаимодействие блоков – с помощью интерфейсных дуг. Блок детализируется на другой диаграмме с помощью нескольких блоков эти блоки представляют подфункции исходной функции. Обратные связи итерации продолжающие процессы и перекрывающая во...
45508. Разработка модели защиты данных в АСОИУ 29.5 KB
  Разработка модели защиты данных в АСОИУ Большое внимание в настоящее время уделяется вопросам формирования принципов построения механизмов защиты информации ЗИ и системы требований к ним. На основе имеющегося опыта можно сформулировать следующие фундаментальные принципы организации защиты информации: системность; специализированность; неформальность. Основные требования принципа системности сводятся к тому что для обеспечения надежной защиты информации в современных АСОИУ должна быть обеспечена надежная и согласованная защита во всех...
45509. Разработка пользовательского интерфейса 44 KB
  Интерфейс пользователя эта та часть программы которая находится у всех на виду. Процесс разработки ПИ разбивается на этапы ЖЦ: Анализ трудовой деятельности пользователя объединение бизнесфункций в роли. Формулировка требований к работе пользователя и выбор показателей оценки пользовательского интерфейса. Разработка обобщенного сценария взаимодействия пользователя с программным модулем функциональной модели и его предварительная оценка пользователями и Заказчиком.
45510. Разработка программы для исследования веб-камер для стрелкового тренажера 3.1 MB
  В процессе работы была разработана программа для исследования веб-камер и микрофонов в качестве регистратора точки прицеливания и спускового крючка для стрелкового тренажера на общедоступных компонентах.