Елементи синтаксичного аналізу, Детальна інформація
Елементи синтаксичного аналізу
first ( F ) = { a, ( }; first ( T*F ) = first ( F ), звідки
first ( T*F ) \xF0C7 first ( F ) \xF0B9 \xF0C6 ,
тобто G0 не є LA(1)-граматикою. Проте мова виразів L(G0) задається еквівалентною LA(1)-граматикою. Побудуємо її.
Із T виводяться слова F, F*F, F*F*F, … . Додамо нетермінал B та правила B\xF0AE \xF065 |*FB, T\xF0AE FB замість правил T\xF0AE F|T*F. Маємо
first ( T ) = first ( F ) = { a, ( }, first ( *FB ) = { * },
first ( B ) = { * }, follow ( B ) = follow ( T ) =
= follow ( E ) = { +, ) }.
Отже, продукції T\xF0AE FB і B\xF0AE \xF065 |*FB не порушують LA(1)-умови. Аналогічно, додавши нетермінал A, а замість правил E\xF0AE E+T|T правила E\xF0AE TA, A\xF0AE \xF065 |+EA, одержимо LA(1)-граматику.
2.4. Ліворекурсивні та розширені продукції
Правило вигляду A\xF0AE Av називається ліворекурсивним. Якщо в граматиці є продукції A\xF0AE Av|u, де u\xF0B9 \xF065 , то first(Av)=first(u)\xF0B9 \xF0C6 , і граматика не є LA(1)-граматикою. Але за допомогою цих правил виводяться слова з множини {u, uv, uvv, …}, яка задається регулярним виразом uv* або u{v}. Замість продукцій A\xF0AE Av|u запишемо A\xF0AE u{v}. Продукції з регулярними виразами в правій частині називаються розширеними, як і граматики з такими продукціями. Неважко переконатися, що розширені правила не збагачують множину мов, породжених КВ-граматиками.
Приклад 10. Розширена граматика G01 із правилами E\xF0AE T{+T}, T\xF0AE F{*F}, F\xF0AE (E)|a еквівалентна граматиці G0. Фактично РБНФ є іншим записом розширених продукцій, а сукупності РБНФ – іншою формою розширених КВ-граматик.\xF0E7
3.1. Правила побудови
Нехай G=(X, N, P, S) – LA(1)-граматика без \xF065 -правил, можливо, розширена. Опишемо побудову програми синтаксичного аналізу слів мови L(G). Програма буде містити процедури, іменами яких є відповідні їм нетермінали граматики.
Процедура, відповідна нетерміналу A, описує аналіз ланцюжків, вивідних із A. Цими ланцюжками є слова мови або їхні підслова. Алгоритм процедури такий. Нехай A\xF0AE 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\xF0B3 2 початок непроаналізованої частини ланцюжка ajaj+1… повинен виводитися з Y2 тощо. Перший символ непроаналізованої частини ланцюжка називатимемо поточним.
Отже, за правими частинами wi продукцій будуються фрагменти процедури A; вони виконуються, коли поточний символ ланцюжка міститься у відповідній множині first ( wi ).
Зробимо уточнення програми та правил побудови процедур. Нехай w – слово, що аналізується, ch – його поточний символ, функція getc задає добування наступного символу слова, змінна finch позначає спеціальний символ, що повертається функцією getc після закінчення слова w. Нехай ok – бульова змінна, що є ознакою належності w\xF0CE L(G), а процедура error задає присвоювання ok:=false. Тілом програми є
begin
ok := true;
ch := getc;
S; { виклик процедури, відповідної }
{ головному нетерміналу }
writeln ( (ch = finch) and ok )
end.
Нехай A є нетерміналом із продукціями A\xF0AE w1|…|wk , а S1,…, Sk позначають множини first(w1),…,first(wk), які не перетинаються. За таких умов тілом процедури A є складений оператор
begin
if ch in S1 then оператор-для-w1 else
…
first ( T*F ) \xF0C7 first ( F ) \xF0B9 \xF0C6 ,
тобто G0 не є LA(1)-граматикою. Проте мова виразів L(G0) задається еквівалентною LA(1)-граматикою. Побудуємо її.
Із T виводяться слова F, F*F, F*F*F, … . Додамо нетермінал B та правила B\xF0AE \xF065 |*FB, T\xF0AE FB замість правил T\xF0AE F|T*F. Маємо
first ( T ) = first ( F ) = { a, ( }, first ( *FB ) = { * },
first ( B ) = { * }, follow ( B ) = follow ( T ) =
= follow ( E ) = { +, ) }.
Отже, продукції T\xF0AE FB і B\xF0AE \xF065 |*FB не порушують LA(1)-умови. Аналогічно, додавши нетермінал A, а замість правил E\xF0AE E+T|T правила E\xF0AE TA, A\xF0AE \xF065 |+EA, одержимо LA(1)-граматику.
2.4. Ліворекурсивні та розширені продукції
Правило вигляду A\xF0AE Av називається ліворекурсивним. Якщо в граматиці є продукції A\xF0AE Av|u, де u\xF0B9 \xF065 , то first(Av)=first(u)\xF0B9 \xF0C6 , і граматика не є LA(1)-граматикою. Але за допомогою цих правил виводяться слова з множини {u, uv, uvv, …}, яка задається регулярним виразом uv* або u{v}. Замість продукцій A\xF0AE Av|u запишемо A\xF0AE u{v}. Продукції з регулярними виразами в правій частині називаються розширеними, як і граматики з такими продукціями. Неважко переконатися, що розширені правила не збагачують множину мов, породжених КВ-граматиками.
Приклад 10. Розширена граматика G01 із правилами E\xF0AE T{+T}, T\xF0AE F{*F}, F\xF0AE (E)|a еквівалентна граматиці G0. Фактично РБНФ є іншим записом розширених продукцій, а сукупності РБНФ – іншою формою розширених КВ-граматик.\xF0E7
3.1. Правила побудови
Нехай G=(X, N, P, S) – LA(1)-граматика без \xF065 -правил, можливо, розширена. Опишемо побудову програми синтаксичного аналізу слів мови L(G). Програма буде містити процедури, іменами яких є відповідні їм нетермінали граматики.
Процедура, відповідна нетерміналу A, описує аналіз ланцюжків, вивідних із A. Цими ланцюжками є слова мови або їхні підслова. Алгоритм процедури такий. Нехай A\xF0AE 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\xF0B3 2 початок непроаналізованої частини ланцюжка ajaj+1… повинен виводитися з Y2 тощо. Перший символ непроаналізованої частини ланцюжка називатимемо поточним.
Отже, за правими частинами wi продукцій будуються фрагменти процедури A; вони виконуються, коли поточний символ ланцюжка міститься у відповідній множині first ( wi ).
Зробимо уточнення програми та правил побудови процедур. Нехай w – слово, що аналізується, ch – його поточний символ, функція getc задає добування наступного символу слова, змінна finch позначає спеціальний символ, що повертається функцією getc після закінчення слова w. Нехай ok – бульова змінна, що є ознакою належності w\xF0CE L(G), а процедура error задає присвоювання ok:=false. Тілом програми є
begin
ok := true;
ch := getc;
S; { виклик процедури, відповідної }
{ головному нетерміналу }
writeln ( (ch = finch) and ok )
end.
Нехай A є нетерміналом із продукціями A\xF0AE w1|…|wk , а S1,…, Sk позначають множини first(w1),…,first(wk), які не перетинаються. За таких умов тілом процедури A є складений оператор
begin
if ch in S1 then оператор-для-w1 else
…
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021