Общее понятие структуры данных.

⇐ ПредыдущаяСтр 6 из 7Следующая ⇒

Понятие структуры данных является настолько фундаментальным, что для него сложно подобрать простое определение. Задача упрощается, если попробовать сформулировать это понятие по отношению к типам данным и переменным. Как известно, программа представляет собой единство алгоритма (процедур, функций) и обрабатываемых ими данных. Данные, в свою очередь, определяются базовыми и производными типами данных -" идеальными" представлениями переменных фиксированной размерности с наборами известных операций над ними и их компонентами. Переменные -это именованные области памяти, в которые " отображаются" сконструированные типы данных.
В программе всегда можно выделить группы косвенно связанных (по использованию данных в одних и тех же процедурах и функциях) и непосредственно связанных (по наличию взаимосвязей через указатели) переменных. Их в первом приближении и можно считать структурами данных.

Различаются ПРОСТЫЕ (базовые, примитивные) структуры (типы) данных и ИНТЕГРИРОВАННЫЕ (структурированные, композитные, сложные). Простыми называются такие структуры данных, которые не могут быть расчленены на составные части, большие, чем биты. С точки зрения физической структуры важным является то обстоятельство, что в данной машинной архитектуре, в данной системе программирования мы всегда можем заранее сказать, каков будет размер данного простого типа и какова структура его размещения в памяти. С логической точки зрения простые данные являются неделимыми единицами. Интегрированными называются такие структуры данных, составными частями которых являются другие структуры данных - простые или в свою очередь интегрированные. Интегрированные структуры данных конструируются программистом с использованием средств интеграции данных, предоставляемых языками программирования.

В зависимости от отсутствия или наличия явно заданных связей между элементами данных следует различать НЕСВЯЗНЫЕ структуры (векторы, массивы, строки, стеки, очереди) и СВЯЗНЫЕ структуры (связные списки).

Весьма важный признак структуры данных - ее изменчивость - изменение числа элементов и (или) связей между элементами структуры. В определении изменчивости структуры не отражен факт изменения значений элементов данных, поскольку в этом случае все структуры данных имели бы свойство изменчивости. По признаку изменчивости различают структуры СТАТИЧЕСКИЕ, ПОЛУСТАТИЧЕСКИЕ, ДИНАМИЧЕСКИЕ. Классификация структур данных по признаку изменчивости приведена на рис. 1.1. Базовые структуры данных, статические, полустатические и динамические характерны для оперативной памяти и часто называются оперативными структурами. Файловые структуры соответствуют структурам данных для внешней памяти.

18) Алгоритмические языки. Простые и составные типы операторов (на примере языка Паскаль).

Алгоритмические языки программирования – см. Языки программирования

Простые операторы Простыми являются те операторы, которые не содержат в себе других операторов. К ним относятся: - оператор присваивания; - обращение к процедуре; - оператор безусловного перехода GOTO; - пустой оператор. Структурированные операторыСтруктурированными являются такие операторы, которые включают в себя другие операторы. К структурированным операторам относятся: - составной оператор; - условный оператор IF; - условный оператор CASE; - оператор цикла REPEAT; - оператор цикла WHILE; - оператор цикла FOR; - оператор над записями WITH. 19) - Этапы создания программ для ЭВМ. Трансляция с языка программирования.

Этапы создания программ для ЭВМ – см Этапы разработки программ для ЭВМ

Структура транслятора

Рис. 1. Структура компилятора

Транслятором называется программа, обрабатывающая текст на некотором входном языке. Наиболее распространёнными видами трансляторов для языков программирования являются компиляторы и интерпретаторы.

Компиляторы переводят текст программы с языка высокого уровня на язык низкого уровня – машинный код.

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

На рис. 1 представлена общая схема компилятора. Он состоит из двух частей – анализирующей и генерирующей. Интерпретатор может содержать ещё интерпретирующую часть – абстрактную машину. Кроме того, если входом этой машины является непосредственно семантическая структура, построенная анализирующей частью, то он не нуждается в генераторе кода.

Анализирующая часть синтаксически управляемого транслятора состоит из лексического, синтаксического и контекстного анализаторов.

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

" x1-3.5+x2 < > y"

преобразуется в последовательность из 7 лексем

[id(x1), `-, n(3.5), `+, id(x2), '< > ', id(y)].

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

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

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

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

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

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

В данной книге для определения всех " постсинтаксических" аспектов языка используются предикативные грамматики. Благодаря своей твёрдой математической основе (математическая логика) и универсальности, эти грамматики позволяют дать достаточно абстрактные определения и строго обосновывать многие проектные решения, например, семантическую правильность трансляции. С другой стороны, благодаря реализации предикативных грамматик в системах логического программирования на базе языка Пролог, эти определения могут быть отлажены ещё на этапе проектирования транслятора или даже языка.

Основное отличие данной книги от многих других, посвящённых этой теме, состоит в том, что в ней излагается не только теория формализмов, используемых для определения языков и трансляторов (грамматик, автоматов и т.п.), но и теория самих языков программирования, их семантики и трансляции. Несмотря на огромное разнообразие языковых конструкций и методов их реализации, есть некоторые общепризнанные концепции построения языков программирования и трансляторов, которые мы здесь попытались осветить. К таким концепциям относятся, например, концепции типа, блочной видимости, принципы адресации, реализации рекурсивных процедур и т.д. К счастью, есть довольно простой язык программирования - Паскаль, из которого нетрудно выделить небольшое подмножество, содержащее все затронутые понятия. Это позволило проиллюстрировать все рассмотренные методы трансляции в виде полной реализации этого языка и тем самым рассмотреть их не изолированно, а во взаимосвязи. Благодаря встроенности предикативных грамматик в Пролог-системы, студенты получают не только теоретические знания, но и могут проверить их на практике.

⇐ Предыдущая 1 2 3 4 567 Следующая ⇒