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


 

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

32150. Базовые элементы построения стратегии по Портеру 24.5 KB
  Портер 1985 выделяет три ключевые общие стратегии: лидерство по затратам ндивидуализация и фокусирование. Лидерство по затратам. Жесткий контроль над затратами и накладными расходами сведение до минимума расходов в таких областях как исследования и разработки реклама и т. Стратегия лидерства по затратам часто создает прочную основу для конкуренции в отрасли.
32151. Стратегический переход от экономики производства к экономике знаний 28 KB
  Превращение науки в непосредственную производительную силу отмеченное в начале 1960х гг. На смену экономики фабричных труб когда преобладало массовое производство пришла экономика основанная на интеллектуальном труде человеческом капитале. Появление всемирной электронной рулетки когда реальные инвестиции подменяются спекуляцией когда человеческие ресурсы отвлекаются на бесплодные биржевые игры не может позитивно влиять на развитие мировой экономики. Касаясь вопросов связанных с...
32152. СУ в системе менеджмента 100.5 KB
  Конечная цель системы менеджмента выполнение миссии организации. Миссия это наиболее общая цель организации как конкурентоспособной структуры представленная в наиболее общей форме и четко выражающая основную причину существования организации. Стратегия корпорации это деловая концепция организации на заданную стратегическую перспективу представленная в виде долгосрочной программы конкретных действий которые способны реализовать данную концепцию и обеспечить организации конкурентные преимущества в достижении целей.
32153. Конкурентные преимущества. Базовые конкурентные стратегии 32.5 KB
  Конкурентные преимущества. Базовые конкурентные стратегии Конкретную рыночную позицию организации определяет ее конкурентные преимущества. Портеру конкурентные преимущества делятся на два основных вида: дифференциация продуктовтоваров и более низкие издержки на создание и реализацию товаров. Организации добиваются конкурентного преимущества находя новые способы конкуренции в своей отрасли и выходя с ними на рынок что можно назвать одним словом нововведение.
32154. Цепочка стоимости и система стоимости 24 KB
  Цепочка стоимости и система стоимости Виды деятельности при конкуренции в какойлибо конкретной отрасли можно разделить на категории. Они объединены в так называемую цепочку стоимости. Все виды деятельности входящие в цепочку стоимости вносят свой вклад в конечную потребительскую стоимость продуктатовара. Выбранная конкурентная стратегия определяет способ которым организация выполняет отдельные виды своей деятельности а также всю цепочку стоимости в целом.
32155. Переход от стратегического планирования к стратегическому менеджменту 36.5 KB
  Переход от стратегического планирования к стратегическому менеджменту Предшественником стратегического планирования была система долгосрочного планирования longrnge plnning. В арсенал новых методов используемых стратегическим планированием входят: модели анализа инвестиционных портфелей компаний разработка ситуационных планов развития применение сценарного планирования использование систем экспертных оценок применение различных аналитических матриц для исследования альтернатив возможного стратегического развития и т. Некоторые...
32156. Модели стратегического менеджмента 27 KB
  Модели стратегического менеджмента Одно из классических образных представлений о стратегическом мышлении в отличие от других видов мышления сделано К. В соответствии с моделью укрупненными являются следующие три этапа или фазы стратегического цикла организации: 1 стратегический анализ; 2 разработка стратегии стратегический синтезразвитие; 3 реализация стратегии. Отметим что рассматриваемая модель характеризует стратегическое управление организации и как органичную систему. В рамках предлагаемой модели стратегический...
32157. Анализ внешней среды организации. SWOT-анализ и PEST 38 KB
  Анализ внешней среды организации. К особенностям целевого SWOТ анализа при исследовании внешней среды организации относятся следующие. Вовторых анализ сильных и слабых сторон организации на втором этапе желательно увязывать с соответствующими результатами которые были выявлены и зафиксированы на первом этапе. Но и ценность любого тщательно просчитанного оптимального решения если оно появляется слишком поздно становится равной нулю На основании последовательного рассмотрения этих факторов принимаются решения по корректировке целей и...
32158. Анализ внутренней среды организации. SNW-анализ 26.5 KB
  Анализ внутренней среды организации. SNWанализ Исследование внутренней среды организации как части стратегического анализа представляет отдельный блок. Анализ внутренней среды организации осуществляемый во имя ее стратегических целей так же как и стратегический анализ внешней среды должен быть системным и многофакторным. При стратегическом анализе вся внутренняя среда организации и ее отдельные подсистемы и компоненты рассматриваются как стратегический ресурс развития организации.