А.А. Вылиток - Металингвистические формулы и синтаксические диаграммы (1113679)
Текст из файла
Московский государственный университет им. М.В. ЛомоносоваФакультет вычислительной математики и кибернетикиА.А. ВылитокМеталингвистические формулыи синтаксические диаграммы(Учебно-методическое пособие для студентов 1 курса)Москва2012УДК 519.7 (075.8)ББК 22.18я73В92Печатается по решениюРедакционно-издательского совета факультетавычислительной математики и кибернетики МГУ им. М.В. ЛомоносоваРецензенты:доцент кафедры системногопрограммирования ВМК МГУпрофессор кафедры алгоритмическихязыков ВМК МГУКузьменкова Е.А.Соловьев С.Ю.Вылиток А.А.В92 Металингвистические формулы и синтаксические диаграммы:Учебно-методическое пособие. - М.: Издательский отдел ФакультетаВМК МГУ им. М.В.
Ломоносова (лицензия ИД №05899 от 24.09.2001 г.);МАКС Пресс, 2012. – 24с.ISBN 978-5-89407-484-9ISBN 978-5-317-04154-0Учебно-методическое пособие «Металингвистические формулы исинтаксические диаграммы» предназначено для студентов 1 курса факультетаВМК МГУ им. М.В. Ломоносова.
В пособии рассматриваются два способаописания синтаксиса языков: металингвистические формулы и синтаксическиедиаграммы. Предложен набор задач и примеры их решения.УДК 519.7(075.8)ББК 22.18я73Учебно-методическое пособиеВЫЛИТОК Алексей АлександровичМЕТАЛИНГВИСТИЧЕСКИЕ ФОРМУЛЫ И СИНТАКСИЧЕСКИЕ ДИАГРАММЫ19992, ГСП-2, Москва, Ленинские Горы, МГУ им. М.В. Ломоносова, 2-й учебный корпусISBN 978-5-89407-484-9ISBN 978-5-317-04154-0 Вылиток А.А. Факультет вычислительной математики икибернетики МГУ им. М.В. Ломоносова, 20121. Языки и метаязыкиОбработка данных с помощью компьютеров основана наиспользовании искусственных языков, таких как языкипрограммирования,управлениязаданиями,форматированиядокументов, протоколы связи и другие специальные языки.Каждый язык имеет три составляющие: алфавит, синтаксис исемантику. Алфавит — это фиксированный набор символов.Синтаксис определяет, по каким правилам из символов образуютсятексты.
Семантика — набор правил истолкования, позволяющих потексту понять его смысл.Рассмотрим язык арифметических выражений. В его алфавитвходят цифры, скобки, знаки арифметических операций + , – , * ,/, означающие соответственно сложение, вычитание, умножение иделение. Опишем способ образования текстов на этом языке, вводявспомогательные понятия для обозначения частей выражения.Простымвыражением,илитермом,будемназыватьпоследовательность цифр, т.е. число, а также любое выражение,заключенноевскобки.Слагаемоеопределимкакпоследовательность термов, соединенных операциями умножения иделения.Наконец, выражение — это последовательностьслагаемых, соединенных операциями сложения и вычитания.
Передпервым слагаемым может стоять знак минус. Смысл выражения —это его значение, которое вычисляется по математическим правиламс учетом старшинства операций и скобок.Язык арифметических выражений мы описали с помощьюестественного языка. Язык, используемый для описания другогоязыка, называется метаязыком. В качестве метаязыка можноиспользовать естественный язык, однако он не вполне удобен дляточного описания синтаксических конструкций искусственныхязыков, так как содержит двусмысленности, метафоры и т.п. Дляописания синтаксиса был создан специальный метаязык —металингвистические формулы Бэкуса-Наура1, или, сокращенно,язык БНФ.1Джон Бэкус, Петер Наур – учёные в области информатики, авторы данной нотации.-3-2.
Металингвистические формулыБудем называть цепочкой последовательность из символовалфавита. Сцеплением двух цепочек будем называть результатприписывания второй цепочки в конец первой.Описание на языке БНФ представляет собой набор формул.Формулы описывают способ формирования цепочек, являющихсясинтаксически правильными текстами. В формулы входятметапеременные исимволы алфавита. Символы алфавитасоответствуют элементарным понятиям языка. Например, символ +в языке арифметических выражений означает операцию сложения.Метапеременные соответствуют более сложным понятиям языка.
Кпримеру, понятие «выражение» языка арифметических выраженийможно обозначить с помощью метапеременной выражение. Длязаписи метапеременных используются курсивный шрифт и угловыескобки.Формула БНФ состоит из левой и правой частей, разделенныхсимволом ::=, который обычно читается как «есть по определению».В левой части находится метапеременная, означающая определяемоепонятие, в правой части – комбинации метапеременных, символовалфавита и некоторых специальных символов.
Приведем формулудля понятия «число 5».число 5::= 5Теперь, используя сцепление символов 1, 2 и 5 в цепочку,определим более сложное понятие – «число 125».число 125::= 125Мы можем использовать в правой части формулы сцеплениесимволов алфавита и метапеременных.
Например, определить число9125125 можно как сцепление символа 9 и двух чисел 125.число 9125125::= 9 число 125 число 125-4-Сложное понятие может состоять из нескольких более простыхпонятий –альтернатив. В БНФ альтернативы разделяютсявертикальной чертой. Опишем понятие «цифра».цифра::= 0|1|2|3|4|5|6|7|8|9Теперь, с помощью сцепления цифр, можно определить число издвух знаков (цифр).число из двух знаков::= цифра цифраДанная формула выражает множество цепочек, состоящих издвух цифр: 00, 01, 02,…, 99.Если к числу из двух знаков приписать еще одну цифру, получимчисло из трех знаков.число из трех знаков::= число из двух знаков цифраПонятно, что число из n знаков можно описать через число из n−1знаков, приписывая к нему еще одну цифру.Зададимся теперь вопросом, как описать с помощью БНФ все nзнаковые числа для всех натуральных n.
Мы не сможем выписатьотдельную формулу для каждого n, так как множество натуральныхчисел бесконечно, а число формул БНФ должно быть конечным.Заметим, что если к некоторому числу приписать цифру, тополучится новое число. Начать процесс приписывания можно сэлементарных чисел, являющихся цифрами. Таким образом,получаем следующую БНФ для множества всех чисел.число::= цифра | число цифраЗдесь понятие числа определяется через само себя – такоеопределение называется рекурсивным. В рекурсивном определениидолжна быть хотя бы одна альтернатива, не содержащаяопределяемое понятие, иначе получится замкнутый круг.
В БНФ дляпонятия число такой альтернативой является первая альтернатива –цифра .-5-Убедимся, что все числа описываются данной БНФ.Доказательство проведем индукцией по количеству знаков в записичисла. Очевидно, что число из одного знака входит в множествоцепочек, определяемых метапеременной число. Пусть числа из nзнаков (n>0) входят в множество цепочек для понятия число.Тогда сцепление метапеременныхчисло цифра определяетмножество цепочек, являющихся числами из n+1 знака.Следовательно, все числа определяются метапеременной число.Существует способ определить понятие число без использованиярекурсии.
Для этого в БНФ используется итерация. Итерациейназывается последовательность метапеременных и символовалфавита, заключенная в фигурные скобки. Фигурные скобкииграют служебную роль и означают, что последовательность,заключенная в эти скобки, может повторяться несколько раз илиотсутствовать. С использованием итерации БНФ для числа выглядиттак:число::= цифра { цифра}Дадим определение с помощью БНФ понятию числа в«единичной» системе счисления.
В этой системе числапредставляются в виде последовательности палочек (или единиц).единичное число::= {1}Ноль представляется пустой последовательностью. Дляобозначения пустой цепочки в БНФ будем использовать пусто.Приписывание пустой цепочки слева или справа к произвольнойцепочке x дает снова цепочку x. Другое определение единичногочисла, с помощью рекурсии, выглядит так:единичное число::= единичное число 1 | пустоКроме фигурных скобок особую роль в БНФ играютпрямоугольные скобки: последовательность, заключенная в нихможет либо отсутствовать, либо присутствовать ровно один раз.Опишем понятие целое число. Перед целым числом может стоятьзнак минус.-6-целое число::= [−] число { число}Опишем с помощью БНФ более сложное понятие – выражение.выражение::= [−] слагаемое {знак + или − слагаемое}знак + или − ::= + | −слагаемое::= терм {знак * или / терм}знак * или / ::= * | /терм::= число | ( выражение )В данном определении есть косвенная рекурсия: выражениеопределяется через слагаемое, слагаемое – через терм, терм – черезвыражение.
Полностью избавиться от рекурсии при описаниивыражения нельзя. Доказательство существования языков, вописании которых нельзя обойтись без рекурсии, можно найти в [1].3. Синтаксические диаграммыСинтаксическая диаграмма (СД) представляет собой графическийспособ описания языка. Элементами диаграммы являютсяпрямоугольники и овалы с надписями, соединенные стрелками. Впрямоугольниках записываются названия метапеременных, в овалах– основные символы. В диаграмме есть одна входная стрелка (неисходящая из какого-либо элемента) и одна выходная (не входящаяв какой-либо элемент). Входная и выходная стрелки означаютсоответственно начало и конец синтаксического определения.Приведем диаграмму для понятия число 5.
Само определяемоепонятие будем, как и в случае БНФ, заключать в угловые скобки иотделять от синтаксического определения знаком ::= .число 5::=5Диаграмма для числа 125 будет содержать три овала, по одномуна каждую цифру.число 125::=125-7-Покажем на примере понятия цифра, как с помощью диаграммыизображаются альтернативы.цифра::=0123456789Опишем теперь понятие «число» с помощью СД.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
