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

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

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

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

 

ПОШУК:   

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

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

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

 

Побудова алгоритму LA(1)-аналізу

 

1. Правила побудови

 

Нехай G=(X, N, P, S) – LA(1)-граматика без ? -правил, можливо,

розширена. Опишемо побудову програми синтаксичного аналізу слів мови

L(G). Програма буде містити процедури, іменами яких є відповідні їм

нетермінали граматики.

 

Процедура, відповідна нетерміналу A, описує аналіз ланцюжків, вивідних

із A. Цими ланцюжками є слова мови або їхні підслова. Алгоритм процедури

такий. Нехай A? w1|…|wk – усі продукції з нетерміналом A ліворуч,

a1a2…an – ланцюжок, початок якого треба виводити з A. Спочатку

визначається, якій із множин first(w1), … , first(wk) належить символ

a1. Нехай нею буде first(w1), і в найпростішому випадку w1=Y1Y2…Ym, де

Yi – термінал або нетермінал. Початок ланцюжка має виводитися з Y1.

 

Якщо Y1 – термінал, то перевіряється рівність a1=Y1.

 

Якщо Y1 – нетермінал, то з a1 починається частина слова, вивідна з Y1, і

для аналізу початку ланцюжка a1a2… викликається процедура Y1.

 

В обох випадках, після перевірки рівності або повернення з виклику Y1,

за деякого j? 2 початок непроаналізованої частини ланцюжка ajaj+1…

повинен виводитися з Y2 тощо. Перший символ непроаналізованої частини

ланцюжка називатимемо поточним.

 

Отже, за правими частинами wi продукцій будуються фрагменти процедури A;

вони виконуються, коли поточний символ ланцюжка міститься у відповідній

множині first ( wi ).

 

Зробимо уточнення програми та правил побудови процедур. Нехай w – слово,

що аналізується, ch – його поточний символ, функція getc задає добування

наступного символу слова, змінна finch позначає спеціальний символ, що

повертається функцією getc після закінчення слова w. Нехай ok – бульова

змінна, що є ознакою належності w? L(G), а процедура error задає

присвоювання ok:=false. Тілом програми є

 

begin

 

ok := true;

 

ch := getc;

 

S; { виклик процедури, відповідної }

 

{ головному нетерміналу }

 

writeln ( (ch = finch) and ok )

 

end.

 

Нехай A є нетерміналом із продукціями A? w1|…|wk , а S1,…, Sk позначають

множини first(w1),…,first(wk), які не перетинаються. За таких умов тілом

процедури A є складений оператор

 

begin

 

if ch in S1 then оператор-для-w1 else

 

 

if ch in Sk then оператор-для-wk else

 

error

 

end

 

Зокрема, якщо Si містить лише один символ x, то замість умови chinSi

можна записати ch = x.

 

Праві частини розширених граматик є виразами, складеними з

послідовностей символів алфавіту X і метасимволів, якими є дужки (), [],

{} та символи |. Розглянемо праву частину v розширеного правила як

послідовність виразів Y1 … Yk , в якій Yi є або символом з X? N, або

виразом вигляду (u), [u], чи {u}, що не міститься всередині інших дужок,

де u – послідовність нетерміналів, терміналів и дужок. За правою

частиною v будується складений оператор із послідовністю операторів,

відповідних до Y1,…,Yk. Нехай Y позначає один із виразів Y1,…,Yk.

Відповідний оператор визначається виглядом Y за наступними правилами.

 

Якщо Y є першим терміналом Y1, то оператором є

 

ch:=getc.

 

Якщо Y є терміналом, але не першим у ланцюжку v, то оператор має вигляд

-----> Page:

0 [1] [2]

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