А.А. Вылиток - Металингвистические формулы и синтаксические диаграммы (1113679), страница 2
Текст из файла (страница 2)
В ней будетиспользовано вспомогательное понятие «цифра», изображенное ввиде прямоугольника.число::=цифраПодставим вместо прямоугольника соответствующую диаграммуи получим СД для понятия «число», не содержащуювспомогательных понятий (метапеременных).число::=0123456789Существуют языки, которые невозможно описать, не используя вдиаграмме вспомогательных понятий. Рассмотрим, к примеру, язык,цепочки которого состоят из букв a и b, причем сначала в цепочкеследуют n букв a (n0), а за ними столько же букв b: ab, aabb,aaabbb и т.д. Пустая цепочка тоже принадлежит данному языку(случай n=0). Определим понятие «слово» для данного языка спомощью СД.слово::=aсловоbПопытаемся устранить рекурсию – построим СД, в которой нетвспомогательного понятия (метапеременной) «слово»:слово::=ab-8-Однако полученная диаграмма описывает другой язык – в егословах количество букв a может отличаться от количества букв b.Опишем с помощью СД понятие «выражение».+−−слагаемоевыражение::=*/термслагаемое::=числотерм::=(выражение)Как металингвистические формулы, так исинтаксическиедиаграммы используются для описания синтаксиса языковпрограммирования (см., например, [2]).
Синтаксические диаграммыобеспечивают большую наглядность. Преимущество БНФ в том, чтоони могут использоваться в системах автоматизированнойобработки языков.4. УпражненияВ данном разделе приводятся упражнения для развития навыковработы с БНФ и СД, а также задачи, связывающие описание языковс теорией алгоритмов [3]. К некоторым задачам даются образцырешений.Вусловияхотдельныхзадачопределяютсявспомогательные понятия, которые могут использоваться и впоследующих задачах.-9-1.Перечислить все цепочки, которые удовлетворяют понятию«слово», описанному с помощью БНФ:слово::= корень суффикскорень::= сад | сурсуффикс::= ик | окРешениеИскомые цепочки получаются сцеплением двух цепочек: перваядолжна удовлетворять понятию корень, вторая – понятию суффикс.Понятию корень удовлетворяет множество цепочек {сад, сур}, апонятиюсуффиксудовлетворяетмножество{ик,ок}.Всевозможные сцепления цепочек из первого множества сцепочками из второго множества дают такие слова: садик, садок,сурик, сурок.2.Перечислить все цепочки, которые удовлетворяют понятию«слово», заданному СД:рпобирслово::=задача3.С помощью БНФ описано понятие «поезд».
Буква П означаетпаровоз, буква В – вагон.поезд::= тяга составтяга::= Псостав::= В состав | пустоУдовлетворяет ли цепочка ПВВ понятию поезд ?РешениеДанная цепочка является сцеплением двух цепочек П и ВВ.Первая непосредственно удовлетворяет понятию тяга. Покажем,что ВВ удовлетворяет понятию состав, тогда ПВВ удовлетворяет- 10 -понятию поезд. Сначала покажем, что цепочка В удовлетворяетпонятию состав. Действительно, так как пустая цепочканепосредственно удовлетворяет понятию состав (согласно второйальтернативе в формуле), то сцепление В с пустой цепочкой, т.е. ссоставом, также удовлетворяет понятию состав (согласно первойальтернативе в формуле). Далее, в цепочке ВВ первая буква Всоответствует вхождению в первую альтернативу, а вторая буква В,по доказанному, удовлетворяет понятию состав.
Следовательно,сцепление В с составом (т.е. с еще одной В) дает состав. Итак, П– это тяга, ВВ – состав, а ПВВ – поезд.4.Дана БНФ для понятия «поезд, следующий на юг»:поезд на юг::= ПВ{ВВ}Какие из перечисленных ниже поездов следуют на юг?(а) ПВ ;(б) ПВВ ;(в) ПВВВВВ ;(г) ППВВВ.5.Дана СД для понятия «поезд, следующий на север». Буква Цозначает цистерну, Э означает электровоз.Цпоезд на север::=ЦЭЦКакие из перечисленных ниже поездов следуют на север?(а) ЭЦ ;6.(б) ЭЦЦ ;(в) ЭЦЦЦЦЦ ;(г) ЭЦЦЦЦ.Обезьяний язык с помощью БНФ описывается так:фраза::= слово @ фраза | словослово::= слог слог | слово слогслог ::= слог ba | слог bb слог | aКто из перечисленных нижезамаскированным под обезьяну?ораторов- 11 -являетсяшпионом,Бабуин: ababbaa@abaabba@aaШимпанзе: ababa@abba@abbaaaaГорилла: abaa@abbaaa@aabbaa7.Язык «пляшущих человечков» задается БНФ:предложение ::=фраза ::=Какие из приведенныхчеловечков» фальшивые?фраза|предложениенижеписем|нафразаязыке«пляшущиха)б)в)8.Описать с помощью БНФ и СД понятие «электричка».Электричка состоит из простых (В) и тяговых (Т) вагонов.
Простые итяговые вагоны чередуются. Первый и последний вагоны – тяговые.9.В лесу планируется забег зверей на длинную дистанцию. Взабеге участвуют зайцы (З), волки (В) и медведи (М). Пообъективным причинам заяц не может бежать рядом с волком.Помогите организаторам соревнований расположить зверей настартовой линии. Построить БНФ и СД допустимых расположений.РешениеБНФ:старт ::= M старт | З не волк | В не заяц | M | З | Вне волк::= M старт | З не волк | М | Зне заяц::= M старт | В не заяц | М | В- 12 -СД:Встарт::=МЗ10. Описать с помощью БНФ с минимальным числом альтернативязык, состоящий из цепочек длины 5 в алфавите {a, b}.11.Описать с помощью СД с минимальным числом дуг язык,состоящий из цепочек длины 5 в алфавите {a, b}.12.
Описать с помощью БНФ и СД понятие «товарный поезд».Поезд состоит из тяги и состава. Тяга содержит от одного до трехэлектровозов (Э). В состав входят крытые вагоны (К) и платформы(П). Между двумя соседними крытыми вагонами находятся какминимум две платформы.13.
Описать с помощью БНФ и СД понятие «грузовой поезд».Поезд состоит из тяги и состава. Тяга содержит ненулевое четноечисло тепловозов (Т). В состав входят думпкары (Д) и хопперы (Х).В поезде может встречаться не более трех думпкаров подряд.14. Описать с помощью БНФ и СД понятие «пассажирскийпоезд». Поезд состоит из тяги и состава. Тяга содержит нечетноечисло электровозов (Э). В состав входят вагоны (В) и рестораны (Р).В поезде может быть не более трех ресторанов.15. Описать с помощью БНФ и СД понятие «скорый поезд».Поезд состоит из тяги и состава. Тяга состоит из двух электровозов(Э). В состав входят обычные вагоны (В) и рестораны (Р). Двапоследних вагона поезда одновременно не могут быть ресторанами.16.
Описать с помощью БНФ и СД понятие «пассажирскийпоезд». Поезд состоит из тяги и состава. Тяга состоит из одного- 13 -электровоза (Э). В состав входят купейные (К) и плацкартные (П)вагоны. В поезде должно быть четное число плацкартных вагонов.17.Построить БНФ и СД для понятия «периодическая дробь».Примеры дробей: 0.5, 1.(3), 5. 34656(45665).18. Университет состоит из факультетов. Факультеты состоят изкафедр и лабораторий. Лаборатории состоят из сотрудников (С).Кафедры состоят из преподавателей (П).
Например, университет издвух факультетов, в первом из которых одна кафедра с тремяпреподавателями, а во втором одна лаборатория с однимсотрудником и одна кафедра с двумя преподавателями, можноописать с помощью такой структуры: (((ППП))((С)(ПП))). Внешниескобкисоответствуют университету, наиболее вложенные –кафедрам и лаборатории, скобки второго уровня вложенностисоответствуют факультетам. Построить БНФ и СД для описаниявсех возможных структур университета.19.
Определим понятие функциональная запись выражения.Функциональной записью выражения, состоящего из одной цифры,является эта цифра. Функциональной записью выражения А op B,где op – операция, является запись op(A’,B’), где А’и B’ –функциональные записивыражений A и B соответственно.Функциональной записью выражения в скобках являетсяфункциональная запись этого выражения без скобок.
Например,для выражения 2*(5+6) функциональная запись выглядит так:*(2,+(5,6)). Построить БНФ и СД для функциональных записейвыражений, содержащих цифры, скобки и знаки операций +, −, , .20. Определимпонятиепрефикснаязаписьвыражения.Префиксной записью выражения, состоящего из одной цифры,является эта цифра. Префиксной записью выражения А op B, где op– операция, является запись op A’B’, где А’и B’ – префиксныезаписи выражений A и B соответственно.
Префиксной записьювыражения в скобках является префиксная запись этого выражения- 14 -без скобок. Построить БНФ и СД для префиксных записейвыражений, содержащих цифры, скобки и знаки операций +, −, , .21. Определим понятие постфиксная запись выражения.Постфиксной записью выражения, состоящего из одной цифры,является эта цифра.
Постфиксной записью выражения А op B, гдеop – операция, является записьA’B’op , где А’и B’ –постфиксные записивыраженийA и B соответственно.Постфиксной записью выражения в скобках является постфикснаязапись этого выражения без скобок. Построить БНФ и СД дляпостфиксных записей выражений, содержащих цифры, скобки изнаки операций +, −, , .22. Для правильного понимания смысла выражения, когда скобкив нем явно не расставлены, как в случаях a b с и a b c,важно учитывать приоритет операций, а также ассоциативностьопераций одинакового приоритета.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
