42370

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

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

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

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

Украинкский

2013-10-29

142.5 KB

7 чел.

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

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

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

Звіт за лабораторною роботою №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.  Конспект лекцій з курсу лінгвістичного забезпечення САПР


 

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

2138. Гігієнічна оцінка впливу кредитно-модульної системи навчання на функціональний стан студентів вищих медичних навчальних закладів 155 KB
  Європейська кредитно-трансферна (ECTS) та традиційна (семестрово-залікова) освітні системи мають як схожість, так й принципову розбіжність за умовами та характером навчання, що безпосередньо впливає на життєдіяльність студентів Вищих медичних навчальних закладів. Особливості освітньої системи відбиваються на загальному та психологічному стані студентів.
2139. Формирование межкультурной коммуникативной компетенции студентов гуманитарного профиля в процессе профессиональной подготовки 375.54 KB
  Цель исследования заключается в разработке модели формирования МКК специалиста гуманитарного профиля и ее практической реализации в иноязычных профессиональных контекстах в единстве аксиологических, национально-специфических и коммуникативных компонентов.
2140. Нелинейные элементы и нелинейные характеристики 380.1 KB
  Для понимания поведения сложных объектов, как и для создания сложных систем с заданными свойствами, очень часто имеет смысл представлять объект как совокупность составных частей, элементов, каждый из которых может быть охарактеризован совокупностью тех и только тех его свойств, которые существенны для функционирования системы в целом.
2141. Асимметрия в переводе художественного текста: этнолингвокультурный аспект 384.47 KB
  Цель работы состоит в сопоставительном исследовании асимметрии как переводческого феномена на материале художественных текстов на немецком и русском языках.
2142. Категория оценки в публичных политических речах П.А. Столыпина и Отто фон Бисмарка 380.89 KB
  Цель исследования заключается в том, чтобы выявить, описать и сопоставить компоненты оценочной ситуации и особенности выражения оценочного значения в публичном политическом выступлении П.А. Столыпина и Отто фон Бисмарка.
2143. Понятие и сущность мирового хозяйства и международных экономических отношений 388.27 KB
  Понятие мировая экономика равнозначно терминам мировое хозяйство и всемирное хозяйство. Экономисты выделяют их в одно и дают несколько определений. Можно рассмотреть как в обобщенном, так и в частном смысле.
2144. Антикризисное управление. Конспект лекций 388.44 KB
  Кризисы в тенденциях макро и микроразвития. Причины и последствия возникновения кризисов. Возможность, необходимость и содержание антикризисного управления. Признаки и порядок установления банкротства предприятия.
2145. Конспект лекций по детским болезням 393.12 KB
  История отечественной педиатрии, организация охраны материнства. Хронические расстройства питания, гиповитаминозы у детей. Острые и хронические вирусные гепатиты у детей. Геморрагические болезни у детей, геморрагические диатезы, тромбоцитопеническая пурпура, геморрагический васкулит.
2146. Когнитивные особенности перевода научно-технического текста 398.53 KB
  Цель диссертационного исследования состоит в выявлении когнитивной сущности переводческого процесса путем разработки когнитивной модели перевода и её описания на основе научно-технических материалов.