UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75843
останнє поновлення: 2016-12-04
за 7 днів додано 15

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваФормальні мови та їх задання (реферат)
Автор
РозділІнформатика, компютерні науки
ФорматWord Doc
Тип документуРеферат
Продивилось2233
Скачало190
Опис
ЗАКАЧКА
Замовити оригінальну роботу

ЕЛЕМЕНТИ СИНТАКСИЧНОГО АНАЛІЗУ

 

1. Формальні мови та їх задання

 

1.1. Формальна мова та задача належності

 

Алфавітом називається скінченна множина символів. Позначатимемо його X.

Словом (фразою, або ланцюжком) у алфавіті X називається послідовність

символів із X. Множина всіх скінченних слів у алфавіті X позначається

X*. Зауважимо, що вона нескінченна. Вона містить порожнє слово –

послідовність довжиною 0, позначену буквою ? . Множину X*\{? } позначимо

X+, а слово вигляду ww? w, де слово w із X+ записано n разів – wn.

Вважатимемо, що w0 = ? .

 

Довільна підмножина множини X* називається формальною мовою. Далі в

цьому розділі вона буде називатися просто мовою.

 

Приклади

 

21.1. Множина всіх слів у алфавіті {a} позначається {a}* = {? , a, aa,

aaa, … } = { an | n ? 0 }. {an|n–непарне} позначає множину, або мову

слів непарної довжини в алфавіті {a}; обидві мови нескінченні.

 

21.2. Ідентифікатор є послідовністю букв і цифр, що починається буквою.

Множина всіх ідентифікаторів у алфавіті X={a, b, 1} нескінченна. Якщо

записати їх за зростанням довжини, то початок буде таким: { a, b, a1,

aa, ab, b1, ba, bb, ? }.

 

Задача перевірки, чи належить слово w мові L, називається задачею

належності, або проблемою слів. Як правило, множина L задається певним

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

елементів.

 

Задача належності розв'язується найчастіше шляхом перевірки, чи має

слово відповідну структуру, тобто шляхом синтаксичного аналізу, або

розпізнавання. Наприклад, структура всіх можливих синтаксично правильних

Паскаль-програм визначається скінченною та відносно невеликою сукупністю

БНФ. Саме на її основі будуються синтаксичні аналізатори в трансляторах,

тобто програми аналізу синтаксичної правильності вхідних програм.

 

Формальні мови розглядатимуться далі як мови, задані саме скінченним

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

У розділі 10 ми вже познайомилися з одним із них – це були БНФ та їх

сукупності. Розглянемо ще деякі.

 

1.2. Регулярні операції, вирази та мови

 

Означимо регулярні операції над мовами: об'єднання, катенацію та

ітерацію. Нехай L1 , L2 , L позначають довільні мови в алфавіті X.

 

Вираз L1? L2 позначає об'єднання L1 і L2 – мову {w|w? L1 або w? L2}.

Наприклад, {a, ab}? {a, b, ba}={a, b, ab, ba}.

 

Катенацією слів v і w називається дописування w після v: vw. Вираз L1L2

позначає катенацію мов – мову {vw|v? L1, w? L2}. Так, за L1={a, bc},

L2={x, y} катенація L1L2={ax, bcx, ay, bcy}, за L1={a, ab}, L2={? , b}

катенація L1L2={a, ab, abb}.

 

Від катенації походить піднесення до степеня: L0={? }, Li=Li-1L за i>0.

Так, вираз {? , a, aa}2 задає мову {? , a, aa, aaa, aaaa}.

 

Вираз L* позначає ітерацію мови L – мову {wi|w? L за i? 0}, тобто {? }?

L? L2? ? . Зазначимо, що ітерація не подається жодним скінченним виразом

з операціями катенації та ? і тому не є похідною від них. Якщо в мові L

є непорожнє слово, то мова L* нескінченна. Наприклад, вираз {ab}* задає

мову {? ,ab,abab,ababab,? }, {a,b}{a,b,1}* – множину ідентифікаторів у

-----> Page:

0 [1] [2] [3] [4] [5] [6] [7] [8]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ