Page 36 - 4625

    ...  та побудуємо нове дерево. Даний пункт
i
1 2
l
виконувати доти, доки не переглянемо всі елементи з .
Сформулюємо декілька проблем для стратегії
аналізу "зверху донизу":
 загалом у класі КС-граматик існує проблема
неоднозначності (недетермінізму) виводу   L(G). Як
приклад можемо розглянути граматику з "циклами". Це така
граматика, у якої в схемі P існує така послідовність правил за
участю нетермінала A , що: A  , де A – будь-який
i
j
i
i
нетермінал граматики G;
 як наслідок з попереднього пункту, граматики з
ліворекурсивним нетерміналом для стратегії аналізу "зверху
донизу" недопустимі;
 існують підкласи класу КС-граматик, які природно
забезпечують стратегію аналізу "зверху донизу". Один з
таких підкласів — це LL(k)-граматики, які забезпечують
синтаксичний аналіз ланцюжка   L(G) за час O(n) , де n |
 |, та при цьому є однозначним.

5. ЛАБОРАТОРНИЙ ПРАКТИКУМ ПОБУДОВИ
СИНТАКСИЧНИХ АНАЛІЗАТОРІВ
Граматика мови програмування визначається множиною
БНФ-правил, що записані в текстовому файлі. Кожне провило
обов'язково починається з першої позиції рядка. Для зручності
правило можна продовжити в наступних рядках, але не з
першої позиції. Нетермінал граматики - це ланцюжок літер,
який починається з символу < та закінчується символом >,
наприклад <програма>. Термінальні ланцюжки записуються
традиційно, наприклад, begin. Альтернативи правила для
зручності позначаються символом ! в першій позиції рядка,
при цьому ліва частина правила опускається. Оскільки сим-
воли <, > та ! є мета символами при визначенні граматики, то
для їх запису в термінальних ланцюжках використовується ще

35