Syntax Analysis | تحليل بناء الجملة [3]

بسم الله الرحمن الرحيم

السلام عليكم ورحمة الله وبركاته

 

عودة بعد انقطاع بعدما شرحنا المرحلة الاولى من مراحل التحليل في المُترجم ، وهي مرحلة التحليل المعجمي ويتم فيها قراءة الـمُدخل و تقسيمه الى كلمات tokens وحفظة في جدول الرموز ، نبدأ اليوم بشرح المرحلة الثانية من التحليل و هي تحليل بناء أو تركيب الجملة syntax Analysis.

 

 

تحليل بناء الجملة ( syntax analysis ) أو مايسمى ايضاً بـ ( Parser ) تقوم مهمته على التأكد من أن المُدخل متوافق مع القواعد المخصصة بلغة البرمجة و تكون قواعد اللغة محددة إما بـ (context-free-Grammer (CFG أو بـ BNF) Backus-Naur Form) وهي طرق لوصف قواعد اللغة. وتحليل بناء الجملة (syntax analysis ) من مهامه ايضاً اخراج الـtokens بشكل شجري وما يسمى ايضا بـ parsing tree وذلك بعد التاكد من أن الـ tokenn مطابق للشكل العام لقاعدة اللغة.

 

هناك عدة انواع للمحلل ( parser ) :

١- المحلل العام ( universal ) وهو محلل عام لأي قاعدة لغة ، ولها عدة طرق أو خوارزميات مثل خوارزمية Cocke-Younger-Kasami و خوارزمية Earley. ولكن تعتبر طريقة غير فعالة جدا لتنفيذ المترجم.

بالنسبه للنوع الثاني والثالث تعتبر هي الانواع الشائعة للمحلل ( parser ).

٢- محلل يعرف بـ الاعلى – الاسفل ( top-down parsing )  وهو اسم يصف العملية التي يقوم بها وهي بناء الشجرة tree parser ويبدأ ببنائها من الاصل/الجذر ( root ) انتهائا لـ الاطراف/الاوراق ( leaves ).

٣- محلل الاسفل-الاعلى ( bottom-up parsing ) وهو عكس النوع الذي قبله ، فهو يبني الشجرة من الاسفل ( leaves ) الى ان يصل لأعلى نقطه وهي الـ (roott).

 

ولنفهم طريقة عمل المحلل ( parser ) يجب قبل ذلك ان نحدد ونعرف طريقة وصف قواعد اللغة  الذي سيتبعه المحلل.

وهنا سنعطي شرح عام وبسيط عن وصف اللغة بـ (context-free-Grammer (CFG.

#context-free-Grammer هي طريقة لوصف اللغة وتحتوي على :

- Variable/non-Terminal وهي المتغيرات التي تُحدد كيف تُبنى اللغة.

- Terminal هي كلمات او الـ tokens

- قاعدة التوليد production rule وهي التي تستبدل المتغير non-Terminal بإحدى/مجموعة من المتغيرات non-trminals أو الـكلمات terminalss.

- رمز البداية  start symbol و هو الرمز الذي نبدأ به عملية التبديل أو الاشتقاق ، ويعتبر ضمن مجموعة المتغيرات non-Terminall.

 

#مثال :   S → a B c

                B → d

S و B هي متغيرات [non-terminal]

a و d و c هي الكلمات [terminal] أو ماتسمى token 

S =>  a B c => a d c

في الخطوه الاولى استبدلنا الـS بـ  a B c وذلك باتباع القاعدة الأولى

وفي الخطوة التي تليها استبدلنا الـB بـ الـ d وذلك بإتباع القاعدة الثانية

 

#الاشتقاق ( Derivation ) :

هي مجموعة من الخطوات المتسلسلة تبدأ من رمز البدء start symbol، ويتم استخدام قواعد التوليد production rule لاستبدال جميع المتغيرات non-terminal بـ ( terminals ). وهذه الطريقة تساعدنا  في بناء الرسم الشجري بطريقة صحيحة.

وللاشتقاق طريقتين :

- اشتقاق اقصى اليسار ( left-most derivation ): بحيث يكون اختيار المتغير لتبديلة دائما هو المتغير  المتواجد في اقصى اليسار.

- اشتقاق اقصى اليمين ( right-most derivation ): بحيث يكون اختيار المتغير لتبديلة دائما هو المتغير  المتواجد في اقصى اليمين.

مثال :

E → E + E

E → E * E

E → id

اشتقاق اقصى اليسار ( left-most derivation )

E => E + E =>  E * E + E  => id * E + E => id * id + E => id * id + id

اشتقاق اقصى اليمين ( right-most derivation )

E => E + E => E + E * E => E + E * id => E + id * id =>  id + id * id

نعود حاليا لموضوعنا الأساسي ، المحلل ( parser ) يأخذ المدخل من المرحلة التي قبله – مرحلة التحليل المعجمي – على شكل token و يتأكد من خلوها من الاخطاء المخصصة بتركيب وبناء الجملة بناءاً على قاعدة اللغة ، ومن بعد ذلك يبنى parser tree أو مايسمى ايضا بالـ syntax tree - ولها مسمى آخر أيضا هو semantic structure – وهو النتيجة من مرحلة تحليل بناء أو تركيب الجملة والتي ستذهب مباشرة للمرحلة التي بعدها وهي مرحلة التحليل الدلالي semantic analysis التي من خلالها يتم تصدير اللغة المتوسطة intermidiate code.

 

*ملاحظة: مرحلة تحليل بناء الجملة syntax analysis فيها تفصيلات كثيرة ولا  استطيع ذكرها جميعا في هذه التدوينة ، لمن يريد الاستزادة ، انصح بكتاب (Compilers Principles Techniques and Tools (2nd Edition .

كلمات دليلية: