Bu qiziq / Dasturlash
0
09.06.2017 15:26 Manuchehr 235 0

Bu qanday ishlaydi: Kompilyator (2-qism)

Ushbu maqolaning 1-qismida kompilyasiya jarayoni va undagi birinchi bosqich – kiritilgan matnni bo’laklash  haqida gapirib o’tgan edim. Ushbu maqolada mavzuni davom ettiramiz.

 

Oldin ham aytilganidek har qanday (dasturlash) til o’zining alifbosiga va qoidalar to’plamiga egadir. So’zlarning qanday tartibda kelishi tilning grammatikasini belgilaydi. Avvalgi maqolada erkin-kontekstli dasturlash tillarini grammatikasini yozish uchun foydalaniladigan Bekus-Naur yozuvi haqida ham gapirgandim.  Kompilyasiya jarayonining keyingi bosqichi kiritilgan dastur matnidan, ya’ni biz o’tgan safar bo’laklarga ajratib olgan qismlardan til grammatikasiga mos ravishda tuzilmaviy daraxt hosil qilishidan iborat bo’ladi. Ushbu jarayonni sintaktik daraxt hosil qilish yoki parsing ham deyiladi. Sintaktik daraxtda dasturdagi dasturlash tilining harbir so’zi va buyruqlar ketma-ketligi shoxchalar yordamida ifodalanadi.

Parsing tushunchasi umumiy ma’nodagi so’z bo’lib, sodda qilib aytganda har qanday matnli ahborotni tahlil qilish, qayta ishlash deb ham tushunish mumkin. Sintaktik daraxt hosil qilishda qo’llaniladigan parsing jarayoni turlari bir necha hil bo’lib ulardan eng ko’p ishlatiladigani – Yuqoridan pastga qarab ishlovchi va Pastdan yuqoriga qarab ishlovchi parsing turlaridir (top-down va bottom-up). Bularning bir biridan farqi sintaktik daraxtning qay tomondan boshlab yaratishidadir. Bular haqida batafsil gapirib o’tirmayman, bularni bitta maqolada tushuntirishni iloji ham yo’q. Biz faqatgina Yuqoridan pastga qarab ishlovchi turga kiruvchi Rekursiv parserni ko’rib chiqamiz. Qolgan parser turlari haqida balki keyingi maqolalarda ham yozishga harakat qilib ko’raman.

Rekursiv tushuvchi parserning qolgan parserlardan asosiy afzalligi uni bevosita dasturlash mumkin. Qolgan parser turlarida esa steklar, mos kelish jadvallardan foydalaniladi.

Rekursiv parserni tuzishni boshlaymiz.

Deylik, bizning tilimizda faqatgina bitta qoida mavjud:

 

<Son>             := ButunSon | HaqiqiySon

 

 

Ya’ni, dastur kodi faqat bitta butun yoki haqiqiy sondan iborat bo’lishi mumkin bo’lsin. “|” belgisi “yoki” degan ma’noni anglatadi (BN yozuvi). Grammatikada har doim boshlang’ich qoidani ham ko’rsatish kerak bo’ladi. Ushbu boshlang’ich qoida dastur qaysi qoidadan boshlanishini bildiradi. Bizda bitta qoida bor (yuqoridagi) va boshlang’ich qoida ham shunga teng deb olamiz:

 

<Dastur boshi>    := <Son>

 

 

Bizda tayyor bo’laklar mavjud, shulardan foydalanib parserimizni yozamiz. Avvalo Parser nomli class yaratamiz.

 

class Parser
{

    string text; // kiritilgan matn
    Lexer lex; // ajratilgan bo’laklar, Lexer

    public Parser (string _text)
    {

        this.text = _text;

    }

    public void Parse ()
    {

        lex = new Lexer(text);

        StartProgram(); // boshlang’ich qoida

    }

}

 

 

Dastur matni faqatgina 1 ta sondan tashkil topishi mumkinligidan birinchi bo’lak sonligini va undan boshqa bo’lak yo’qligini tekshirsak parserimiz tayyor ))

 

// <Son> qoidasi
// Joriy bo'lakni butun yoki haqiqiy sonligini tekshiradi

public bool NumValue()
{

    // agar keyingi bo’lak son bo’lsa

    if (lex.LookNextToken().Type == Token.TokenType.NUMLITERAL)
    {

        lex.ReadToken();

        return true;

    } else

        return false;

}

// <Dastur boshi> 

public void StartProgram()
{

    // NumValue() ijobiy qiymat qaytarsa va keyingi bo'lak dastur
    // oxiri belgisi bo'lsa unda hammasi OK

    if (NumValue() && lex.ReadToken().Type==Token.TokenType.EOP )

        Console.WriteLine ("Parsing OK.");

    else

        Console.WriteLine ("Syntax Error!");

}

 

 

Ko’rib turganingizdek oddiy qoidamizga juda oddiy parser hosil bo’ldi. Endi til qoidalarini (mos ravishda parserni ham) biroz murakkablashtiramiz. Matn faqat bitta son emas sonlar va faqat qo’shish amalidan iborat arifmetik ifodadan iborat degan qoidani kiritamiz:

 

<Qo’shish>        := <Son> | <Son> “+” <Qo’shish>
<Son>             := <Qo’shish>

 

 

<Qo’shish> qoidasi faqat 1 ta sonning o’zi yoki son, “ ” belgisi va yana <Qo’shish> qoidasidan tashkil topgan. Bu rekursiv bog’lanish bizga <Son> <Son> <Son> … ko’rinishidagi ifodalarni ko’rsatishga yordam beradi.

 

// <Qo’shish> qoidasi

public bool Add()
{

    if (NumValue())
    {

        Token t = lex.LookNextToken();

        // Agar keyingi bo’lak amali bo’lsa

        if ((t.Type == Token.TokenType.OPERATOR) && (t.Text == "+"))
        {

            // amalini tashlab yuborish, chunki LookNextToken
            // joriy bo’lakni o’zgartirmaydi

            lex.ReadToken();

            // Qushishni rekursiv chaqirish va funksiyadan chiqish
            // funksiya qiymati rekursiv chaqiruv qiymatiga teng

            return Add();

        }

        // faqat sonni o’zidan iborat

        return true;

    }

    return false;

}

 

 

StartProgram prosedurasida NumValue() ni Add() ga almashtiramiz. Bu qoidani ham dasturlashtirdik. Natijani dasturni ishlatib tekshirib ko’rishimiz mumkin.

Endi qoidamizni yana o’zgartiramiz bu safar matn to’liq arifmetik ifodadan iborat bo’lishi mumkin bo’ladi:

 

<Qo’shish>        := <Ko’paytirish>
                  | <Ko’paytirish> “+” <Qo’shish>
                  | <Ko’paytirish> “-“ <Qo’shish>
<Ko’paytirish>    := <Daraja>
                  | <Daraja> “*” <Ko’paytirish>
                  | <Daraja> “/” <Ko’paytirish>
<Daraja>          := <Son>
                  | <Son> “^” <Daraja>
<Son>             := ButunSon
                  | “(“ ButunSon “)”
                  | HaqiqiySon
                  | “(“ HaqiqiySon “)”

<Dastur boshi> := <Qo’shish>

 

 

Amallar qoidasi har doim deyarli shunday ketma-ketlikda yoziladi. Bunda qoidalar amallarning qaysi biri birinchi qaysi oxiri bajarilishiga qarab yoziladi. Masalan ko’paytirish amali qo’shishdan oldin bajarilgani sababli qo’shish qoidasida avval ko’paytirish qoidasiga murojaat bo’ladi va xok.

Ushbu qoida uchun yuqoridagi dasturimizning Add() funskiyasiga biroz o’zgartirish kiritib va qolgan qoidalarni ham dasturga qo’shsak kifoya.

 

// <Qo'shish> qoidasi

public bool Add()
{

    if (Mul())
    {

        Token t = lex.LookNextToken();

        if (t.Type == Token.TokenType.OPERATOR)
        {

            if ((t.Text == "+") || (t.Text == "-"))
            {

                lex.ReadToken();

                return Add();

            }

        }

        return true;

    }

    return false;

}

// <Ko'paytirish> qoidasi

public bool Mul()
{

    if (Pow())
    {

        Token t = lex.LookNextToken();

        if (t.Type == Token.TokenType.OPERATOR)
        {

            if ((t.Text == "*") || (t.Text == "/"))
            {

                lex.ReadToken();

                return Mul();

            }

        }

        return true;

    }

    return false;

}

// <Daraja> qoidasi

public bool Pow()
{

    if (NumValue())
    {

        Token t = lex.LookNextToken();

        if (t.Type == Token.TokenType.OPERATOR)
        {

            if (t.Text == "^")
            {

                lex.ReadToken();

                return Pow();

            }

        }

        return true;

    }

    return false;

}

// <Son> qoidasi

public bool NumValue()
{

    if (lex.LookNextToken().Type == Token.TokenType.NUMLITERAL)
    {

        lex.ReadToken();

        return true;

    // <Son>:= "(" <Qo'shish> ")"

    } else if (lex.LookNextToken().Text == "(") {

        lex.ReadToken();

        if (Add() && lex.LookNextToken().Text == ")")
        {

            lex.ReadToken();
            return true;

        } else

            return false;

    } else

        return false;

}

 

 

Balki “Sintaktik daraxt qani?” degan savol tug’ilgandir? Sintaktik daraxt aynan shuni o’zidir. Aniqrog’I ushbu rekursiv chaqirilayotgan qoida funksiyalari sintaktik daraxtning shoxchalarini tashkil etadi. Endi sintaktik daraxtni ifodalovchi class yaratib, yuqoridagi funksiyalar tanasida daraxt haqidagi ma’lumotni yozib boruvchi kod qo’shilsa yetarli. Dasturni ishlatib ko’ramiz va biror to’g’ri ifodani kiritib ko’ramiz:

 

2 * 3 + 4 / ( 1 - 2 ^ ( 1 + 1 ) * 2 )

 

Parsing OK.

 

Demak ifoda to’g’ri. Endi biror noto’g’ri ifoda kiritamiz:

2 + 5 * 1 - ( 1 * 2

 

Syntax Error: 10

 

 

Demak parserimiz matnni to’g’ri tahlil qilyapti. Maqolaning keyingi qismida ushbu parserimizga (va mos ravishda tilimizga) o’zgartirishlar kiritib uni mukammallashtirib boramiz. Shuningdek kompilyasiyaning oxirgi bosqichi – dasturni mashina kodiga tarjima qilish, virtual mashinalar haqida ham fikr almashamiz.

P.S. Maqolada yozilgan kodlar deyarli tekshirilmagan, unda ba’zi “qo’polliklar”, “chiroyli yozish”ga amal qilinmagan holatlar yoki mantiqiy hatolar uchrashi mumkin.

Avtor: Alisher Djalolov

шаблоны для dle 11.2

Ma`lumotnoma
Xabarga izoh qoldirish uchun iltimos saytimizda ro`yxatdan o`ting.
Ommabop yangiliklar