русс | укр

Мови програмуванняВідео уроки php mysqlПаскальСіАсемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование


Linux Unix Алгоритмічні мови Архітектура мікроконтролерів Введення в розробку розподілених інформаційних систем Дискретна математика Інформаційне обслуговування користувачів Інформація та моделювання в управлінні виробництвом Комп'ютерна графіка Лекції


Розбір ланцюжків


Дата додавання: 2013-12-24; переглядів: 1394.


Синтаксичний розбір. Лівий і правий висновок. Неоднозначні та еквівалентні граматики. Способи завдання схем граматик. Рекомендації з побудови граматик. Опис списків. Приклад побудови граматик

Приклади граматик і мов

Співвідношення між типами мов

1. Кожна регулярна мова є КВ-мовою, але існують КВ-мови, що не є регулярними (наприклад, L={anbn | n>0}).

2. Кожна КВ-мова є КЗ-мовою, але існують КЗ-мови, що не є КВ-мовами (наприклад, L={anbncn | n>0});

3. Кожна КЗ-мова є мовою типу 0.

Зауваження: УКВ-мова, що містить порожній ланцюжок, не є КЗ-мовою.

Зауваження: варто підкреслити, якщо мова задана граматикою типу k, то це не означає, що не існує граматики типу k| (k|>k), що описує ту саму мову. Тому, коли говорять про мову типу k, звичайно мають на увазі максимально можливий номер k.

Наприклад: КЗ-граматикаG1=({0,1},{A,S},P1,S) і КВ-граматика G2=({0,1},{S}, P2, S),

де

Р1: S0A1

0A00A1

A

P2: S0S1 | 01

описують ту саму мову L=L(G1)=L(G2)={0n1n | n>0}.

Мову L називають КВ-мовою, тому, що існує КВ-граматика, що її описує. Але вона не є регулярною мовою тому, що не існує регулярної граматики, що описує цю мову.

 

Зауваження: якщо при описі граматики зазначені тільки правила висновку Р, то будемо вважати, що великі латинські букви позначають нетермінальні символи, S – ціль граматики, всі інші символи термінальні.

1. Мова типу 0:

G(L):

 

2. Мова типу 2: L={ланцюжок з 0 і 1 з однаковим числом 0 і 1}

G(L):

 

3. Мова типу 2:

G(L):

4. Мова типу 3: , де немає двох , що знаходяться поруч}

G(L):

Ланцюжок належить мові, породженою граматикою, тільки у тому випадку, якщо існує її висновок з мети цієї граматики. Процес побудови такого висновку (а, отже, і визначення належності ланцюжка мові), називається розбором.

З практичної точки зору найбільший інтерес представляє розбір за контекстно-вільними граматиками (КВ чи УКВ). Їхньої породжуючої потужності досить для опису більшої частини синтаксичної структури мов програмування, для різних підкласів КВ-граматик є добре розроблені практично прийнятні способи рішення задачі розбору.

Розглянемо основні визначення, пов‘язані з розбором за КВ-граматикою.

Висновок ланцюжка з у КВ-граматиці G=(VT, VN, P, S), називається лівим (лівостороннім), якщо у цьому висновку кожна чергова сентенціальна форма виходить з попередньої заміною самого лівого нетермінала.


<== попередня лекція | наступна лекція ==>
Співвідношення між типами граматик | Визначення


Онлайн система числення Калькулятор онлайн звичайний Науковий калькулятор онлайн