مقدمة في نظرية المترجم: التحليل المعجمي للغة باسكال باستخدام C #

المقدمة

في الآونة الأخيرة ، يبدأ معظم المبتدئين في البرمجة بلغات عالية المستوى مثل Java أو Python أو C # أو أي لغة أخرى تحتوي على "مجموعة جنتلمان" في شكل جامع القمامة وهياكل البيانات الجاهزة وما إلى ذلك. بالطبع ، هذا النهج له مزاياه ، ولكن ، كقاعدة عامة ، فإن المطور المبتدئ الذي يستخدم الوظيفة الجاهزة للغة يفتقد الشيء الأكثر أهمية - هيكلها وآليات التشغيل والتنفيذ.



لن أخوض في تفاصيل تخصيص الذاكرة وطرق تفسير الكود ، لكن على العكس من ذلك ، أود أن أتحدث عن المترجم نفسه ، أي المحلل المعجمي ، وأحاول تنفيذه في C #. الغالبية العظمى تعرف اللغة التي سنحللها - إنها باسكال.



المحلل المعجمي هو الأول من "طبقات" المترجم المسؤولة عن تمييز الرموز لمزيد من المعالجة.



lexeme هي أصغر وحدة في القاموس تمثل لغتنا. يمكن أن تكون كلمات الخدمة والمشغلين والمعرفات وما إلى ذلك بمثابة رمز مميز.

التنفيذ

وصف الهيكل

سيتم تخزين الوصف الرسمي للغة في صفيفتين: في الأولى - كلمات الخدمة ، وفي الثانية - المحددات وقائمة بالرموز التي تم العثور عليها

private string[] Words = { "program", "var", "integer", "real", "bool", "begin", "end", "if", "then", "else", "while", "do", "read", "write", "true", "false" };
private string[] Delimiter = { ".", ";", ",", "(", ")", "+", "-", "*", "/", "=", ">", "<" };
public List<Lex> Lexemes = new List<Lex>();

سيقوم lexeme نفسه بتخزين المفتاح ، والذي سيتم استخدامه لتحديد النوع (كلمات الخدمة ، المشغلين ، المعرفات ، الأرقام) ، معرف الرمز المميز والقيمة نفسها.

class Lex
{
    public int id;
    public int lex;
    public string val;

    public Lex(int _id, int _lex, string _val)
    {
        id = _id;
        lex = _lex;
        val = _val;
    }
}

أفضل حل لمعالجة الرموز هو آلة الحالة. سيؤدي ذلك إلى التخلص من ifs غير الضرورية ، كما سيسهل إجراء تغييرات على الحلقة. S هي الحالة الأولية ، و NUM ، و DLM ، و ASGN ، والمعرف هي حالة الأنواع المقابلة من الرموز المميزة ، وسيتم استخدام ER للخطأ ، و FIN للحالة النهائية.

private string buf = ""; //    
private char[] sm = new char[1];
private int dt = 0;
private enum States { S, NUM, DLM, FIN, ID, ER, ASGN, COM } //  state-
private States state; //   
private StringReader sr; //    

الطرق الرئيسية هي SearchLex ، التي تبحث عن رمز مميز في المصفوفة الخاصة بنا وترجع معرفها وقيمتها في مجموعة (نعم ، يمكن أن تكون tuples مفيدة أيضًا) ، و PushLex ، التي تضيف رمزًا مميزًا جديدًا إلى القاموس.

private (int, string) SerchLex(string[] lexes)
{
    var srh = Array.FindIndex(lexes, s => s.Equals(buf)); 
    if (srh != -1)
        return (srh, buf);             
    else return (-1, "");
}

private (int, string) PushLex(string[] lexes, string buf)
{
    var srh = Array.FindIndex(lexes, s => s.Equals(buf));
    if (srh != -1)
        return (-1, "");
    else
    {
        Array.Resize(ref lexes, lexes.Length + 1);
        lexes[lexes.Length - 1] = buf;
        return (lexes.Length - 1, buf);
    }
}

تنفيذ الخوارزمية

تتمثل الخطوة الأولى في تحديد نهاية الدورة - حالة FIN ، وكذلك تنفيذ الحالة الأولية ، والتي ستكون

sr = new StringReader(text); //    
while (state != States.FIN)
{
    switch (state)
    {
        case States.S:
            if (sm[0] == ' ' || sm[0] == '\n' || sm[0] == '\t' || sm[0] == '\0' || sm[0] == '\r' )
                GetNext();
            else if (Char.IsLetter(sm[0]))
            {
                ClearBuf();
                AddBuf(sm[0]);
                state = States.ID;
                GetNext();
            }
            else if (char.IsDigit(sm[0]))
            {
                dt = (int)(sm[0]-'0');
                GetNext();
                state = States.NUM;
                
            }
            else if (sm[0] == '{')
            {
                state = States.COM;
                GetNext();
            }
            else if (sm[0] == ':')
            {
                state = States.ASGN;
                ClearBuf();
                AddBuf(sm[0]);
                GetNext();
            }
            else if (sm[0] == '.')
            {
                AddLex(Lexemes, 2, 0, sm[0].ToString());
                state = States.FIN;
            }
            else
            {
                state = States.DLM;
            }
        break;
    }  
}

تسمح لك طريقة GetNext بالحصول على الحرف التالي في السلسلة ، ClearBuf ، على التوالي ، يمسح المخزن المؤقت الذي يخزن الرمز المميز

private void GetNext()
{
    sr.Read(sm, 0, 1);
}

يجب إيلاء اهتمام خاص لعامل التخصيص ": =" ، والذي يتكون من عاملين منفصلين. إن أبسط طريقة لتعريف هذا العامل هي إضافة شرط وكتابة القيمة الوسيطة إلى المخزن المؤقت. لهذا ، تم تنفيذ حالة ASGN منفصلة ( في تخصيص الترجمة - التخصيص ). إذا تم تعريف المخزن المؤقت على أنه ":" ، فإن الخوارزمية ستضيف ببساطة رمزًا جديدًا ، وإذا كانت العلامة التالية هي "=" ، فسيتم إضافة عامل تعيين واحد.

case States.ASGN:
    if (sm[0] == '=')
    {
        AddBuf(sm[0]);
        AddLex(Lexemes, 2, 4, buf);
        ClearBuf();
        GetNext();
    }
    else
        AddLex(Lexemes, 2, 3, buf);
    state = States.S;
break;

يتم تنفيذ الحالة النهائية والحالة التي بها خطأ فقط من خلال رسائل الخدمة. يمكنك تحسين هذا الخيار والتحقق من الخطأ أيضًا ، ولكن ربما يمكن نقل هذه الوظيفة إلى المحلل اللغوي.

case States.ER:
    MessageBox.Show("  ");
    state = States.FIN;
    break;
case States.FIN:
    MessageBox.Show("  ");
    break;

اختبارات

يمكنك اختبار الخوارزمية بطرق مختلفة: تحديد مسار ملف .pas مباشرةً ، أو إنشاء سلسلة برمجيًا ، أو أي خيار مناسب آخر. نظرًا لأننا نكتب بلغة C # ، فلن يكون من الصعب إضافة نموذج إلى التطبيق ، والذي سيحتوي على مربعين نصيين ، الأول لإدخال رمز البرنامج ، والثاني - يعرض نتيجة الخوارزمية.



بالضغط على الزر ، سنبدأ في تحليل النص ، وستتم معالجة النتيجة الناتجة باستخدام إنشاء المفتاح : بالإضافة إلى ذلك ، سنعرض نوع الرمز المميز الذي تم العثور عليه.

private void button1_Click(object sender, EventArgs e)
{
    textBox2.Clear();
    TplMain tpl = new TplMain();
    tpl.Analysis(textBox1.Text);
    
    foreach(var lex in tpl.Lexemes)
    {
        switch (lex.id)
        {
            case 1:
                textBox2.Text += "id: " + lex.id + " lex: " + lex.lex + " val: " + lex.val + " |" + "   "+ Environment.NewLine;
                break;
            case 2:
                textBox2.Text += "id: " + lex.id + " lex: " + lex.lex + " val: " + lex.val + " |" + "  " + Environment.NewLine;
                break;
            case 3:
                textBox2.Text += "id: " + lex.id + " lex: " + lex.lex + " val: " + lex.val + " |" + "  " + Environment.NewLine;
                break;
            case 4:
                textBox2.Text += "id: " + lex.id + " lex: " + lex.lex + " val: " + lex.val + " |" + "  " + Environment.NewLine;
                break;
                
        }     
    }       
}

ادخال البيانات

program hellohabr;
	var a, b, c : integer;
begin
	c := a - b + 15;
end.

انتاج |

id: 1 lex: 0 val: program |   
id: 4 lex: 1 val: hellohabr |  
id: 2 lex: 1 val: ; |  
id: 1 lex: 1 val: var |   
id: 4 lex: 1 val: a |  
id: 2 lex: 2 val: , |  
id: 4 lex: 1 val: b |  
id: 2 lex: 2 val: , |  
id: 4 lex: 1 val: c |  
id: 2 lex: 3 val: : |  
id: 1 lex: 2 val: integer |   
id: 2 lex: 1 val: ; |  
id: 1 lex: 5 val: begin |   
id: 4 lex: 1 val: c |  
id: 2 lex: 4 val: := |  
id: 4 lex: 1 val: a |  
id: 2 lex: 6 val: - |  
id: 4 lex: 1 val: b |  
id: 2 lex: 5 val: + |  
id: 3 lex: 1 val: 15 |  
id: 2 lex: 1 val: ; |  
id: 1 lex: 6 val: end |   
id: 2 lex: 0 val: . |  

خوارزمية كاملة

public void Analysis(string text)
{
    sr = new StringReader(text);
    while (state != States.FIN)
    {
        switch (state)
        {

            case States.S:
                if (sm[0] == ' ' || sm[0] == '\n' || sm[0] == '\t' || sm[0] == '\0' || sm[0] == '\r')
                    GetNext();
                else if (Char.IsLetter(sm[0]))
                {
                    ClearBuf();
                    AddBuf(sm[0]);
                    state = States.ID;
                    GetNext();
                }
                else if (char.IsDigit(sm[0]))
                {
                    dt = (int)(sm[0] - '0');
                    GetNext();
                    state = States.NUM;

                }
                else if (sm[0] == '{')
                {
                    state = States.COM;
                    GetNext();
                }
                else if (sm[0] == ':')
                {
                    state = States.ASGN;
                    ClearBuf();
                    AddBuf(sm[0]);
                    GetNext();
                }
                else if (sm[0] == '.')
                {
                    AddLex(Lexemes, 2, 0, sm[0].ToString());
                    state = States.FIN;
                }
                else
                {
                    state = States.DLM;

                }

                break;
            case States.ID:
                if (Char.IsLetterOrDigit(sm[0]))
                {
                    AddBuf(sm[0]);
                    GetNext();
                }
                else
                {
                    var srch = SerchLex(Words);
                    if (srch.Item1 != -1)
                        AddLex(Lexemes, 1, srch.Item1, srch.Item2);
                    else
                    {
                        var j = PushLex(TID, buf);
                        AddLex(Lexemes, 4, j.Item1, j.Item2);
                    }
                    state = States.S;
                }
                break;

            case States.NUM:
                if (Char.IsDigit(sm[0]))
                {
                    dt = dt * 10 + (int)(sm[0] - '0');
                    GetNext();
                }
                else
                {

                    var j = PushLex(TNUM, dt.ToString());
                    AddLex(Lexemes, 3, j.Item1, j.Item2);
                    state = States.S;
                }
                break;
            case States.DLM:
                ClearBuf();
                AddBuf(sm[0]);

                var r = SerchLex(Delimiter);
                if (r.Item1 != -1)
                {
                    AddLex(Lexemes, 2, r.Item1, r.Item2);
                    state = States.S;
                    GetNext();
                }
                else
                    state = States.ER;
                break;
            case States.ASGN:
                if (sm[0] == '=')
                {
                    AddBuf(sm[0]);
                    AddLex(Lexemes, 2, 4, buf);
                    ClearBuf();
                    GetNext();
                }
                else
                    AddLex(Lexemes, 2, 3, buf);
                state = States.S;

                break;
            case States.ER:
                MessageBox.Show("  ");
                state = States.FIN;
                break;
            case States.FIN:
                MessageBox.Show("  ");
                break;
        }
    }
}

خاتمة

قد يبدو أن محلل المعجم ليس شيئًا واضحًا جدًا ، وفي الواقع ليس مهمًا جدًا. لماذا لا يمكنك وضع كل هذا في محلل؟ كيف تعمل مع الهياكل المعقدة؟ نعم ، تختلف طرق تنفيذ المحلل المعجمي من مترجم إلى مترجم ، ولكن عندما تقوم بتحليل كل هذه المبادئ ، فلن تفهم فقط كيفية عمل لغة البرمجة X ، ولكن سيكون لديك أيضًا أساس لتطوير لغة البرمجة الخاصة بك: Python ثانية ، أو لغة لمجالك - كل هذا ممكن أن تدرك بفهم جميع تفاصيل العمل وجهاز المترجم بشكل عام.



يمكن العثور على المشروع هنا