правила 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}, 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 , записуються за цими ж правилами.
3.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
Побудовані процедури взаємно рекурсивні: тіло E містить виклики процедури T, тіло T – виклики F, а тіло F – виклики E. У мові Паскаль кожне ім'я повинно бути означеним вище від його вживання, тому незрозуміло, в якій послідовності треба записати процедури E, T, F. У таких