Информация


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

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

Глава 2. Сложные структуры данных

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

Язык программирования является подмножеством естественного языка и предназначен для поддержки процесса общения человека с компьютером. В общем случае язык — это множество предложений, которые можно записать на нем. Отличие языка программирования от естественного — в его законченности или замкнутости. Под этим понимается, что теоретически можно перечислить все предложения, которые можно на нем составить. Для естественного языка это невозможно. В контексте нашего изложения под языком программирования будем понимать не только языки высокого уровня, но и языки командных процессоров и вообще любые наборы предложений, с помощью которых производится управление работой некоторой программы.
Теория компиляции базируется на том, что любой язык может быть описан формально.
Основа любого естественного языка — его алфавит, то есть множество символов букв. Вспомним, что обучение в школе начинается с букваря, то есть со знакомства с набором символов, из которых в дальнейшем будут строиться слова. Приступая к изучению языка программирования, программист также вначале знакомится с набором символов (букв, цифр, разделительных знаков), из которых строятся слова программы и объединяются затем в предложения программы. Для формального описания языка программирования также необходимо знать алфавит, но в этом случае его понятие отличается от того, к которому мы привыкли. К этому мы вернемся чуть позже. Для написания программы недостаточно знать только лишь один алфавит. Так, в школе после изучения алфавита дети начинают изучать предмет «Русский язык». Можно выделить по крайней мере две цели, которые при этом ставятся: во-первых, на основе алфавита и набора правил научить школьника правильно строить слова языка (которые составляют его лексику); во-вторых, научить его правильно составлять предложения из слов, то есть делать это так, чтобы его могли понимать окружающие. Для построения правильных предложений в любом языке существует набор правил, которые описывают синтаксис этого языка. Каждому правильному предложению языка приписывается некоторый смысл. Описание смысла предложений составляет семантику языка.
Естественный язык многозначен, и часто с его помощью одну и ту же мысль можно выразить несколькими синтаксически разными предложениями. Компьютер — не человек, и общение с ним (во всяком случае, пока) должно быть однозначным, то есть не может быть двух разных по написанию предложений, выполняющих одно действие. Применительно к компьютеру семантика языка программирования представляет собой описание того, как следует исполнять на машине конкретное предложение. Различие синтаксиса и семантики лучше всего иллюстрирует следующий классический пример. Имеются два одинаковых с точки зрения синтаксиса предложения:
Здесь I, J, К — целые, а X, Y, Z — вещественные числа. В машинном представлении для вычисления данных выражений будут использоваться не только разные команды, но и алгоритмы. Если вдруг перед нами будет поставлена задача перевода программы на другой язык программирования, то в той или иной степени будет меняться все — алфавит, лексика, синтаксис, но семантика в идеале должна остаться неизменной.
Таким образом, для формального описания языка необходимы по крайней мере два элемента — алфавит и набор правил (синтаксис) — для построения предложений языка. Существует еще несколько элементов формального описания, которые также важны для процесса однозначного построения и распознавания предложений языка. Знакомство с ними целесообразно вести в рамках такого понятия, как грамматика языка.
Грамматика языка представляет собой механизм порождения предложений языка и определяет форму (синтаксис) допустимых предложений языка. Это важное положение, запомните его. В своем изложении мы постараемся по возможности избежать «формализмов», которыми изобилует теория компиляции, хотя полностью сделать это нам не удастся. В частности, без этого трудно ввести понятие грамматики. Формально грамматику языка G можно определить как совокупность четырех объектов: G-{Vt. Vn. P. Z}
Эти объекты можно описать следующим образом.

  • Vt — множество терминальных символов грамматики. Кстати, в этом контексте слово «символ» не означает отдельную литеру. В контексте терминальных и нетерминальных символов символы — это ключевые слова, допустимые имена идентификаторов, знаки операций, разделительные знаки, то есть все отдельные объекты исходного текста программы, имеющие смысл для компилятора. По сути, множество терминальных символов представляет собой набор лексем, которые являются допустимыми словами языка, составляющими его лексику. Таким образом, важно понимать, что исходный текст программы состоит только из терминальных символов.
  • Vn — множество нетерминальных символов. Эти символы являются вспомогательными конструкциями, определенными внутри грамматики. К пояснению того, что представляют собой нетерминальные символы, мы вернемся чуть позже. Важно отметить, что множества Vt и Vn не пересекаются. Объединение множеств Vt и Vn составляет алфавит языка. Отметим, что введенное здесь понятие алфавита грамматики (а значит, и языка) отличается от того, что есть в букваре. Не забывайте об этом важном моменте при проведении дальнейших аналогий.
  • P- набор правил грамматики, определяющих синтаксис языка. Эти правила называются правилами вывода. Эти правила определяют возможность получения любого предложения языка.
  • Z- начальный символ языка. Он входит в множество Vn. Одна из его особенностей состоит в том, что он должен встретиться по крайней мере в левой части одного из синтаксических правил, входящих в множество Р. И именно это правило является первым в процессе вывода любого допустимого предложения языка.

Далее, если не оговорено особо, прописными буквами будем обозначать терминальные символы, а строчными — нетерминальные.
Поясним, как с помощью грамматики задается язык. Начнем с простого примера. Опишем грамматику G1nt языка целых чисел:

Glnt = {Vt=(0.1.2,3.4.5.6.7.8.9). VrH число, цифра). Р. г=(число)}.

Множество правил Р грамматики Gint выглядит так:

число::=цифра
число::=цифра число
цифра::=0
цифра::=1
цифра::=2
цифра::-3
цифра::=4
цифра::=5
цифра::=6
цифра::-7
цифра::-8
цифра::=9

Обычно подобные правила записывают короче:

число::= цифра | цифра число цифра::=0|1|2|3|4|5|6|7|8|9

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

число::= цифра (2.9)
число::= цифра число (2.10)

Сам процесс вывода предложения языка итеративный и состоит из одного или нескольких шагов. Например, рассмотрим процесс получения предложения 8745. Согласно сказанному выше, на первом шаге вывода можно использовать правило (2.9) или (2.10). Если использовать правило (2.9), то это означает, что предложение будет состоять из одной цифры. В нашем случае на первом шаге необходимо применить правило (2.10). Производя дальнейшие подстановки, можно получить предложение, состоящее из любого количества цифр. Заметьте, что на последнем шаге вместо правила (2.10) применяется правило (2.9), что в конечном итоге приводит к желаемому результату. Таким образом, предложение 8745 получается использованием правил вывода грамматики в следующей последовательности:

число => цифра число => 8 число => 8 цифра число => 87 число => 87 цифра число => 874 число => 874 цифра => 8745.

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

цифра число, 8 число, 8 цифра число, 87 число, 87 цифра число, 874 число, 874 цифра, 8745.

Предложением языка является только одна из этих сентенциальных форм — строка 8745.
На правила грамматики обычно накладываются определенные ограничения. В зависимости от этих ограничений языки делятся на 4 класса.

  • Класс 0. Грамматики без ограничений. Правила этих грамматик имеют форму: u=>w. При этом не накладывается каких-либо ограничений на строки и и v в левой и правой частях правил вывода. Используя языки этого класса, можно моделировать естественный язык.
  • Класс 1. Контекстно-чувствительные грамматики. Правила этих грамматик имеют форму: AuB=>AwB. Замена и на v возможна лишь в контексте строк А и В (отсюда и название). При этом: ueVn; we(VnuVt)*; A, Be(VnuVt)+. Символы * и + обозначают множество всех строк, выводимых в рамках данной грамматики, включая ("*") и исключая ("+") пустую строку.
  • Класс 2. Контекстно-свободные, или контекст}ю-нечувствительные, грамматики. Их правила имеют форму: u=>w, где ueVn, we(VnuVt)*. Название данного класса грамматик отражает тот факт, что и можно заменить на w, не обращая внимания на контекст. Другая особенность грамматик этого класса в том, что в правой части всех правил грамматики стоит только один нетерминал. Отметим, что языки программирования моделируются с использованием грамматик именно этого класса.
  • Класс 3. Регулярные, или автоматные, грамматики. Исходя из вида правил, которые используются в таких грамматиках, их делят на два подкласса.
  • Грамматика, выравненная вправо. Ее правила имеют форму: u=>Aw или и=>А, где AeVt, u и weVn.
  • Грамматика, выравненная влево. Ее правила имеют форму: u=>\vA или и=>А, где AeVt, u и weVn. Это очень важный класс грамматик, который наряду с грамматикой класса 2 используется для моделирования языков программирования. Заметим, что рассмотренная выше грамматика языка целых чисел как раз и является грамматикой класса 3. Чтобы убедиться в этом, необходимо лишь немного подправить правила:

число: ."¦ цифра
число: :*=0 число |1 число |2 число |3 число |4 число |5 число |б число |7 число
|8 число |9 число иифра::=0|1|2|3|4(5|6|7|8|9

Приведенная выше классификация языков была введена в 1959 году американским ученым-лингвистом Н. Хомским.
Выше, при изложении основ работы с двусвязными списками, мы ввели понятие конечного автомата. Язык, который воспринимает любой конечный автомат, относится к языкам класса 3, то есть является регулярным. Покажем это, сформулировав грамматику для языка вещественных чисел. Напомним соответствующее регулярное выражение: (+| -)dd*.dd*e(+| 0dd*, где d* обозначает цифру 0-9 или пусто.

Grea1-{Vt-(.. + . -. е. 0. 1, 2, 3. 4. 5. 6. 7. 8. 9). VrHreal. s. m, n. k, t). P. Z-(< real >)}.

Множество правил P грамматики Greal:

real=>+s|-s|Ds s=>ds |. m m=>Dn | D n=>Dn | ek k=>+t|-t|Dt|D T=>dT|d

Попробуйте, используя данную грамматику, самостоятельно вывести следующие предложения языка вещественных чисел: 5.5, +0.6е-5. Покажите, что предложение «+.45е4» невыводимо в терминах данной грамматики. При необходимости посмотрите еще раз материал раздела «Сеть» данной главы, где было введено понятие конечного автомата и разработана программа, моделирующая его работу при распознавании строки с вещественным числом.
Анализ правил вывода грамматики Greal показывает, что генерируемый ею язык относится к языкам класса 3, а сама грамматика является грамматикой, выровненной вправо.
Рассмотрим еще одну грамматику для языка идентификаторов Gident.

G1dent-{Vt-(.. +. -. е. 0. 1. 2. 3. 4. 5. 6. 7. 8, 9). VrHreal. S. M. N. К. Т), Р, 2=(< real >)}

Множество правил Р грамматики Gident:

ident=>letter| ident letter | ident figure letter => A|B|C| ... X|Y|Z figure => 0|l|2|...8|9

Видно, что это тоже грамматика языка класса 3.
А теперь приведем пример грамматики, генерирующей язык класса 2. С ее помощью смоделируем псевдоязык, похожий на Pascal, который мы используем в нашей книге для пояснения некоторых алгоритмов:

Vt=(riPOrPAMMA, ПЕРЕМЕННЫЕ, НАЧ_ПРОГ. КОН_ПРОГ, НАЧ_БЛОК. КОН_БЛОК. ".".ID. CHJNT. СН_ REAL. «:».«:». «/». REAL. INTJYTE. INT_WORD. INT_OWORD. «,».«:»». «=».«+».«-».«*». DIV. MOO. «(». «)». «[». «]». «<».«>», «==»,«>=».«=<». ЧИТАТЬ, ПИСАТЬ, ДЛЯ. ДОДЕЛАТЬ. ПОКА. Д08НИЗ, ЕСЛИ. ЕСЛИ. ДО. ТО. ПЕРЕЙТИ_НА. ПОВТОРИТЬ),
Vn»( prog, prog-name, dec-list, stmt-list, dec. id-list, type. var. varjnd. ind. label. go_to. stmt, assign, read, write, until, for. call_func. exp. term, factor, index-exp. body, condition. cond_op). P. Z-(< prog >) }

Множество правил Р грамматики G:

prog => ПРОГРАММА prog-name ПЕРЕМЕННЫЕ dec-list НАЧ_ПРОГ stmt-list КОН_ПРОГ
prog-name => ID
dec-list => dec | dec-list : dec
dec => type id-list
type => INTJYTE | INT_WORD | INT_DWORD | REAL
1d-list=> var | id-list , var
var=> ID | varjnd
var_ind=> ID ind
ind => [ exp ]
stmt-list => stmt | stmt-list ; stmt
stmt => assign | read | write | for | while | until | label | go_to | cond op | call_
func
assign => var :- exp exp => term | exp + term | exp - term
term => factor | term * factor | term DIV factor| term MOD factor factor => var | CH_INT | CH_REAL | ( exp ) read => ЧИТАТЬ (id-list) ~ write => ПИСАТЬ (id-list) for=> ДЛЯ index-exp ДЕЛАТЬ body until => ПОВТОРИТЬ body ПОКА logical_exp call_func => ID (id-list) cond_op=> ЕСЛИ logical_exp TO body while => ПОКА logical_exp ДЕЛАТЬ body label => ID : stmt-list go_to => ПЕРЕЙТИ_НА idjabel idjabel => ID
index-exp => var := exp ДО exp | exp Д0ВНИЗ exp logical_exp => ( condition )
condition => l_exp < l_exp | l_exp <@062> l_exp | l_exp >- l_exp | l_exp =< l_exp | l_exp — l_exp | l_exp ИЛИ l_exp | l_exp И l_exp | l_exp XOR l_exp | HE l_exp l_exp => exp | condition body => stmt | НАЧ_БЛОК stmt-list КОН_БЛОК

Посмотрим внимательно на правило вывода, в левой части которого стоит начальный символ языка prog. Правая часть этого правила представляет собой сентенциальную форму, содержащую все необходимые элементы программы. На примере этой грамматики хорошо видно, что представляет собой алфавит языка программирования. По сути это совокупность лексем, которые программист использует для написания программы и которые в терминах языка являются терминальными символами, а также нетерминалов, которые имеют смысл в рамках грамматики. Более того, к терминальным символам относятся также символы ID (идентификатор), CHINT (целое число) и CHREAL (вещественное число). В программе им соответствуют Совершенно разные сочетания символов букв, цифр и разделительных знаков, например идентификаторы — chl, sab, masl; целые числа — 1, 24, 98584; вещественные числа — +33.5, 0.95е-3. С точки зрения синтаксиса эти разные по написанию объекты являются терминальными символами — идентификатором, целым числом, вещественным числом. Это ключевой момент. Мы
к нему еще вернемся, а пока давайте посмотрим, каким превращениям подвергается исходный текст программы, для того чтобы превратиться в форму, пригодную для машинного исполнения.