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




Скачать 426.05 Kb.
НазваниеПрограмма, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке
страница1/11
Дата публикации27.03.2013
Размер426.05 Kb.
ТипПрограмма
uchebilka.ru > Информатика > Программа
  1   2   3   4   5   6   7   8   9   10   11

Оглавление


Оглавление 1

1.Упрощенная модель компилятора 2

2.Конечные автоматы 3

3.Приведение конечных автоматов 4

4.Недетерминированные КА. Преобразование НКА в КА 5

5.Проблемы реализации КА 7

6.Автоматы с магазинной памятью 8

7.Формальные языки и грамматики. Классификация языков по Хомскому 9

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

9.Бесполезные нетерминалы. Удаление из грамматики бесполезных нетерминалов 11

10.Перевод при помощи автомата с магазинной памятью. Зацикливание АМП. 13

11.Транслирующие грамматики. Преобразование арифметического выражения из инфиксной в постфиксную форму записи 14

12.Атрибутивные транслирующие грамматики. Синтезируемые и наследуемые атрибуты 15

13.S,Q – грамматики 16

14.LL(1) – грамматика 18

15.L(1) - грамматика 19

16.Методы обработки ошибок при нисходящем разборе 21

17.Построение блока генерации 22


  1. ^

    Упрощенная модель компилятора


Компилятор – программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке. Интерпретатор – выполняет анализ программы на некот. Языке построчно или пооператорно. После анализа сразу реализует действия, определенные оператором или строчкой входной программы. Под транслятором будем понимать и компилятор, и интерпретатор. Рис. – упрощенная модель компиляторов.


Транслитератор – преобразует вх. поток символов в вых. Поток символьных лексем. Каждому симв. ставится в соответствие символьная лексема – это сам символ и его класс (А → (буква, «А»)). Основной задачей является определение класса каждого допустимого вх. символа. Дополнительным действием может являться сокращение количества пробелов и табуляций, идущих подряд, до одного пробела. Лексический блок – разрезает вх. поток на части, которые являются словами языка (лексемы). Заполняет таблицы идентификаторов, констант, ошибок и меток. Синтаксический блок – преобразует вх. поток лексем в вых. поток атомов (элементарных действий). Определяет, какие элемент. действия и в каком порядке надо выполнить для реализации вх. алгоритма. В синтаксич. блок как правило интегрируется семантический анализ, который используя данные из синтаксического блока и таблицы символов производит проверку исходной программы на семантическую согласованность с определением языка. Он также собирает информацию о типах (пример – возможно ли приведение типов). Блок оптимизаций – пытается «улучшить» промежуточный код, лучший может означать например более быстрый или короткий код. Блок генерации – генератор кода получает в качестве вх. данных промежуточное представление исх. программы и отображает его в целевой язык. Если целевым является машинный код, для каждой переменной выбираются соотв. регистры и ячейки памяти. Если каждый блок отдельно полностью обрабатывает вх. поток, считывая вх. файл и записывая в выходной, то мы можем получаем 4х-проходный компилятор.

  1. ^

    Конечные автоматы


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

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

КА = {K, ∑, δ, S, F}, где K – состояние, ∑ - вх. алфавит, δ – ф-ции переключения состояний, S – начальное состояние, F – допускающие состояния.

Примером задачи распознавания может служить проверка нечетности числа единиц в произвольной цепочке, состоящей из нулей и единиц. Соответствующий конечный автомат будет «допускать» все цепочки, содерж. нечетное число единиц и «отвергать» четные. На вход подается цепочка символов из конечного множества, называемого вх. алфавитом автомата, и представляющего собой совокупность символов, для работы с которыми он предназначен. Как допускаемые, так и отвергаемые цепочки состоят только из символов вх. алфавита. Не принадлежащие символы нельзя подавать на вход. Наш входной алфавит для контроля нечетности будет состоять из символов 0 и 1. В каждый момент времени автомат имеет дело лишь с одним вх. символом, а о прочитанных ранее помнит только то, что при их обработке перешел в некоторое состояние (кот. наз-ся памятью автомата о прошлом). Контроллер нечетности будет построен так, чтобы он умел запоминать четное или нечетное число единиц ему встретилось при чтении отрезка вх. цепочки. Поэтому мн-во состояний нашего автомата содержит состояния ЧЕТ и НЕЧЕТ. Начальным состоянием назначим состояние ЧЕТ. При чтении очередного вх. символа состояние автомата меняется, что зависит только от текущего символа. Такое изменение состояния называется переходом. Работу автомата можно описать с помощью функции δ – функция перехода. По текущ. сост. и текущему вх. симв. она дает новое сост. автомата: . Определим функцию переходов контроллера четности таким образом:

δ(ЧЕТ,0) = ЧЕТ; δ(ЧЕТ,1) = НЕЧЕТ; δ(НЕЧЕТ, 0) = НЕЧЕТ; δ(НЕЧЕТ, 1) = ЧЕТ – т.е. четность меняется только тогда, когда на входе появляется 1. Некоторые состояния автомата выбираются в качестве допускающих. Если автомат пройдя всю цепочку переходит в одно из допускающих состояний, говорят, что эта цепочка допускается автоматом. Если последнее состояние не является допускающим, говорят, автомат отвергает цепочку. Контроллер нечетности имеет единственное допускающее состояние НЕЧЕТ.

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





0

1




ЧЕТ

ЧЕТ

НЕЧЕТ

0

НЕЧЕТ

НЕЧЕТ

ЧЕТ

1


  1   2   3   4   5   6   7   8   9   10   11

Добавить документ в свой блог или на сайт

Похожие:

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconМетодические указания к лабораторной работе №1 по курсу Информатика для студентов
Написание программы на языке программирования. Программы, написанные на языке C++, имеют расширение. Срр

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconКурс «Компонентные программные технологии» 1 Лабораторная работа...
Однако для реализации этой системы необходимо разработать исходный текст программы на некотором языке программирования (C++, Pascal,...

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

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconПрограммирование
Введение в программирование на языке Pascal. Программа. Структура программы. Идентификатор. Правила записи идентификатора. Блок описаний....

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconПрограмма написана на языке программирования Delphi под ос windows Vista
Не забудьте указать номер версии в любом докладе о проблеме. Кроме того, необходимо постоянно обновлять программу и использовать...

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconПрограмма аппроксимации на языке бэйсик см-1
Для подготовки исходных данных, необходимых при построении датчиков с заданным распределением в gpss-моделях, описанный алгоритм...

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconПрограммирование на языке С++ Лабораторный практикум
Цель: Изучение символьных и строковых переменных и способов их обработки в языке Си

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconНеотъемлемое право личности?
«образование должно быть направлено на полное развитие человеческой личности», а такое развитие возможно только в том случае, если...

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

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconО том, как создавать программы на встроенном в Microsoft Office языке...
Но теория будет еще полезнее, если подкрепить ее практикой примерами реально работающих программ, написанных на этом языке. А таких...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<