7-mavzu. Sintaktik tahlil

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 etarli 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;
2-qadam. x → ε qoida uchun FIRST(x) to‘plamga ε ni qo‘shamiz;
3-qadam. Agar x teminal emas va grammatika qoidasi x → y₁ y₂ … y_k bo‘lsa, FIRST(X)ga a terminalni qo‘shamiz, agar qandaydir i uchun a terminal FIRST(y_i)ga tegishli bo‘lsa va ε - FIRST(y₁), ... ,FIRST(y_i-1) to‘plamlarga tegishli bo‘lsa, y₁ y₂ … y_i-1 => * ε, agar barcha j=1,2,…k uchun ε - FIRST(y_j) to‘plamga tegishli bo‘lsa, ε ni FIRST(y) to‘plamga qo‘shamiz.
FIRST(w) to‘plamni qurish algoritmini shakllantiramiz.