А.А. Вылиток - Металингвистические формулы и синтаксические диаграммы (1113679), страница 3
Текст из файла (страница 3)
Умножение имеет большийприоритет, чем сложение, поэтому в выражении a b c операнд bотносится к операции умножения и эквивалентное выражение соскобками будет таким: a (b c). В выражении a b c операнд bотносится к левой операции, т. е. к «минусу», а не к «плюсу» (в силулевой ассоциативности операций и , имеющих одинаковыйприоритет), и это выражение эквивалентно выражению (a b) c.Лево-ассоциативные операции группируются с помощью скобокслева направо: a b c dэквивалентно (( a b ) c) d .Построить БНФ для арифметических выражений в алфавите { +, –,*, / , ^, a, (, ) }, где a символизирует операнд, ^ — операциювозведения в степень. В БНФ должен отражаться естественныйприоритет операций, правая ассоциативность операции возведения встепень и левая ассоциативность остальных операций.23. Палиндромом называется цепочка, которая читаетсяодинаково слева направо и справа налево.
Например, цепочки a, aba,abba являются палиндромами. Пустая цепочка также являетсяпалиндромом. Построить БНФ и СД для понятия «палиндром» валфавите {a, b}.- 15 -24. Если из арифметического выражения удалить все символы,кроме скобок, получим скобочную систему. Пустая цепочка такжеявляется скобочной системой. Построить БНФ и СД для скобочныхсистем.25.
Назовем неделимой скобочную систему, которую нельзяпредставить в виде сцепления двух других скобочных систем.Например, скобочная система((()())()) является неделимой, а(()())() не является. Построить БНФ для неделимой скобочнойсистемы.РешениеЗаметим, что если произвольную скобочную систему заключитьв объемлющие скобки, то получим неделимую скобочную систему.Поэтому БНФ для неделимой скобочной системы определяется так:неделимая скобочная система ::= ( скобочная система )Теперь опишем понятие скобочная система.
Простейшейскобочной системой является пустая цепочка. Непустая скобочнаясистема может быть представлена как сцепление неделимойскобочной системы и произвольной скобочной системы.Следовательно, БНФ для произвольной скобочной системы можноопределить так:скобочная система ::=( скобочная система ) скобочная система | пусто26. Построить СД, описывающуюсистемы.неделимые скобочные27. Глубиной скобочной системы называется максимальныйуровень вложенности скобок. Например, система (()(())()())имеет глубину 3, а система ()() глубину 1. Глубина пустойсистемы равна нулю.
Описать с помощью БНФ и СД скобочныесистемы с глубиной не более трех.- 16 -28. Построить БНФ и СД для скобочных систем с глубиной неменее двух.29. Протяжением скобочной системы называется количествонеделимых скобочных систем, сцепление которых дает даннуюсистему. Например, система ()(()())() имеет протяжение 3.Протяжение пустой системы равно нулю. Построить БНФ и СД дляскобочных систем с протяжением от трех до пяти.30. Построить БНФ и СД для скобочных систем с протяжениемне менее четырех.31.
Шириной скобочной системыназывается максимальноепротяжение среди всех подсистем, входящих в данную систему.Например, ширина системы ()(()()()) равна трем, а ширина()(()) равна двум. Ширина пустой системы равна нулю.Построить БНФ и СД для скобочных систем с шириной не болеетрех.32. Построить БНФ и СД для скобочных систем с шириной неменее двух.33. ПостроитьБНФиСДудовлетворяющих ограничениям:дляскобочныхсистем,(а) глубина и ширина не превосходят двух;(б) глубина не более двух, а ширина не менее двух;(в) глубина не менее двух, а ширина не более двух;(г) глубина и ширина не менее двух;(д) протяжение не более двух, ширина не менее трех;(е) протяжение, глубина и ширина не менее двух.34.
Описать с помощью БНФ понятие «пассажирский поезд». Вначале поезда находится электровоз (Э). Далее следуют вагоны.- 17 -Вагоны бывают плацкартные (П) и купейные (К). В поезде должнобыть одинаковое количество купейных и плацкартных вагонов.РешениеПоезд представляет собой сцепление электровоза (символа Э) ипоследовательностивагонов.Последовательностьвагоновобозначим с помощью метапеременной состав.пассажирский поезд ::= Э составРазобьем состав (т.е. последовательность вагонов) на непустыеучастки так, что в каждом участке купейных и плацкартных вагоновпоровну и никакой участок нельзя представить в виде сцеплениядвух меньших участков, в которых вагонов обоих типов поровну.Например, состав КПППККККПКПП разбивается на три участка: КП,ППКК, ККПКПП.
Каждый такой участок можно рассматривать какнеделимую скобочную систему со скобками К и П. Если участокначинается символом К и заканчивается символом П, то онпредставляет собой неделимую скобочную систему, в которойсимвол К – открывающая скобка, а П – закрывающая. Обозначимтакой участок метапеременной участок КП . Если участокначинается символом П и заканчивается символом К, то онпредставляет собой неделимую скобочную систему, в которойсимвол П – открывающая скобка, а К – закрывающая. Обозначимтакой участок метапеременной участок ПК .
Состав можнорассматривать как последовательность участков двух видов:состав ::= участок КП состав |участок ПК состав |пустоОсталось определить участки двух видов аналогично тому, как этоделалось в упражнении 25 для неделимых скобочных систем.участок КП::= К система КП Псистема КП::= К система КП П система КП | пустоучасток ПК::= П система ПК Ксистема ПК::= П система ПК К система ПК | пусто- 18 -35. Описать понятие «пассажирский поезд» из упражнения 34 спомощью БНФ, содержащей всего три альтернативы.36. Построить СДупражнения 34.дляпонятия«пассажирский поезд» из37.
Описать с помощью БНФ и СД понятие «пассажирскийпоезд». Поезд состоит из тепловоза (Т) и вагонов. Вагоны бываютплацкартные (П) и купейные (К). В поезде должно быть неравноеколичество купейных и плацкартных вагонов.38. Описать с помощью БНФ и СД понятие «пассажирскийпоезд». Поезд состоит из электровоза (Э) и вагонов. Вагоны бываютплацкартные (П) и купейные (К). В поезде купейных вагонов должнобыть больше, чем плацкартных.39. Построить БНФ и СД для «товарных поездов». Поездсостоит из тяги, за которой следуют вагоны.
Тяга — это один илинесколько тепловозов (Т). Вагоны бывают двух типов: цистерны (Ц)и рефрижераторы (Р). На каждый рефрижератор в поездеприходится по меньшей мере две цистерны.40. Построить нормальный алгоритм Маркова (НАМ), областьприменимости которого относительно алфавита {a, b} совпадает смножеством слов, описываемых с помощью БНФ:слово::= a окончаниеокончание::= a окончание | b окончание | пусто41. По заданному НАМ построить БНФ, описывающую областьприменимости данного НАМ относительно алфавита {a, b}. ab b a a b- 19 -42. Построить несамоприменимый НАМ, область применимостикоторого относительно алфавита {a, b} задается СД:baслово::=aba43. Построить самоприменимый НАМ, область применимостикоторого относительно алфавита {a, b} задается БНФ:слово::= a слово b | ab44.
Построить БНФ, описывающую множество слов, в которыезаданный НАМ переводит слова вида |||…||#||…|||. |# | # 45. Построить самоприменимый НАМ, область применимостикоторого состоит из слов четной длины в алфавите {a, b}. ПостроитьБНФ и СД для области применимости.- 20 -Литература1.
И.А. Волкова, А.А. Вылиток, Т.В. Руденко. Формальныеграмматики и языки. Элементы теории трансляции. — М.: МГУ,2009.2. В.Г. Абрамов, Н.П. Трифонов, Г.Н. Трифонова. Введение в языкПаскаль. — М.: Наука, 1988.3. В. Н. Пильщиков, В. Г. Абрамов, А. А. Вылиток, И. В. Горячая.Машины Тьюринга и алгоритмы Маркова. Решение задач. — М.:МГУ, 2006.4. В.Г. Абрамов, Н.П. Трифонов, Г.Н. Трифонова. Введение в языкПаскаль.
— М.: КНОРУС, 2011.- 21 -Содержание1. Языки и метаязыки ..................................................................... 32. Металингвистические формулы ................................................ 43. Синтаксические диаграммы ....................................................... 74. Упражнения................................................................................. 9Литература ...................................................................................... 21- 22 -.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
