Головна Головна -> Реферати українською -> Інформатика, комп'ютери, програмування -> Побудова алгоритму LA(1)-аналізу

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

Назва:
Побудова алгоритму LA(1)-аналізу
Тип:
Реферат
Мова:
Українська
Розмiр:
10,50 KB
Завантажень:
17
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2 
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, то оператор має вигляд

if ch = Y then ch:=getc else error,

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

• Якщо Y є нетерміналом, то оператором є виклик процедури

Y.

• Якщо Y має вигляд (u1|…|um) і Ti позначає first(ui) при i=1,…,m, то треба визначити, до якої з множин Ti належить поточний символ, і виконати оператор, відповідний до ui:

if ch in T1 then оператор-для-u1 else



if ch in Tm then оператор-для-um else

error.

• Якщо Y має вигляд [u], T=first(u), то за виконання умови ch T треба виконати оператор, відповідний до u:

if ch in T then оператор-для-u.

• Якщо Y має вигляд {u}, T=first(u), то за виконання умови ch T треба повторювати виконання оператора, відповідного до u:

while ch in T do оператор-для-u.

Зокрема, коли ланцюжок u починається терміналом, тобто u=xu1, де x X, то цикл має вигляд

while ch = x do

begin

ch := getc;

оператор-для-u1

end.

Оператори, відповідні до u, u1, … , um , записуються за цими ж правилами.

2. Побудова аналізатора арифметичних виразів

Розширена LA(1)-граматика G01 із продукціями E T{+T}, T F{*F}, F (E)|a породжує мову арифметичних виразів. Згідно з наведеними правилами запишемо процедури E, T, F:

procedure E;

begin

T;

while ch = '+' do

begin ch := getc; T end

end;

procedure T;

begin

F;

while ch = '*' do

begin ch := getc; F end

end;

procedure F;

begin

if ch = '(' then

begin

ch := getc; E;

if ch = ')' then ch := getc

else error

end

else

if ch = 'a' then ch := getc

else error

end

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2 



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

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок