42370

ВИЗНАЧЕННЯ ВІДНОШЕНЬ ПЕРЕДУВАНЬ ЗА ПРАВИЛАМИ ГРАМАТИКИ

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

Информатика, кибернетика и программирование

Задачею висхідного розбору є зведення вхідного термінального ланцюжка до аксіоми. Для висхідного розбору критичним є тип виводу. Вивід зліва направо визначається таким чином, що на кожному кроці замінюється основа поточної синтенсійної форми. Тоді ланцюжок справа від основи завжди буде складатися лише з термінальних символів. Ключовим питанням при висхідному розборі є питання – як знайти основу та на який не термінал її замінити? Це питання легко вирішується для граматик простого передування.

Украинкский

2013-10-29

142.5 KB

9 чел.

Міністерство освіти і науки, молоді та спорту України

Національний Технічний університет України «КПІ»

Кафедра АПЕПС

Звіт за лабораторною роботою №4

з дисципліни «Лінгвістичне забезпечення САПР»

на тему:

«ВИЗНАЧЕННЯ ВІДНОШЕНЬ ПЕРЕДУВАНЬ ЗА ПРАВИЛАМИ ГРАМАТИКИ»

Виконав

студент 3-го курсу ТЕФ

групи ТР-91

Лисий А.І.

Перевірила

Третяк В.А.

Київ – 2011


Вступ

Задачею висхідного розбору є зведення вхідного термінального ланцюжка до аксіоми. Для висхідного розбору критичним є тип виводу. Вивід зліва направо визначається таким чином, що на кожному кроці замінюється основа поточної синтенсійної форми. Тоді ланцюжок справа від основи завжди буде складатися лише з термінальних символів. Ключовим питанням при висхідному розборі є питання – як знайти основу та на який не термінал її замінити? Це питання легко вирішується для граматик простого передування.


  1.  Виконання лабораторної роботи

Граматика називається граматикою простого передування, якщо вона є приведеною, оборотною, і якщо між будь-якими двома не терміналами або терміналами виконується не більше однієї умови передування.

Розглянувши два символи, що належать обєднаному словнику V, можна припустити, що існує деяка синтенсійна форма RS…, і на деякому етапі або R, або S, або RS належать основі.

  1.  RS… R•>S  U::=…R, SєVT*
  2.  RSR=S  U::=…RS…
  3.  …RS… R<•S  U::=S…

Жодне з умов передування не є симетричним. Якщо умови передування не визначені – не можуть стояти поряд в синтенсійній формі.

Визначення відношень передувань:

  1.  R=S => U::=…RS…
  2.  R<•S  => U::=…RV…, (R=V), SєFirst+(V), VєVN
  3.  R•>S => SєVT, U::=…VW…(V=W), RєFirst+(V), SєFirst+(W)

Алгоритм побудови відношень передувань:

  1.  Визначення рівностей R=S
  2.  Вибірка рівностей R=V, VєVN, R<•First+(V)
  3.  Визначення відношень R•>S
  4.  V=W, VєVN:

обираємо ті нерівності, де першим є не термінал

Last+(V) •>W

  1.  якщо WєVN, то необхідно визначити Last+(V) •>First+(W)

Для вирішення можливих конфліктів, наприклад, праворекурсивне правило або правило, в якому після праворекурсивного нетерміналу щось стоїть можна використовувати стратифікацію. Але вирішити усі конфлікти за допомогою стратифікації не завжди вдається, тоді слід дієти по ситуації.  

 

  1.  Граматика заданої мови програмування

<програма> ::= program id var <спис.огол1> main { <спис.опер1> }

<спис.огол> ::= <огол.> ; <спис.огол> | <огол.> ;

<спис.огол1> ::= <спис.огол>

<огол.>::=<тип> :  <спис.id1>

<тип>::=double  |  int

<спис.опер>::=<оператор1> ; | <оператор1> ; <спис.опер>

<спис.опер1>::=<спис.опер>

<оператор1>::=<оператор>

<оператор>::=<цикл>  |  <ум.оп>  |  <ввід>  |  <вивід>  |  <присвоєння>

<цикл>::= for id = <вираз1> : <лог.вираз1> | id = <вираз1>  <оператор>

<ум.оп>::=if [ <лог.вираз1> ] { <спис.опер1> }

<ввід>::=read ( <спис.id1> )

<вивід>::=write ( <спис.id1> )

<присвоєння>::= id = <вираз1>

<вираз>::= <додан.>  | <вираз> + <додан.1>  |  <вираз> - <додан.1>  |  - <додан.1>

<додан.> ::= <множн.>  |  <додан.> * <множн.>  | <додан.> / <множн.>

<додан.1> ::= <додан.>

<множн.> ::= con  |  ( <вираз1> )  |  id

<спис.id>::=id |  <спис.id> , id

<спис.id1> ::= <спис.id>

<відношення>::=<вираз> <знак> <вираз1>

<вираз1>::=<вираз>

<знак>::= >  |  <  |  >=  |  <=  |  ==  |  !=

<лог.вираз>::=<лог.додан.1> | <лог.вираз> && <лог.додан.1>

<лог.вираз1>::=<лог.вираз>

<лог.додан.> ::= <лог.множ.>  |  <лог.додан.> || <лог.множ.>

<лог.множ.>::= <лог.од.>  |  ! <лог.множ.>  |  [ <лог.вираз1> ]

<лог.додан.1>::=<лог.додан.>

<лог.од.> ::=<відношення> | true | false


  1.  Приклади роботи програми

На рисунку нижче наведено приклад роботи програми з помилками. Результат роботи подано в вигляді таблиці відношень. Помилки відмічаються за допомогою забарвлення відповідної клітки таблиці в червоний колір.

Рисунок 1 - Приклад роботи програми з помилками

На рисунку 2 наведено приклад роботи програми без помилок. Жодна з кліток не забарвлена в червоний колір, що свідчить про відсутність конфліктів відношень.

Рисунок 2 - Приклад роботи програми без помилок


Висновки

В даній лабораторній роботі були визначені відношення передування для заданої граматики. Результатом роботи програми є таблиця передувань та можливих конфліктів заданої граматики.


Список використаних джерел

  1.  Сліпченко, В.Г. Основи побудови компіляторів: Навч. посібник / В.Г. Сліпченко, В.М. Медведєва. – К.: ІЗМН, 2004. – 104с.
  2.  Ахо, А. Компиляторы: принципы, технологии и инструменты. : Пер. с англ / А. Ахо, Р. Сети, Дж. Ульман. – М. : Издательский дом «Вильямс», 2003. – 768с. : ил. – Парал. тит. англ.
  3.  Конспект лекцій з курсу лінгвістичного забезпечення САПР


 

А также другие работы, которые могут Вас заинтересовать

29477. ЧЕЛОВЕК НЕДОВОЛЬНЫЙ: ПРОТЕСТ И ТЕРПЕНИЕ 114.5 KB
  Чтобы преодолеть видимый парадокс нужно определить те социальные условия и структуры которые формируют и поддерживают такое сочетание а точнее взаимодействие недовольства и терпения в обществе. или к неэффективности современного социального недовольства фонового констатируют бесспорные факты но не объясняют их. Состояние общественно значимого недовольства возникает как реакция на сравнение то ли с лучшим по крайней мере более спокойным прошлым то ли с неосуществленным светлым будущим точнее с иллюзией такого будущего...
29478. ЧЕЛОВЕК ЛУКАВЫЙ: ДВОЕМЫСЛИЕ ПО-РОССИЙСКИ 150 KB
  Он приспосабливается к социальной действительности ища допуски и лазейки в ее нормативной системе то есть способы использовать в собственных интересах существующие в ней правила игры и в то же время что не менее важно постоянно пытаясь в какойто мере обойти эти правила. Успех этой системы на долгие десятилетия по крайней мере был бы невозможен если бы она опиралась только на массовое принуждение и массовый обман. Практическое отсутствие общеобязательных авторитетов создает многополярную структуру нормативного поля где...
29479. «ЧЕЛОВЕК ОГРАНИЧЕННЫЙ»: УРОВНИ И РАМКИ ПРИТЯЗАНИЙ 107.5 KB
  Стабильность притязаний На протяжении ряда лет данные ВЦИОМ охватывают как реальные так и воображаемые приписанные показатели положения человека: данные о полученном и желаемом нормальном по мнению опрошенных доходе и т. При этом 72 опрошенных считали что они получают намного меньше или несколько меньше чем заслуживают; 19 что они получают столько сколько заслуживают; 8 что получают больше чем того заслуживают. Если бы в распоряжении опрошенных исследование типа Мониторинг март 1997 г. При сходной формулировке...
29480. НАШИ ДЕСЯТЬ ЛЕТ: ИТОГИ И ПРОБЛЕМЫ (околоюбилейные размышления) 128 KB
  было подписано Постановление Президиума ВЦСПС и Госкомтруда СССР О создании Всесоюзного центра изучения общественного мнения по социальноэкономическим вопросам формальная дата появления на свет ВЦИОМ. Первое десятилетие жизни и работы ВЦИОМ можно рассматривать под разными углами зрения перебирать опросы отчеты оценивать кадры вспоминать конфликты и т. Что такое ВЦИОМ Условия и время создания нашего центра естественно наложили свой отпечаток на характер ВЦИОМ как организации или даже как своеобразного организма. Вопервых...
29481. Общественные перемены и общественное мнение 23 KB
  Человек политический: сцена и роли переходного периода 9. Человек толпа и масса в общественном мнении 17. Средний человек: фикция или реальность 19. Советский человек пять лет спустя: 19891994 гг.
29482. ОТ МНЕНИЙ К ПОНИМАНИЮ 90 KB
  Москва 2000 ОТ АВТОРА В книге собраны статьи публиковавшиеся в журнале Мониторинг общественного мнения1 с 1993 по 2000 гг. В этой формуле выражен один из основных принципов работы нашего центра: использовать данные изучения общественного мнения для понимания процессов и перемен в социальной экономической политической и культурной жизни общества. ВЕКТОРЫ ПЕРЕМЕН: СОЦИОКУЛЬТУРНЫЕ КООРДИНАТЫ ИЗМЕНЕНИЙ Уровни и предмет анализа в социальном исследовании Результаты массовых опросов общественного мнения как зарубежные так и отечественные чаще...
29483. ОБЩЕСТВЕННОЕ МНЕНИЕ В ГОД КРИЗИСНОГО ПЕРЕЛОМА 64.5 KB
  Дело не просто в падении или росте доверия к отдельным лидерам организациям институтам власти и пр. Первая относится к марту апрелю парламентский кризис попытка импичмента президента референдум как стремление найти выход из парламентского а точнее конституционного тупика при помощи прямого обращения президентской власти к авторитету общественного мнения. Обратная сторона этой медали изменение содержания таких традиционных категорий политической жизни как лидерство доверие поддержка властных структур или оппозиция власти. оказалась...
29484. ФАКТОРЫ И РЕСУРСЫ ОБЩЕСТВЕННОГО МНЕНИЯ В УСЛОВИЯХ «ПОСТМОБИЛИЗАЦИОННОГО ОБЩЕСТВА» 60.5 KB
  Малоэффективны поэтому реальными заслонами на пути лавины может служить лишь инерция сила привычки массового сознания и поведения а также относительная кратковременность всякого эмоционального состояния общества будь то увлечение или отталкивание восторг и страх. Эмоциональный всплеск оказался кратковременным уже в октябре ноябре стали усиливаться факторы массового разочарования и отчуждения. Ни устойчивые демократические институты ни устойчивая расстановка основных политических сил не сложились. Негативная мобилизация охватила...
29485. ФАКТОРЫ ПЕРЕМЕННЫЕ И ПОСТОЯННЫЕ: СВОДНЫЙ МОНИТОРИНГ 1994–1995 гг. 83.5 KB
  Объединенный мониторинг (апрель 1994 г. — май 1995 г.) суммирует данные девяти исследований, проведенных в течение года, свободного от электоральной горячки. Как видно из приводимых ниже данных, основные показатели социальных процессов и оценки событий в общественном мнении за этот период оставались практически стабильными. На этом внешне спокойном фоне выделяются три зоны достаточно резких сдвигов