Tiplarni dinamik tarzda

Rekursiv kamayish usulidan foydalanish sharti. Qiymat qaytarmaslik asosidagi rekursiv kamayish usulidan faqat quyidagi shart bajarilganda foydalanish mumkin.
Shart: har bir ifodaning birinchi belgisi bu holatda qaysi ifodaga amal qilishini aniqlash uchun yetarli bo‘lishi kerak. Bu shartni aniqroq tushunishni FIRST to‘plamini aniqlash orqali amalga oshirish mumkin.
Taʻrif: KS grammatika uchun terminal va terminal bo‘lmagan belgilardan iborat G grammatika va w zanjir asosida FIRST k (w) to‘plamni quyidagicha aniqlaymiz:
FIRST _k (w) = {x | w =>* xv, |x| = k yoki w =>* x, |x| < k}, k – natural son.
^{Boshqacha qilib aytganda, FIRST} k ^{(w) to‘plam w dan olingan terminal} zanjirlarning uzunligi k bo‘lgan barcha terminal prefikslardan iborat.
Universal algoritmik tilda tiplarning kichik qismini yaratadigan grammatikani ko‘rib chiqaylik:
type → imple type → ^id
type → array[simple] of type simple → integer
simple → char
simple → num … num
Bu grammatika uchun quyidagilarni aniqlash mumkin: FIRST₁ (simple) = {integer, char, num}
FIRST₁ (^id) = {^}
FIRST₁ (array [simple] of type) = { array }
^{Agar w zanjir faqat terminallardan iborat bo‘lsa, FIRST} k ^{(w) - w zanjirda birinchi} k belgilardir, aks holda |w| >=, yoki agar |w| < k < bo‘lsa, w zanjirning o‘zi.
Parser sinfi. FIRST to‘plamning qurish algoritmi. Birinchi navbatda belgilar grammatikasi uchun FIRST to‘plamni aniqlaymiz.

1. 
   qadam. Agar x terminal bo‘lsa, FIRST(x)=x;
   

7 qadam. x → ε qoida uchun FIRST(x) to‘plamga ε ni qo‘shamiz;

2. 
   qadam. Agar x teminal emas va grammatika qoidasi x → y1 y2 … yk bo‘lsa, FIRST(X)ga a terminalni qo‘shamiz, agar qandaydir i uchun a terminal FIRST(yi)ga tegishli bo‘lsa va ε - FIRST(y1), ... ,FIRST(yi-1) to‘plamlarga tegishli bo‘lsa, y1 y2 … yi-1 => * ε, agar barcha j=1,2,…k uchun ε - FIRST(yj) to‘plamga tegishli bo‘lsa, ε ni FIRST(y) to‘plamga qo‘shamiz.
   

FIRST(w) to‘plamni qurish algoritmini shakllantiramiz.
Kirish: KS grammatika G=(N, T, P, S) va w zanjirning terminal va terminal bo‘lmagan belgilari.
Chiqish: FIRST(w).
Usul: FIRST (X1)dan barcha bo‘sh bo‘lmagan belgilarni FIRST (X 1 X 2 …X k) ga qo‘shamiz. Agar ε - FIRST (X1)ga tegishli bo‘lsa, FIRST (X2) dan barcha bo‘sh bo‘lmagan belgilarni,shu bilan iteratsiyani davom ettiramiz. Oxirida, Agar barcha j uchun FIRST (Xj) bo‘sh belgiga ega bo‘lsa, FIRST (X1 X2…Xk)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 = (VT, VN, P, S) grammatika LL(k)-grammatika deb aytiladi, agar FIRST k (x) = FIRSTk (y) teng, u=u1 bo‘lsa va ikkita ixtiyoriy chap chiqishlar uchun ifoda o‘rinli bo‘lsa,
S =>* wAv => wuv =>* wx S =>* wAv => wu1v =>* 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 = u1 = aAS. Agar x va y zanjirlar b bilan boshlansin. Bu esa chiqishda S → b qoida ishtirok etganini bildiradi. Haqiqattan ham u = u1 = 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(); }}