7-mavzu. Sintaktik tahlil

Kirish: KS grammatika G=(N, T, P, S) va w zanjirning terminal va terminal bo‘lmagan belgilari.
CHiqish: FIRST(w).
Usul: FIRST (X₁)dan barcha bo‘sh bo‘lmagan belgilarni FIRST (X ₁ X ₂ …X _k) ga qo‘shamiz. Agar ε - FIRST (X₁)ga tegishli bo‘lsa, FIRST (X₂) dan barcha bo‘sh bo‘lmagan belgilarni,shu bilan iteratsiyani davom ettiramiz. Oxirida, Agar barcha j uchun FIRST (X_j) bo‘sh belgiga ega bo‘lsa, FIRST (X₁ X₂…X_k)to‘plamga ε ni qo‘shamiz.
Misol: Quyidagi qoidalar bilan berilgan grammatika qaraymiz:
S → BA
S → +BA
A → ε
B → DC
C → *DC
C → ε
D → (S)
D → a
Ushbu grammatika uchun FIRST to‘plami quyidagicha aniqlanadi.
FIRST(D)= {(,a}, FIRST(C) = {*,ε}, FIRST(B) = FIRST(D), FIRST(A) = {+,ε}, FIRST(S) = {(,a}.
LL(k)-grammatika ko‘rib chiqamiz.
Ta’rif: G = (V_T, V_N, P, S) grammatika LL(k)-grammatika deb aytiladi, agar FIRST _k (x) = FIRST_k (y) teng, u=u₁ bo‘lsa va ikkita ixtiyoriy chap chiqishlar uchun ifoda o‘rinli bo‘lsa,
S =>* wAv => wuv =>* wx
S =>* wAv => wu₁v =>* wy
Av dan chiquvchi terminal va terminal bo‘lmagan belgilar va k birinchi belgilardan (agar mavjud bo‘lsa) iborat wAv joriy zanjir uchun mavjud bo‘lsa, w bilan boshlanadigan va aytib o‘tilgan k terminallar bilan davom etadigan chiqishda kandaydir terminal zanjirini olish uchun A ga qo‘llash mumkin bo‘lgan kamida bitta qoida mavjud.
Qoidaga asoslangan grammatikani qarymiz:
S → aAS
S → b
A → a
A → bSA
va ikkita chiqish
(1) S =>* wSv => wuv =>* wx
(2) S =>* wSv => wu₁v =>* wy.
Agar x va y zanjirlar a bilan boshlansin. Bu esa chiqishda S → aAS qoida ishtirok etganini bildiradi. Haqiqattan ham u = u₁ = aAS. Agar x va y zanjirlar b bilan boshlansin. Bu esa chiqishda S → b qoida ishtirok etganini bildiradi. Haqiqattan ham u = u₁ = b. Bunday ko‘rinadiki, ikkita chiqish amallari o‘xshash va teng kuchlidir. Bunday esa yuqoridagi grammatika LL(1) – grammatika xususiyatlarini qo‘llab quvvatlaydi.
LL(1) – grammatikaga asoslangan Qiymat qaytarmaslik asosidagi rekursiv kamayish usuli uchun tahlilovchi qurish mumkin. Masalan,
(1) S → if S then S else S
(2) S → begin S L
(3) S → print E
(4) L → end
(5) L →; S L
(6) E → num = num
LL(1) – grammatikaga asoslangan rekursiv kamayish usuli uchun quyidagi grammatikani qaraymiz:
(1) S → if E then S else S
(2) S → begin S L
(3) S → print E
(4) L → end
(5) L →; S L
(6) E → num = num
Bu grammatikani qo‘llab quvvatlvchi tahlillovchini rekursiv kamayish usuli asoslanib yaratish mumkin. Buning uchun terminal bo‘lmagan grammatika uchun har biri uchun bittadan protsedura yozish kerak bo‘ladi.

class SimpleParser { const int IF = 1; const int THEN = 2; const int ELSE = 3; const int BEGIN = 4; const int END = 5; const int PRINT = 6; const int SEMICOLON = 7; const int NUM = 8; const int EQ = 9; public static void nextStep(int lc){ if (lexical_class == lc) lexical_class = getLC(); else error(); } public static void S(void){ switch(getLC()) { case IF: E(); nextStep(THEN); S(); nextStep(ELSE); S(); break; case BEGIN: S(); L(); break; case PRINT: E(); break; default: error(); break; } } public static void L(void){ switch (lexical_class) { case END: getLC(); break; case SEMICOLON: getLC(); S(); L(); break; default: error(); break; } } public static void E(void){ nextStep(NUM); nextStep(EQ); nextStep(NUM); } public static void main(void){ lexical_class = getLC(); S(); } }