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

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

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

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

продукцій A w1 | w2 | … | wk означимо множини
first ( wi ) = { a | a X* і wi ==> az для деякого слова z },
first ( A ) = first ( wi ).
Граматика може мати так звані -продукції вигляду A . У такому разі, якщо Av==> *b1…bn, то b1 може починати слово, вивідне як з A, так і з v. Визначити за символом b1 , з чого саме виводиться слово, можна за умови, що first(A) не містить перших символів слів, вивідних із v. Множину цих перших символів ланцюжків, що виводяться з усіх можливих правих контекстів нетермінала A, позначимо follow (A):
follow ( A ) = { a | S ==> * uAv, a first ( v ) }.
Граматика називається LA(1)-граматикою, якщо:
(1) для кожного нетермінала A зпродукціями A w1|…|wk , де wi для всіх i=1,…,k, справджується умова
first ( wi ) first ( wj ) = при i, j = 1, … , k, i j;
(2) для кожного нетермінала A такого, що в P є продукція A , справджується
first ( A ) follow ( A ) = .
Умови (1), (2) називаються LA(1)-умовами.
Не кожна КВ-мова породжується LA(1)-граматикою, але синтаксис практично всіх конструкцій сучасних мов програмування можна задати LA(1)-граматиками. Досить часто мова "природно" задається не LA(1)-граматикою, але таку граматику для неї можна побудувати.
Приклад 9. За продукціями E E+T|T, T T*F|F, F (E)|a граматики G0 маємо
first ( (E) ) = { ( }, first ( a ) = { a }, звідки
first ( F ) = { a, ( }; first ( T*F ) = first ( F ), звідки
first ( T*F ) first ( F ) ,
тобто G0 не є LA(1)-граматикою. Проте мова виразів L(G0) задається еквівалентною LA(1)-граматикою. Побудуємо її.
Із T виводяться слова F, F*F, F*F*F, … . Додамо нетермінал B та правила B |*FB, T FB замість правил T F|T*F. Маємо
first ( T ) = first ( F ) = { a, ( }, first ( *FB ) = { * },
first ( B ) = { * }, follow ( B ) = follow ( T ) =
= follow ( E ) = { +, ) }.
Отже, продукції T FB і B |*FB не порушують LA(1)-умови. Аналогічно, додавши нетермінал A, а замість правил E E+T|T правила E TA, A |+EA, одержимо LA(1)-граматику.
2.4. Ліворекурсивні та розширені продукції
Правило вигляду A Av називається ліворекурсивним. Якщо в граматиці є продукції A Av|u, де u , то first(Av)=first(u) , і граматика не є LA(1)-граматикою. Але за допомогою цих правил виводяться слова з множини {u, uv, uvv, …}, яка задається регулярним виразом uv* або u{v}. Замість продукцій A Av|u запишемо A u{v}. Продукції з регулярними виразами в правій частині називаються розширеними, як і граматики з такими продукціями. Неважко переконатися, що розширені правила не збагачують множину мов, породжених КВ-граматиками.
Приклад 10. Розширена граматика G01 із правилами E T{+T}, T F{*F}, F (E)|a еквівалентна граматиці G0. Фактично РБНФ є іншим записом розширених продукцій, а сукупності РБНФ - іншою формою розширених КВ-граматик.Р
3.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},
Loading...

 
 

Цікаве