Загрузка...

ТЯП — лабораторная №2, теория.


  1. Что такое трансляция, компиляция, транслятор, компилятор?

Трансляция программы — преобразование программы, представленной на одном из языков программирования, в программу на другом языке и, в определённом смысле, равносильную первой.         Язык, на котором представлена входная программа, называется исходным языком, а сама программа — исходным кодом. Выходной язык называется целевым языком или объектным кодом.           Понятие трансляции относится не только к языкам программирования, но и к другим компьютерным языкам, вроде языков разметки, аналогичных HTML, и к естественным языкам, вроде английского или русского.

Компиляция:

— трансляция программы на язык, близкий к машинному,[2][3] и последующая её компоновка.трансляция программы, составленной на исходном языке, в объектный модуль (осуществляется компилятором.[2]) и последующая её компоновка в готовый к использованию программный модуль.

— трансляция программы, составленной на исходном языке, и последующая её компоновка в программу на некоем машинонезависимом низкоуровневом интерпретируемом коде (как например в случае языка Java).

Компилировать — производить трансляцию машинной программы с проблемно-ориентированного языка на машинно-ориентированный язык [3] и последующую компоновку программы в готовый к использованию программный модуль.

Трансля́тор — программа или техническое средство, выполняющее трансляцию программы

Транслятор — в широком смысле — программа, преобразующая текст, написанный на одном языке, в текст на другом языке.

Транслятор — в узком смысле — программа, преобразующая: программу, написанную на одном (входном) языке в программу, представленную на другом (выходном) языке.

Транслятор обычно выполняет также диагностику ошибок, формирует словари идентификаторов, выдаёт для печати тексты программы и т. д.

Компиля́тор —

— Программа или техническое средство, выполняющее компиляцию.

— Машинная программа, используемая для компиляции.

— Программа, переводящая текст программы на языке высокого уровня в эквивалентную программу на машинном языке.

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

— Программа выполняющая (после трансляции) компоновку программы.

  1. Из каких процессов состоит компиляция? Расскажите об общей структуре компилятора.

Структура компилятора

Любой компилятор состоит из транслятора и компоновщика. Часто в качестве компоновщика компилятор использует внешний компоновщик, реализованный в виде самостоятельной программы, а сам выполняет лишь трансляцию исходного текста (по этой причине многие ошибочно считают компилятором разновидность транслятора). Компилятор может быть реализован и как своеобразная программа-менеджер, для трансляции программы вызвающая сооствествующий транслятор (трансляторы — если разные части программы написаны на разных языках программирования) и затем — для компоновки программы, — вызывающая компоновщик. Ярким примером такого компилятора является имеющаяся во всех UNIX-системах (и Linux-системах в том числе) утилита make (имеются реализации утилиты make и в других системах, в частности в Windows-системах).

Процесс компиляции состоит из следующих фаз:

Лексический анализ. На этой фазе последовательность символов исходного файла преобразуется в последовательность лексем.

Синтаксический (грамматический) анализ. Последовательность лексем преобразуется в древо разбора.

Семантический анализ. Древо разбора обрабатывается с целью установления его семантики (смысла) — например, привязка идентификаторов к их определениям, типам данных, проверка совместимости типов данных, определение результирующих типов данных выражений и т. д. Результат обычно называется «промежуточным представлением/кодом», и может быть дополненным древом разбора, новым древом, абстрактным набором команд или чем-то ещё, удобным для дальнейшей обработки.

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

Генерация кода. Из промежуточного представления порождается код на целевом языке (в том числе выполняется компоновка программы).

  1. Какую роль выполняет лексический анализ в процессе компиляции?

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

  1. Как связаны лексический и синтаксический анализ?

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

  1. Дайте определение цепочки, языка. Что такое синтаксис и семантика языка?

Цепочка – некоторая последовательность лексем принадлежащих этому языку и удовлетворяющих синтаксическим правилам.

         Цепочка (слово) над алфавитом Σ – конечная последовательность символов:    a = c1cc2…cn (ci I Σ)

e — пустая цепочка, Σ* — множество цепочек над Σ

Семантический анализ. Древо разбора обрабатывается с целью установления его семантики (смысла) — например, привязка идентификаторов к их определениям, типам данных, проверка совместимости типов данных, определение результирующих типов данных выражений и т. д. Результат обычно называется «промежуточным представлением/кодом», и может быть дополненным древом разбора, новым древом, абстрактным набором команд или чем-то ещё, удобным для дальнейшей обработки.

  1. Какие существуют методы задания языков? Какие дополнительные вопросы

необходимо решить при задании языка программирования?

Для задания языка программирования необходимо решить три вопроса:

− определить множество допустимых символов языка;

− определить множество правильных программ языка;

− задать смысл для каждой правильной программы.

Только первые два вопроса полностью или частично удаётся решить с помощью лексики формальных языков.

  1. Что такое грамматика? Дайте определения грамматики.

Грамматика − это описание способа построения предложений некоторого языка. Иными словами, грамматика − это математическая система, определяющая язык.

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

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

  1. Как выглядит описание грамматики в форме Бэкуса-Наура.

Форма Бэкуса—Наура (сокр. БНФ, Бэкуса—Наура форма) — формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории. БНФ используется для описания контекстно-свободных формальных грамматик.

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

БНФ-конструкция определяет конечное число символов (нетерминалов). Кроме того, она определяет правила замены символа на какую-то последовательность букв (терминалов) и символов.

  1. Какие классы грамматик существуют? Что такое регулярные грамматики?

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

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

  1. Дайте определения контекстно-свободной грамматики, выводимости цепочки, непосредственной выводимости, длины вывода.

Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются одиночными нетерминалами. Смысл термина «контекстно-свободная» заключается в том, что возможность применить продукцию к нетерминалу, в отличие от общего случая грамматики Хомского, не зависит от контекста этого нетерминала.

Язык, который может быть задан КС-грамматикой, называется контекстно-свободным языком или КС-языком.

КС-грамматики находят большое применение в информатике. Ими задаётся грамматическая структура большинства языков программирования, структурированных данных и т.д. (см. грамматический анализ).

Для разбора КС-грамматики достаточно автомата со стеком, для разбора не-КС-грамматик может потребоваться полная машина Тьюринга.

Цепочка β ∈ (VT ∪ VN)* выводима из цепочки α ∈ (VT ∪ V N ) + в

грамматике G = (VT , VN , P, S ) (обозначается α⇒*β), если существует последо-

вательность цепочек γ 0 , γ 1 , K , γ n (n≥0) такая, что α = γ 0 => γ 1 => K => γ n = β .

  1. Что такое лексема? Расскажите, какие типы лексем существуют в языках программирования.

Группа символов входной последовательности, идентифицируемая на выходе процесса как токен, называется лексемой. В процессе лексического анализа производится распознавание и выделение лексем из входной последовательности символов.

Распознавание лексем в контексте грамматики обычно производится путём их идентификации (или классификации), согласно идентификаторам (или классам) токенов, определяемых грамматикой языка

  1. Что такое конечный автомат? Дайте определение детерминированного и недетерминированного конечных автоматов.

Конечный автомат — абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию. Автомат начинает работу в состоянии q0, считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается».

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

Недетерминированный конечный автомат (НКА) является обобщением детерминированного. Недетерминированность автоматов достигается двумя способами:

— Существуют переходы, помеченные пустой цепочкой ε

— Из одного состояния выходит несколько переходов, помеченных одним и тем же символом

  1. Расскажите о возможности преобразования недетерминированного конечного автомата в детерминированный.

Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными). Однако, поскольку количество состояний в эквивалентном ДКА в худшем случае растёт экспоненциально с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом в общем случае не поддаются детерминизации.

В силу последних двух замечаний, несмотря на бо́льшую сложность недетерминированных конечных автоматов, для задач, связанных с обработкой текста, преимущественно применяются именно НКА.

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

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

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

— При неуспешном распознавании выдается сообщение об ошибке, а дальнейшие действия зависят от реализации сканера — либо его выполнение прекращается, либо делается попытка распознать следующую лексему (идет возврат к первому этапу алгоритма).

Загрузка...