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


 

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

22026. Метод ДСК 195 KB
  Температуры плавления некоторых синтетических фосфолипидов Жирные кислоты Название остатка жирной кислоты Сокращённое название фосффолипида Температура плавления Tc oC 14:0 Миристоил ДМЛ 23 16:0 Пальмитоил ДПЛ 41 18:0 Стеароил ДСЛ 58 18:1 Олеил ДОЛ 21цисформа Полное название фосфолипидов: ДМЛ 12димиристоилфосфатидилхолин еще одно возможное сокращение ДМФХ и так далее. На первом этапе нас будут интерессовать три из них: Температура фазового перехода плавления Tc. T полуширина фазового перехода Tc температура...
22027. Активированная хемилюминесценция и биолюминесценция 114 KB
  Так например комплекс редкоземельного иона европия Eu3 c антибиотиком хлортетрациклином усиливает ХЛ при окислении липидов почти в 1000 раз. Хемилюминесцентный иммунный анализ По идеологии хемилюминесцентный иммунный анализ не отличается от радиоиммунного с той только разницей что вместо радиоактивномеченных субстратов или антител используются субстраты и антитела меченные соединением которое вступает в реакции сопровождающиеся хемилюминесценцией в присутствии перекиси водорода и катализатора обычно это фермент пероксидаза....
22028. Биологические мембраны Строение, свойства, функции 403 KB
  Клеточная или цитоплазматическая мембрана окружает каждую клетку. Ядро окружено двумя ядерными мембранами: наружной и внутренней. Все внутриклеточные структуры: митохондрии эндоплазматический ретикулум аппарат Гольджи лизосомы пероксисомы фагосомы синаптосомы и т представляют собой замкнутые мембранные везикулы пузырьки.
22029. Мембранные потенциалы 232.5 KB
  Более подробно межфазные и поверхностные потенциалы будут рассмотрены позже а сейчас мы рассмотрим как повлияет на перенос ионов наличие на мембране трансмембранного потенциала. Однако липидная часть мембраны состоит всегото из двух слоёв молекул фосфолипидов причём размеры подвижных звеньев цепей жирных кислот в этих молекулах соизмеримы с размерами ионов которые передвигаются внутри мембраны. Это заставляет при рассмотрении переноса ионов в мембране отказаться от полностью макроскопического подхода к явлениям и рассматривать процессы на...
22030. Перемещения иона в мембране 347 KB
  В случа переноса ионов через биомембраны за ось Х можно принять ось нормальную к мембране и направленную изнутри везикулы например клетки наружу см. Как же перемещается ион в толще липидного слоя мембраны В разделе 1 говорилось о том что такое перемещение возможно благодаря перестройке конфигурации жирнокислотных цепей и образованию нового кинка . Движение иона поперёк мембраны путём перескакивания из одного кинка в другой. На рисунке показаны не разные молекулы фосфолипидов в бислое а разные стадии процесса переноса иона...
22031. Системы передачи с временным разделением каналов 139 KB
  Напомним что для преобразования аналогового сигнала в цифровой используются операции ДИСКРЕТИЗАЦИЯ КВАНТОВАНИЕ КОДИРОВАНИЕ. Значение шума квантования зависит от количества уровней квантования скорости изменения сигнала и от спосрба выбора шага квантования. не зависит от а } = где вероятность попадания сигнала в iю зону квантования. зависит лишь от шага квантования и не зависит от уровня сигнала.
22032. Дельта - модуляция (кодирование с предсказанием) (ДИКМ) 158.5 KB
  Основные параметры характеристики компрессии по А закону приведены в таблице: № сегмента Вид кодовой комбинации P XYZ ABCD Относительный интервал изменения входного сигнала Значение шага квантования относительно Uогр 0 P 000 ABCD 0  1 128 1 2048 1 P 001 ABCD 1 128  1 64 1 2048 2 P 010 ABCD 1 64  1 32 1 1024 3 P 011 ABCD 1 32  1 16 1 512 4 P 100 ABCD 1 16  1 8 1 256 5 P 101 ABCD 1 8  1 4 1 128 6 P 110 ABCD 1 4  1 2 1 64 7 P 111 ABCD 1 2  1 1 32 Кодовая комбинация и есть код квантованного сигнала P  ABCD ...
22033. Особенности передачи сигналов данных 67 KB
  Качество передачи при этом оценивается не искажениями формы сигналов как в аналоговых системах а числом ошибок в принятой информации т. верностью передачи. В хороших модемах перед началом передачи информации вначале устанавливается связь между модемами которые автоматически обмениваясь сигналами подстраиваются под конкретную линию связи и автоматически выбирают необходимую скорость передачи а затем передают саму информацию.
22034. Графическая визуализация вычислений 83.54 KB
  В ходе выполнения данной лабораторной работы я освоил визуализацию вычислений средствами указанных функций