Контрольні запитання на мкр №2

Синтаксичний аналіз в мовних процесорах

1. Які граматики називаються однозначними?

2. Які дві стратегії виведення ви знаєте?

3. Що таке синтаксичне дерево виведення?

4. Що таке лівосторонній аналіз ланцюжка?

5. Що таке синтез дерева за аналізом?

6. Які дві стратегії синтезу дерева за аналізом ви знаєте?

7. Що таке граматика з циклами і які проблеми вона створює для стратегії “згори донизу”?

8. Який підклас КС-граматик забезпечує стратегію аналізу “зверху донизу”?

Магазинні автомати

1. Що таке магазинний автомат?

2. Що таке конфігурація магазинного автомату?

3. Які конфігурації магазинного автомату називаються початковою і заключною?

4. Що таке такт роботи і робота магазинного автомату?

5. Яку мову розпізнає магазинний автомат?

6. Що таке проблема порожньої множини $L(M)$?

7. Як за КС-граматикою $G$ побудувати магазинний автомат $M$ такий, що $L(G) = L(M)$?

8. Яку стратегію виведення $\omega$ в $G$ реалізує побудований у попередньому питанні автомат, і яка обчислювальна складність алгоритму розпізнавання слова $\omega$?

Синтаксичний аналіз без повернення назад

1. Яка граматика називається $LL(k)$-граматика?

2. Чи кожна КС-граматика є $LL(k)$-граматикою для деякого $k$?

3. Яка $LL(1)$-граматика називається розподіленою?

4. Яку бінарну операцію над мовами позначає символ $\oplus_k$?

5. Яку мову (множину слів) позначає запис $\text{First}_k(\alpha)$?

6. Опишіть алгоритм пошуку $\text{First}_k$ і доведіть його збіжність.

7. Яка $LL(k)$-граматика називається сильною?

8. Чи кожна $LL(k)$-граматика є сильною $LL(k)$-граматикою?

9. Яку мову (множину слів) позначає запис $\text{Follow}_k(\alpha)$?

10. Опишіть алгоритм пошуку $\text{Follow}_k$ і доведіть його збіжність.

11. Який нетермінал $A_i \in N$ називається $\varepsilon$-нетерміналом?

12. Опишіть алгоритм перевірки нетерміналу $A_i \in N$ на $\varepsilon$-нетермінал і доведіть його збіжність.

13. Який нетермінал $A_i \in N$ називається ліворекурсивним?

14. Опишіть алгоритм перевірки нетерміналу $A_i \in N$ на ліву рекурсію і доведіть його збіжність.

Синтаксичний аналіз на $LL(1)$-граматиках

1. Які дві умови повинна задовольняти граматика щоб бути $LL(1)$-граматикою?

2. Що таке таблиця керування синтаксичного аналізатора на основі $LL(1)$-граматики?

3. Який автомат і яка таблиця використовуються в алгоритмі роботи $LL(1)$-синтаксичного аналізатора?

4. Опишіть алгоритм роботи $LL(1)$-синтаксичного аналізатора.

5. Як необхідно модифікувати таблицю керування для сильної $LL(2)$-граматики яка є майже $LL(1)$-граматикою?

6. Як необхідно модифікувати алгоритм роботи синтаксичного аналізатора для сильної $LL(2)$-граматики яка є майже $LL(1)$-граматикою?

Програмування синтаксичних аналізаторів

1. Який граф називається синтаксичною діаграмою?

2. Як на синтаксичній діаграмі позначаються термінали і нетермінали?

3. Як на синтаксичній діаграмі позначаються прості (без $\vert$) і складені (з $\vert$) правила?

4. Напишіть фрагмент коду (наприклад на мові С) для обробки терміналів і нетерміналів.

5. Напишіть фрагмент коду (наприклад на мові С) для обробки простих (без $\vert$) і складених (з $\vert$) правил.

6. Як на синтаксичній діаграмі позначаються правила вигляду $A \mapsto \omega \mid \varepsilon$?

7. Напишіть фрагмент коду (наприклад на мові С) для обробки правил вигляду $A \mapsto \omega \mid \varepsilon$.

Побудова $LL(k)$-синтаксичного аналізатора

1. Наведіть визначення множини $\text{Local}_k(S, A)$.

2. Опишіть алгоритм побудови $\text{Local}_k(S, A)$.

3. Опишіть алгоритм побудови таблиць керування (або рядків великої результуючої таблиці керування).

4. Якою формулою визначається кількість рядків таблиці керування?

5. Опишіть алгоритм синтаксичного аналізу для $LL(k)$-граматики.

(традиційні відповіді можна переглянути у коментарях у вихідному коді цієї сторінки)

Назад на головну