ОПК:перша контрольна

Матеріал з USIC Wiki

Перейти до: навігація, пошук

Ця стаття відноситься до групи довідкових статей для студентів ФІН.

Портал:Інформаційні науки

Перша контрольна з цієї дисципліни відбудеться у п"ятницю, 22 лютого о 8.30, аудиторія 1-225

Зміст

1 Завдання1
2 Завдання2
3 Завдання3
4 Додаткові матеріали
5 Варіанти

Завдання1

Ця стаття не закінчена. Будь ласка, допишіть її.

Дана блочна структура програми. За нею побудувати таблицю імен та адресні бази (як це робить компілятор, аналізуючи код програми)

блок - структура, яка починається на begin, закінчується на end, в собі містить оголошення типу: int a,b; float A[],...

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

Статична пам'ять:

номер блоку (НБ) (як пронумеровали кожен блок)
номер блоку (КБ), що охоплює даний
кількість змінних цього блоку + мітка L_i (КЗм)
стек - при проходженні коду програми, вниз автоматично потраляють змінні та мітка, блок яких потрапив першим в область видимості. Як тільки блок закриється - все це добро піднімається вверх(на ту позицію, що ще незайнята). Отже найнижче знаходяться змінні, які пропадають з області видимості найпізніше. найвище ті, що закриті раніше.
адресна база - навпроти елементів стеку написати АБ та номер блоку, що містить їх.

Пронумеровати блоки, краще це робити згори донизу, йдучи по вкладеним - по ходу виконання програми. (НБ)
Таким самим чином розставляємо мітки, зручніше їх ставити біля оголошення змінних.
Для кожного блоку вкажемо номер його батьківського блоку КБ
заповнюємо стек:

першим покладемо донизу блок [a1, b1, c1, L1] -він там і залишиться до кінця, оскільки закривається останнім

другим піде блок [a2, b2, c2, L2]

третім знизу впаде [s3, L3], але його зразу піднімаємо до самої гори, оскільки це перший блок що закривається

другий піднімаємо догори, оскільки був закритий після блоку три

третім зверху буде [s4, L4], оскільки він закривається другим по рахунку

четвертим зверху стане [a5, b5, L5]

блоку [x1, y1, L6] нема куди подітись окрім як бути другим знизу

Маємо:

Побудувати таблицю імен та накласти на неї рамки відповідно до блочної структури.

Встановити активний дисплей та область видимості для точки з міткою L1231.

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

Завдання2

Ця стаття не закінчена. Будь ласка, допишіть її.

Дано завдання, наприклад: "стрічка починається з нуля та містить парну кількість нулів".

Побудувати Діаграму переходів

Побудувати Матрицю переходів

Поради до виконання завдання:

1.написати кілька "крайніх" тестових стрічок, які б задовольняли умові задічі

2.для себе скласти уявний шаблон цих стрічок

3.Завжди вхідним для кожної із стрічок буде "0", але він обрізається тому про нього можна забути

4.Петлі виду - можуть йти по "0" та по "1", означають що скількись разів виконується вставляння "0" або "1", може не виконатись жодного разу

5.Переходи виду - перехід із стану у стан.Виконуються завжди обов"язково і по тому символу, який написаний.

6.Заключний стан - на схемі обведений колом - цикл після якоїсь ітерації закінчується саме на ньому. Значить символ, по якому перейшли в цей заключний стан буде останнім у ланцюжку.

Приклад. Побудувати автомат, який пропускає рядки з непарною кількістю нулів.

Спочатку побудуємо діаграму переходів.

Можна побачити, що автомат пропускає всі одиниці, поки не натрапить на нуль. Потім він переходить у стан $q 1$ , у якому одиниці так само пропускаються, а в разі, якщо трапився нуль, автомат переходить у стан $q 2$ . У цьому стані пропускаються одиниці, а за нулем переходимо назад у $q 1$ . Цей стан $q 1$ є заключним, тобто якщо ми дійшли до кінця рядка, і ми в цьому стані, то наш рядок правильний для цього автомату.

Побудуємо матрицю переходів.


	0	1
$q 0$	$q 1$	$q 0$
$q 1$	$q 2$	$q 1$
$q 2$	$q 1$	$q 2$

Завдання3

Ця стаття не закінчена. Будь ласка, допишіть її.

Дана граматика, наприклад: (ba)ⁿb^ma^m

Вказати тип граматики (самовставляння, квазіавтомат)
Написати правила граматики (аксіомами описати граматику)
Вказати, чи однозначна/неоднозначна, приведена/неприведена (приведена тоді, коли перехід в епсілон є тільки в одній аксіомі - S $\rightarrow$ AB| $\varepsilon$ , а також коли вона є однозначною. Граматика є однозначною тоді, коли в кожного ланцюжка є лише один вивід)
Побудувати дерево синтаксичного розбору

Приклад:

Дана граматика: aⁿ⁺¹(bc)²ⁿ(abc)^m

1) Спростимо граматику: aⁿ⁺¹(bc)²ⁿ(abc)^m = aaⁿ(bc)²ⁿ(abc)^m

бачимо, що фрагмент aⁿ(bc)²ⁿ - з узгодженим степенем n тобто граматика самовставляння, при кожній ітерації буде записуватись A $\rightarrow$ aAbcbc . Тобто всі ланцюжки виду: abcbc, n=1; aaabcbcbcbcbcbc; n=3
фрагмент a при будь-якій ітерації лишиться,тому при написанні аксіоми ми його просто лишимо S
фрагмент (abc)^m C $\rightarrow$ abcC, тобто усі ланцюжки виду abc, m=1; abcabcabcabcabc, m=5

Тепер можна виписати правила граматики:

S $\rightarrow$ aAC

A $\rightarrow$ aAbcbc| $\varepsilon$

C $\rightarrow$ abcC| $\varepsilon$

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

A - великими латинськими літерами позначають нетермінальні символи (з яких виводяться терми - малі латинські)

a - термінальний символ (терм)

$\varepsilon$ - символ, яким закінчується вивід граматики

Додаткові матеріали

Класифікація граматик за Хомським
Нормальна форма Хомського

Нормальна форма Хомського (НФХ - бінарна нормальна форма) встановлюється для приведеної контекстно-вільної (КС) граматики, всі правила якої мають вигляд:

1. A->BC, де A,B,C належать N (множині нетермінальних символів)

2. A-> a, де a належить

Σ

3. S -> $\varepsilon$ , якщо $\varepsilon \in$ L(G)

Твердження 1. нехай L(G) – КС-мова. Тоді L(G) = L(G’) для деякої КС-граматики G’ в нормальній формі Хомського.

Для виконання перетворень необхідно спочатку отримати приведену форму, застосовуючи розглянуті алгоритми ([1]), а потім отримати НФХ. Отримати НФХ розглянемо на прикладі.

Нехай G – приведена КС-граматика з правилами:

S -> aAB | BA

A -> BBB | a

B -> AS | b

Введемо додаткові символи, що замінять ланцюжки AB, BB, a:

C -> AB,

D -> BB,

F -> a

Отримаємо G’ – грамматику в НФХ и L(G) = L(G’):

S -> FC | BA

A -> BD | a

B -> AS | b

C -> AB

D -> BB

F -> a

Нормальна форма Грейбах

Нормальна форма Грейбах (НФГ). КС-граматика (контекстно-вільна)

G = (Ν,Σ,Ρ, S)

перебуває в НФГ, якщо вона приведена і кожне равило із Р, відмінне від S -> $\varepsilon$ , має вигляд A -> aα, де $a \in \Sigma$ та $\alpha \in \Nu*$ . При додаткових обмеженнях накладених на мову і правила, за такою граматикою будуються прості та ефективні СА, оскільки майже завжди можна одразу встановити, скільки символів треба читати із вхідного потоку, щоби однозначно обрати правила в процесі виводу. Побудова граматики в НФГ має за основу позбуття лівої рекурсії в правилах.

Право/ліворекурсивна граматика

Нетермінал $Α$ контекстно-вільної (КС) граматики $G = (Ν,Σ,Ρ, S)$ називається ліворекурсивним, якщо $\Alpha \Rightarrow ^+ \Alpha\beta$ для деякого $\beta\,$ та праворекурсивним, якщо $\Alpha \Rightarrow^+ \alpha\Alpha$ для деякого $\alpha\,$ .

Граматика, що має хоч один ліворекурсивний нетермінал є ліворекурсивною граматикою,а та що має хоч один праворекурсивний нетермінал - є праворекурсивною граматикою. Граматика є рекурсивною, якщо вона ліво- або праворекурсивна.

http://en.wikipedia.org/wiki/Help:Formula

Варіанти

Варіант 16

ОПК:перша контрольна

Матеріал з USIC Wiki

Зміст

Завдання1

Завдання2

Завдання3

Додаткові матеріали

Варіанти

Перегляди

Особисті інструменти

Навігація

Пошук

Інструменти