Синтаксические диаграммы языка программирования + видео обзор

Содержание
  1. Описание синтаксиса языков программирования
  2. Материал из ПИЭ.Wiki
  3. Содержание
  4. Форма Бэкуса-Наура (БНФ)
  5. Синтаксические диаграммы
  6. Расширенная форма Бэкуса-Наура
  7. Описания синтаксиса языков семейства Си
  8. Особенности языка Си
  9. Пример программы «Hello world » на Си
  10. Описания синтаксиса языка Ада
  11. Особенности
  12. Осбенности синтаксиса
  13. Пример программы «Hellow world» на Аде
  14. Определение синтаксиса Кобола и ПЛ/1
  15. Особенности языка Кобол
  16. Пример программы «Hello world » на Коболе
  17. Основные свойства ПЛ/1
  18. Пример программы «Hello world» на ПЛ/1
  19. Алфавит языка
  20. Синтаксические диаграммы Вирта
  21. Лекция 7 Синтаксис языков программирования Нотация Бэкуса-Наура и синтаксические диаграммы Вирта
  22. Главная > Документ
  23. Лекция 7
  24. Синтаксис языков программирования
  25. Нотация Бэкуса-Наура и синтаксические диаграммы Вирта
  26. Грамматики, языки и классификация Н. Хомского
  27. Способы описания синтаксиса языка программирования
  28. Видео

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

Материал из ПИЭ.Wiki

При описании известных языков программирования используются следующие нотации:

Содержание

Форма Бэкуса-Наура (БНФ)

Форма Бэкуса-Наура (БНФ) была впервые применена при описании Алгола-60. БНФ совпадает по сути с нотацией КС-грамматик, отличаясь лишь обозначениями. Предусмотрены следующие метасимволы:

Терминальные символы записываются как есть, никаких специальных способов их выделения не предусмотрено. Вот пример определений на БНФ, взятый из спецификации Алгола-60 — «Модифицированного сообщения»:

Как видим, для выражения повторений используется рекурсия, причем повсеместно — левая. БНФ использована Н. Виртом при описании языка Паскаль. Хотя в нотацию были добавлены метаскобки <и>, обозначающие повторение, применены они лишь в отдельных случаях, в то время как, например, грамматика выражений леворекурсивна.

Синтаксические диаграммы

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

Таким образом, синтаксические диаграммы могут служить не только для порождения, но и для распознавания автоматных языков. Диаграммы стали популярны после выхода книги К. Йенсен и Н. Вирта «Паскаль». Они использованы в первой ее части — «Руководстве» — компактном учебнике языка. На рис. 3.1 показана одна из имеющихся там диаграмм. Синтаксические диаграммы языка программирования

Расширенная форма Бэкуса-Наура

Как уже говорилось, отсутствие в нотации формальных грамматик (и БНФ) средств явного задания повторений создает ряд трудностей. Во-первых, определения оказываются сложными для понимания, недостаточно наглядными из-за обилия рекурсий. Во-вторых, возникают проблемы с тем, что грамматики, дающие подходя- щие семантические деревья, оказываются леворекурсивными. При описании Модулы-2 и Оберона Н. Вирт использовал расширенную Бэкуса-Наура форму (РБНФ). Главные модификации касаются введения скобок < и>для повторений, а [ и ] — для обозначения необязательного вхождения цепочек терминалов и нетерминалов в правые части правил. Соглашения относительно обозначений терминалов и нетерминалов также изменены, что не столь принципиально. В дальнейшем мы будем пользоваться именно РБНФ. Вот как она определяется в спецификации Оберона-2: Варианты разделяются знаком |. Квадратные скобки [ и ] означают необязательность записанного внутри них выражения, а фигурные скобки < и >означают его повторение (возможно, 0 раз). Нетерминальные символы начинаются с заглавной буквы (например, Оператор). Терминальные символы или начинаются малой буквой (например, идент), или записываются целиком заглавными буквами (например, begin), или заключаются в кавычки (например, «:=»). К этому следует добавить, что в роли знака «есть по определению» в РБНФ используется «=», а каждое правило заканчивается точкой. Вот так может быть определен синтаксис идентификатора (имени) с помощью РБНФ:

Являясь метаязыком, РБНФ должна быть пригодна для описания языков, имеющих практический интерес. В том числе с помощью РБНФ может быть определен и синтаксис самой РБНФ:

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

Описания синтаксиса языков семейства Си

Си (англ. C) — стандартизированный процедурный язык программирования, разработанный в начале 1970-х годов сотрудниками Bell Labs Кеном Томпсоном и Денисом Ритчи как развитие языка Би. Си был создан для использования в операционной системе UNIX. С тех пор он был портирован на многие другие операционные системы и стал одним из самых используемых языков программирования. Си ценят за его эффективность; он является самым популярным языком для создания системного программного обеспечения. Его также часто используют для создания прикладных программ. Несмотря на то, что Си не разрабатывался для новичков, он активно используется для обучения программированию. В дальнейшем синтаксис языка Си стал основой для многих других языков. Для языка Си характерны лаконичность, современный набор конструкций управления потоком выполнения, структур данных и обширный набор операций.

В знаменитой книге Б. Кернигана и Д. Ритчи описание синтаксиса языка Си дано в нотации, которая эквивалентна БНФ, но использует другие соглашения об обозначениях терминалов и нетерминалов, альтернативных правых частей правил, необязательных конструкций. Нетерминалы записываются курсивом, терминалы — прямым шрифтом. Альтернативные части правил выписываются в столбик по одному в строке или помечаются словами «one of» (один из). Необязательные части сопровождаются подстрочным индексом «opt (от optional) — необязательный; «необ» — в некоторых русских пере- водах). Левая часть правила записывается отдельной строкой с отступом влево. Вот пример определений конструкций языка Си:

Как видим, из-за отсутствия явного способа выражения повторений, определе- ния изобилуют рекурсией. Аналогичная нотация с минимальными изменениями использована для описа- ния синтаксиса языков-потомков Си: Си++, Ява, Си#. Вот выдержка из стандарта ЕСМА-334 на язык Си#:

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

Особенности языка Си

Пример программы «Hello world » на Си

Описания синтаксиса языка Ада

Ада(Ada) — язык программирования, созданный в 1979—1980 годах в результате проекта, предпринятого Министерством обороны США с целью разработать единый язык программирования для встраиваемых систем (то есть систем управления автоматизированными комплексами, работающими в реальном времени). Имелись в виду, прежде всего, бортовые системы управления военными объектами (кораблями, самолётами, танками, ракетами, снарядами и т. п.). Перед разработчиками не стояло задачи создать универсальный язык, поэтому решения, принятые авторами Ады, нужно воспринимать в контексте особенностей выбранной предметной области. Язык назван в честь Ады Лавлэйс.Исследования, выполненные в начале и середине 1970-х годов, показали, что если Пентагон будет использовать единый язык программирования для решения всех своих задач вместо примерно 450 языков и их диалектов, то появится возможность получить огромную экономию средств (около 24 млрд долл. за период с 1983-го по 1999 год).Язык Ада основан на идеях структурного программирования и обеспечивает поддержку разработки сложных многомодульных программ, высокую степень машино-независимости и переносимости.При проектировании языка в первую очередь внимание акцентировалось на надежности и эффективности — язык создавался специально для разработки больших программных комплексов реального времени для встроенных систем, к которым предъявляются высокие требования надежности.

Особенности

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

Осбенности синтаксиса

Контекстно-свободные грамматики языков Aда-83 и Ада-95 определены с помощью варианта БНФ, в который добавлены обозначения повторений и необязательных частей. Названия нетерминалов записываются обычным шрифтом с использованием знака подчеркивания, если название составное, а зарезервированные слова — жирным шрифтом. Поскольку ни квадратные, ни фигурные скобки в Аде не используются, как не используется и знак «|» (все это метасимволы), никакого специального обозначения для терминалов не предусмотрено. Определение синтаксиса оператора if, взятое из стандарта Ада-95, выглядит так:

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

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

Пример программы «Hellow world» на Аде

Определение синтаксиса Кобола и ПЛ/1

Кобол (COBOL, COmmon Business Oriented Language), язык программирования третьего поколения (первая версия в 1959), предназначенный, в первую очередь, для разработки бизнес-приложений.Разработчиком первого единого стандарта Кобола являлась Грейс Хоппер (бабушка Кобола). К 1997 году активно использовалось около 240 миллиардов строк кода на Коболе. Около 90 % финансовых транзакций в мире обрабатывается кодом на Коболе, и 75 % коммерческой обработки данных написано на Коболе. Общая стоимость используемого в настоящее время коболовского кода оценивается в 2 триллиона долларов США. До сих пор ежегодно пишутся миллиарды новых строк кода на Коболе.

Своеобразная система обозначений, являющаяся примером ранних нотаций, была применена при описании языков Кобол и ПЛ/1. Вот пример — определение формата глагола MOVE в Коболе:

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

Особенности языка Кобол

Пример программы «Hello world » на Коболе

ПЛ/1-(PL/I, Programming Language I — «Язык программирования номер один») — разработанный в 1964 году язык программирования, созданный для научных, инженерных и бизнес-ориентированных вычислений. Он содержит такой широкий набор синтаксических конструкций и встроенных функций, что, вероятно, не существует ни одного компилятора, поддерживающего все возможности языка ПЛ/1. ПЛ/1 поддерживает рекурсию и структурное программирование, и его основная область применения — обработка данных

Основные свойства ПЛ/1

Пример программы «Hello world» на ПЛ/1

Алфавит языка

Первоначальный алфавит ПЛ/1 включал 60 символов:

Была предусмотрена возможность работы и с более ограниченным 48-символьным алфавитом, в который не входили:

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

Источник

Синтаксические диаграммы Вирта

Формальные языки и теория автоматов

Лабораторная работа № 1

Описание языка программирования

Описание языка программирования

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

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

Основными функциями языкового процессора являются:

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

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

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

Определение синтаксиса языка

Разработка языка программирования начинается с определения его синтаксиса. Естественный язык мало пригоден для этой цели, поэтому для точного описания синтаксиса языка программирования нужен некоторый вспомогательный язык. Язык, предназначенный для описания другого языка, называется метаязыком.

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

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

□ форма Бэкуса-Наура и ее различные модификации;

□ синтаксические диаграммы Вирта;

Форма Бэкуса-Наура

Характерной особенностью многих металингвистических форм является наличие в них рекурсии. Рекурсия имеет место в том случае, когда для определения конструкций языков программирования используются металингвистические переменные, обозначающие саму определяемую конструкцию. Рекурсия может быть явной или неявной. Явная рекурсия используется, например, в определении конструкции «двоичное целое». Неявная рекурсия имеет место в случае, когда металингвистическая переменная, обозначающая какую-либо конструкцию, используется на некотором промежуточном шаге определения этой конструкции.

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

□ необязательные элементы синтаксической конструкции заключаются в квадратные скобки ‘[‘ и ‘]’;

□ альтернативные варианты могут в случае необходимости заключаться в круглые скобки для образования многовариантного выбора;

□ элементы синтаксической конструкции, повторяющиеся нуль и более раз, заключаются в фигурные скобки ‘<' и '>‘.

С учетом указанных расширений приведенное ранее определение множества целых чисел можно записать в таком виде:

Оба описания эквивалентны, но второе описание более компактно и естественно. Любая синтаксическая конструкция, полученная с помощью РБНФ, Может быть получена с помощью БНФ и наоборот.

Синтаксические диаграммы Вирта

Синтаксические диаграммы были предложены Никлаусом Виртом для описания синтаксиса языка Pascal и являются удобной графической формой представления РБНФ.

Элементами синтаксических диаграмм Вирта являются: прямоугольники, кружки или овалы, стрелки. В прямоугольниках записываются имена металингвистических переменных, в кружках или овалах – основные символы языка, а стрелки определяют порядок сочетания металингвистических переменных и основных символов языка для образования определяемой синтаксической конструкции. Каждой синтаксической конструкции соответствует одна диаграмма Вирта. Имя определяемой синтаксической конструкции записывается над стрелкой, входящей в диаграмму (точка входа в диаграмму), которая, как правило, располагается в левом верхнем углу. Любой путь от точки входа в синтаксическую диаграмму к выходу (исходящая из диаграммы стрелка) представляет собой цепочку металингвистических переменных и основных символов языка, соответствующую одному из вариантов правой части РБНФ. На рис. 2.1 приведены синтаксические диаграммы, определяющие множество целых чисел.

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

Рис. 2.1. Синтаксические диаграммы для определения множества целых чисел

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

Формальные грамматики и рассмотренные в разд. 2.1 формальные модели не позволяют описать синтаксис языка программирования полностью. Некоторые его аспекты, например контекстные условия, могут быть описаны только семантическими правилами.

Источник

Лекция 7 Синтаксис языков программирования Нотация Бэкуса-Наура и синтаксические диаграммы Вирта

Главная > Документ

Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

Лекция 7


Синтаксис языков программирования


Нотация Бэкуса-Наура и синтаксические диаграммы Вирта

Как уже было сказано в предыдущих лекциях, для определения синтаксиса языков программирования широко применяется нотация, предложенная Дж. Бэкусом и П.Науром.

Определение. Нотация Дж. Бэкуса и П.Наур используют зарезервированные метасимволы «::=» и «|», которые читаются как «является» и «или», определяемые понятия, которые выделяются посредством угловых скобок «» и «», и символы алфавита языка (которые называются терминальными символами). Каждое правило (определение) в этой нотации имеет вид

определяемое понятие ::= серия альтернатив разделённых «|»

Точный смысл нотации будет определён после того, как будет определено понятие грамматики и порождаемого языка. А пока ограничимся тем, что приведём один пример. Так, понятие число в языке НеМо может быть определено 1 посредством следующих трёх правил:

цифра::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Графический формализм для определения синтаксиса языков программирования – синтаксические диаграммы, введённые в активный «оборот» Н. Виртом.

Определение. В нотации синтаксических диаграмм каждое определение представляет собой ориентированны граф с одним входом и одним выходом, в котором вершины – это

или терминальные символы,

или определяемые синтаксические понятия,

или разветвления/соединения для представления альтернатив,

а дуги представляют отношение «следующий синтаксический элемент».

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

Нотацию Бэкуса-Наура легко перевести в синтаксические диаграммы. Для этого, во-первых, надо «избавиться» от вспомогательных метаскобок «[» и «]», «<» и «>»:

всякое использование пары метаскобок «[» и «]» можно заменить парой альтернатив с использованием и без использования их содержимого;

всякое использование пары метаскобок «<» и «>» можно заменить на новый метаэлемент и добавить новое определение

метаэлемент::= пусто | содержимое метаскобок метаэлемент

(где пусто имеет очевидное определение).

Во-вторых, надо каждое правило

определяемое понятие ::= серия альтернатив разделённых «|»

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

Пример преобразования нотации Бэкуса-Наура в синтаксические диаграммы: определение число ::= [знак] цифра <цифра>. Во-первых, избавимся от метаскобок:

сначала от «[» и «]»: число ::= цифра <цифра>| знак цифра <цифра>;

Во-вторых, заменим каждое из получившихся определений на диаграмму:

ССинтаксические диаграммы языка программирования
интаксические диаграммы также легко перевести в нотацию Бэкуса-Наура.

Грамматики, языки и классификация Н. Хомского

«Глокая куздра штеко бодланула бокра и курдячит бокренка»

“Colorless green ideas sleep furiously”

Определение. Грамматика – это четвёрка вида (N, T, R, S), где

N – конечный алфавит нетерминальных символов (или нетерминалов),

T – конечный алфавит терминальных символов (или терминалов),

S – начальный (или стартовый) нетерминалы.

Определение. Каждая грамматика G = (N, T, R, S) определяет некоторый L(G) язык следующим образом. Для любых слов  и  в объединённом алфавите NT

w L w R – одна из продукций из R;

будем писать  G  n  и говорить, что « получается из  в G за n шагов» (где n0),

если n=0 и  совпадает с ,

или n>0 и существует такое слово  в объединённом алфавите NT, что  G  и  G  (n-1) ;

будем писать  G * и говорить, что « получается из  в G», если существует такое n0, что  G  n .

Язык L(G) состоит из всех слов  в алфавите терминальных символов T таких, что S G *. Принято говорить, что грамматика G порождает язык L(G).

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

Регулярные грамматики используют продукции вида nt, ntm и nm где n и m – любые нетерминалы, а t – любой терминал;

контекстно-свободные грамматики используют продукции вида nw, где n – любой нетерминал, а w – любое непустое слово в объединённом алфавите нетерминалов и терминалов;

грамматики со фразовой структурой общего вида используют любые продукции с непустой правой частьюы.

Определение. Грамматики G и G называются эквивалентными (по языку), если их языки совпадают: L(G) = L(G).

ИСинтаксические диаграммы языка программирования
з определения следует, что классификация Н. Хомского не задаёт разбиение всех грамматик на непересекающиеся классы, а представляет собой некоторую «матрёшку» из вложенных классов:

Определение. Язык L называется

со фразовой структурой (или рекурсивно-перечислимым)

Источник

Способы описания синтаксиса языка программирования

Алгоритмы

Свойства алгоритма

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

Пример. Найти max из чисел x, y, z.

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

Алгоритм 1. (Словесное описание)

Если x>=y и x>=z, то положить max:=x и завершить алгоритм
Если y>=x и y>=z, то положить max:=y и завершить алгоритм
Если z>=x и z>=y, то положить max:=z и завершить алгоритм

Алгоритм 2. (Описание на псевдокоде)

max:=x
Если y>max то max:=y
Если z>max тоmax:=z

Определение. Два алгоритма называются эквивалентными, если множества допустимых исходных данных для них совпадают и применение этих алгоритмов к одинаковым исходным данным дает одинаковые результаты.

Способы описания алгоритмов

3. C помощью блок-схем.

Пример. (алгоритм 2, представленный блок-схемой)

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

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

4. C помощью языка программирования.

Язык программирования

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

Синтаксис ЯП определяет правила записи основных конструкций ЯП и устанавливает, какие фрагменты текста программы следует считать неделимыми (например, :=,

Семантика ЯП определяет смысловое значение синтаксических конструкций.

Множество всех лексем образует словарь языка.

Способы описания синтаксиса языка программирования

При описании синтаксиса используются БНФ, РБНФ (разработаны в 1960 году для описания Алгола-60 Джоном Бэкусом и Петером Науром) и синтаксические диаграммы (разработаны Н. Виртом).

1. БНФ (Бэкуса-Наура форма)

условный оператор ::= if логическое условие then оператор
| if логическое условие then оператор1 else оператор2

имя ::= буква | имя буква | имя цифра

В последнем примере нетерминал имя определяется через самого себя. Такое определение называется рекурсивным.

РБНФ (Расширенная БНФ)

Помимо значков ::= и |, используются значки:

< >— 0 или более повторений

условный оператор ::= if логическое выражение then оператор [else оператор ]

вызов процедуры ::= имя [( параметр <, параметр> )]

Синтаксическая диаграмма

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

Архитектура и принцип работы компьютера

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

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

Комментарии в программе

< >и (* *) – могут быть вложенными

Комментарии игнорируются компилятором и предназначены для пояснения текста программы.

Общая структура программы

Правила записи программ

Лексемы языка Pascal

1) Специальные символы

2) Идентификаторы (используются в качестве имен объектов программы).

3) Константные значения

Раздел описаний

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

Раздел описания переменных

var i,j: integer;
s: string;
b: boolean;
r1,r2: real;
c: char;

Раздел описания типов

type int = integer;
IArr = array [1..100] of real;

Оператор присваивания

Оператор присваивания имеет вид:

имя переменной := выражение

Присваивание переменной некоторого начального значения называется инициализацией этой переменной.

Если переменной можно присвоить выражение, то говорят, что они совместимы по присваиванию. Переменная и выражение совместимы по присваиванию:

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

var i: integer;
.
i:=2.0; // неверно!

Для преобразования вещественного в целое следует использовать функции round и trunc.

Операторы ввода/вывода

Оператор вызова процедуры ввода имеет одну из следующих форм:

read(список переменных);
readln(список переменных);
readln;

Оператор вызова процедуры вывода имеет одну из следующих форм:

write(список выражений);
writeln(список выражений);
writeln;

Для перехода на новую строку в процессе вывода можно использовать следующий прием:

const newline = #10;
.
writeln(x, newline, y);

Форматы вывода

Для любых типов:

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

Для вещественного типа:

Вещественные числа в этом формате выводятся в виде с фиксированной точкой.

Неправильный формат вывода игнорируется. Например, если x=14.457, то после

будет выведено 14.46.

Выражения и операции

Выражения

Каждое выражение имеет тип, зависящий от типов входящих в него операндов. Выражение называют арифметическим, если его значением является число. Выражение называют логическим, если его значение имеет логический тип.

Логическое выражение всегда имеет тип boolean.

Тип арифметического выражения определяется типом операнда «старшего» типа: если в выражении есть хотя бы один операнд типа real, то выражение имеет тип real, если нет операндов типа real, но есть операнды типа integer, то выражение имеет тип integer. Исключение составляет операция деления: результатом деления целого на целое является вещественное.

Не все типы совместимы в выражении: к примеру, нельзя сложить целое и строку, нельзя из строки вычесть символ.

Операции

Таблица приоритетов операций языка Pascal

Логические операции

Простые: x>0 или 2*2=4

Составные: состоят из простых + логические операции (and, or, not, xor)

(x>=3) and (x 5) = not ((x>=3) or (x B) and (A C) and (A x1) and (x y1) and (y x2) or (y y2);
OnTheBoundary:=not Inside and not Outside;

Стандартные функции

Стандартные функции в Dephi

Требуется подключение модуля Math:uses Math;

power(x,y)x^у
arccos(x)
arcsin(x)
sec(x)
cosec(x)
tan(x)
DivMod(x,y,d,m)d:=x div y; m:=x mod y;
InRange(x,min,max)min a then
min:=a
else
min:=b;

Пример. Упорядочить значения в a, b по возрастанию.

if a>b then
поменять значения местами

Составной оператор

begin
операторы
end

Необходимость составного оператора: составной оператор объединяет несколько операторов в один:

if a>b then
begin
v:=a;
a:=b;
b:=v;
end;

Пример.

case Month of
4,6,9,11: DayInMonth:=30;
2: DayInMonth:=28;
else DayInMonth:=31;
end.

Циклы while, repeat и for

Оператор цикла с предусловием (цикл ПОКА)

while B do
оператор

где оператор образует тело цикла, B является логическим выражением.

Семантика оператора while задается следующей блок-схемой:

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

Сравнение while и repeat

Оператор цикла с параметром

for x:=x1 to x2 do
оператор

for x:=x2 downto x1 do
оператор

где переменная x называется параметром цикла, x1 и x2 – выражения совместимого с x типа.

Важно! Выражения x1 и x2 вычисляются один раз до цикла.

for i:=1 to n do
i:=i-1; // ошибка!

for i:=1 to n do
read(i); // ошибка!

for i:=1 to n do
for i:=1 to m do // ошибка!

Определение. Инвариант цикла – это предикат, который истинен перед выполнением цикла и после каждой его итерации. Например, если находится сумма чисел, то инвариант цикла – сумма уже введенных чисел. Если находится минимум, то инвариант цикла: в min – минимальные из уже введенных. Инвариант цикла служит для доказательства правильности алгоритма.

Зацикливание

repeat
write(i);
until False;

while True do
write(i);

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

Пример 1. Сумма n чисел.

s:=0;
for i:=1 to n do
s:=s+xi

Пример 2. Произведение n чисел.

p:=1;
for i:=1 to n do
p:=p*xi

Пример 3. n!!=n*(n-2)*(n-4)*. *2 (или 1)

p:=1;
x:=n;
while x>=2 do
begin
p:=p*x;
x:=x-2;
end;

Пример 4. Сколько нечетных среди 10 введенных.

c:=0;
for i:=1 to n do
begin
read(x);
ifx mod 2 <> 0 then
c:=c+1;
// if Odd(x) then Inc(c); // вариант
end;

Пример 5. Защита от неверного ввода.

repeat
write(‘Введите x (>0): ‘);
readln(x);
if x 0;

Пример 6. Табулирование функции f(x) на отрезке [a,b] в точках, разбивающих [a,b] на N частей.

assert(N>0);
h:=(b-a)/N;
x:=a;
for i:=0 to N do
begin
writeln(x:5:2, f(x):10:4);
x:=x+h;
end;

Пример 7. Вывод 10 первых степеней двойки.

x:=10;
for i:=1 to 10 do
begin
writeln(i:2,x:5);
x:=x*2;
end;

Пример 8. Вывод всех двузначных чисел, кратных 5.

x:=1;
while x 0 do
begin
S:=S + m mod 10;
m:=m div 10;
end;

Алгоритм Евклида: НОД (А,В) = НОД (В, А mod B); НОД (А,0)=А

read(A,B);
repeat
C:=A mod B;
A:=B;
B:=C
until C=0;
NOD:=A;

Замечание. Доказательство того, что цикл завершится: С уменьшается на каждом шаге, оставаясь >=0.

Пример 12. Найти max из N введенных чисел.

Алгоритм 1. max:= первое введенное

read(x);
max:=x;
// Инвариант I: max = максимальное из всех введенных
for i:=2 to N do
begin
read(x);
if max:=x then
max:=x
// I выполняется
end;

for i:=1 to N do
.

Пример 13. Разложение числа на простые множители.

Алгоритм на псевдокоде

цикл
если х делится на i, то
<
вывод i
x:=x/i
>
иначе увеличить i на 1
до х=1

Алгоритм на Паскале

read(x);
assert(x>1);
i:=2;
repeat
if
x mod i = 0 then
begin

write(i,’ ‘);
x:=x div i;
end
else
Inc(i);
until x=1;

read(x);
S:=0;
for i:=0 to n do
begin
read(a);
S:=S*x+a;
end;

n+1 операций «+» и n+1 операций «* «

Примеры на суммирование рядов

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

x:=x0;
S:=x;
for i:=2 to n do
begin
x:=f(x);
S:=S+x
end;

Пример 15. Вычислить сумму
Синтаксические диаграммы языка программирования

x:=1;
S:=x;
for i:=2 to n do
begin
x:=x*y/i;
S:=S+x;
end;

Если существует предел суммы
Синтаксические диаграммы языка программирования

Пример 16. Знакопеременный ряд
Синтаксические диаграммы языка программирования
xi = xi-1 + 0.1
zi=(-1) i
zi=-zi-1

z:=1;
s:=0;
x:=1; // эта часть может меняться
for i:=0 to n do
begin
s:=s+z*x;
x:=x+0.1; // эта часть может меняться
z:=-z;
end;

Пример 17. Вычислить сумму
Синтаксические диаграммы языка программирования

for i:=0 to n do
begin

p:=p*y;
s:=s+p/i;
end;

Пример 18. Метод половинного деления

Метод окаймления

«Заморозим» А и составим алгоритм при фиксированном А.

for A:=2 to 10do
begin
p:=1;
for i:=1 tok do
p:=p*A;
writeln(p);
end.

Разморозим А и окаймим данный участок цикла по А от 2 до 10.

Задача. Вывести все простые числа от 100 до 999.

Переборные задачи

Задача. Вывести все тройки целых положительных a, b, c 2 +b 2 =c 2
Решение 1. (В лоб)

for a:=1 to 99 do
for b:=1 to 99 do
for c:=1 to 99 do
if a*a+b*b=c*c then
writeln(a:3;b:3;c:3)

Решение 1а.

for a:=1 to 99 do
for b:=a+1 to99 do
for c:=b+1 to 99 do
ifa*a+b*b=c*c tnen
writeln(a:3;b:3;c:3)

Решение 1б.

for a:=1 to 99 do
for b:=a+1 to99 do
c:=round(sqrt(a*a+b*b));
if a*a+b*b=c*c tnen
writeln(a:3;b:3;c:3)

Но! Нельзя заниматься преждевременной оптимизацией!

Процедуры

Пример. Составить процедуру вычисления среднего арифметического и среднего геометрического А и В. С ее помощью найти среднее арифметическое и среднее геометрическое пар A,B; A,C; B,C.

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

procedure Mean(A,B: real; var MA,MG: real);
// A,B-входные параметры
// MA,MG-выходные параметры
begin
assert(A>0); // предусловия процедуры
assert(B>0);
MA:=(A+B)/2;
MG:=sqrt(A*B);
end;

var A,B,C: real;
MA1,MA2,MA3,MG1,MG2,MG3: real;

begin
readln(A,B,C);
Mean(A,B,MA1,MG1);
Mean(A,C,MA2,MG2);
Mean(B,C,MA3,MG3);
writeln(MA1,MG1);
writeln(MA2,MG2);
writeln(MA3,MG3);
end.

Оператор вызова процедуры

имя[(список фактических параметров)]

Количество и типы фактических параметров при вызове процедуры должны соответствовать количеству и типам формальных параметров.

Функции

Пример. Функция
Синтаксические диаграммы языка программирования

function sign(x: real): integer;
begin
if x 0 then
sign:=1
else sign:=0
end;

Для того, чтобы функция вернула значение необходимо в её теле имени функции присвоить некоторое значение. Имя функции в этом контексте ведет себя как обычная переменная, но имя функции нельзя использовать в правой части оператора присваивания в качестве значения этой переменной.

vars,a: real;
begin
s:=sign(-3);
writeln(s);
read(a);
writeln(sign(a)+sign(1));
end.

Для сравнения реализуем вычисление sign в виде процедуры.

procedure CalcSign(x: real; varsign: integer);
begin
if x 0 then
sign:=1
else sign:=0
end;

vara: real;
s,s1,s2: integer;

begin
Calcsign(-3,s);
writeln(3);
read(a);
Calcsign(a,s1);
Calcsign(1,s2);
writeln(s1+s2);
end.

Переменная Result

В Delphi и FreePascal неявно определена переменная Result, присваивание которой равносильно и хранит результат функции.

function Sum(n: integer): integer;
var i: integer;
begin
Result:=0;
for i:=1 to n do
Result:=Result+i // Inc(Result,i)
end;

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

Способы передачи параметров

Перегрузка имен подпрограмм

Перегрузка имен подпрограмм имеется в Delphi, FreePascal и отсутствует в Turbo Pascal.

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

procedure swap(var a,b: integer); overload;
.
procedure swap(var a,b: real); overload;
.

Это явление называется полиморфизмом.

Полиморфизм – использование одного имени (одного знака операции) для выполнения родственных действий.

writeln(a,b) – полиморфная процедура: параметры различных типов.

a+b – операция «+» используется для различных типов.

Тонкости перегрузки

procedure A(i: integer); overload;
procedure
A(i: real); overload;

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

Параметры по умолчанию

Параметры по умолчанию имеются в Delphi, FreePascal и отсутствуют в Turbo Pascal.

procedure DoOperation(a,b: real; var res: real; op: char=’+’);
begin
case op of
’+’: res:=a+b;
’-’: res:=a-b;
.
end;
end.
.
DoOperation(2,3,res);
DoOperation(2,3,res,’*’);

Правило. Параметры по умолчанию всегда должны идти последними.

Предварительное объявление подпрограмм

procedure p(i: integer); forward; // Предварительное объявление. p будет определена далее

procedure q;
begin
p(3); // можно вызывать
end;

procedure p(i: integer);
begin
.
end;

Методы разработки программ

Источник

Видео

Информатика, 10-й класс, Языки программирования. Синтаксические диаграммы

Информатика, 10-й класс, Языки программирования. Синтаксические диаграммы

Создаем свой ЯЗЫК ПРОГРАММИРОВАНИЯ. Лексер, Парсер, Абстрактное синтаксическое дерево (AST)

Создаем свой ЯЗЫК ПРОГРАММИРОВАНИЯ. Лексер, Парсер, Абстрактное синтаксическое дерево (AST)

Основы программирования. Синтаксис и семантика

Основы программирования. Синтаксис и семантика

Синтаксические модели - Екатерина Лютикова

Синтаксические модели - Екатерина Лютикова

Языки программирования и теории компиляций 5. Синтаксическое дерево разбора (AST). Паттерн Visitor

Языки программирования и теории компиляций 5. Синтаксическое дерево разбора (AST). Паттерн Visitor

Синтаксис языка программирования Python.

Синтаксис языка программирования Python.

Синтаксическое дерево

Синтаксическое дерево

Разработка парсеров с помощью ANTLR

Разработка парсеров с помощью ANTLR

Лекция 3. Синтаксический анализ (Языки программирования и компиляторы)

Лекция 3. Синтаксический анализ (Языки программирования и компиляторы)

Принципы и интерпретация динамических языков программирования | 2. Универсализация синтаксиса

Принципы и интерпретация динамических языков программирования | 2. Универсализация синтаксиса
Поделиться или сохранить к себе:
Добавить комментарий

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