/  
 ДОКУМЕНТІВ 
20298
    КАТЕГОРІЙ 
30
Про проект  Рекламодавцям  Зворотній зв`язок  Контакт 

Елементи синтаксичного аналізу, Детальна інформація

Тема: Елементи синтаксичного аналізу
Тип документу: Реферат
Предмет: Комп`ютерні науки
Автор: Олексій
Розмір: 0
Скачувань: 687
Скачати "Реферат на тему Елементи синтаксичного аналізу"
Сторінки 1   2   3   4   5   6   7   8   9  
ЕЛЕМЕНТИ СИНТАКСИЧНОГО АНАЛІЗУ

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

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

Алфавітом називається скінченна множина символів. Позначатимемо його X. Словом (фразою, або ланцюжком) у алфавіті X називається послідовність символів із X. Множина всіх скінченних слів у алфавіті X позначається X*. Зауважимо, що вона нескінченна. Вона містить порожнє слово – послідовність довжиною 0, позначену буквою \xF065 . Множину X*\{\xF065 } позначимо X+, а слово вигляду ww\xF0BC w, де слово w із X+ записано n разів – wn. Вважатимемо, що w0 = \xF065 .

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

Приклади

21.1. Множина всіх слів у алфавіті {a} позначається {a}* = {\xF065 , a, aa, aaa, … } = { an | n \xF0B3 0 }. {an|n–непарне} позначає множину, або мову слів непарної довжини в алфавіті {a}; обидві мови нескінченні.

21.2. Ідентифікатор є послідовністю букв і цифр, що починається буквою. Множина всіх ідентифікаторів у алфавіті X={a, b, 1} нескінченна. Якщо записати їх за зростанням довжини, то початок буде таким: { a, b, a1, aa, ab, b1, ba, bb, \xF0BC }.

Задача перевірки, чи належить слово w мові L, називається задачею належності, або проблемою слів. Як правило, множина L задається певним скінченним описанням, що визначає не тільки її саму, а й структуру її елементів.

Задача належності розв'язується найчастіше шляхом перевірки, чи має слово відповідну структуру, тобто шляхом синтаксичного аналізу, або розпізнавання. Наприклад, структура всіх можливих синтаксично правильних Паскаль-програм визначається скінченною та відносно невеликою сукупністю БНФ. Саме на її основі будуються синтаксичні аналізатори в трансляторах, тобто програми аналізу синтаксичної правильності вхідних програм.

Формальні мови розглядатимуться далі як мови, задані саме скінченним описом. Отже, головним у вивченні формальних мов стає засіб їх задання. У розділі 10 ми вже познайомилися з одним із них – це були БНФ та їх сукупності. Розглянемо ще деякі.

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

Означимо регулярні операції над мовами: об'єднання, катенацію та ітерацію. Нехай L1 , L2 , L позначають довільні мови в алфавіті X.

Вираз L1\xF0C8 L2 позначає об'єднання L1 і L2 – мову {w|w\xF0CE L1 або w\xF0CE L2}. Наприклад, {a, ab}\xF0C8 {a, b, ba}={a, b, ab, ba}.

Катенацією слів v і w називається дописування w після v: vw. Вираз L1L2 позначає катенацію мов – мову {vw|v\xF0CE L1, w\xF0CE L2}. Так, за L1={a, bc}, L2={x, y} катенація L1L2={ax, bcx, ay, bcy}, за L1={a, ab}, L2={\xF065 , b} катенація L1L2={a, ab, abb}.

Від катенації походить піднесення до степеня: L0={\xF065 }, Li=Li-1L за i>0. Так, вираз {\xF065 , a, aa}2 задає мову {\xF065 , a, aa, aaa, aaaa}.

Вираз L* позначає ітерацію мови L – мову {wi|w\xF0CE L за i\xF0B3 0}, тобто {\xF065 }\xF0C8 L\xF0C8 L2\xF0C8 \xF0BC . Зазначимо, що ітерація не подається жодним скінченним виразом з операціями катенації та \xF0C8 і тому не є похідною від них. Якщо в мові L є непорожнє слово, то мова L* нескінченна. Наприклад, вираз {ab}* задає мову {\xF065 ,ab,abab,ababab,\xF0BC }, {a,b}{a,b,1}* – множину ідентифікаторів у алфавіті {a, b, 1}.

Регулярні вирази й задані ними регулярні мови означимо індуктивно. Вирази \xF0C6 , \xF065 та a при a\xF0CE X є регулярними в алфавіті X і задають відповідно регулярні мови \xF0C6 , {\xF065 }, {a}. Якщо r1 і r2 – регулярні вирази, що задають регулярні мови L1 і L2 , то вирази (r1), r1+r2, r1r2, r1* є регулярними й задають відповідно регулярні мови L1, L1\xF0C8 L2, L1L2, L1*.

Очевидно, що кожна скінченна мова є регулярною, оскільки задається регулярним виразом як скінченне об'єднання одноелементних регулярних мов.

Множина регулярних мов, заданих усіма можливими регулярними виразами в алфавіті X, називається класом регулярних мов над X.

Регулярні операції застосовні до будь-яких мов, а не тільки до регулярних. За означенням, застосування їх до регулярних мов породжує регулярні мови.

Не всі мови є регулярними. Наприклад, "мова вкладених дужок", задана БНФ

<вкл-дуж> ::= ( ) | ( <вкл-дуж> ),

є множиною {(n)n|n>0}, яка не задається жодним скінченним регулярним виразом (доведення можна знайти в [АУ]). Отже, розглянемо інші, потужніші засоби задання мов.

21.1.3. Граматики Хомського

Граматикою Хомського називається четвірка G = (X, N, P, S). Тут

X – алфавіт означуваної мови, або множина термінальних символів (терміналів).

N – множина позначень понять мови, тобто нетермінальних символів (нетерміналів).

P – множина правил виведення (продукцій) вигляду v\xF0AE w, де

v \xF0CE ( X \xF0C8 N )* N ( X \xF0C8 N )* , w \xF0CE ( X \xF0C8 N )*

Сторінки 1   2   3   4   5   6   7   8   9  
Коментарі до даного документу
Додати коментар