Розробка формальних граматик

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Розробка формальних граматик

1. Дотримуючись умов завдання, виходячи із заданих операцій та їх пріоритетів, була побудована наступна граматика:

Перегляд вираження і згортка зліва-направо.

ВИРАЗ = А_ВИР!

Л_ВИР.

Л_ВИР = Л_ВИР «EQU» Л_ОПЕР1! / / Операція леворекурсівная => згортка зліва-направо

Л_ОПЕР1.

Л_ОПЕР1 = Л_ОПЕР1 «XOR» Л_ОПЕР2!

Л_ОПЕР1 «OR» Л_ОПЕР2!

Л_ОПЕР2.

Л_ОПЕР2 = Л_ОПЕР2 «AND» Л_ОПЕР3!

Л_ОПЕР3.

Л_ОПЕР3 = «NOT» ЗНАК!

ЗНАК.

ЗНАК = А_ВИР ОПЕР_СР А_ВИР.

А_ВИР = А_ВИР «+» А_ОПЕР1!

А_ВИР «-» А_ОПЕР1!

А_ОПЕР1.

А_ОПЕР1 = А_ОПЕР1 «*» А_ОПЕР2!

А_ОПЕР2.

А_ОПЕР2 = А_ОПЕР2 «MOD» А_ОПЕР3!

А_ОПЕР3.

А_ОПЕР3 = А_ОПЕР4 «^» А_ОПЕР3! / / Операція праворекурсівная => згортка справа-наліво

А_ОПЕР4.

А_ОПЕР4 = FUNK «(« А_ВИР «)»!

FUNK «(» ІД_К «)»!

«(» А_ВИР «)»!

ІД_К.

ІД_К = ВД!

Конст.

ВД = «DOUBLE»!

«INTEGER»!

«STRING».

Конст = «Конст _10»!

«КОНСТ_16»!

«КОНСТ_2».

FUNK = «LEFT»!

«SIN».

ОПЕР_СР = «<»!

«>»!

«<=»!

«>=»!

«<>»!

«=».

EOG

2. Побудуємо матрицю передування вихідної граматики відповідно до вимог методу паралельного передування:

Матриця має конфлікти:

* Рядок 1, стовпець 31: 1 - конфлікт типу =, <

* Рядок 2, стовпець 32: 1 - конфлікт типу =, <

* Рядок 3, стовпець 32: 1 - конфлікт типу =, <

* Рядок 6, стовпець 36: 1 - конфлікт типу =, <

* Рядок 7, стовпець 36: 1 - конфлікт типу =, <

* Рядок 8, стовпець 37: 1 - конфлікт типу =, <

* Рядок 11, стовпець 29: 1 - конфлікт типу =, <

* Рядок 11, стовпець 41: 1 - конфлікт типу =, <

* Рядок 21, стовпець 29: 4 - конфлікт типу>, X

* Рядок 22, стовпець 29: 4 - конфлікт типу>, X

* Рядок 23, стовпець 29: 4 - конфлікт типу>, X

* Рядок 24, стовпець 29: 4 - конфлікт типу>, X

* Рядок 25, стовпець 29: 4 - конфлікт типу>, X

* Рядок 26, стовпець 29: 4 - конфлікт типу>, X

* Рядок 35, стовпець 29: 1 - конфлікт типу =, <

Налагодження

Для наочності побудуємо дерево:

Конфлікт 1-го типу:







Для уникнення конфліктів 1-го типу введемо нові правила:

Л_ВИР = Л_ВИР «EQU» Л_ОПЕР11!

Л_ОПЕР1.

Л_ОПЕР11 = Л_ОПЕР1.


Конфлікт ліквідований і рекурсія збережена.





При ліквідації конфліктів 1-го типу зникають конфлікти 4-го типу.

Отримаємо нову безконфліктну граматику:

ВИРАЗ = А_ВИР!

Л_ВИР.

Л_ВИР = Л_ВИР «EQU» Л_ОПЕР11!

Л_ОПЕР1.

Л_ОПЕР11 = Л_ОПЕР1.

Л_ОПЕР1 = Л_ОПЕР1 «XOR» Л_ОПЕР22!

Л_ОПЕР1 «OR» Л_ОПЕР22!

Л_ОПЕР2.

Л_ОПЕР22 = Л_ОПЕР2.

Л_ОПЕР2 = Л_ОПЕР2 «AND» Л_ОПЕР3!

Л_ОПЕР3.

Л_ОПЕР3 = «NOT» ЗНАК!

ЗНАК.

ЗНАК = А_ВИР ОПЕР_СР А_ВИР2.

А_ВИР2 = А_ВИР.

А_ВИР = А_ВИР «+» А_ОПЕР11!

А_ВИР «-» А_ОПЕР11!

А_ОПЕР1.

А_ОПЕР11 = А_ОПЕР1.

А_ОПЕР1 = А_ОПЕР1 «*» А_ОПЕР22!

А_ОПЕР2.

А_ОПЕР22 = А_ОПЕР2.

А_ОПЕР2 = А_ОПЕР2 «MOD» А_ОПЕР3!

А_ОПЕР3.

А_ОПЕР3 = А_ОПЕР4 «^« А_ОПЕР3!

А_ОПЕР4.

А_ОПЕР4 = FUNK «(» А_ВИР2 »)"!

FUNK «(» ІД_К1 »)"!

«(» А_ВИР2 »)»!

ІД_К.

ІД_К1 = ІД_К.

ІД_К = ВД!

Конст.

ВД = «DOUBLE»!

«INTEGER»!

«STRING».

Конст = «КОНСТ_10»!

«КОНСТ_16»!

«КОНСТ_2».

FUNK = «LEFT»!

«SIN».

ОПЕР_СР = «<»!

«>»!

«<=»!

«>=»!

«<>»!

«=».

EOG

Побудуємо матрицю передування безконфліктної граматики:

4. Розробка сканера

1) Визначаємо лексеми мови

Табл.1. Лексеми мови

Позначення лексем и

Сенс лексеми

до онст _10

Десяткова константа

конст_16

Шістнадцяткова константа (префікс & H)

конст_2

Двійкова константа (префікс & B)

ід_р

Ідентифікатор (integer, double або string)

sin

Синус дійсного числа

left

Функція роботи з рядками

not

Логічне «НІ»

and

Логічне «І»

or

Логічне «АБО»

xor

Виключне «АБО»

роздільник

Пробіл

+

Арифметична операція додавання

-

Арифметична операція віднімання

*

Арифметична операція множення

mod

Арифметична операція цілочисельне ділення

^

Арифметична операція піднесення до степеня

оо

Операція відносини (результат - логічний)

(

Відкриваюча дужка

)

Закриваюча дужка

2) розробляти иваем базу даних сканера

Табл.2. Таблиця одно-літерних


Табл.3. Таблиця класів літер


термінальних символів




ТТС1


KTL


«А»

...

«Z»

«A»

«C»

...

«K»

«M»

...

«Z»

Букв и

б


б

0






«B»

1






д

2






н

3






р

4






«+»

5






«-»

6






«*»

7






«^»

8









«H»

Шістнадцятковий префікс

«H»


«=»

9


«B»

Двійковий префікс

«B»


«<»

10


«0»

«1»

Двійкові цифри

д


«>»

11






«#»

12


«2»

...

«9»

Недвійкова цифри

н


«%»

13






«$»

14






«(»

15


«»

Роздільник (пропуск)

р


«)»

16


«+»

Додавання

«+»


«.»

17


«-»

Віднімання

«-»


«И»

18


«*»

Множення

«*»


«H»

19


«^»

Ступінь

«^»


Табл.4. Таблиця типів лексем


«<»

Менше

«<»





«>»

Більше

«>»


TLE


«=»

Так само

«=»


конст _10

0


«#»

Суфікс double

«#»


конст _16

1


«%»

Суфікс integer

«%


конст _2

2


«$»

Суфікс string

«$»


ід_р

3


«(»

Про ткривающая дужка

«(»


sin

4


«)»

За вають дужка

«)»


left

5


«.»

Точка

«.»


not

6



Неприпустимий символ

х


and

7



Кінець файлу

и


or

8






xor

9


Табл.5. Таблиця ключових слів



equ

10





роздільник

11


ТКС



+

12


sin



-

13


left



*

14


not



mod

15


and



^

16


or



оо

17


xor



(

18


equ



)

19


mod






Тимчасові таблиці:

Табл.6. Таблиця ідентифікаторів






ТІ

Ід

описатели

адр


т ип

точка

точність

осн













Табл.7. Таблиця констант






ТК


конст

описатели



тип

точка

точність

осн













Табл.8. Таблиця операції, і спеціальні и х символів



ТОС


символ









Табл.9. Таблиця стандартних символів






ТСС




TLE

ALE









3) Кожен тип лексичних одиниць описуємо за допомогою автоматної граматики і для кожної граматики складаємо еквівалентний їй кінцевий автомат.

  • конст_10

S = НD 1! дD 1.

D 1 = НD 1! дD 1! ». «D 2! е.

D 2 = НD 3! дD 3.

D 3 = НD 3! дD 3! е.

е = «"! «*»!» - "! «+»! «*»! «/"! «^»!»)"! «=»! «<»! «>».







  • конст_2

S = «&« B 0.

B 0 = «B» B 1.

B 1 = тюнер 2.

B 2 = тюнер 2! ». «B 3! е.

B 3 = тюнер 4.

B 4 = тюнер 4! е.

е = «"! «*»!» - "! «+»! «*»! «/"! «^»!»)"! «=»! «<»! «>».







  • конст_16

S = «&« B 0.

B 0 = «H» H 1.

H 1 = д H 1! Н H 1! «A" H 1! «B» H 1! «C» H 1! «D» H 1! «E» H 1! «F» H 1! Тобто

е = «"! «*»!» - "! «+»! «*»! «/"! «^»!»)"! «=»! «<»! «>».




  • ід_р

S = б А! «B» A! «H» A.

А = Ба! нА! ТАК! «A» A! «B» A! «C» A! «D» A! «E» A! «F» A! «H» A! «%« A 2! «&« A 2! «$« A 2.

A 2 = е.

е = «"! «*»!» - "! «+»! «*»! «/"! «^»!»)"! «=»! «<»! «>».




  • sin

S = «s» A 4.

A 4 = «i» A 5.

A 5 = «n» A 6.

A 6 = е 4.

е 4 = р! «(».



  • left

S = «l» A 7.

A 7 = «e» A 8.

A 8 = «f» A 9.

A 9 = «t» A10.

A10 = е 4.

е 4 = р! «(».


  • not

S = «n» A 11.

A 11 = «o» A 12.

A 12 = «t» A 13.

A 13 = е 4.

е 4 = р! «(».



  • and

S = «a» A 14.

A 14 = «n» A 15.

A 15 = «d» A 16.

A 16 = е 4.

е 4 = р! «(».



  • or

S = «o» A 17.

A 17 = «r» A 18.

A 18 = е 4.

е 4 = р! «(».



  • xor

S = «x» A 19.

A 19 = «o» A 20.

A 20 = «r» A 21.

A 21 = е 4.

е 4 = р! «(».



  • equ

S = «e» A 22.

A 22 = «q» A 23.

A 23 = «u» A 24.

A 24 = е 4.

е 4 = р! «(».



  • роздільник

S = РR 1.

R 1 = р R 1! E 0

e 0 - будь-який символ з ТТС1




  • +

S = «+« U 1.

U 1 = e 3.

e 3 = б! «B»! «H»! д! н! р! «&»! «(».



  • -

S = «-« U 1.

U 1 = e 3.

e 3 = б! «B»! «H»! д! н! р! «&»! «(».



  • *

S = «*« U 1.

U 1 = e 3.

e 3 = б! «B»! «H»! д! н! р! «&»! «(».



  • mod

S = «mod» U 1.

U 1 = e 3.

e 3 = б! «B»! «H»! д! н! р! «&»! «(».



S = «^« U 1.

U 1 = e 3.

e 3 = б! «B»! «H»! д! н! р! «&»! «(».



  • оо

S = «<« O 1! «>« O 2! «=« O 3.

O 1 = «>« O 4! «=« O 4! e 3.

O 2 = «=« O 5! e 3.

O 4 = e 3.

O 5 = e 3.

O 3 = e 3.

e 3 = б! «B»! «H»! д! н! р! «&»! «(».


  • (

S = «(« K 1.

K 1 = e 2.

e 2 = б! «B»! «H»! д! н! р! «+»!» - "!« & »!« (».



  • )

S = »)« K 2.

K 2 = e.

е = «"! «*»!» - "! «+»! «*»! «^»!»)"! «=»! «<»! «>».



4) Оп ісиваем використані в сканері підпрограми:

end - Процедура закінчення роботи сканера

podgot - Процедура виробляє загальну підготовку сканера до роботи

tip - Процедура встановлює тип літери

vkl - Процедура додає поточну літеру в поточну лексему

cll - Процедура зчитує з файлу чергову літеру

zaptab - Процедура перевіряє наявність поточної лексеми в таблиці ключових слів

out - Процедура заповнює основні таблиці

6) Приклад роботи сканера

Початкове в ираженіе:

(Sin (2 * aa% - & B01) <bb #) and (2 +3 +4 <10) xor & H0

Заповнений ні в результаті роботи сканера таблиці:

Табл.10. Таблиця ідентифікаторів


ТІ

ід

описатели

а ін


т ип

точка

точність

осн


Aa%

Integer

0

2

10

0

Bb #

Double

1

16

10

2






Табл.11. Таблиця констант






ТК


конст

Про письменники



тип

точка

точність

осн


2

Integer

0

0

10


& B01

Bin

0

0

2


2

Integer

0

0

10


3

Integer

0

0

10


4

Integer

0

0

10


10

Integer

0

0

10


& H0

H ex

0

0

16







Табл.12. Таблиця операції, і спеціальні и х символів



ТОС


Символ


(


Sin


(


*


-


)


<


)


And


(


+


+


<


)


Xor












5. Синтаксичний аналіз вираження, яке використовувалося в п. 2

Синтаксичний аналіз виконує певні функції:

1) виділення синтаксичної конструкції

2) класифікація синтаксичної конструкції

3) визначення синтаксичної помилки і, можливо, її нейтралізація

4) у процесі синтаксичного аналізу формується деяка внутрішня форма представлення програми.

Метод паралельного передування:

Ставлення передування, використовувані в методі паралельного передування:

<Аналог відносини простого передування

= Два символи входять в просту фразу

X> 1 Y, X - останній символ фрази, Y - слід за Х і знаходиться правіше відповідної простої фрази і Y не є першим символом простої фрази.

X> <Y, X - останній символ простої фрази, Y - перший символ наступного простої фрази (Y слід за X)

(> 1) = (LAST) (=)

(><)=( LAST) (=) FIRST

Вхідна ланцюжок представляється у вигляді черги, кожен елемент якої має два поля: S - символ ланцюжка і nx - покажчик на наступний символ.

В алгоритмі використовуються наступні позначення:

TL - поточна літера

NTL - номер поточної літери

PL - попередня літера

ST - наступна літера

SL - стік результату

ST 2 - стік перетворень

ST. SIZE - розмір стека

ST. PUSH - додати в «голову» стека

ST. POP - взяти (видалити) з «голови» стека

ST. RESET - очистити стек.

Блоки 2-4 виробляють ініціалізацію черги (установка в початкове положення)

Блоки 5-6 проводиться перевірка на наявність відносин між символами, якщо таких не існує, то помилка, інакше триває аналіз

Блоки 7-10 здійснюється пошук простої фрази

Блоки 10-14 здійснюється редукція простої фрази на ліву частину G [i]. 1 правило i з граматики G

Блоки 15-17 здійснюється збереження результату редукції і перехід на наступний елемент

Блок 18 здійснюється перевірка на закінчення рядка

Блоки 19-23 здійснюється перевірка на закінчення аналізу, якщо аналіз закінчено, УСПІХ, інакше збереження результату і переклад в початок.

Сентенціальная форма:

1) # NOT A% MOD 5 <C # AND M% ^ 6 ^ I% - SIN (& HA09B + B # - C% * D #) + & B1> 0 #

2) # NOT ВД MOD конст_10 о_ср ВД AND ВД ^ конст_10 ^ ІД - FUNK (конст_16 + ИД-ВД * ВД) + конст_2 о_ср ВД #

3) # NOT ІД_К MOD ІД_К о_ср ІД_К AND ІД_К ^ ІДК ^ ІДК-FUNK (ІД_К + ІД_К-ІД_К * ІД_К) + ІД_К о_ср ІД_К #

4) # NOT A_4 MOD A_4 ​​o_cp A_4 AND A_4 ​​^ A_4 ^ A_4 - FUNK (A_4 + A_4 - A_4 * A_4) + A_4 o_cp A_4 #

5) # NOT A_3 MOD A_3 o_cp A_3 AND A_4 ​​^ A_ ^ A_3 - FUNK (A_3 + A_3 - A_3 * A_3) + A_3 o_cp A_3 #

6) # NOT A_2 MOD A_3 o_cp A_2 AND A_4 ​​^ A_3 - FUNK (A_2 + A_2 - A_2 * A_2) + A_2 o_cp A_2 #

7) # NOT A_2 o_cp A_1 AND A_3 - FUNK (A_1 + A_1 - A_2 * A_1) + A_1 o_cp A_1 #

8) # NOT A_1 o_cp A_B AND A_2 - FUNK (A_B + A_1 - A_1) + A_1 o_cp A_B #

9) # NOT A_B o_cp A_B AND A_1 - FUNK (A_B - A_1) + A_1 o_cp A_B #

10) # NOT ЗНАК AND A_B - FUNK (A_B) + A_1 o_cp A_B #

11) # Л _3 AND A_B - FUNK (A_B) + A_1 o_cp A_B #

12) # Л _2 AND A_B - A_4 + A_1 o_cp A_B #

13) # Л _2 AND A_B - A_3 + A_1 o_cp A_B #

14) # Л _2 AND A_B - A_2 + A_1 o_cp A_B #

15) # Л _2 AND A_B - A_1 + A_1 o_cp A_B #

16) # Л _2 AND A_B + A_1 o_cp A_B #

17) # Л _2 AND A_B o_cp A_B #

18) # Л _2 AND ЗНАК #

19) # Л _2 AND Л _3

20) # Л_2 #

21) # Л_1 #

22) # Л_ B #

23) # ВИРАЗ #

Прості фрази:

1) A%, 5, C #, M%, 6, I%, SIN, & HA09B, B #, C%, D #, & B1,>, 0

2) ВД, конст_10, ВД, ВД, конст_10, ВД, конст_16, ВД, ВД, ВД, конст_2, конст_10

3) ІД_К, ІД_К, ІД_К, ІД_К, ІД_К, ІД_К, ІД_К, ІД_К, ІД_К, ІД_К, ІД_К, ІД_К

4) A_4, A_4, A_4, A_4, A_4

5) A_3, A_3, A_4 ^ A_3, A_3, A_3, A_3, A_3, A_3, A_3

6) A_2 MOD A_3, A_2, A_4 ^ A_3, A_2, A_2, A_2, A_2, A_2

Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Контрольна робота
138.3кб. | скачати

Схожі роботи:
Принципи побудови формальних теорій
Вплив формальних і неформальних організацій на ефективність роботи компанії
Розробка турпродукту
Розробка балансів
Розробка СУБД
Розробка загального ПЗ
Розробка сканера
Розробка ПЗ ІС Аптеки
Розробка реклами
© Усі права захищені
написати до нас