Swd1316 sintaktik tahlil. Ifodalarning sintaktik tahlili. Parser sinfi. Sintaktik analizatorni yaratish

Parser sinfi

• 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.

Parser sinfi

• Misol: Quyidagi qoidalar bilan berilgan grammatika qaraymiz:
• S → BA
• S → +BA
• A → εB → DC
• C → *DC
• C → ε
• D → (S)
• D → aUshbu 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‘ribchiqamiz.
• 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

• Qiymat qaytarish asosidagi rekursiv
• kamayish usuli

• Qiymat qaytarish asosidagi rekursiv kamayish usulini qo‘llash uchun grammatikani FIRST to‘plamlar kesishmaydigan shaklga aylantirish kerak. Bu murakkab va ko‘p vaqt talab qiladigan jarayondir. SHuning uchun, amaliyotda, tez-tez ishlatiladigan ibora bor, qiymat qaytarish asosidagi rekursiv kamayish hodisa deb ataladi.
• Buning uchun leksik analizator an’anaviy usullarni to‘laligicha, scan va next ana’naviy usullar va nusxalash konstruktoriga ega bo‘lgan ob’ekt sifatida namoyon bo‘ladi. Keyin, noaniqlik yuzaga kelishi mumkin bo‘lgan barcha holatlarda, tahlil qilishni boshlashdan oldin leksik analizatorning hozirgi holatini aniqlaymiz (ya’ni, leksik analizatorning nusxasini boshlaymiz) va matnni tahlil qilishni davom ettirishga harakat qilamiz.