|
Rekursiv kamayish usulidan foydalanish sharti
|
| bet | 63/131 | | Sana | 16.06.2024 | | Hajmi | 1,92 Mb. | | #264063 |
Bog'liq Tiplarni dinamik tarzdaRekursiv 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: FIRST1 (simple) = {integer, char, num}
FIRST1 (^id) = {^}
FIRST1 (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.
qadam. Agar x terminal bo‘lsa, FIRST(x)=x;
7 qadam. x → ε qoida uchun FIRST(x) to‘plamga ε ni qo‘shamiz;
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 => wu1v =>* 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,
S → if S then S else S
S → begin S L
S → print E
L → end
L →; S L
E → num = num
LL(1) – grammatikaga asoslangan rekursiv kamayish usuli uchun quyidagi grammatikani qaraymiz:
S → if E then S else S
S → begin S L
S → print E
L → end
L →; S L
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();
}}
|
|
| |
