• Parser sinfi. FIRST to‘plamning qurish algoritmi.
  • Rekursiv kamayish usulidan foydalanish sharti




    Download 1,83 Mb.
    bet63/131
    Sana13.05.2024
    Hajmi1,83 Mb.
    #228405
    1   ...   59   60   61   62   63   64   65   66   ...   131
    Bog'liq
    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: 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.

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

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

    1. 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,

    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();
    }}


    Download 1,83 Mb.
    1   ...   59   60   61   62   63   64   65   66   ...   131




    Download 1,83 Mb.

    Bosh sahifa
    Aloqalar

        Bosh sahifa



    Rekursiv kamayish usulidan foydalanish sharti

    Download 1,83 Mb.