ЩЕ МАТЕРІАЛИ ПО ТЕМІ:
Особливість розглянутих вище формальних граматик в тому, що вони дозволяють визначити безліч ланцюжків мови за допомогою кінцевого набору правил (звичайно, безліч ланцюжків мови теж може бути кінцевим, але навіть для простих реальних мов ця умова зазвичай не виконується). Наведена вище в прикладі граматика для цілих десяткових чисел зі знаком визначає безліч цілих чисел за допомогою 15 правил.
У такій формі запису граматики можливість користуватися кінцевим набором правил досягається за рахунок рекурсивних правил. Рекурсія в правилах граматики виражається в тому, що один з нетермінальних символів визначається сам через себе. Рекурсія може бути безпосередньою (явної) - тоді символ визначається сам через себе в одному правилі, або непрямої (неявній) - те ж саме відбувається через ланцюжок правил.
У розглянутій вище граматиці G безпосередня рекурсія присутній в правилі: <чс> ® <чс><цифра>, а в еквівалентній їй граматиці G '- в правилі T®TF.
Щоб рекурсія була нескінченною, для бере участь в ній нетермінального символу граматики повинні існувати також і інші правила, які визначають його, минаючи його самого, і дозволяють уникнути нескінченного рекурсивного визначення (в іншому випадку цей символ в граматиці був би просто не потрібний). Такими правилами є <чс> ® <цифра> - в граматиці G і T ® F - в граматиці G '.
У теорії формальних мов більш нічого сказати про рекурсії можна. Але щоб повніше зрозуміти сенс рекурсії, можна вдатися до семантиці мови - в розглянутому вище прикладі це мова цілих десяткових чисел зі знаком. Розглянемо його зміст.
Якщо спробувати дати визначення того, що ж є числом, то почати можна з того, що будь-яка цифра сама по собі є число. Далі можна помітити, що будь-які дві цифри - це теж число, потім - три цифри і т. Д.
Якщо будувати визначення числа таким методчом, то воно ніколи не буде закінчено (в математиці розрядність числа нічим не обмежена). Однак можна помітити, що кожен раз, породжуючи нове число, ми просто дописуємо цифру праворуч (оскільки звикли писати зліва направо) до вже написаного ряду чисел. А цей ряд цифр, починаючи від однієї цифри, теж в свою чергу є числом. Тоді визначення для поняття "число" можна побудувати таким чином: "число - це будь-яка цифра або інше число, до якого справа дописана будь-яка цифра". Саме це і становить основу правил граматик G і G 'і відображено в правилах <чс> ® <цифра> | <чс><цифра> і Т ® Р | ТF (другий рядок правил). Інші правила в цих граматиках дозволяють додати до числа знак (перший рядок правил) і дають визначення поняттю "цифра" (третій рядок правил). Вони елементарні й не вимагають пояснень.
Принцип рекурсії (іноді його називають "принцип ітерації") - важливе поняття в поданні про формальні граматиках. Так чи інакше, явно або неявно рекурсія завжди присутній в граматиках будь-яких реальних мов програмування. Саме вона дозволяє будувати безліч ланцюжків мови, і говорити про їх породженні неможливо без розуміння принципу рекурсії. Як правило, в граматиці реального мови програмування міститься не одне, а ціле безліч правил, побудованих за допомогою рекурсії.