WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Формальні мови та їх задання - Реферат

Формальні мови та їх задання - Реферат

Інколи довжину записують замість '*' таким чином: v==> nw, наприклад, BC ==> 2a1.
3. Якщо S==> G*w, то послідовність S==> …==> w називається виведенням слова w у граматиці G, а слово w - вивідним. Так, слова A, BC, aC, a1 вивідні в граматиці G1.
4. Вивідні слова в алфавіті X називаються породжуваними, а множина їх усіх - мовою, що задається(породжується) граматикою G: L(G) = {w | w X* та S ==> * w }.
Приклади
4. Граматика G1 із прикладу 21.3 задає мову { a, a1, a2 }.
5. Граматика
G2 = ( { a, …, z, 0, …, 9 }, { I, L, D },
{ I L | IL | ID, L a | … | z, D 0 | ... | 9 },
I )
породжує множину ідентифікаторів.
6. Граматика G3 = ( { (, ) }, { S }, { S | ( S ) }, S ) задає множину "вкладених дужок" { (n)n | n 0 }.Р
21.7. Граматика
G4 = ( { a, b, c }, { S, A, B, C},
{ S aSBC | abC, CB BC, bB bb, bC bc, cC cc },
S )
визначає мову { anbncn | n 1 }.Р
Граматики називаються еквівалентними, якщо задають ту саму мову. Наприклад, граматика
( { a, 1, 2 }, { A }, { A a [ 1 | 2 ] }, A )
еквівалентна граматиці G1, граматика
( {a, …, z, 0, …, 9}, {I, C}, {I (a|…|z)C, C |C(a |…|z|0|…|9)}, I )
- граматиці G2.
Є два види граматик з продукціями обмеженого вигляду, якими задаються регулярні мови, - це праволінійні та ліволінійні граматики. Праволінійною (ліволінійною) називається граматика, всі продукції якої мають вигляд A w або A wB (відповідно, A w або A Bw), де A, B - нетермінали, w X*. Усі можливі праволінійні та ліволінійні граматики з термінальним алфавітом X породжують в точності клас регулярних мов над X. Це доводиться, наприклад, в [АУ].
2. Контекстно-вільні та LA(1)-граматики
2.1. Контекстно-вільні граматики
Контекстно-вільною, або КВ-граматикою, називається граматика, в якій ліві частини всіх продукцій є нетерміналами. Зміст терміну "контекстно-вільна" полягає в тім, що застосування продукції A w до ланцюжка uAv не залежить, тобто є вільним від сусідніх з A символів, які утворюють контекст uv.
Зазначимо, що БНФ вигляду A::=w цілком аналогічна продукції A w. Отже, сукупності БНФ є просто іншою формою КВ-граматик.
Контекстно-вільною мовою (КВ-мовою) називається мова, що може бути задана КВ-граматикою.
Прикладами КВ-граматик та КВ-мов є граматики з прикладів 21.3, 21.5, 21.6 у попередньому параграфі й задані ними мови. Граматика з прикладу 21.7 не є КВ-граматикою. До речі, мова, задана нею, не є КВ-мовою, оскільки не існує КВ-граматики, яка б її задавала.
КВ-граматики відіграють особливу роль у програмуванні, оскільки ними описується синтаксис практично всіх конструкцій мов програмування. Більше того, він описується КВ-граматиками, продукції яких задовольняють певні структурні обмеження. З використанням цих обмежень було побудовано алгоритми синтаксичного аналізу, час виконання яких прямо пропорційний довжині аналізованого слова. А лінійна складність цих алгоритмів великою мірою зумовила ефективність сучасних систем програмування.
2.2. Дві ідеї аналізу
Заміна нетермінала з лівої частини продукції на її праву називається розгортанням нетермінала, а зворотна заміна - згортанням правої частини. Розглянемо дві стратегії аналізу, основані на згортаннях та на розгортаннях, за допомогою наступного прикладу.
Приклад 8. Нехай
G0 = ( { a, +, *, (, ) }, { E, T, F },
{ E E + T | T, T T * F | F, F (E ) | a },
E )
- граматика. Нетермінали E, T, F відповідно є скороченнями слів "Expression", "Term", "Factor", тобто "вираз", "доданок", "множник". Вони позначають вирази зі знаками операцій +, *, доданки та множники в них відповідно.
Виведення слова a+a*a в G0 з розгортанням нетерміналів, перших ліворуч у проміжних ланцюжках, має вигляд:
E ==> E+T ==> T+T ==> F+T ==> a+T ==> a+T*F ==> a+F*F ==> a+a*F ==>
==> a+a*a
Тут нетермінали, що розгортаються, підкреслені. Аналіз ланцюжка, що відтворює такі розгортання від початкового символу до термінального слова, називається низхідним, або аналізом "від верху до низу".
Тепер розглянемо виведення слова a+a*a з розгортанням нетерміналів, останніх праворуч:
E ==> E+T==> E+T*F ==> E+T*a ==> E+F*a ==> E+a*a ==> T+a*a ==> F+a*a==>
==> a+a*a
Проміжні слова в цьому виведенні, записані у зворотному порядку, дістаються згортаннями правих частин продукцій, починаючи з термінального слова. Такі згортання від ланцюжка терміналів до початкового нетермінала граматики відтворюються в процесі висхідного аналізу, або аналізу "від низу до верху".Р
Головною проблемою побудови алгоритмів аналізу в обох випадках є необхідність вибору продукції, застосованої для розгортання чи згортання. Чому, наприклад, у першому виведенні на першому кроці вибирається продукція E E+T, а не E T, а на другому, навпаки, E T ? Чому за оберненого виведення в слові E+T*F, в якому є дві праві частини продукцій E+T і T*F, саме ланцюжок T*F згортається в T, а не E+T в E ? Тут необхідний вибір зроблено тому, що структура термінального слова була відома заздалегідь. Але, взагалі, структура слова до початку його аналізу невідома, і виникає необхідність перебирати продукції для застосування потрібної.
Теоретично, можна розробити алгоритм аналізу на основі перебирання продукцій, але він буде практично неприйнятним внаслідок його оцінки складності. Один із шляхів до ефективних алгоритмів аналізу полягає в обмеженні структури продукцій і позбавленні від перебирання за рахунок звуження множини КВ-граматик. Далі розглядаються саме такі обмежені граматики та побудова алгоритму аналізу для них, складність якого лінійна.
2.3. LA(1)-граматики
LA(1)-граматики дозволяють вибирати необхідну для розгортання продукцію при низхідному аналізі за першим символом ще не розпізнаної частини слова. "LA(1)" позначає речення "Look Ahead 1 symbol", тобто "подивитися спереду на 1 символ".
Нехай G=(X, N, P, S) - КВ-граматика, і за словом w треба визначити, чи належить воно до L(G). Нехай S v1|…|vp - усі продукції з нетерміналом S ліворуч. Потрібну для розгортання S продукцію S vi можна визначити безпосередньо за першим символом слова w, якщо множини перших символів ланцюжків, вивідних із v1, v2, … , vp, не перетинаються. Взагалі, нехай am…an - нерозпізнана частина слова, початок якої має виводитися з нетермінала A, і A w1|…|wk - усі продукції з A ліворуч. Тоді потрібна для розгортання A продукція A wi визначається за першим символом am, якщо множини перших символів ланцюжків, вивідних з w1, w2, … , wk, не перетинаються.
Отже, для кожного нетермінала A та кожної правої частини wi
Loading...

 
 

Цікаве