Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте za4eti.ru

Компьютеры, Программирование Компьютеры, Программирование     Программирование, Базы данных Программирование, Базы данных

Построение функции предшествования по заданной КС-грамматике

Ручка "Помада".
Шариковая ручка в виде тюбика помады. Расцветка корпуса в ассортименте, без возможности выбора!
25 руб
Раздел: Оригинальные ручки
Фонарь садовый «Тюльпан».
Дачные фонари на солнечных батареях были сделаны с использованием технологии аккумулирования солнечной энергии. Уличные светильники для
106 руб
Раздел: Уличное освещение
Горшок торфяной для цветов.
Рекомендуются для выращивания крупной рассады различных овощных и цветочных, а также для укоренения саженцев декоративных, плодовых и
7 руб
Раздел: Горшки, ящики для рассады

САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ имени академика С.П. КОРОЛЕВАКафедра информационных систем и технологий ПОЯСНИТЕЛЬНАЯ ЗАПИСКАк курсовому проекту по курсу &quo ;Информационные технологии&quo ; на тему&quo ;Построение функции предшествования по заданной КС-грамматике&quo ; Выполнил: студент группы 634 Абраров А.М.Руководитель проекта:Шамашов М.А.Дата сдачи:Оценка: Самара 2001 г. РЕФЕРАТ Курсовой проект Пояснительная записка: 30 с., 5 рис., 3 схем программ и алгоритмов, 3 библиографического источника. ТЕРМИНАЛ, НЕТЕРМИНАЛ, ГРАММАТИКА, ФУНКЦИЯ ПРЕДШЕСТВОВАНИ, ГРАФ, ЛИНЕАРИЗАЦИЯ. В курсовом проекте разработан алгоритм и соответствующая ему программа, позволяющая по введённой пользователем КС-грамматике построить функцию предшествования, используя граф линеаризации и алгоритм пересчета с визуализацией шагов построения графа. Грамматика может быть введена как в самой программе, так и из текстового файла. Также существует возможность сохранения результата. Программа написана на языке Pascal 7.0. СОДЕРЖАНИЕ СОДЕРЖАНИЕ3 1. Постановка задачи4 2. Описание структуры данных5 3. Грамматики предшествования6 3.1 Грамматики простого предшествования6 3.2 Грамматики операторного предшествования8 3.3 Пример построения матрицы предшествования10 3.4 Линеаризация матрицы предшествования13 4. Руководство пользователя13 5. Текст программы 15 6. Список использованных источников30 1. Постановка задачи По заданной КС-грамматике построить отношение простого или операторного предшествования и функцию предшествования, используя граф линеаризации и алгоритм пересчета с визуализацией шагов построения графа. 2. Описание структуры данных Типы: Для хранения терминалов и терминалов используется тип: o erm=^Lis ; Lis =Record{список терминалов и нетерминалов} ame:S r10;{терминал или нетерминал} ex : o erm; E d; Для хранения грамматики (текста) используется: s rBuf=array of Char; Матрица предшествования: ma rixPr=array of 0.4; Функция предшествования: Fu cPr=array of By e; Процедуры и функции (основные): Ввод грамматики осуществляется функцией: Fu c io I pu ex :Boolea ; Для синтаксического анализа КС-грамматики используется процедура: Procedure Check; Для нахождения «левых» и «правых» используется процедура: Procedure SearchLR; Построение матрицы предшествования выполняет процедура: Procedure Ma rix; Построение функции предшествования осуществляется процедурой: Procedure Fu cPrecede; 3. Грамматики предшествования КС-языки делятся на классы в соответствии со структурой правил их грамматик. В каждом из классов налагаются дополнительные ограничения на допустимые правила грамматики. Одним из таких классов является класс грамматик предшествования. Они используются для синтаксического разбора цепочек с помощью алгоритма “сдвиг-свертка”. Выделяют следующие типы грамматик предшествования: простого предшествования; расширенного предшествования; слабого предшествования; смешанной стратегии предшествования; операторного предшествования. Далее будут рассмотрены ограничения на структуру правил и алгоритмы разбора для двух типов - грамматик простого и операторного предшествования.

3.1 Грамматики простого предшествования Грамматикой простого предшествования называют такую КС-грамматику G(V ,V ,P,S), V=V V в которой: Для каждой упорядоченной пары терминальных и нетерминальных символов выполняется не более чем одно из трех отношений предшествования: Si = Sj ( Si,Sj V), если и только если  правило U xSiSjy  P, где U V , x,y V ; Si < Sj ( Si,Sj V), если и только если  правило U xSiDy  P и вывод D Sjz, где U,D V , x,y,z V ; Si > Sj ( Si,Sj V) , если и только если  правило U xCSjy  P и вывод C zSi или  правило U xCDy  P и выводы C zSi и D Sjw, где U,C,D V , x,y,z,w V . Различные порождающие правила имеют разные правые части. Отношения =, < и > называют отношениями предшествования для символов. Отношение предшествования единственно для каждой упорядоченной пары символов. При этом между какими-либо двумя символами может и не быть отношения предшествования - это значит, что они не могут находиться рядом ни в одном элементе разбора синтаксически правильной цепочки. Отношения предшествования зависят от порядка, в котором стоят символы, и в этом смысле их нельзя путать со знаками математических операций - например, если Si > Sj, то не обязательно, что Sj < Si (поэтому знаки предшествования иногда помечают специальной точкой: = , ) Метод предшествования основан на том факте, что отношения предшествования между двумя соседними символами распознаваемой строки соответствуют трем следующим вариантам: Si < Si 1, если символ Si 1 - крайний левый символ некоторой основы; Si > Si 1 , если символ Si - крайний правый символ некоторой основы; Si = Si 1 , если символы Si и Si 1 принадлежат одной основе. Исходя из этих соотношений выполняется разбор строки для грамматики предшествования. На основании отношений предшествования строят матрицу предшествования грамматики. Строки матрицы предшествования помечаются первыми символами, столбцы - вторыми символами отношений предшествования, а в клетки матрицы на пересечении соответствующих столбца и строки помещаются знаки отношений. При этом пустые клетки матрицы говорят о том, что между данными символами нет ни одного отношения предшествования. Матрицу предшествования грамматики можно построить, опираясь непосредственно на определения отношений предшествования, но удобнее воспользоваться двумя дополнительными множествами - множеством крайних левых и множеством крайних правых символов относительно нетерминалов грамматики. Эти множества определяются следующим образом: L(U) = {  U z}, U,  V, z V - множество крайних левых символов относительно нетерминального символа U (цепочка z может быть и пустой цепочкой); R(U) = {  U z }, U,  V, z V - множество крайних правых символов относительно нетерминального символа U. Тогда отношения предшествования можно определить так: Si = Sj ( Si,Sj V), если  правило U xSiSjy  P, где U V , x,y V ; Si < Sj ( Si,Sj V), если  правило U xSiDy  P и Sj L(D), где U,D V , x,y V ; Si > Sj ( Si,Sj V) , если  правило U xCSjy  P и Si R(C) или  правило U xCDy  P и Si R(C), Sj L(D), где U,C,D V , x,y V .

Такое определение отношений удобнее на практике, так как не требует построения выводов, а множества L(U) и R(U) могут быть построены для каждого нетерминального символа U V по очень простому алгоритму: Шаг 1. Для каждого нетерминального символа U ищем все правила, содержащие U в левой части. Во множество L(U) включаем самый левый символ из правой части правил, а во множество R(U) - самый крайний символ правой части. Переходи к шагу 2. Шаг 2. Для каждого нетерминального символа U: если множество L(U) содержит нетерминальные символы грамматики U’,U”,., то его надо дополнить символами, входящими в соответствующие множества L(U’), L(U”), . и не входящими в L(U). Ту же операцию надо выполнить для R(U). Шаг 3. Если на предыдущем шаге хотя бы одно множество L(U) или R(U) для некоторого символа грамматики изменилось, то надо вернуться к шагу 2, иначе построение закончено. После построения множеств L(U) и R(U) по правилам грамматики создается матрица предшествования. Матрицу предшествования дополняют символами  н и  к (начало и конец цепочки). Для них определены следующие отношения предшествования:  н  a V, если  S ax, где S V , x V или (с другой стороны) если a L(S);  к > a,  a V, если  S xa, где S V , x V или (с другой стороны) если a R(S). 3.2 Грамматики операторного предшествования Грамматикой операторного предшествования называется приведенная КС-грамматика без  -правил (e-правил), в которой правые части продукций не содержат смежных нетерминальных символов. Для грамматики операторного предшествования отношения предшествования можно задать на множестве терминальных символов (включая символы  н и  к). Отношения предшествования для грамматики операторного предшествования G(V ,V ,P,S) задаются следующим образом: a = b, если и только если существует правило U xaby  P или правило U xaCby, где a,b V , U,C V , x,y V ; a < b, если и только если существует правило U xaCy  P и вывод C bz или вывод C Dbz, где a,b V , U,C,D V , x,y,z V ; a > b, если и только если существует правило U xCby  P и вывод C za или вывод C zaD, где a,b V , U,C,D V , x,y,z V . В грамматике операторного предшествования различные порождающие правила имеют разные правые части. Для грамматики операторного предшествования тоже строится матрица предшествования, но она содержит только терминальные символы грамматики. Для построения этой матрицы удобно ввести множества крайних левых и крайних правых терминальных символов относительно нетерминального символа U - L (U) или R (U): L (U) = {  U z или  U C z}, где  V , U,C V , z V ; R (U) = {  U z или  U z C }, где  V , U,C V , z V . Тогда определения отношений операторного предшествования будут выглядеть так: a = b, если  правило U xaby  P или правило U xaCby, где a,b V , U,C V , x,y V ; a < b, если  правило U xaCy  P и b L (C), где a,b V , U,C V , x,y V ; a > b, если  правило U xCby  P и a R (C), где a,b V , U,C V , x,y V .

Объем фрагмента текста мы обозначает через vol, длительность описанного интервала времени - через d, среднее значение функции объема f=vol/d. ВАЖНОЕ ЗАМЕЧАНИЕ. В конце каждой главы Ф.Грегоровиус помещает довольно большое число комментариев к событиям, описанным в этой главе. Мы рассматривали этот текст как относящийся КО ВСЕМУ ОПИСАННОМУ В ДАННОЙ ГЛАВЕ ИНТЕРВАЛУ ВРЕМЕНИ. То есть, мы не детализировали подробно - какому именно событию посвящен тот или иной комментарий. Мы попросту "усредняли эту информацию", распределив ее по равномерно по всей описанной здесь эпохе. Иными словами, мы подсчитывали средний объем комментариев, разделив их объем на длительность того периода времени, которому они посвящены. ***************************************************************** 1) Ф.Грегоровиус начинает описание истории средневекового Рима с начала IV века. Поэтому при построении функции объема, мы начинаем отсчет времени примерно с 300 года н.э. Первые две главы тома 1 труда [47] носят вводный характер. Здесь Ф.Грегоровиус дает общий обзор сохранившихся сведений по истории Рима IV-V веков н.э

1. Практические задачи на вычисление эластичности, построения кривых спроса и предложения, оплата труда, издержки (Контрольная)

2. Механизм индивидуальных рынков: спрос, предложение, цена

3. Спрос, предложение, эластичность

4. График и его элементы. Классификация видов графиков

5. Спрос, предложение и их эластичность

6. Построение сетевого графика
7. Построение диаграмм и графиков на основе электронных таблицах Excel
8. Построение сетевого графика

9. Построение графиков функций

10. Вычисление функций в Еxcel и построение графиков

11. Исследование функций и построение их графиков

12. Построение сетевого графика и определение резервов выполнения работы

13. Виды графики

14. Графика русского языка до и после Кирилла

15. Векторная графика

16. Цифровая обработка графики

Подарочный набор "Покер", арт. 42449.
Подарочный набор "Покер" безусловно будет тем самым неизбитым презентом, произведённым из дерева. Регулярно удалять пыль сухой,
1292 руб
Раздел: VIP-игровые наборы
Клей универсальный UHU "Twist&Glue", 90 мл, арт. 38850.
Склеивает металл, бумагу, дерево, текстиль, стекло, керамику, пробку, большинство пластиков и кожу. Не подходит для ремонта кожаной
350 руб
Раздел: Универсальный
Набор детской складной мебели Ника "Хочу все знать".
В комплект входит стол и стул с мягким сиденьем. Материалы: металл окрашенный, цветная ламинированная ДСП, пластмасса. Для детей от 3 до 7
1270 руб
Раздел: Наборы детской мебели

17. Обучающая программа "Графика" программированию в графическом режиме на языке turbo-pascal 7.x

18. Панельное представление многоугольников (Компьютерная Графика OpenGL)

19. Проблема эффективности урока графики

20. Исследование престижности, популярности, объемов продаж, спроса и предложения на автомобили различных фирм на российском рынке

21. Рынок. Процесс формирования цен и объемов производства (спрос и предложение)

22. Эластичность спроса и предложения
23. Макроэкономический анализ: совокупный спрос и совокупное предложение
24. Спрос и предложение товаров

25. Спрос и предложение

26. Анализ рынков: спрос и предложение

27. Исторический взгляд на эластичность спроса и эластичность предложения: прошлое и настоящее

28. Анализ теории спроса и предложения (по книге К.Р. Макконнела и С.Л. Брю «Экономикс: принципы, проблемы и политика»)

29. Теодор Жерико (1791-1824) французский живописец и график

30. Поэтическая графика

31. Сетевые графики

32. Ионометрия. Метод градуировочного графика

Табурет складной "Моби".
Табурет изготовлен из пищевой пластмассы и абсолютно безопасен для детей, легко собирается и моется. Яркая цветовая гамма табурета
522 руб
Раздел: Стульчики
Двусторонние клеевые подушечки UHU Fix, 50 штук.
Двухсторонние клеящие подушечки с высокой клеящей способностью для постоянного крепления. Позволяют прикрепить практически любой нетяжелый
350 руб
Раздел: Универсальный
Сетка москитная на кроватку "Карапуз", размер М.
По всему краю данное изделие имеет резинку. Закрывает кроватку полностью, сверху и по бокам. Для кроватки 120х60 см. Сезон: лето.
385 руб
Раздел: Сетки противомоскитные

33. Начертательная геометрия и инженерная графика

34. Статистические таблицы и статистические графики - основные способы наглядного изображения данных

35. Спрос и предложение, основные ценообразующие факторы

36. Теория совокупного спроса и совокупного предложения. Эффект храповика

37. Макроэкономические проблемы и показатели. Совокупный спрос и совокупное предложение

38. Закон спроса и предложения
39. Основные элементы спроса и предложения
40. Расчет сетевого графика

41. Спрос и предложение на рынке труда

42. Совокупный спрос и совокупное предложение

43. Нетрудовые теории стоимости: теория предельной полезности, теория факторов производства, теория спроса и предложения

44. Форматы векторной графики

45. Компьютерная графика укр

46. Web-графика

47. Компьютерная графика VISIO

48. Трехмерная графика. Теория

Столик универсальный "Раскладушка".
"Раскладушка" - это многофункциональный складной столик, который с лёгкостью устанавливается и разбирается. Его можно
1083 руб
Раздел: Столы, тумбы
Простыня на резинке "Лимон", 90x200 см.
Трикотажная простыня "Tete-a-Tete" изготовлена из 100% хлопка высокого качества. Натуральный, экологически чистый материал
571 руб
Раздел: Простыни, пододеяльники
Подвесные качели "Кассон".
Подвесные детские качели изготовлены из прочного жгута и пластиковых разноцветных деталей. Размер: 48х48х24 см. Материал:
394 руб
Раздел: Качели

49. Использование машинной графики

50. Закраска гранично-заданной области с затравкой, Машинная графика, C++ Builder 4.0

51. Компьютерная графика и основные графические редакторы

52. Тенденции развития рынка компьютерной графики и анимации

53. Операции над графикой

54. Основы цифровой графики и цвета в Adobe
55. Растровая графика
56. Применение графиков в решении уравнений

57. C++: Стандартные библиотечные функции работы с графикой

58. Статистические таблицы и графики

59. Этапы составления графика документооборота и графика учетных работ на предприятии

60. Графика русского письма

61. Автоматизированное редактирование частиц в компьютерной графике

62. Векторная и растровая графика

63. Знакомство с фрактальной графикой

64. Использование диаграмм и графиков в табличном процессоре Microsoft Office Excel

Светильник Uniel TLI-201, Е27, синий.
Светильники серии Universal подойдут для широкого круга потребителей, умеющих ценить разумное сочетание качества и цены продукции.
379 руб
Раздел: Офисные (для рабочего стола)
Доска магнитно-маркерная, 60x90 см, алюминиевая рамка, полочка.
Доска магнитно-маркерная 60*90 см. Лакированная поверхность для письма сухостираемыми маркерами и прикрепления информации магнитами или
1393 руб
Раздел: Доски магнитно-маркерные
Шезлонг детский "Веселый динозаврик".
В кресле-шезлонге вашему ребенку будет одинаково удобно и кушать, и спать, и бодрствовать. Что бы вы ни делали — работу по дому,
2009 руб
Раздел: Качели, кресла-качалки, шезлонги

65. Общие сведения о Компас-График

66. Основные понятия компьютерной графики

67. Понятие компьютерной графики. Графический редактор Adobe Photoshop

68. Программирование графики и обработка событий

69. Проектирование и разработка электронного учебного курса по дисциплине "Начертательная геометрия, инженерная графика"

70. Размещение графики в документе
71. Растровая графика
72. Создание 3D-графики средствами языка программирования Visual Basic

73. Создание компьютерной графики при помощи OpenGL

74. Технологические возможности редактора векторной графики CorelDraw

75. График функции по Assembler’у

76. Графика на Web-страницах

77. Шагал Марк живописец и график

78. Механизм действия закона спроса и предложения, рыночное равновесие

79. Законы спроса и предложения

80. Графики и их функции

Набор разделочных досок на подставке (4 штуки ).
Материал: пластик. Количество: 4 штуки. Каждая доска для определенных продуктов.
2090 руб
Раздел: Пластиковые
Стиральный порошок "INDEX", универсал, 4500 грамм.
Предназначение: для стирки изделий из хлопчатобумажных, льняных, синтетических тканей, а также тканей из смешанных волокон (кроме изделий
786 руб
Раздел: Стиральные порошки
Сумка-транспортный чехол усиленная для колясок "Книжка".
Сумка чехол выполнена из прочной и легко чистящейся ткани оснащена двумя ручками для переноски. Размеры: 93x50x36 см.
907 руб
Раздел: Дождевики, чехлы для колясок

81. Книжная графика в работе с детьми-дошкольниками

82. Расчёт годового графика ремонта и обслуживания электрооборудования участка зубофрезерных станков

83. Инженерная графика

84. Разработка календарного графика строительства

85. Разработка графика движения электровоза 2ТЭ10В

86. Изменение спроса и предложения под влиянием налогообложения. Дотации, фиксирование цен
87. Анализ формирования равновесия между спросом и предложением в рыночной экономике
88. Взаимодействие спроса и предложения. Рыночное равновесие и его сдвиги

89. Методы изучения эластичности спроса и предложения

90. Основные факторы спроса и предложения, степень их влияния и проблема измерения

91. Основы теории спроса и предложения

92. Рынок труда: спрос и предложение. Уровень заработной платы

93. Спрос и предложение

94. Спрос и предложение

95. Спрос и предложение в условиях рыночной экономики

96. Труд как фактор производства: спрос и предложение. Установление заработной платы в условиях конкуренции

Глобус Земли "Двойная карта", рельефный, с подсветкой, 420 мм.
Рельефный глобус с физической и политической картой мира станет незаменимым атрибутом обучения не только школьника, но и студента. На
2642 руб
Раздел: Глобусы
Точилка механическая, металлический корпус.
Механическая точилка имеет прозрачный контейнер. Удобная и безопасная точилка оснащена механизмом, позволяющим крепить ее к столу. Нож из
1097 руб
Раздел: Точилки
Сушилка для белья напольная складная, 181х54х95 см, серая.
Сушилка для белья напольная складная. Размеры: 181x54x95 см. Цвет каркаса: серая. Размер в раскрытом виде: 181х95х54 см.
733 руб
Раздел: Сушилки напольные

97. Построение и анализ функции спроса на товар

98. Гидрогеология. Построение разреза по скважинам

99. Понятие, структура и методики построения страховых тарифов

100. Сложное предложение


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.