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

Всього в базі: 75834
останнє поновлення: 2016-11-29
за 7 днів додано 10

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

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

 

ПОШУК:   

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

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

Реферат на тему:

 

Контекстно-вільні та LA(1)-граматики

 

1. Контекстно-вільні граматики

 

Контекстно-вільною, або КВ-граматикою, називається граматика, в якій

ліві частини всіх продукцій є нетерміналами. Зміст терміну

"контекстно-вільна" полягає в тім, що застосування продукції A? w до

ланцюжка uAv не залежить, тобто є вільним від сусідніх з A символів, які

утворюють контекст uv.

 

Зазначимо, що БНФ вигляду A::=w цілком аналогічна продукції A? w. Отже,

сукупності БНФ є просто іншою формою КВ-граматик.

 

Контекстно-вільною мовою (КВ-мовою) називається мова, що може бути

задана КВ-граматикою.

 

Прикладами КВ-граматик та КВ-мов є граматики з прикладів 21.3, 21.5,

21.6 у попередньому параграфі й задані ними мови. Граматика з прикладу

21.7 не є КВ-граматикою. До речі, мова, задана нею, не є КВ-мовою,

оскільки не існує КВ-граматики, яка б її задавала.

 

КВ-граматики відіграють особливу роль у програмуванні, оскільки ними

описується синтаксис практично всіх конструкцій мов програмування.

Більше того, він описується КВ-граматиками, продукції яких задовольняють

певні структурні обмеження. З використанням цих обмежень було побудовано

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

довжині аналізованого слова. А лінійна складність цих алгоритмів великою

мірою зумовила ефективність сучасних систем програмування.

 

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 ?

-----> Page:

0 [1] [2]

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