Язык Паскаль (Основные понятия и определения)

V_H = {v_Hi}, i=(1,2,...,m) -множество нетерминальных символов или конструкций языка (применительно к разговорным языкам это, например, префикс, корень, подлежащее, сказуемое, простое предложение и т. п.):

P = {p_i}, i=(1,2,..., m) - множество правил грамматики или синтаксических конструкций, с помощью которых строится нетерминальный словарь; множество правил грамматики иначе еще называют синтаксисом языка;

S - цель грамматики (старший нетерминальный символ); по аналогии с разговорным языком это, например, текст; в языках программирования это программа.

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

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

< - открывающая угловая скобка;

> - закрывающая угловая скобка;

| - знак альтернативы (союз "или");

::= - "равно по определению" или "это есть".

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

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

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

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

<основной символ> ::= <буква>

<цифра>

<знак операции>

<ограничитель>

<разделитель>

<зарезервированое слово>

<буква> ::= abcdefghijklmnoprstuvwxyz

<цифра> ::= 0123456789

<знак операции> ::= +-div/notandorin :=<><=>==<>

<ограничитель> ::= ( ) [ ] begin end ' ' . , ; .. :

<разделитель> ::= { } (* *)

<зарезервированое слово> ::= and array case do downto else filefor

function goto if label mod nilof

packed procedure programrecord repeat

set then to type until varwhilewith

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

Приведенными выше синтаксическими конструкциями основные символы разделены на шесть групп. Это буквы, цифры, знаки операций, ограничители, разделители и зарезервированные слова. Такое разделение условно, т.е. правила можно сформулировать иначе и определять последующие правила с учетом изменений. Например, правило определяющее знаки операций можно представить так:

<знак операции> ::= <знак арифметической операции>

<знак логической операции>

<знак операции отношения>

<прочие>

<знак арифметической операции> ::= +- div /

<знак логической операции> ::= not and or

<знак операции отношения> ::= <><=>==<>

<прочие> ::= in :=

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

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

В качестве следующего примера рассматривается правило, определяющее конструкцию <идентификатор>. Идентификаторы используются в качестве имен переменных, процедур и т. п.

<идентификатор> ::= <буква>

<идентификатор> <буква>

<идентификатор > <цифра>

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

Грамматический разбор произвольно выбранной цепочки a12hx на соответствие ее конструкции <идентификатор> иллюстрируется рисунком (Рис.1.6).

Рис.1.6 Пример разбора правила грамматики

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

<число> ::= <число без знака>

<знак><число без знака>

<число без знака> ::= <целое без знака>

<вещественное без знака>

<вещественное без знака> ::= <десятичная дробь>

<десятичная дробь>

<десятичный порядок>

<десятичная дробь> ::= <целое без знака>.<целое без знака>

<десятичный порядок> ::= Е <целое без знака>

Е <знак><целое без знака>

целое без знака>` ::= <цифра><целое без знака><цифра>

<знак> ::= +-

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

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

<строка> ::= '<последовательность символов>'

<последовательность символов> ::= <символ>

<последовательность символов>

<символ>

<символ> ::= <основной символ>

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

Рассмотренные выше в примерах нетерминальные конструкции по сути являются лексемами. К лексемам обычно относят специальные символы, метки, идентификаторы, числа и строки, поскольку с позиций разработчика транслятора зарезервированные слова и некоторые группы символов (например, := или <>) также рассматриваются как конструкции, а не единичный символ. Таким образом программа на первом уровне грамматического разбора состоит из лексем и разделителей, причем разделитель обычно представляет собой пробел или комментарий. Две соседние лексемы, если они являются зарезервированным словом, идентификатором, меткой или числом, должны быть отделены друг от друга одним и несколькими разделителями. Исключение - строки, которые могут включать символ пробела.

7. Стандарт языка Паскаль

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

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

Предварительное описание языка было опубликовано в 1968 году Никлаусом Виртом, профессором Цюрихского технического университета (Швейцария), в виде Сообщения о Паскале. В 1973 г. вышло в свет Пересмотренное сообщение, где язык был уже определен в терминах множества символов Международной организации по стандартизации (ISO). В сообщении описывается Стандарт Паскаля, который затем уточнялся Британской рабочей группой по стандартам (BSWG), Американским национальным институтом стандартов (ANSI) и другими организациями. Однако, предлагаемые уточнения по существу мало затрагивали авторское Сообщение о Паскале.

Наиболее распространенные версии систем программирования на основе этого языка для машин типа IBM PС и совместимых с ними разрабатывались фирмой Borland International начиная с 1983 г. и имели название Turbo Pascal с порядковыми номерами. Версии с номерами до 4.0 реализовали Стандарт Паскаля с незначительными расширениями. Четвертая версия (1987 г.) внесла существенные изменения в технологию организации модульнной структуры программ и имела встроенную интегрированную среду разработки (Integrated Development Environment - IDE). Начиная с версии 5.5 (1989 г.) язык был концептуально расширен, т.е. дополнен средствами объектно-ориентированного программирования. Версия 6.0 снабжалась объектной библиотекой Turbo Vision, встроеным ассемблером (BASM), усовершенствованными средствами отладки в рамках новой IDE и другими дополнениями. Очередные версии ориентированы на оконные операционные системы, более совершенные объектные библиотеки и продолжают интенсивно развиваться.

С учетом существенных расширений языка понятие "Стандарт языка Паскаль" по настоящее время не теряет смысла, поскольку именно Стандарт является ядром современных версий языка, если не принимать во внимание концептуальное расширение за счет включения в язык средств объектно-ориентированного программирования. При этом следует отметить, что для разработки версии языка Object Pascal фирмой Apple в конце восьмидесятых годов привлекался автор языка Н. Вирт.

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

8. Упражнения

1. Скорректируйте известные Вам синтаксические конструкции в соответствии с принятыми в Borland Pascal расширениями.

2. При наличии машины, не анализируя смысл и не обращая внимания на разметку текста разным шрифтом, наберите программу:

Program XXX;

var

A,B,S : Integer;

C,D,R : Real;

begin

A := . . . ;

B := . . . ;

C := . . . ;

D := . . . ;

S := A+B;

R := C+D

end.

Замените в тексте многоточия изображением целых чисел (Integer) в строках A := . . . ; B := . . . ; и изображениями вещественных чисел (Real) в строках C := . . . ; D := . . . ; . При ошибках в записи чисел транслятор об этом сообщит. Замените имя А (во всем тексте) на другой идентификатор. Ошибка в записи также будет отмечена транслятором. Поупражняйтесь в выборе имен. Два последних оператора позволяют определить диапазон представления целых и вещественных чисел. Определите этот диапазон, используя сообщение транслятора о "переполнении".

При отсутствии машины запишите различные варианты целых и вещественных чисел, а также идентификаторов. Корректность записи проверьте с помощью грамматического разбора в соответствии с приведенными выше примерами (Рис.1.10, 1.11).

2. Составьте различные варианты блок-схем алгоритмов вычисления степенной функции для Y 0 и произвольного целого (в том числе и отрицательного) значения Y. Вариантов таких блок-схем может быть более двух десятков.

3. Используя разложение функции в ряд (выберите подходящее по справочнику), составьте блок-схемы алгоритмов для вычисления функции ln(x) и тригонометрических функций.

4. В предположении, что индексы последовательности могут вычисляться, т.е. для индекса справедливо присваивание значения, вычисленного с помощью некоторого выражения, например I:=I+1, составьте блок схемы алгоритмов для:

вычитания из некоторого числа А последовательности n чисел b₁, b₂, ..., b_n по формулам

С = (...((A - b₁) - b₂ - ... - b_n);

C = A - b_i. i=1, …, n;

вычитания из последовательности n чисел a₁, a₂, ..., a_n, последовательности чисел b₁, b₂, ..., b_n, т.е. алгоритм вычисления по формуле

C_i = a_i - b_i, i=1, …, n;

вычислений по формулам:

C_k = a_i - b_k (1 I n, 1 k m);

C_i = a_i b_i (1 i m);

C = П a_i i=1, …, n;

C_i = П a_k b_i (1 i m, 1 k m).

5. Составьте:

алгоритм определения количества одинаковых чисел в последовательности, заданной в виде: a₁, a₂, ..., a_n.

алгоритм определения количества одинаковых элементов в матрице В размерностью n m.

алгоритм умножения матрицы на вектор.

алгоритм умножения матрицы на матрицу.

алгоритм транспортирования матрицы.

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

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

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

Размещено на Allbest.ru