CompilerLesson

Transcription

1 2010 مترجما... تبرمج كي فيف فهم برمجة الكومبايلر ( Compiler )خطوة بخطوة ياسين الجزاي ري khatibe_30@hotmail.fr هذا الكتاب مجاني و لا يحق لا ي بيعه أو المتاجرة به

2 الحمد الله رب العالمين والصلاة و السلام على المبعوث الا مين رحمة للعالمين محمد إبن عبد االله و على ا له و صحبه و سلم تسليما آثيرا. على الرغم من أن المكتبة العربية غنية جدا بعديد المصادر في شتى المواضيع لدرجة أن الطالب يضيع بين رفوف الكتب محاولا إيجاد الكتاب المناسب إلا أن الكتب التي تتناول موضوع الترجمة compilation) (La معدومة تقريبا, و في محاولة لتدعيم المكتبة العربية نقدم لكم هذا الكتاب الذي يشرح بطريقة سهلة و مفهومة الخطوات الا ساسية لكيفية برمجة مترجم (Compilateur) خاص بك, لا يهم أن تكون مهمة هذا المترجم ترجمة أآواد لغة متقدمة إلى لغة الا لة بل يمكن إستعمال الكتاب لبرمجة برامج تحول الا آواد من لغة إلى أخرى, و لعل من أبرز الا مثلة البرامج المنتشرة التي تحول من اللغة C إلى PASCAL أو إلى JAVA و غيرها. سنستهل آتابنا بمقدمة سريعة عن الترجمة و أصولها و من ثم عرض للا دوات اللازمة مع روابط تحميلها و آيفية تنصيبها, بعد ذلك نتطرق إلى مثال بسيط الهدف منه شرح الا دوات المستعملة في هذا الكتاب لنكمل بقية الكتاب في شرح آيفية برمجة مترجم خطوة بخطوة و سطرا بسطر. من الضروري جدا أن تحيط علما با ساسيات لغة البرمجة ++C لا نها ما سنعتمد عليه في هذا الكتاب بالا ضافة إلى معرفة و إن آانت سطحية بلغة التجميع أو ما تعرف بالا سمبلي. 2

3 4 الفهرس 1. مقدمة... 4 (1 المحلل المعجمي lexicale)...(l analyse 6 (2 المحلل النحوي syntaxique)...(l analyse 7 (3 المحلل المعنوي sémantique)...(l analyse 7 (4 توليد الكود ) code...(génération de LEX و BISON و متطلبات العمل برمجة المترجم

4 المترجم... هل فكرت يوما في برمجة مترجم ما آمترجم السي أو الباسكال أو غيرهما من اللغات هل تعتقد أن الا مر صعب أجل هو ليس باليسير و أيضا ليس بالمستحيل, و سنحاول في هذا الكتاب با ذن االله أن نوضح خطوات برمجة مترجم صغير. 1. مقدمة لدينا برنامج مكتوب بلفة ما, إذا آانت هذه اللغة مفهومة من طرف الحاسوب فا نه يقوم بتنفيذ البرنامج مباشرة, أما إذا آانت لغة البرنامج غير مفهومة من طرف الحاسوب فيجب تحويل الكود المصدر source) (texte إلى آود مفهوم من طرف الحاسوب, cible),(code هذه العملية تسمى الترجمة, المترجم هو برنامج مكتوب بلغة ما يقوم بترجمة آود من لغة مصدر إلى لغة الا لة. - مراحل ترجمة برنامج لنلقي نظرة سريعة على مراحل الترجمة. :L analyse lexicale (1 المرحلة الا ولى من التحليل, يقوم المترجم هنا باستخراج الكلمات و التي تسمى tokens انطلاقا من سلسلة من الحروف, مثلا, لاحظ هذا السطر من الكود المصدر: for i := 1 to vmax do a := a+i 4

5 : نستخرج هذه السلسة من ال tokens for i := 1 to vmax do a := a + 1 آلمة محجوزة( clé (mot معرف (identificateur) إسناد (affectation) صحيح (entier) آلمة محجوزة clé) (mot معرف (identificateur) آلمة محجوزة clé) (mot معرف (identificateur) إسناد (affectation) معرف (identificateur) عملية رياضية arithmétique) (opérateur معرف (identificateur) فاصل (séparateur) مباشرة و بعد تحليل الكود نقوم ببناء جدول الرموز symboles) (table des عن قاي مة من مجموعة ترآيبات تحمل خصاي ص آل token و يكون آالا تي: وهو عبارة Numéro de symbole Token for to do Type de token mot clé mot clé mot clé séparateur Type de variable بهذه الطريقة يقوم المحلل المعجمي lexicale) (L analyseur بتحليل الكود المصدر و بناء جدول الرموز إن صحت ترجمة المصطلحات و إن آنت قد لاحظت, فا ن المحلل المعجمي لا يهتم بترتيب ال tokens و لذلك فا ن السطر التالي صحيح تماما بالنسبة لل :analyseur lexical for for for i := := 10 do for a a هنا يا تي دور التحليل النحوي أو.l analyse syntaxique 5

6 :L analyse syntaxique (2 في هذه المرحلة نتحقق أن ترتيب ال tokens موافق لتعريف اللغة التي نريد برمجة مترجم لها, نستطيع أن نقول أننا نتحقق من النحو الخاص باللفة و يكون هذا إنطلاقا من مجموعة من القواعد أو ما يسمى,grammaire يقوم المحلل النحوي ببناء شجرة (arbre) باستخدام ال tokens التي يوفرها المحلل المعجمي: for i := 1 to vmax do a := a+i - الشجرة النحوية المستخرجة بعد التحليل النحوي - أما القواعد المحدد للنحو فا نها تكون معرفة على الشكل التالي: prog -> debut inst fin point inst -> ident affectaion expression expression -> ident entier reel 6

7 :L analyse sémantique (3 أثناء التحليل المعنوي sémantique) (L analyse نتا آد مثلا أن القيمة التي سنسندها لا حد المتغيرات تكون من نفس نوع المتغير, إذ لا يجب إسناد قسمة حقيقية لمتغير صحيح و هكذا. :Génération de code (4 نقوم هنا با نتاج آود بلغة الا لة أو لغة التجميع و هذا مثال لكود بلغة قريبة من لغة الا لة: var_a A0000 les étiquettes des variables var_i A0001 var_vmax A0002 le code du programme mov var_i,1 loop : mov A0, (var_i) comparaison i >= vmax jge A0, (var_vmax), finfor si vrai aller en finfor mov A0, (var_a) calcul de a+i add A0, A0, (var_i) mov var_a,a0 a := a+i mov A0, (var_i) on incrémente i add A0, A0, 1 mov var_i, 1 jmp loop et on continue la boucle finfor :... 7

8 LEX و BISON و متطلبات العمل.2 آانت تلك مقدمة سريعة جدا و مختصرة جدا عن مراحل الترجمة, ماذا بعد, قبل نحدد قواعد اللغة التي سنستخدمها و نبدأ برمجت المحلل المعجمي و النحوي و المعنوي سنلقي نظرة على أداتين مهمتين و هما LEX و.BISON Scanner أو ما يسمى ب (Analyseur lexicale) هي أداة تقوم بتوليد محلل معجمي LEX مكتوب باللغة C, يستعمل LEX قوالب (patterns) لمطابقة السلاسل الحرفية الموجودة في الكود المصدر و تحويلها إلى tokens و من ثم إرسالها إلى المحلل النحوي, ال tokens تكون عبارة عن معرفات عددية ثابتة, أي أن ال scanner عندما يجد مثلا المتغير x فا نه يرسل للمحلل النحوي ال token الممثلة للمتغيرات و لتكن IDENT و أيضا يرسل له إسم المتغير و يقوم با دخاله إلى جدول الرموز table des symboles و تعيين خصاي صه آنوعه و غيرها من الخصاي ص. BISON أو YACC يولد لنا شفرة باللغة C لمحلل نحوي syntaxique) (Analyseur و يعرف أيضا بال,parser يستعمل Bison قواعد اللغة لتحليل ال tokens القادمة من ال scanner و يبني عليها شجرة نحوية, تمثل هذه الصورة آيفية التعاون بين ال LEX و :YACC إذا و حسب الشكل السابق الملف bas.y يحمل وصف لل parser وصف لل,scanner الملف y.tab.h يولده ال YACC و يحوي تعريف ال أحد ال tokens في الملف :y.tab.h أما الملف bas.l فيحمل tokens وهذا تصريح عن #define IDENT 102 بعد ذلك يولد لنا آل من LEX و YACC (سنستعمل BISON و هو مشابه لل lex.yy.c (YACC و y.tab.c و هما على الترتيب المحلل المعجمي (scanner) و المحلل النحوي.(parser) 8

9 y.tab.c وباستعمال أحد مترجمات اللغة C نترجم آل من lex.yy.c النهاي ي bas.exe و هو المترجم الجديد... تهانينا. و لنحصل على البرنامج ماذا سنحتاج من أدوات لفعل ذلك : أولا قم بتحميل ++C 3.0 TURBO من هذا أحد هذه الروابط قم بتثبيته في القرص \:D بحيث يكون مسار المجلد bin آالا تي:,D:\TC\BIN طبعا أنت حر في تثبيته في أي مكان و لكن الشرح سيكون على أساس أنه مثيت في المسار السابق لا ننا سنستعمل البرنامج D:\TC\BIN\TC.EXE لترجمة أآواد C. و,BISON حملهما من أحد هذه الروابط: LEX قم بفك الضغط عن الملف Lex_Yacc.zip وانسخ المجلد Lex_Yacc في القرص \:D, لديك المجلد D:\Lex_Yacc\exemples والذي سيكون مسرح الا حداث. ليصبح أنسخ محتويات آل من المجلد D:\Lex_Yacc\Bison\bin و المجلد D:\Lex_Yacc\Lex\bin إلى المسار C:\WINDOWS طبعا هذا إذا آانت الويندوز مثبتة في القرص \:C, المهم أن تنسخه إلى المجلد WINDOWS الخاص بالنظام, أخيرا أنسخ المجلد D:\Lex_Yacc\Bison\share با آمله إلى القرص \:C ليصبح لديك المسار C:\share في جهازك, هنا نكون قد ثبتنا الا دوات اللازمة للعمل, لنبدأ على برآة االله. TURBO =5+5 و قبل البدء في برمجة المترجم سنقوم ببرمجة برنامج صغير باستخدام LEX و BISON و ++c بحيث يقوم بقراءة ملف يحتوي على عمليات حسابية من عدة سطور, مثلا =3+3*100^ *10 و يقوم بحسابها. سنعمل على مستوى المجلد,D:\Lex_Yacc\exemples.scanner أو L analyseur lexicale لنبدأ بكتابة المحلل المعجمي أو 9

10 ,scanner C سنقدم لل LEX الشكل التالي: وصفا معينا ليولد لنا هو آود لل آيف يكون ذلك الوصف يكون من...تعريفات إذا احتجناها -... %%... قواعد... %%... دوال فرعية إذا احتجناها -....C الدوال الفرعية عبارة عن آود بلغة C, التعريفات و أما القواعد فلها نحو خاص + بعض أآواد إفتح المفكرة واآتب الكود التالي: % #include<stdlib.h> #include"d:\lex_yacc\exemples\expy2.h" % blanc [ \t]+ chiffre [0-9] entier chiffre+ قمنا بكتابة التعريفات, لقد احتجنا إلى إضافة آود بلغة Cو لذلك آتبناه بين العلامتين % و %, سنحتاج إلى دالة من المكتبة,stdlib.h أما استعمالنا للملف expy.2h فهو لا نه الملف الذي سيحوي تعريفات ال tokens فيما بعد, لا تقلق فذلك الملف يولده BISON فيما بعد لذلك لا تعره اهتماما الا ن, ذلك الجزء الا ول من التعريفات, الجزء الثاني - 3 سطور الا خيرة- قمنا فيه بالتصريح عن بعض القوالب التي سنستعملها لتصفية ال tokens من الكود المصدر, ماذا تعني لدينا ثلاث قوالب, blanc و chiffre و :entier blanc chiffre entier [ \t]+ [0-9] chiffre+ آل الفراغات, فراغ أو أآثر آل الا عداد من 0 إلى 9 سلسلة من عدد واحد أو أآثر هذا جدول للحروف التي نستعملها لا نشاء القوالب و معانيها:. \n * آل الا حرف باستثناء n\ سطر جديد صفر نسخة أو أآثر من العبارة السابقة لها 10

11 +? ^ $ a b (ab)+ "a+b" [] z نسخة واحدة أو أآثر من العبارة السابقة لها نسخة واحدة أو لا شيء من العبارة السابقة لها بداية السطر نهاية السطر b أو a نسخة أو أآثر من السلسلة ab السلسلة a+b حرفيا في ة من الا حرف, [a-z] تعني آل الا حرف من a إلى وآمثال عن بعض الا قنعة لاحظ هذا الجدول: التطابقات abc ab,abc,abcc,abccc, abc,abcc,abccc, abc,abcbc,abcbcbc, a,abc a,b,c أي حرف بين aو z a,-,z -,a,z حرف أو أآثر(بما في ذلك الا عداد) الفراغات أي شيء باستثناء a و b a,^,b a,,b b أو a العبارة abc abc* abc+ a(bc)+ a(bc)? [abc] [a-z] [a\-z] [-az] [A-Za-z0-9]+ [ \t\n]+ [^ab] [a^b] [a b] a b بهذا يصبح الكود الذي آتبته في المفكرة سابقا أآثر وضوحا و سيتضح آلما تقدمت في قراءة هذا الكتاب, أضف هذا الكود إلى الكود السابق ليصبح: % #include<stdlib.h< #include"d:\lex_yacc\exemples\expy2.h" % blanc [ \t]+ chiffre [0-9] entier chiffre+ %% 11

12 blanc entier yylval=atoi(yytext) return(nombre) "+" return(plus) "*" return(mult) "-" return(moin) "/" return(divs) "^" return(puis) "(" return(parg) ")" return(pard) "=" return(fin) \n %% أضفنا الجزء الخاص بالقواعد و هو بين العلامتين %% و %%, هناك 11 ال LEX بكل بساطة نلخص القواعد في : إذا وجدت... إفعل... قاعدة, ماذا سيفعل مثلا القاعدة الا ولى, إذا وجدت blanc إفعل (لا شيء), أي أن ال scanner الفراغات الموجودة في الملف الذي سنقوم بترجمته و حساب ما فيه. سيفوت yylval = atoi(yytext) return(nombre) القاعدة الثانية, entier إذا وجدت إفعل: السطر الثاني return(nombre) نعيد فيه ال token التي حصلنا عليها وهي رقم صحيح حسب القالب المستخدم( entier ) إلى المحلل النحوي أو,parser مثلا إذا وجدنا في الملف الذي سنحسب ما بداخله العملية =5+5 فا ن أول token نعيدها هي NOMBRE ولكن, سنحتاج إلى قيمة ال NOMBRE الذي عثر عليه ال scanner ولنمررها إلى ال parser نقوم باسنادها إلى المتغير yylval وهو عبارة عن همزة وصل بين ال scanner و ال,parser ولفعل ذلك نحول القيمة الحرفية الموجودة في المتغير yytext الذي يحمل سلسلة الحروف المشكلة لا خر تطابق إلى عدد صحيح باستعمال الدالة atoi الموجودة داخل المكتبة.stdlib.h القاعدة الثالثة, إذا وجدت + إفعل (أعد ال token التالية:,(PLUS قاعدة سهلة وواضحة, إذ سنكتفي بالقول لل parser أننا وجدنا PLUS ولن نحتاج طبعا إلى قيمتها أو شيء من هذا, فقط نعيد ال token و نذهب إلى القاعدة التالية. القاعدة الا خيرة, n\ إذا وجدت (سطر جديد) إفعل (لا شيء). 12

13 أنهيانا الا ن وصف ال,scanner ماذا بعد خزن الكود في المسار D:\Lex_Yacc\exemples باسم,expl2.l وباستعمال الا مر FLEX expl2.l يولد LEX آود C لل,scanner حتى لا نبقى في آل مرة نفتح نافذة الدوس و نكتب الا مر قم بفتح المفكرة و اآتب الا وامر التالية: FLEX expl2.l Pause ثم أحفظ الملف باسم FLEX_2.bat في المجلد,D:\Lex_Yacc\exemples الملف الدفعي flex_2.bat لتحصل على النتيجة التالية: دوبل آليك على لا يوجد أخطاء, في حالة وجود أخطاء سيعرض لك LEX رسالة بالا خطاء و مكان آل خطا و وصفه, لقد قام LEX للتو بتوليد الملف lex.yy.c في المسار D:\Lex_Yacc\exemples والذي يمثل آود C لل scanner أو.L analyseur lexicale ذلك النصف الا ول من البرنامج النهاي ي, لنكمل. :(grammaire) قبل أن نبدأ آتابة وصف YACC سنحدد القواعد Input -> Input Line Line -> FIN Exp FIN Exp -> NOMBRE Exp PLUS Exp Exp MOIN Exp Exp MULT Exp Exp DIVS Exp MOIN Exp Exp PUIS Exp PARG Exp PARD ما هذا 13

14 الرمز يعني فراغ أو لاشيء, الكلمات المكتوبة بحروف آبيرة تمثل ال tokens التي سيعيدها الscanner, أما باقي الكلمات فهي رموز غير نهاي ية non-terminaux).(symboles أحسن طريقة لفهم القواعد السابقة هي تتبع مثال, مثلا هل السلسلة =9*5+5 تحقق شروط ال grammaire السابق Input -> Input Line -> Input -> Exp FIN -> Exp PLUS Exp FIN -> Exp PLUS Exp MULT Exp FIN -> NOMBRE PLUS NOMBRE MULT NOMBRE FIN -> * 9 = إذا وصلنا إلى العبارة =9*5+5 إنطلاقا من,Input هذا سيعطيك فكرة مبدي ية عن ماهية القواعد التي سنستخدمها لاحقا. نعود, إفتح المفكرة و اآتب الكود التالي: % #include<conio.h> #include<stdio.h> #include<stdlib.h> #include<math.h> #include "d:\lex_yacc\exemples\expl2.c" % %token NOMBRE PLUS MOIN MULT DIVS PUIS PARG PARD FIN %left PLUS MOIN %left MULT DIVS %left NEG %right PUIS %start Input بدأنا آتابة الوصف الذي سيولد منه YACC ال,parser أول ما بدأنا به هو آتابة تعاريف نحتاجها أثناء آتابة القواعد, هناك قسمين من التعاريف, قسم مكتوب باللغة C وهو بين العلامتين % و %, واضح الكود المكتوب باللغة C, إذا آنت تتساءل عن الملف expl2.c فهو نفسه الملف lex.yy.c الذي يحمل آود ال scanner السابق, فقط سنغير اسمه فيما بعد. القسم الثاني من الكود هو وصف خاص, باستعمال الكلمة المحجوزة %token قمنا بالتصريح عن ال tokens التي سيستعملها آل من الscanner و ال,parser و لدينا :tokens 9. NOMBRE, PLUS, MOIN, MULT, DIVS, PUIS, PARG, PARD, FIN هناك أولوية أثناء إجراء عمليات الحساب, فالقسمة أقوى من الضرب الذي هو أقوى من الجمع و الطرح, وأقصد بكلمة أقوى أولوية الحساب, مثلا عند حساب 6*5+5 فا ننا نحسب 6*5 ثم نضيف إلى النتيجة العدد 5, ولهذا أضفنا السطور : 14

15 %left PLUS MOIN %left MULT DIVS %left NEG %right PUIS أقل أولوية للجمع و الطرح معا, العمليات تجرى على اليسار القسمة و الضرب أقوى, نبدأ باليسار أثناء الحساب النفي أقوى من ما يسبقه الرفع إلى قوة أقوى من ما سبقه, ولكن نبدأ باليمين السطر الا خير %start Input نحدد فيه القاعدة التي نبدأ منها أثناء التحقق من ترتيب ال.scanner القادمة من ال tokens المرحلة الثانية هي آتابة القواعد اللازمة, نغير الكود السابق ليصبح: % #include<conio.h> #include<stdio.h> #include<stdlib.h> #include<math.h> #include "d:\lex_yacc\exemples\expl2.c" % %token NOMBRE PLUS MOIN MULT DIVS PUIS PARG PARD FIN %left PLUS MOIN %left MULT DIVS %left NEG %right PUIS %start Input %% Input: Input Line Line :FIN Exp FIN printf("=%d\n",$1) Exp :NOMBRE $$=$1 Exp PLUS Exp $$=$1+$3 Exp MOIN Exp $$=$1-$3 Exp MULT Exp $$=$1*$3 Exp DIVS Exp $$=$1/$3 MOIN Exp %prec NEG $$=-$2 Exp PUIS Exp $$=pow($1,$3) PARG Exp PARD $$=$2 %% 15

16 آل ما فعلناه هو آتابة القواعد و إخبار ال parser ماذا يفعل عند تحقق آل قاعدة, القاعدة الا ولى هي Line,Input : Input وهي نقطة البداية, Input ستعطي شيي ين, إما فراغ أو,Input Line سهلة وواضحة. القاعدة الثانية,,Line إما تعطينا FIN (وهي الحرف "=" آما هو معرف على مستوى وصف (LEX أو,Exp FIN وهنا نكتب نتيجة العملية الحسابية باستعمال,printf("=%d\n",$1) ماذا يعني الرمز $1 أثناء التحقق يمكننا أن نعطي و نا خذ قيم الرموز و ال tokens التي نجدها في طريقنا, وهنا سنكتب على الشاشة قيمة Exp وهي معرفة ب $1, أما قيمة FIN إذا أردنا إستعمالها فهي $2 وهكذا. في آل قاعدة هناك نصف أيمن و نصف أيسر, و لا سناد قيم أو قراءة قيم الرموز المكونة للقاعدة فا ننا نستعمل x$: Exp -> Exp PLUS Exp $$ $1 $2 $3 طبعا استعمال قيم الرموز باستخدام x$ أو $$ هو تابع للتحليل المعنوي( L analyse (sémantique فالمحلل النحوي أو L analyseur syntaxique لا يهتم بالقيم. ننتقل إلى القاعدة الثالثة الخاصة ب Exp,Exp تعطينا أحد ثمانية خيارات: في حالة Exp <- NOMBRE فالا مر بسيط, نعطي قيمة الرقم إلى Exp $1=$$, و تسمى هذه الحرآة الا خيرةب Action sémantique آما أذآر. باستعمال في حالة Exp <- Exp PLUS Exp فالا مر بسيك أيضا, Exp التي عى يسار القاعدة تا خذ قيمة مجموع Exp التي على يمين القاعدة و نفعل هذا باستعمال $2+$1=$$, وهكذا نفس الشيء بالنسبة لباقي القواعد المماثلة في حالة Exp <- MOINS Exp هناك شيء جديد, طبعا نقصد من هذه القاعدة حالة النفي مثلا 112-, ولكن تلك الناقص ليست هي نفسها عملية الطرح فهي لها أولوية قصوى, مثلا إذا وجدنا 5/6- فا ننا نحسب 5- أولا, ولهذا نعطيها أولوية NEG باستعمال التعليمة NEG%,prec أما الباقي واضح وهو إعطاء القيمة Exp إلى Exp التي على اليسار باستعمال $2 = $$. Exp <- Exp PUIS Exp فنقصد بها الرفع إلى القوة( 3^2=9 ) و بالنسبة للحالة آما يلي math.h الموجودة في المكتبة pow سنحسبها باستعمال الدالة.$$=pow($1, $3) 16

17 إلى هنا ننهي قسم القواعد الخاصة بال,parser بقي لنا أن نصرح عن الدالة الري يسية main() وهذا في قسم الدوال الفرعية: % #include<conio.h> #include<stdio.h> #include<stdlib.h> #include<math.h> #include "d:\lex_yacc\exemples\expl2.c" % %token NOMBRE PLUS MOIN MULT DIVS PUIS PARG PARD FIN %left PLUS MOIN %left MULT DIVS %left NEG %right PUIS %start Input %% Input: Input Line Line :FIN Exp FIN printf("=%d\n",$1) Exp :NOMBRE $$=$1 Exp PLUS Exp $$=$1+$3 Exp MOIN Exp $$=$1-$3 Exp MULT Exp $$=$1*$3 Exp DIVS Exp $$=$1/$3 MOIN Exp %prec NEG $$=-$2 Exp PUIS Exp $$=pow($1,$3) PARG Exp PARD $$=$2 %% int yyerror (char *s) printf("%s\n",s) int yywrap() return 1 main() clrscr() if((yyin=fopen("d:\\lex_yacc\\exemples\\input.txt","r"))==null) 17

18 printf("input.txt not found!\n") getch() return yyparse() getchar() قمنا بتعريف أجسام الدالتين yyerror() التي تستدعى من طرف ال parser عند وقوع خطا أو عدم تطابق ترتيب ال tokens المرسلة من طرف ال scanner مع القواعد المحددة, الدالة الثانية هي yywrap() وتستدعى عند نفاذ المدخلات وفي حالتنا هذه عند نفاذ العمليات المراد حسابها. الدالة,main() ماذا بها أولا نقوم بفتح الملف input.txt -الذي سيحتوي على العمليات المراد حسابها- باستعمال fopen() التي تعيد إلينا مو شر للملف, نسند ذلك المو شر إلى المتغير yyin و هو متغير معرف مسبقا من طرف YACC و يمثل ملف المدخلات, و في حالت وجود خطا أثناء فتح الملف input.txt نعرض رسالة خطا و نتوقف. بعد ذلك نستدعي الدالة yyparse() والتي تمثل هنا الparser وتقوم بكل العمل الذي وصفناه سابقا. الا ن أحفظ ما آتبناه من وصف في المفكرة إلى الملف,D:\Lex_Yacc\exemples\expy2.y وبنفس الطريقة التي استعملنا بها LEX سنستعمل,BISON عوضا عن آتابة أوامر في نافذة الدوس أنشي ملف دفعي جديد باسم BISON_2.bat داخل المجلد D:\Lex_Yacc\exemples\ واآتب به ما يلي: BISON -d expy2.y Pause دوبل آليك على الملف الدفعي الجديد و ستحصل على هذه النتيجة: أيضا سيولد BISON ملفين و هما expy2.tab.c و,expy2.tab.h الملف expy2.tab.c هو الملف الذي به الدالة main() وبالتالي هو الملف الذي سنترجمه باستخدام.++C,TURBO أما الملف expy2.tab.h فهو يحتوي على تعريفات ال tokens من أجل استعماله داخل 18

19 الscanner و إذا آنت تذآر ففي ملف وصف السكانر expl2.l هناك هذا السطر لاستعمال ملف تعريفات ال :tokens % #include<stdlib.h> #include"d:\lex_yacc\exemples\expy2.h" % ولكن اسمه expy2.tab.h و ليس!! expy2.h ليست مشكلة, سنغير اسمه إلى expy2.h وانتهى الا مر. نفس الشيء بالنسبة لملف وصف البارسر expy2.y لدينا: % #include<conio.h> #include<stdio.h> #include<stdlib.h> #include<math.h> #include "d:\lex_yacc\exemples\expl2.c" % أيضا ملف السكانر الناتج عن LEX اسمه lex.yy.c وليس!!! expl2.c نفس الشيء, سنغير الا سماء فقط و لفعل هذا أضف ملف دفعي جديد باسم rename.bat وليكن محتواه : ren lex.yy.c expl2.c ren expy2.tab.c expy2.c ren expy2.tab.h expy2.h دوبل آليك على الملف الدفعي rename.bat لتتغير أسماء الملفات lex.yy.c و expy2.tab.c و expy2.tab.h إلى expl2.c و expy2.c و expy2.h على الترتيب. إذا و في آل مرة نغير من وصف الملف expl2.l أو expy2.y فا ننا نحذف ملفات الكود القديمة expl2.c) و expy2.c و (expy2.h و نعيد تنفيذ آل من FLEX_2.bat و BISON_2.bat و.rename.bat بعد حصولنا على آود سورس السكانر و البارسر نترجمهما باستعمال TURBO C 4.5 وتحديد باستعمال البرنامج D:\TC\BIN\TC.EXE وآي نتجنب فتح TC في آل فا ننا نفعل ذلك من سطر الا وامر, أنشي ملف دفعي جديد با سم compile.bat واآتب فيه هذا الا مر الذي يترجم الكود: D:\TC\BIN\TC.EXE D:\Lex_Yacc\exemples\expy2.c /b pause compile.bat و ستتم ترجمة الكود و ستحصل على ملف تنفيذي باسم وهو البرنامج النهاي ي و لكي نرى نتيجة عملنا أضف ملف جديد طبعا نحن لا زلنا نفذ الملف EXPY2.EXE 19

20 input.txt و سنبقى نعمل على مستوى المجلد -D:\Lex_Yacc\exemples المدخلات و لنضف اليه بعض العمليات التي نريد حسابها, مثلا: باسم ليحمل 5+5= 10*55= 3+2^2= -5+(11*8)-16= نفذ الا ن برنامجنا الجديد EXPY2.EXE و ستحصل على هذه النتيجة: لقد قام بحساب آل العمليات الموجودة في الملف,input.txt لا تعتقد أن هذا شيء لا أهمية له فهذه أول خطوة لبرمجة المترجم الخاص بنا, يجب أن تكون الرؤيا قد اتضحت الا ن عن آيف سنعمل منذ الا ن فصاعدا, لنكتب عملية خاطي ة -أو بالا حرى لا تتوافق مع القواعد المحددة- لنرى النتيجة, غير الملف input.txt ليصبح: 5+5= 10*55= 3+2^2= -5++(11*8)-16= أآيد لقد لاحظت أين الخطا, بعد تنفيذ EXPY2.EXE سنحصل على هذه النتيجة: 20

21 و تظهر نتيجة الخطا في السطر الرابع, لاحقا سنرى آيف نعرض رسالة بالخطا المحدد و رقم السطر الذي وقع فيه الخطا إن شاء االله. لتحميل المجلد الذي يحتوي على هذا المثال استخدم أحد هذه الروابط: exemples

22 3. برمجة المترجم من هنا نبدأ برمجة المترجم, أول ما يجب تحديده هو اللغة التي سنستخدمها, سنستخدم نفس النحو المستعمل لكتابة ال,Algorithmes وآمثال عن لغتنا: algorithme alg entier resultat,a debut ecrire "Entrer a = " lire a resultat<-5 a<-resultat*10 ecrire!,"a = ",a lire a fin. الرمز (!) نتفق أنه يعني سطر جديد, أي أآتب الجملة الموالية في سطر جديد, مبدي يا لغتنا الجديدة لا تحتوي على حلقات, فقط إسناد و آتابة و قراءة. سنسمي هذا المترجم compalg اختصارا ل,Compilateur d algorithmes هذه اللغة تحتاج إلى grammaire أو مجموعة القواعد التي تحددها و لنبدأ بهذا ال grammaire و سنغيره آلما أردنا إضافة قاعدة جديدة: prog -> ALGO IDENT declaration debut declaration -> decl_type ident POINT_VER declaration decl_type -> DEC_ENTIER DEC_REEL DEC_CARA DEC_CHAINE ident -> IDENT IDENT VER ident debut -> DEBUT command_seq command_seq -> command_seq FIN POINT affect POINT_VER command_seq READ read POINT_VER command_seq WRITE write POINT_VER command_seq Affect -> IDENT AFFECT fexpr IDENT AFFECT sexpr read -> IDENT IDENT VER read write -> writed_expr writed_expr VER write writed_expr -> NEW_LINE fexpr sexpr fexpr -> REEL ENTIER IDENT fexpr PLUS fexpr fexpr MOIN fexpr fexpr MULT fexpr 22

23 fexpr DIVS fexpr MOIN fexpr fexpr PUIS fexpr PARG fexpr PARD sexpr -> CHAINE CARA تذآر أن الرمز ( ) يعني اللاشيء, الرموز بالحروف الكبيرة هي ال tokens التي يرسلها البارسر أو L analyseur lexicale لذلك هي رموز نهاي ية( terminaux.(symboles عد إلى المجلد D:\Lex_Yacc\exemples واحذف منه الملفات التي استخدمناها في المثال السابق و لنبدأ على برآة االله, افتح المفكرة و نبدأ آتابة الكود الذي يمثل وصف السكانر: % #include<stdlib.h> #include<string.h> #include<math.h> #include"d:\lex_yacc\exemples\compalg.h" int line=1 % سنحتاج آل من تلك المكاتب, الملف compalg.h هو الذي سيولده BISON فيما بعد و الذي يحوي التصريح عن ال tokens اللازمة, المتغير line يمثل السطر الحالي الذي نحن بصدد تحليله و استخراج ال tokens منه و سنزيد من قيمتخ عند نهاية آل سطر و هذا لنعرف موقعنا إذا صادفنا خطا ما, واضح. لنعرف الا ن القوالب اللازمة لاستخراج ال tokens من الكودسورس: blanc [ \t]+ nbr [0-9]+ entier nbr reel entier\.nbr ident [a-za-z_]([0-9a-za-z_])* a [aa] b [bb] c [cc] d [dd] e [ee] f [ff] g [gg] h [hh] i [ii] j [jj] k [kk] 23

24 l [ll] m [mm] n [nn] o [oo] p [pp] q [qq] r [rr] s [ss] t [tt] u [uu] v [vv] w [ww] x [xx] y [yy] z [zz] أعتقد أن القوالب السابقة تشرح نفسها, مثلا nbr يمثل آل الا عداد من 1 إلى 9 مرة واحدة على الا قل أو أآثر, أي أنه مثلا تنتمي إلى ذلك القالب. القالب entier هو نفسه,nbr أما القالب reel فيختلف قليلا, إذ أنه عبارة عن nbr.nbr مثلا و غيرها من الا عداد الحقيقية التي تندرج تحت هذا القالب. القالب ident الذي يمثل المتغيرات مثل x أو 10_y- فتكون بدايته عبارة عن أحد الحروف التي تنتمي إلى المجال[ a-z ] أو [A-Z] أو الحرف (-) و هذا حسب [a-za-z_], ثم تليه مجموعة أخرى من الحروف التي تكون ضمن [a-z] أو [A-Z] أو [0-9] أو (_), النصف الثاني من المتغير يمكن أن يكون أو لا يكون و حددنا هذا ب.([0-9a-zA-Z_])* أما بقية القوالب من a إلى z فقد استعملناها فقط حتى تكون الحروف الكبيرة في لغتنا مثلها مثل الحروف الصغيرة, تماما آلغة باسكال التي لا تفرق بين الحروف الكبيرة و الصغيرة, مثلا القالب a يمكن أن يكون a أو A. لننتقل إلى الجزء الثاني و هو تعريف القواعد التي من الشكل إذا وجدت... إفعل... %% "\""."\"" return(cara) "\""(.)+"\"" return(chaine) algorithme return(algo) debut return(debut) fin return(fin) entier return(dec_entier) reel return(dec_reel) caractere return(dec_cara) chaine return(dec_chaine) lire return(read) ecrire return(write) 24

25 "!" return(new_line) \. return(point) return(point_ver), return(ver) \n line++ "<-" return(affect) "(" return(parg) ")" return(pard) "+" return(plus) "-" return(moin) "*" return(mult) "/" return(divs) "^" return(puis) ident return(ident) reel return(reel) entier return(entier) blanc %% لن أشرحها لبساطتها, الا ن أنهينا وصف السكانر, خزن الملف الجديد باسم lcompalg.l طبعا و داي ما داخل المجلد,D:\Lex_Yacc\exemples و أيضا أضف ملفا دفعيا جديدا باسم FLEX_2.bat و اآتب به الا مر : FLEX lcompalg.l lex.yy.c دوبل آليك على FLEX_2.bat تحصل على الملف آنتيجة. لننتقل إلى بناء النصف الثاني من البرنامج وهو البارسر أو,L analyseur syntaxique المفكرة و أآتب : افتح % #include<conio.h> #include<math.h> #include "d:\lex_yacc\exemples\lcompalg.c" int errors=0 % آالمعتاد, سنحتاج إلى دوال من تلك المكاتب أما بالنسبة للملف lcompalg.c فهو نفسه الملف lex.yy.c سنغير تسميته لاحقا-, سنستعمل المتغير errors لحساب عدد الا خطاء الموجودة في الملف الذي يحوي ال,Algorithm بعد ذلك نضيف مزيدا من التعريفات: %token IDENT 25

26 %token ENTIER %token REEL %token CHAINE %token CARA %token ALGO DEBUT FIN POINT POINT_VER VER %token DEC_ENTIER DEC_REEL DEC_CARA DEC_CHAINE %token AFFECT READ WRITE REEL PARG PARD %token PLUS MOIN MULT DIVS PUIS NEW_LINE %left PLUS MOIN %left MULT DIVS %right PUIS %left NEG %start prog في التسع سطور الا ولى قمنا بالتصريح عن ال tokens اللازمة, في الا ربع سطور التالية عرفنا أولوية آل عملية حسابية, السطر الا خير فيه القاعدة التي تمثل نقطة الانطلاق, يا للوضوح... الخطوة التالية هي التصريح عن القواعد المتبعة في هذه اللغة: %% prog:algo IDENT declaration debut declaration: decl_type ident POINT_VER declaration decl_type:dec_entier DEC_REEL DEC_CARA DEC_CHAINE ident:ident IDENT VER ident debut:debut command_seq command_seq: command_seq FIN POINT affect POINT_VER command_seq READ read POINT_VER command_seq WRITE write POINT_VER command_seq affect: IDENT AFFECT fexpr 26

27 IDENT AFFECT sexpr read:ident IDENT VER read write:writed_expr writed_expr VER write writed_expr:new_line fexpr sexpr fexpr:reel ENTIER IDENT fexpr PLUS fexpr fexpr MOIN fexpr fexpr MULT fexpr fexpr DIVS fexpr MOIN fexpr %prec NEG fexpr PUIS fexpr PARG fexpr PARD sexpr:chaine CARA %% نحن نحقق تقدما سريعا هنا, الكود السابق هو نفسه ال grammaire الذي اتفقنا على استعماله سابقا إلا أن شكله تغير قليلا, لا تلمني لكن ألق اللوم على BISON لا نه هو من يريد هذا الشكل لل. grammaire لم نستعمل Les actions sémantiques وهذا لا ننا حاليا نحن بصدد إنجاز السكانر و البارسر فقط أو L analyseur lexicale و L analyseur syntaxique فقط, لكل أوانه. القطعة الباقية من الكود اللازم هي التصريح عن الدالة الري يسية و غيرها في الشطر الثالث من ملف وصف البارسر, أضف هذا الكود إلى المفكرة: int yyerror (char *s) errors++ 27

28 printf("erreur :syntaxe erreur: ligne %d\n",line) int yywrap()return 1 main(int argc,char *argv[]) clrscr() if((yyin=fopen("d:\\lex_yacc\\exemples\\test.alg","r"))==null) printf("test.alg not found!\n") getch() return yyparse() if(!errors) printf("ok") getch() return ما الجديد عن المثال السابق عند وقوع خطا ما يقوم البارسر باستدعاء الدالة yyerror() وهنا نعرض نحن رسالة الخطا, السطر الذي وقع فيه الخطا هو ذو الرقم line وهذا المتغير معرف في الملف lcompalg.c و قد صرحنا عليه في,lcompalg.l و عند وقوع آل خطا نزيد من قيمة المتغير.errors الدالة yywrap() تبقى آما هي, أما الدالة main() فنقوم فيها بفتح الملف test.alg الذي يحوي ال Algorithme الذي نريد ترجمته, وبعد تحليل الملف سنعرض الرسالة Ok إذا آانت قيمة المتغير errors مساوية للصفر. الا ن خزن الكود السابق في ملف باسم compalg.y BISON_2.bat و أآتب فيه هذا الا مر: و أضف ملفا دفعيا جديدا باسم BISON -d compalg.y نفذ الملف BISON_2.bat لتحصل على ملفين اثنين, compalg.tab.c و,compalg.tab.h قبل أن نترجم الكود المولد من طرف LEX و BISON سنغير أسماء الملفات lex.yy.c و compalg.tab.c و compalg.tab.h إلى lcompalg.c و compalg.c و compalg.h على الترتيب لا تسا ل لماذا, فقط تروق لي الا سماء الجديدة وهذا باستعمال هذه الا وامر: ren lex.yy.c lcompalg.c ren compalg.tab.c compalg.c ren compalg.tab.h compalg.h 28

29 الا وامر السابقة هي أوامر DOS وعندما نريد تنفيذها لن نفتح موجه أوامر دوس و ننفذها فقط نضيف ملف دفعي باسم rename.bat و نكتب فيه الا وامر السابقة, دوبل آليك عليه و انتهى الا مر. نفس الشيء بالنسبة لعملية ترجمة الكود النهاي ي, أضف ملف دفعي باسم compile.bat و اآتب فيه هذا الا مر: D:\TC\BIN\TC.EXE D:\Lex_Yacc\exemples\compalg.c /b pause لقد قمنا بترجمة آود C باستعمال سطر الا وامر فا نا أآره فتح ++C TURBO و ترجمة الكود بتلك الطريقة, دوبل آليك على compile.bat وانتهى الا مر. إذن, بعد تنفيذ الملف compile.bat سنحصل على البرنامج النهاي ي وهو,COMPALG.EXE و أثناء آتابة وصف البارسر قمنا باستعمال الملف test.alg آمدخلات للمترجم عن طريق هذا السطر: // if((yyin=fopen("d:\\lex_yacc\\exemples\\test.alg","r"))==null) // ذلك و قبل تنفيذ المترجم, أنشي ملف باسم test.alg و اآتب فيه نص ال Algorithme الذي نحن بصدد ترجمته, وهذا هو الكود: algorithme alg entier resultat,a debut ecrire "Entrer a = " lire a resultat<-5 a<-resultat*10 ecrire!,"a = ",a lire a fin. بعد ذلك نفذ برنامج المترجم COMPALG.EXE حتى يتفحص المترجم, هذه هي نتيجة التنفيذ: 29

30 لقد قام المترجم بتفحص الكود و وجد أنه مطابق للقواعد المحدد أثناء وصف البارسر و لذلك عرض رسالة,(Ok) لنجرب آتابة Algorithme خاطي, مثلا غير السطر الخامس ليصبح : algorithme alg entier resultat,a debut ecrire "Entrer a = " lire a, resultat<-5 a<-resultat*10 ecrire!,"a = ",a lire a fin. هناك فاصلة إضافية, النتيجة: و بما أن هذا لا ينطبق مع قواعد اللغة التي حددناها سابقا ستكون...!!! لقد اآتشف الخطا!!! والسطر الذي وقع فيه الخطا عجيب (وآا ننا نعتمد على الحظ هنا). من المو آد أنه قد تكونت لديك فكرة واضحة جدا عن مبدأ عمل L analyseur lexicale.(scanner & Parser) L analyseur syntaxique و 30

31 ننتقل الا ن إلى المرحلة التالية, ألا وهي برمجة L analyseur sémantique أو عملية التحليل المعنوي, نغير ال Algorithme المراد ترجمته - محتوى الملف -test.alg إلى : algorithme alg entier resultat,a reel r caractere c chaine s, r debut ecrire "Entrer a = " lire a lire r c<-"a" s<-"chaine s" c<-s c<-"hhhh" resultat<-5 a<-resultat*10 ecrire!,"a = ",a a<-r a<-0.5 x<-150 lire a fin. أضفنا بعض التصريحات و التعليمات, طبعا لا معنى لها فنحن فقط نجر و لسنا نكتب في برنامج ذو هدف, أضفنا المتغير الحقيقي r والمتغير c من نوع حرف, أما المتغير s فهو سلسلة حرفية, ما رأيك هل يوجد أخطاء في باقي الكود أجل هناك أخطاء معنوية sémantiques),(des erreurs مثلا في السطر 5 المتغير r معرف مسبقا عل أنه reel و في السطر 12 و 13 لا يمكننا إسناد سلسلة حرفية إلى متغير من نوع,caractere أيضا في السطر 16 و 17 لا يمكننا وضع قسمة حقيقية في متغير صحيح, وفي السطر 18 إذ قمنا با سناد قيمة للمتغير x مع أننا لم نصرح عنه من قبل, لكن, إلى حد الا ن المترجم لا يستطيع الكشف عن هذه الا خطاء, خزن الملف test.alg و شغل البرنامج.L analyseur sémantique و سيقول لك: لا يوجد أخطاء, هنا يا تي دور COMPALG.EXE هنا يجب علينا بناء la table des symboles أو جدول الرموز, سنخزن فيها آل المتغيرات و أنواعها, قيمها لن تهمنا, أضف ملف جديد باسم SYMB_TAB.H داخل المجلد D:\Lex_Yacc\exemples و افتحه و لنبدأ بكتابة الكود اللازم. 31

32 هل تذآر المتغير yylval من المثال الا ول لكيفية استعمال LEX و YACC لقد قلنا عنه أنه حلقة وصل بين LEX و YACC إذ أن LEX إذا وجد مثلا رقما صحيحا فا ننا نستطيع تمرير قيمة ذلك المتغير لل YACC مع ال,token نحن هنا سنحتاج إلى تمرير السلسلة الحرفية التي تمثل المتغير حتى نتمكن من تخزينها في قاي مة المتغيرات و التعامل معها, حاليا LEX و حسب الوصف الذي آتبناه و تحديدا في هذا السطر : ident return(ident) token yylval لا يمرر لل YACC إلا ال طريق المتغير المحجوز نوعه. التي تمثل المتغير و هي,IDENT سنمرر المتغير نفسه عن و لكن نوعه int وليس char[]! لا يهم, بامكاننا التحكم في لن نغير نوع yylval من int إلى char أو غيره فنحن سنمرر لل YACC عدة أنواع, الحل هو في استخدام,union أآيد أنت تعرفها, و إذا لم تكن تعرفها فهي شبيهة بال struct ولكن الفرق يكمن في أن مكونات ال union تشغل نفس المساحة من الذاآرة, مثلا لاحظ هذه ال :union typedef union char Tstr[128] int Tint float Tfloat new_type new_type t إذا قمنا باسناد قيمة ل t.tstr ثم بعد ذلك أسندنا قيمة ل t.tint فا ن قيمة t.tstr ستضيع لا ن المتغيرات الثلاث يتشارآون في الذاآرة المحجوزة لهم وهي الذاآرة اللازمة لتخزين أآبر متغير و هنا هي مساوية ل 128 بايت. آيف نجعل yylval ينتمي إلى ذلك النوع افتح الملف compalg.y و أضف إليه هذا المقطع في المكان المبين: % #include<conio.h> #include<math.h> #include "d:\lex_yacc\exemples\lcompalg.c" % %union char Tstr[128] int Tint float Tfloat %token IDENT // طبعا الجزء المضلل هو الجديد في الكود, أغلق الملف و أحفظه طبعا. 32

33 وبهذا نكون قد غيرنا نوع yylval إلى النوع الذي نحتاجه, بقي لنا أن نمرر اسم المتغير إلى :lcompalg.l آلما وجدناه وهذا على مستوى الملف YACC "^" return(puis) ident strcpy(yylval.tstr,yytext) return(ident) reel return(reel) إذن و قبل أن نعيد IDENT على شكل token إلى YACC قمنا بتمرير قيمة المتغير إلى YACC و هذا بنسخها في,yylval.Tstr طبعا قلنا سابقا أن قيمة آل تطابق نجدها في المتغير المحجوز,yytext أحفظ و أغلق lcompalg.l ولننتقل إلى الخطوة الموالية. سنبدأ بمعالجة الخطا المعنوي الا ول و هو تكرار التصريح عن المتغيرات آما حدث مع المتغير r في المثال السابق, افتح الملف SYMB_TAB.H و لنبدأ با ضافة هذا الكود: #include<stdlib.h> #include<stdio.h> #include<string.h> typedef struct sym_node_ char name[56] struct sym_node *next sym_node sym_node *sym_table=null عرفنا الترآيبة sym_node المتكونة من اسم المتغير و مو شر لترآيبة من نفس النوع, و هنا أردنا إنشاء قاي مة ديناميكية من المتغيرات, حاليا يهمنا فقط اسم المتغير, بعد ذلك صرحنا عن sym_table وهي القاي مة التي تمثل جدول المتغيرات هنا و هي مو شر لترآيبة من نوع,sym_node طبعا هذا من أساسيات البرمجة بلغة C ولو آنت تجهل ماذا يعني ذلك الكود لما آنت تقرأ في هذا الكتاب. لنكمل, سنضيف دالتين, الا ولى put_sym والتي تثبت متغير جديد في القاي مة, أما الثانية get_sym ومن اسمها نستنتج أنها ستعيد إما مو شر للترآيبة التي تحوي المتغير المحدد على شكل بارامتر أو ستعيد NULL إذا آان المتغير غير مثبت من قبل: 33

34 sym_node *put_sym(char *sym_name) sym_node *ptr ptr=(sym_node*)malloc(sizeof(sym_node)) strcpy(ptr->name,sym_name) ptr->next=(sym_node*)sym_table sym_table=ptr return ptr sym_node *get_sym(char *sym_name) sym_node *ptr for(ptr=sym_tableptr!=nullptr=(sym_node*)ptr->next) if(!strcmp(ptr->name,sym_name))return ptr return NULL آود واضح, آيف نستعمله أغلق و أحفظ تغيرات الملف SYMB_TAB.H البارسر,compalg.y افتحه ولنبدأ با ضافة بعض الا آواد: ولنعد إلى ملف وصف % #include<conio.h> #include<math.h> #include "d:\lex_yacc\exemples\lcompalg.c" #include "d:\lex_yacc\exemples\symb_tab.h" int errors=0 void setup_sym(char* sym_name) sym_node *sym sym=get_sym(sym_name) if(sym==null) put_sym(sym_name) else errors++ printf("erreur: %s est deja definie : ligne %d.\n",sym_name,line) int sym_check(char* sym_name) if(get_sym(sym_name)==null) errors++ 34

35 printf("erreur: %s est inconnu : ligne %d.\n",sym_name,line) return 0 return 1 % // بسيطة, الدالة setup_sym تقوم بتثبيت متغير داخل جدول المتغيرات و هذا باستعمال الدوال المعرفة داخل الملف,d:\lex_yacc\exemples\SYMB_TAB.H قبل أن نضيف متغيرا جديدا يجب أن نتا آد من أنه لم يضاف من قبل بواسطة الدالة,get_sym إذا أعادة الدالة get_sym قيمة غير NULL فا ننا نعرض رسالة خطا تفيد أن المتغير معرف من قبل و في أي سطر وقع الخطا, المتغير line عرفناه من قبل داخل الملف lcompalg.l الذي يحمل وصف السكانر و بالتالي هو معرف في الملف lcompalg.c المولد من طرف,LEX أما إذا أعادت الدالة get_sym القيمة NULL فا ننا نثبت المتغير الجديد والسلام. أما الدالة sym_check فنستدعيها لنتا آد أن المتغير المعطى لها على شكل بارامتر مثبت مسبقا في قاي مة المتغيرات, و هذا لتجنب استعمال متغيرات غير مصرح بها من قبل, إذا لم يكن المتغير مثبتا من قبل فا ننا نعرض رسالة خطا. الا ن سنرى أين نستدعي الدوال, الا ضافات على الملف :compalg.y نستدعيها آلما وجدنا متغيرا أثناء تحليل الكود, لاحظ هذه %token <Tstr> IDENT $x,tstr حددنا نوع القيمة التي ستا تي مع ال token الخاص بالمتغيرات,IDENT الموافقة لل token عبارة عن سلسلة حرفية, لنواصل: وهي أي أنه declaration: decl_type ident POINT_VER declaration ident:ident setup_sym($1) IDENT VER ident setup_sym($1) آما ترون فا ن القاعدة <- declaration هي التي نحدد بها شكل التصريح عن المتغيرات, ولدينا ident تعطينا إما متغير أو متغير متبوع بفاصلة للتصريح عن المتغير, هناك يجب أن 35

36 نستدعي الدالة setup_sym() التي تقوم بتثبيت المتغير في جدول المتغيرات و في حالة تكرار التصريح عن نفس المتغير ستعرض خطا, إسم المتغير القادم من LEX سيكون محفوظ في yylval.tstr بالنسبة لل LEX و في $1 بالنسبة لل.BISON يبقى الا ن التحقق من المتغيرات قبل إسناد قيم لها أو استعمالها حتى, إذا و في آل قاعدة نجد فيها ال token الخاصة بالمتغير (IDENT) نقوم باستدعاء الدالة sym_check() للتحقق من المتغير, لاحظ أين يتم هذا: affect:ident AFFECT fexpr sym_check($1) IDENT AFFECT sexpr sym_check($1) read:ident sym_check($1) IDENT VER read sym_check($1) fexpr:reel ENTIER IDENT sym_check($1) fexpr PLUS fexpr fexpr MOIN fexpr fexpr MULT fexpr fexpr DIVS fexpr MOIN fexpr %prec NEG fexpr PUIS fexpr PARG fexpr PARD sym_check الا مر واضح, أضفنا des actions sémantiques اسم المتغير على شكل بارامتر. نستدعي خلالها الدالة با عطاي ها خزن محتوى الملف compalg.y لنرى نتيجة عملنا, احذف الملفات القديمة compalg.c) و compalg.h و (lcompalg.c و قم بتوليد آود المترجم الجديد و هذا بتشغيل الملفات الدفعية BISON_2.bat ثم FLEX_2.bat ثم rename.bat ثم compile.bat لنتحصل على البرنامج COMPALG.EXE النهاي ي, سنسمي هذه العملية بعملية توليد المترجم. 36

37 شغل المترجم COMPALG.EXE ليحلل و يكتشف الا خطاء الموجودة على مستوى الملف test.alg و هذه صورة لراسلة الا خطاء: أجل, لقد اآتشف الخطا ين الواردين في ال Algorithme المتغيرات و استعمال متغيرات لم يتم التصريح عنها من قبل المتعلقين بتكرار التصريح عن بقي لنا أن نكشف عن بقية الا خطاء وهي إسناد قيمة حقيقية لمتغير صحيح أو إسناد سلسلة حرفية لمتغير من نوع,char أآيد هناك المزيد من الا خطاء المعنوية و لكن سنكتفي فقط بما سبق ذآره. بما أن نوع المتغيرات يهمنا من الا ن فصاعدا فا ننا سنغير من بنية جدول المتغيرات, SYMB_TAB.H وغير الترآيبة التي تمثل المتغير إلى: إفتح الملف #include<stdlib.h> #include<stdio.h> #include<string.h> #define _int 1 #define _float 2 #define _str 3 #define _chr 4 typedef struct sym_node_ char name[56] int type struct sym_node *next sym_node حددنا أربع ثوابت int_ و float_ و str_ و chr_ تمثل آل من النوع الصحيح و الحقيقي و سلاسل الحروف و الحروف الوحيدة على التوالي, آما قمنا با ضافة حقل ا خر للترآيبة التي تحمل معلومات المتغير و هو type و الذي يمثل نوع المتغير. 37

38 سنغير أيضا في الدالة put_sym التي تثبت المتغير في الجدول لتصبح: sym_node *put_sym(char *sym_name, int sym_type) sym_node *ptr ptr=(sym_node*)malloc(sizeof(sym_node)) strcpy(ptr->name,sym_name) ptr->type=sym_type ptr->next=(sym_node*)sym_table sym_table=ptr return ptr واضح ما قمنا به من تغييرات, سنخزن نوع المتغير إضافة إلى اسمه من الا ن فصاعدا, سنضيف أيضا دالة جديدة تعيد لنا نوع المتغير المحدد و هي: int get_sym_type(char *sym_name) sym_node *ptr for(ptr=sym_tableptr!=nullptr=(sym_node*)ptr->next) if(!strcmp(ptr->name,sym_name)) return ptr->type return 0 خزن و أغلق الملف SYMB_TAB.H و لننتقل إلى الملف.compalg.y بما أننا غيرنا في الدالة put_sym الموجودة في الملف SYMB_TAB.H إذ أضفنا إليها نوع المتغير فا نه يجب التغيير في الدالة setup_sym الموجودة في compalg.y لتصبح: void setup_sym(char* sym_name, int type) sym_node *sym sym=get_sym(sym_name) if(sym==null) put_sym(sym_name, type) else errors++printf("erreur: %s est deja definie : ligne %d.\n",sym_name,line) 38

39 عند التصريح عن متغير جديد يجب أن نخزن نوعه إضافة إلى اسمه حتى نتمكن لاحقا من التحقق من توافق الا نواع أثنا إجراء عمليات الا سناد, سنضيف متغير جديد current_type نخزن فيه مو قتا نوع ا خر تصريح عن المتغيرات: int errors=0 int current_type ولنغير في آل الا ستدعاءات للدالة :setup_sym declaration: decl_type ident POINT_VER declaration ident:ident setup_sym($1, current_type) IDENT VER ident setup_sym($1, current_type) إذا أصبحا نخزن نوع المتغير مع اسمه, لكن يجب علينا تحديث قيمة current_type مرة يتم التصريح عن نوع جديد, هذا يتم على مستوى هذه القاعدة: في آل decl_type:dec_entier DEC_REEL DEC_CARA DEC_CHAINE current_type = _int current_type = _float current_type = _chr current_type = _str بعد هذا نستطيع التا آد من الا نواع أثناء القيام التي تحدد النحو الخاص بالا سناد: بالا سناد و هذا يتم على مستوى هذه القاعدة affect:ident AFFECT fexpr IDENT AFFECT sexpr fexpr:reel ENTIER IDENT fexpr PLUS fexpr fexpr MOIN fexpr 39

40 fexpr MULT fexpr fexpr DIVS fexpr MOIN fexpr %prec NEG fexpr PUIS fexpr PARG fexpr PARD sexpr:chaine CARA affect : IDENT AFFECT fexpr نحن لم نغير أي شيء في الكود السابق, لنا خذ مثلا هذه القاعدة: آيف نتحقق أثناء إسناد fexpr إلى IDENT يجب التحقق من أن نوع fexpr متوافق مع نوع IDENT وإلا نعرض رسالة خطا, IDENT هو متغير و لذلك نستطيع الحصول على نوعه من جدول المتغيرات باستعمال الدالة,get_sym_type أما بالنسبة إلى نوع fexpr فيجب علينا الحصول عليه من القاعدة التالية: fexpr : REEL ENTIER IDENT في الحالة الا ولى, أي عند fexpr <- reel نرجع النوع float_ إلى,fexpr في الحالة الثانية نرجع int_ إلى fexpr و في الحالة الثالثة نرجع إلى fexpr نفس نوع المتغير المرفق مع int قيمة النوع إذا نوعها يجب أن يكون fexpr و هكذا نكمل مع بقية القواعد.. وبما أن IDENT و آذلك نفس الشيء بالنسبة ل sexpr و نحدد ذلك بهذه الا ضافة إلى الكود: %union char Tstr[128] int Tint float Tfloat %type <Tint> fexpr %type <Tint> sexpr %token <Tstr> IDENT 40

41 sexpr إذا أول ما نفعله الا ن هو تحديد نوع fexpr آل من قواعدهما: و وهذا با ضافة هذا الكود المفهوم جدا إلى writed_expr:new_line /*لن نفعل شيي ا هنا*/ fexpr /* لن نفعل شيي ا هنا*/ sexpr fexpr:reel $$=_float ENTIER $$=_int IDENT if(sym_check($1)) $$ = get_sym_type($1) fexpr PLUS fexpr if(($1 == _int) && ($3 == _int)) $$ = _int else $$ = _float fexpr MOIN fexpr if(($1 == _int) && ($3 == _int)) $$ = _int else $$ = _float fexpr MULT fexpr if(($1 == _int) && ($3 == _int)) $$ = _int else $$ = _float fexpr DIVS fexpr $$ = _float MOIN fexpr %prec NEG $$=$2 fexpr PUIS fexpr $$=$1 PARG fexpr PARD $$=$2 sexpr:chaine $$=_str CARA $$=_chr $$=_float : fexpr float_ في القاعدة fexpr -> REEL أعدن القيمة إلى باستخدام الكود 41

42 في القاعدة fexpr <- IDENT أعدا نفس نوع المتغير IDENT بعد التا طد من أنه مثبت مسبقا في جدول المتغيرات إلى :fexpr if(sym_check($1)) $$ = get_sym_type($1) fexpr _int في القاعدة fexpr -> fexpr PLUS fexpr على اليمين من النوع :_int فا ننا نعيد النوع إذا آان آل من اللذان if(($1 == _int) && ($3 == _int)) $$ = _int else $$ = _float sexpr وهكذا نكمل باقي القواعد, الا ن استطعنا الحصول على آل من نوع fexpr لاستخدامهما في القاعدة المسو ولة عن تصريح المتغيرات, لنفعل ذلك: و affect:ident AFFECT fexpr if(sym_check($1)) int sym_type = get_sym_type($1) if((sym_type==_int) && ($3==_float)) printf("erreur:imposible de converter (reel a entier) : ligne %d.\n",line) errors++ else if((sym_type==_str) && ($3==_float)) printf("erreur:imposible de converter (reel a chaine) : ligne %d.\n",line) errors++ else if((sym_type==_chr) && ($3==_float)) printf("erreur:imposible de converter (reel a caractere) : ligne %d.\n",line) errors++ else if((sym_type==_chr) && ($3==_str)) printf("erreur:imposible de converter (chaine a caractere) : ligne %d.\n",line) errors++ 42

43 IDENT AFFECT sexpr if(sym_check($1)) int sym_type = get_sym_type($1) if((sym_type==_chr) && ($3==_str)) printf("erreur:imposible de converter (chaine a caractere) : ligne %d.\n",line) errors++ else if((sym_type==_int) && ($3==_str)) printf("erreur:imposible de converter (chaine a entier) : ligne %d.\n",line) errors++ else if((sym_type==_float) && ($3==_str)) printf("erreur:imposible de converter (chaine a reel) : ligne %d.\n",line) errors++ مثلا, في القاعدة affect <- IDENT AFFECT fexpr تحققنا أولا من وجود المتغير IDENT باستخدام,(sym_check($1 إذا آان موجودا نصرح عن متغير جديد باسم sym_type و نخزن فيه نوع المتغير IDENT باستخدام الدالة get_sym_type و بعد ذلك نبدأ عميلية التحقق من توافق نوع IDENT و fexpr,و آمثال إذا آان نوع IDENT هو _int و نوع fexpr هو _float فا ننا نعرض رسالة خطا تقول (لا يمكن التحويل من حقيقي إلى صحيح) و هكذا البقية. 43

44 أعد الا ن توليد المترجم آما تعلمت سابقا و نفذ برنامج المترجم الجديد COMPALG.EXE لتحصل على هذه النتيجة: لقد تمكننا الا ن من الكشف عن بقية الا خطاء المعنوية و هذا يكفي الا ن بالنسبة لمرحلة التحليل المعنوي أو,L analyse sémantique المرحلة التالية هي توليد الكود ) du Génération.(code 44

45 توليد الكود, هي عملية صعبة نوعا ما مقارنة مع ما سبقها, سنحاول هنا أن نولد آود assembleur فقط وهو الا قرب إلى لغة الا لة و أيضا سنعتمد طريقة بسيطة في توليد الكود و لن يكون هناك (édition de liens) linking لا ننا لن نستورد أي دوال من أي مكاتب. سنتعامل مع ال Assembleur 16 bit فقط, لن نحتاج إلى Assembleur 32 bit و هذا لا ننا نولد الكود النهاي ي هنا و سنحاول فيه أن نعتمد فقط على المقاطعات interruptions) (les و لن نتعامل مع الدوال الجاهزة أو les appels système إذ أن الكود يجب أن يكون على أبسط شكل و أقرب شكل إلى لغة الا لة, هذا مثال لكود assembleur يقوم بطباعة الجملة hello world على الشاشة:.MODEL small.stack 100h.data.code start: msg mov mov db " Hello, World!",13,10,"$" ds,ax mov dx,offset msg mov ah,9 int 21h المقاطعة التي ستعرض محتوى العنوان الموجود في دي اآس على الشاشة mov ax,0c07h int 21h الانتظار إلى أن يتم ضغط مفتاح من لوحة المفاتيح mov int end start ax, 4C00h 21h إذا أردت ترجمته استعمل أي Assembleur آ WinAsm Studio أن تكون على إطلاع و لو قليل بلغة التجميع مثلي. مثلا, لتفهم بقية الكتاب يجب 45

46 أنشي ملف جديد باسم CODE_GEN.H المولد في ملف من نوع :*.asm لنكتب فيه بعض الدوال التي تمكننا من آتابة الكود #include<stdio.h> قسم التصريحات// data_section[1024] char قسم الكود// code_section[8192] char FILE *fcode مقبض للملف الذي سيحمل الكود الناتج// دالة تمكننا من إنشاء ملف جديد ليكون // *file) void Init_Code(char بمثابة نتيجة لترجمة الا لغوريتم fcode = fopen(file, "wb") strcpy(data_section, "") strcpy(code_section, "") إضافة تصريح// *data) void Add_Data(char strcat(data_section, data) إضافة تعليمة// *code) void Add_Code(char strcat(code_section, code) تقوم با غلاق الملف وإتمام العملية حين ننهي توليد // Dispose_Code() void الكود fprintf(fcode, ".MODEL small\r\n.stack 100h\r\n.DATA\r\n") fprintf(fcode, "%s", data_section) fprintf(fcode, ".CODE\r\nstart:\r\n") fprintf(fcode, "mov ax,@data\r\n") fprintf(fcode, "mov ds,ax\r\n") fprintf(fcode, "%s", code_section) fprintf(fcode, "end start\r\n") fclose(fcode) أغلق الملف CODE_GEN.H مع حفظ التغييرات. 46

47 إذا إفتح الملف compalg.y و لنبدأ بهذا التغيير بما أننا سنستعمل دوال الملف :CODE_GEN.H #include "d:\lex_yacc\exemples\symb_tab.h" #include "d:\lex_yacc\exemples\code_gen.h" يجب علينا تهيي ة الملف الذي سنكتب فيه الكود المولد و هذا على مستوى الدالة الري يسية: main(int argc,char *argv[]) clrscr() if((yyin=fopen("d:\\lex_yacc\\exemples\\test.alg","r"))==null) printf("test.alg not found!\n") getch() return Init_Code("d:\\lex_yacc\\exemples\\test.asm") yyparse() Dispose_Code() if(!errors) printf("ok") getch() return ا ه, تذآرت, الملف test.alg آنا قد آتبنا فيه أآواد خاطي ة معنويا أثناء برمجة المحلل المعنوي, عد إلى الملف test.alg و أآتب فيه هذا الكود الصحيح ليكون فا ر التجربة: algorithme alg entier resultat,a reel r caractere car chaine s debut ecrire "Entrer a = " lire a lire r lire s s<-s s<-" " ecrire "c" 47

48 car<-"a" resultat<-5 a<-resultat*10+5 ecrire!,"a = ",a lire a fin. الا ن, أعد توليد المترجم COMPALG.EXE و شغله ليقوم بترجمة test.alg و ستلاحظ أنه سيولد لنا الملف الجديد TEST.ASM الذي يحمل آود التجميع, و بما أن آل ما ولدناه إلى الا ن هو رأس الكود فسيكون محتواه آالا تي:.MODEL small.stack 100h.DATA.CODE start: mov ax,@data mov ds,ax end start الا ن اتضحت لك الفكرة ماي ة في الماي ة, لنواصل توليد بقية الكود. في حالة التصريح عن المتغيرات فا ن ذلك يندرج تحت القاعدة التالية: ident:ident IDENT VER ident setup_sym($1, current_type) setup_sym($1, current_type) بدأنا نقترب من إآمال هذه المرحلة, طبعا لا, مازلنا بعيدين آل البعد و لكن الفكرة تتضح أآثر فا آثر و لهذا أنهي هذا الكتاب هنا و لتكمل البقية بنفسك...أمزح فقط(أردت الهروب قبل أن تزداد المسا لة صعوبة..), لا يهم, لنكمل. التصريح عن المتغيرات, بما أنني مبتدأ جدا في البرمجة بلغة التجميع فسا تعامل مع النوع الحقيقي على أنه صحيح أما سلاسل الحروف و الحروف فسهل التعامل معها, لزيادة الفهم لاحظ هذا التصريح وإلى ماذا سنحوله: entier a reel r caractere car chaine s a dw 6 dup(?) r dw 6 dup(?) car db? s db 56 dup( ) 48

49 قد لا يكون ذلك التصريح المثالي بالنسبة للغة التجميع و لكن تلك حدودي حاليا, تستطيع فعل ما هو أفضل من ذلك فافعل, نتجه الا ن إلى compalg.y لنفعل ذلك: إذا آنت ident:ident setup_sym($1, current_type) if((current_type == _int) (current_type == _float)) Add_Data($1) Add_Data("\tdw\t6 dup(?)\r\n") else if(current_type == _chr) Add_Data($1) Add_Data("\tdb\t?\r\n") else if(current_type == _str) Add_Data($1) Add_Data("\tdb\t56 dup( )\r\n") IDENT VER ident setup_sym($1, current_type) if((current_type == _int) (current_type == _float)) Add_Data($1) Add_Data("\tdw\t6 dup(?)\r\n") else if(current_type == _chr) Add_Data($1) Add_Data("\tdb\t?\r\n") else if(current_type == _str) Add_Data($1) Add_Data("\tdb\t56 dup( )\r\n") 49

50 TEST.ASM جميل, أعد توليد المترجم ثم شغل البرنامج COMPALG.EXE بالمحتوى التالي: لينتج لنا الملف.MODEL small.stack 100h.DATA a dw 6 dup(?) resultat dw 6 dup(?) r dw 6 dup(?) car db? s db 56 dup( ).CODE start: mov ax,@data mov ds,ax end start التصريح عن المتغيرات آان سهلا, أرجو أن يكون الباقي سهلا أيضا أو أسهل. لنبدأ بتوليد الكود الخاص ب lire و,ecrire سنبدأ ب ecrire لا نها تبدو أسهل و بما أنها تخرج نصوص على الشاشة فا ننا سنستخدم المقاطعة,int 21h لنرى. الدالة ecrire قد تا خذ على شكل بارامتر إما متغير أو سلسلة حرفية, إذا آانت سلسلة حرفية فيجب أن نصرح عنها أولا في قسم البيانات ثم نخرجها إلى الشاشة, مثلا: ecrire "Entrer a = " ecrire "c".data _msg_1 db "Entrer a = ","$".CODE mov dx,offset msg mov ah,9 int 21h.CODE mov mov int dl, "c" ah,2 21h CHAINE لنثبت هذا قبل أن ننتقل إلى غيره, ولكن, عندما يرجع LEX التوآن CARA يرفق معهما قيمة السلسة الحرفية و لهذا إفتح الملف :lcompalg.l أو يجب أن "\""."\"" strcpy(yylval.tstr,yytext) return(cara) 50

51 "\""(.)+"\"" strcpy(yylval.tstr,yytext) return(chaine) إذا آان بارامتر الدالة ecrire عبارة عن سلسلة حرفية فا ننا سنحتاج إلى التصريح عنه و آا نه متغير عادي, لذلك, سنعطي لتلك السلسلة من المتغيرات هذا الشكل _msgx_ حيث سيتغير X من 0 إلى 9, لذلك نعود إلى الملف CODE_GEN.H و لنصرح عن المتغير data_counter ليكون بمثابة عداد لقيمة X و آذلك سنصرح عن متغير مو قت strtemp وهو عبارة عن مو شر لسلسة حرفية قد نحتاجها لحفظ بعض العناوين بشكل مو قت, آذلك سنحتاج إلى متغير نحدد فيه ما إذا آانت التعليمة الا خيرة أهي ecrire إو إسناد لا نهما يتقاطعان في نفس القاعدة fexpr و :sexpr #include<stdlib.h> #define _WRITE 2 #define _AFFECT 3 char data_section[1024] char code_section[8192] FILE *fcode int data_counter = 0 char *strtemp int current_op الا ن لنعرف دالة جديدة تقوم با رجاع قيمة جديدة للمتغير :_msgx_ char* GenStrIdent() char *temp = (char*)malloc(sizeof(char)*8) char string[3] itoa(data_counter++, string, 10) sprintf(temp, "_msg%s_", string) return temp 51

52 compalg.y أغلق و احفظ الملف CODE_GEN.H المحدد لشكل الدالة :ecrire و نعد إلى الملف و بالتحديد إلى القاعدة %token <Tstr> CHAINE %token <Tstr> CARA write:writed_expr writed_expr VER write writed_expr:new_line current_op = _WRITEfexpr current_op = _WRITEsexpr sexpr:chaine $$=_str if(current_op == _WRITE) strtemp = GenStrIdent() Add_Data(strtemp) Add_Data("\tdb\t") Add_Data($1) Add_Data(",\"$\"\r\n") Add_Code("\r\necrire ") Add_Code($1) Add_Code("\r\n") Add_Code("mov dx, offset ") Add_Code(strtemp) Add_Code("\r\n") Add_Code("mov ah, 9\r\n") Add_Code("int 21h\r\n") CARA $$=_chr if(current_op == _WRITE) Add_Code("\r\necrire ") Add_Code($1) Add_Code("\r\n") Add_Code("mov dl, ") Add_Code($1 ) Add_Code("\r\n") 52