48984 (666135), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

Формальною граматикою Г називається сукупність таких об’єктів:

Г={V_T,V_N,,R},

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

V_N – нетермінальний (допоміжний) алфавіт. Його букви використовуються при побудові ланцюжків, вони можуть входити в проміжні ланцюжки, але не можуть входити в результат побудови.

- початковий символ.

R – множина правил виведення.

Множина кінцевих ланцюжків термінального алфавіту V_T граматики Г, виведених з початкового символу називають мовою, яка породжена граматикою Г і позначається L(Г).

Якщо правило виведення граматики мінить один нетермінальний символ, як в лівій, так і в правій частині, то таке правило називається рекурсивним.

Типи формальних граматик

Виділяють 4 типи формальних граматик. Ці граматики визначаються шляхом накладання обмежень на правила граматики.

Граматика типу 0 – граматика загального вигляду, немає обмежень на правила породження.

Граматика типу 1 – контекстно залежна.

Правило: χ₁χ₂→ χ₁ωχ₂.

Ланцюжки χ₁ і χ₂ залишаються незмінними при застосуванні правил, тому їх називають контекстом, а граматику – контекстно залежною.

Граматика типу 2 – контекстно вільна.

Правило: →α, де .

Ці правила слідують із правил граматики типу 1 за умови χ₁ = χ₂ = $.

Граматика типу 3 – автоматна.

Правила виведення: →a або →a або →a, де

.

Способи задання схем граматик

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

символічна

форма Бекуса-Наура (ФБН)

ітераційна

синтаксичні діаграми

Символьна мова передбачає використання елементів нетермінального словника і стрілки, як роздільника правої і лівої частини. Але при описі конкретних мов програмування доводиться вводити велику кількість не термінальних символів і символьна форма запису втрачає свою наочність.

Характеристики

Список файлов реферата