Blog · November 2026 · 9 min read Blog · Novembre 2026 · 9 min de lectureالمدونة · نوفمبر 2026 · 9 دقائق قراءة

From source code to 8086 assembly: writing a compiler in C Du code source à l'assembleur 8086 : écrire un compilateur en Cمن الشيفرة المصدرية إلى تجميع 8086: كتابة مترجم بلغة C

One small program, followed through every phase of the MiniAlgo compiler: tokens, grammar, semantic checks, quadruplets, five optimization passes and 8086 code. With the real output at each step, and the jump-target bugs that make compilers tricky. Un petit programme, suivi à travers toutes les phases du compilateur MiniAlgo : les tokens, la grammaire, les vérifications sémantiques, les quadruplets, cinq passes d'optimisation et le code 8086. Avec la vraie sortie à chaque étape, et les bugs de cibles de saut qui rendent les compilateurs délicats.برنامج صغير نتتبّعه عبر كل مراحل مترجم MiniAlgo: الوحدات المعجمية، والقواعد النحوية، والفحوص الدلالية، والرباعيات، وخمس مراحل تحسين، وشيفرة 8086. مع المخرجات الحقيقية في كل خطوة، وأخطاء أهداف القفز التي تجعل المترجمات دقيقة.

Why write a compilerPourquoi écrire un compilateurلماذا نكتب مترجماً

Every day I write code that something else turns into instructions: TypeScript, C#, SQL. The MiniAlgo compiler was a team project for the compilation course of my Master's at USTHB: take a small algorithmic language and go all the way down to 8086 assembly that runs in the emu8086 emulator, written in C with Flex and Bison. Tous les jours, j'écris du code que quelque chose d'autre transforme en instructions : TypeScript, C#, SQL. Le compilateur MiniAlgo était un projet d'équipe pour le cours de compilation de mon Master à l'USTHB : partir d'un petit langage algorithmique et descendre jusqu'à de l'assembleur 8086 qui tourne dans l'émulateur emu8086, en C avec Flex et Bison.أكتب كل يوم شيفرة يحوّلها شيء آخر إلى تعليمات: TypeScript وC# وSQL. كان مترجم MiniAlgo مشروعاً جماعياً في مقياس الترجمة ضمن الماستر في جامعة هواري بومدين: الانطلاق من لغة خوارزمية صغيرة والنزول حتى شيفرة تجميع 8086 تعمل في المحاكي emu8086، بلغة C مع Flex وBison.

Here is the program we will follow through the whole article: Voici le programme que nous allons suivre tout au long de l'article :هذا هو البرنامج الذي سنتتبّعه طوال المقال:

PROGRAM Demo
DECL
    INTEGER : A, B, Res ;
ENDDECL
BEGIN
    A = 2 + 3 ;
    B = A * 1 ;
    WHILE (A < 10) {
        Res = (A + B) * (A + B) ;
        A = A + 1 ;
    }
    WRITE(Res) ;
END

It is written badly on purpose: 2 + 3 can be computed in advance, A * 1 is useless, and A + B is computed twice. A good compiler should notice all three. Il est mal écrit exprès : 2 + 3 peut être calculé à l'avance, A * 1 ne sert à rien, et A + B est calculé deux fois. Un bon compilateur doit remarquer les trois.كُتب بشكل سيئ عن قصد: 2 + 3 يمكن حسابه مسبقاً، وA * 1 لا فائدة منه، وA + B يُحسب مرتين. والمترجم الجيد يجب أن ينتبه إلى الثلاثة.

The pipelineLes étapesمراحل الترجمة

LexerLexiqueالمحلل المعجميFlex
→
ParserSyntaxeالمحلل النحويBison + checksvérifsفحوص
→
QuadrupletsQuadrupletsالرباعيات(op, a, b, res)
→
OptimizerOptimiseurالمحسِّن5 passes5 passes5 مراحل
→
8086output.asm
  • The lexer (Flex) cuts the text into tokens: keywords, identifiers, numbers, operators. It also tracks the line and column of each token, so every error can say exactly where it is.L'analyseur lexical (Flex) découpe le texte en tokens : mots-clés, identifiants, nombres, opérateurs. Il suit aussi la ligne et la colonne de chaque token, pour que chaque erreur indique exactement où elle se trouve.المحلل المعجمي (Flex) يقطّع النص إلى وحدات: كلمات مفتاحية، ومعرّفات، وأعداد، وعمليات. ويتتبّع أيضاً السطر والعمود لكل وحدة، حتى يحدد كل خطأ مكانه بالضبط.
  • The parser (Bison) checks the grammar. Its actions do the rest of the front end: filling the symbol table (a hash table with chaining), the semantic checks, and generating intermediate code.L'analyseur syntaxique (Bison) vérifie la grammaire. Ses actions font le reste du travail : remplir la table des symboles (une table de hachage avec chaînage), les vérifications sémantiques, et la génération du code intermédiaire.المحلل النحوي (Bison) يتحقق من القواعد. وتقوم أفعاله ببقية العمل: ملء جدول الرموز (جدول تجزئة مع التسلسل)، والفحوص الدلالية، وتوليد الشيفرة الوسيطة.

The semantic checks catch what the grammar cannot: undeclared or duplicate variables, assigning a float to an integer, changing a constant, dividing by a constant zero, an array index out of bounds. The errors follow the format required by the course: Les vérifications sémantiques attrapent ce que la grammaire ne peut pas voir : variables non déclarées ou déclarées deux fois, réel affecté à un entier, constante modifiée, division par un zéro constant, indice de tableau hors bornes. Les erreurs suivent le format demandé par le cours :الفحوص الدلالية تلتقط ما لا تراه القواعد: متغيرات غير مصرّح بها أو مصرّح بها مرتين، وإسناد عدد حقيقي إلى عدد صحيح، وتعديل ثابت، والقسمة على صفر ثابت، وفهرس جدول خارج الحدود. وتتبع الأخطاء الصيغة المطلوبة في المقياس:

Erreur Semantique : ligne 20 , colonne 18 , element 'A' (double declaration)
Erreur Semantique : ligne 48 , colonne 15 , element '/' (division par zero)
Erreur Semantique : ligne 51 , colonne 16 , element 'T[15]' (indice hors bornes, taille=10)

Quadruplets, and jumping to a line that does not exist yetLes quadruplets, et sauter vers une ligne qui n'existe pas encoreالرباعيات، والقفز إلى سطر لم يوجد بعد

The intermediate code is a list of quadruplets: (operator, operand 1, operand 2, result). Expressions use temporaries T0, T1… and control flow uses two jumps: BZ (jump if zero, so if the condition is false) and BR (always jump). Le code intermédiaire est une liste de quadruplets : (opérateur, opérande 1, opérande 2, résultat). Les expressions utilisent des temporaires T0, T1… et le contrôle utilise deux sauts : BZ (sauter si zéro, donc si la condition est fausse) et BR (sauter toujours).الشيفرة الوسيطة قائمة من الرباعيات: (العملية، المعامل 1، المعامل 2، النتيجة). تستعمل التعابير متغيرات مؤقتة T0 وT1… ويستعمل التحكم قفزتين: BZ (القفز إذا كانت القيمة صفراً، أي إذا كان الشرط خاطئاً) وBR (القفز دائماً).

The hard part: when the parser reads WHILE (A < 10) {, it must emit the BZ that leaves the loop, but it does not know yet where the loop ends. The answer is backpatching: emit the jump with an empty target, remember its index, and fill it in once the closing brace is reached. La partie difficile : quand l'analyseur lit WHILE (A < 10) {, il doit émettre le BZ qui sort de la boucle, mais il ne sait pas encore où la boucle se termine. La réponse, c'est le backpatching (la reprise arrière) : émettre le saut avec une cible vide, retenir son numéro, et le compléter une fois l'accolade fermante atteinte.الجزء الصعب: عندما يقرأ المحلل WHILE (A < 10) {، يجب أن يولّد قفزة BZ التي تخرج من الحلقة، لكنه لا يعرف بعد أين تنتهي الحلقة. والحل هو الترقيع الخلفي (backpatching): توليد القفزة بهدف فارغ، وحفظ رقمها، ثم إكماله عند الوصول إلى القوس المغلق.

while_stmt
    : while_mark '(' expression ')' '{'
      { $<int_val>$ = gen_quad("BZ", $3.name, "", ""); }  /* target unknown */
      instructions '}'
      {
          sprintf(lbl, "%d", $<int_val>1);
          gen_quad("BR", "", "", lbl);          /* back to the condition */
          sprintf(lbl, "%d", quad_count);
          update_quad_result($<int_val>6, lbl); /* now we know the exit */
      }
    ;
while_mark : WHILE { $<int_val>$ = quad_count; } ;  /* where the condition starts */

For our program, the compiler produces 14 quadruplets. Look at line 5: its target, 13, was filled in only after the whole loop body was generated. Pour notre programme, le compilateur produit 14 quadruplets. Regardez la ligne 5 : sa cible, 13, n'a été remplie qu'après la génération de tout le corps de la boucle.لبرنامجنا، يولّد المترجم 14 رباعية. انظر إلى السطر 5: هدفه، 13، لم يُملأ إلا بعد توليد جسم الحلقة كاملاً.

 0  ( +     , 2   , 3  , T0  )
 1  ( =     , T0  ,    , A   )
 2  ( *     , A   , 1  , T1  )
 3  ( =     , T1  ,    , B   )
 4  ( <     , A   , 10 , T2  )
 5  ( BZ    , T2  ,    , 13  )   <- exit, backpatched
 6  ( +     , A   , B  , T3  )
 7  ( +     , A   , B  , T4  )   <- same as line 6
 8  ( *     , T3  , T4 , T5  )
 9  ( =     , T5  ,    , Res )
10  ( +     , A   , 1  , T6  )
11  ( =     , T6  ,    , A   )
12  ( BR    ,     ,    , 4   )   <- back to the condition
13  ( WRITE , Res ,    ,     )

Five optimization passesCinq passes d'optimisationخمس مراحل تحسين

The optimizer runs five small passes over the quadruplets, again and again, until a full round changes nothing. One pass often creates work for another, which is why the loop matters. L'optimiseur applique cinq petites passes sur les quadruplets, encore et encore, jusqu'à ce qu'un tour complet ne change plus rien. Une passe crée souvent du travail pour une autre, c'est pour ça que la boucle compte.يطبّق المحسِّن خمس مراحل صغيرة على الرباعيات، مرة بعد مرة، حتى لا تغيّر جولة كاملة أي شيء. فكثيراً ما تخلق مرحلة عملاً لمرحلة أخرى، ولهذا تهم الحلقة.

  • Constant folding: (+, 2, 3, T0) becomes (=, 5, , T0).Repli des constantes : (+, 2, 3, T0) devient (=, 5, , T0).طيّ الثوابت: تصبح (+, 2, 3, T0) هي (=, 5, , T0).
  • Algebraic simplification: A * 1 becomes a simple copy of A; the pass also knows x+0, x-x, x/1, and turns x*2 into the cheaper x+x.Simplification algébrique : A * 1 devient une simple copie de A ; la passe connaît aussi x+0, x-x, x/1, et remplace x*2 par x+x, moins coûteux.التبسيط الجبري: تصبح A * 1 مجرد نسخ لـ A؛ وتعرف المرحلة أيضاً x+0 وx-x وx/1، وتحوّل x*2 إلى x+x الأقل كلفة.
  • Common subexpressions: line 7 computes exactly what line 6 already computed, so it becomes (=, T3, , T4).Expressions communes : la ligne 7 calcule exactement ce que la ligne 6 a déjà calculé, elle devient donc (=, T3, , T4).التعابير المشتركة: السطر 7 يحسب بالضبط ما حسبه السطر 6، فيصبح (=, T3, , T4).
  • Copy propagation: after (=, T3, , T4), later uses of T4 can read T3 directly, so T3 * T4 becomes T3 * T3.Propagation de copie : après (=, T3, , T4), les utilisations suivantes de T4 peuvent lire T3 directement, donc T3 * T4 devient T3 * T3.نشر النسخ: بعد (=, T3, , T4)، يمكن للاستعمالات اللاحقة لـ T4 قراءة T3 مباشرة، فتصبح T3 * T4 هي T3 * T3.
  • Dead code: a temporary that is written but never read again, like T4 now, is removed.Code mort : un temporaire écrit mais jamais relu, comme T4 maintenant, est supprimé.الشيفرة الميتة: المتغير المؤقت الذي يُكتب ولا يُقرأ بعدها، مثل T4 الآن، يُحذف.

On our program: 9 transformations in 3 rounds, and 14 quadruplets become 11. Sur notre programme : 9 transformations en 3 tours, et les 14 quadruplets deviennent 11.على برنامجنا: 9 تحويلات في 3 جولات، وتصبح الرباعيات الـ 14 إحدى عشرة.

 0  ( =     , 5   ,    , A   )   <- 2 + 3 folded
 1  ( =     , A   ,    , B   )   <- A * 1 simplified
 2  ( <     , A   , 10 , T2  )
 3  ( BZ    , T2  ,    , 10  )   <- was 13
 4  ( +     , A   , B  , T3  )
 5  ( *     , T3  , T3 , T5  )   <- A + B computed once
 6  ( =     , T5  ,    , Res )
 7  ( +     , A   , 1  , T6  )
 8  ( =     , T6  ,    , A   )
 9  ( BR    ,     ,    , 2   )   <- was 4
10  ( WRITE , Res ,    ,     )

The real trap: jump targetsLe vrai piège : les cibles de sautالفخ الحقيقي: أهداف القفز

Look at the jumps above: BZ went from 13 to 10 and BR from 4 to 2. Jumps point to quadruplet numbers, so deleting a single line shifts every target after it. If you forget, the program jumps into the middle of the wrong instruction and nothing tells you. Regardez les sauts ci-dessus : BZ est passé de 13 à 10 et BR de 4 à 2. Les sauts pointent vers des numéros de quadruplets, donc supprimer une seule ligne décale toutes les cibles qui suivent. Si on l'oublie, le programme saute au milieu de la mauvaise instruction, sans aucun message d'erreur.انظر إلى القفزات أعلاه: انتقلت BZ من 13 إلى 10 وBR من 4 إلى 2. تشير القفزات إلى أرقام الرباعيات، لذا فحذف سطر واحد يزيح كل الأهداف التي تليه. وإذا نسينا ذلك، يقفز البرنامج إلى وسط التعليمة الخاطئة دون أي رسالة خطأ.

So the passes never delete anything directly. They mark dead lines as NOP, and only at the end a compaction step removes them, builds an old-index → new-index map, and rewrites every jump. A jump whose target was deleted moves to the next line that survived: Les passes ne suppriment donc jamais rien directement. Elles marquent les lignes mortes comme NOP, et seulement à la fin, une étape de compactage les retire, construit une table ancien numéro → nouveau numéro, et réécrit tous les sauts. Un saut dont la cible a été supprimée passe à la ligne suivante qui a survécu :لذلك لا تحذف المراحل أي شيء مباشرة. بل تعلّم الأسطر الميتة بـ NOP، وفي النهاية فقط تزيلها خطوة الضغط، وتبني جدول الرقم القديم ← الرقم الجديد، وتعيد كتابة كل القفزات. والقفزة التي حُذف هدفها تنتقل إلى السطر التالي الذي بقي:

for (int i = 0; i < quad_count; i++)
    map[i] = is_nop(i) ? -1 : new_count++;   /* old index -> new index */

/* for each jump (BZ, BR): */
int target = atoi(quads[i].result);
int moved  = map[target];
while (moved == -1 && target < quad_count)   /* target was deleted */
    moved = (++target < quad_count) ? map[target] : new_count;

The same reason explains why copy propagation and common subexpression elimination stop scanning as soon as they meet a jump: past a jump, the value of a variable depends on which path the program took. C'est aussi pour ça que la propagation de copie et l'élimination des expressions communes arrêtent leur recherche dès qu'elles rencontrent un saut : après un saut, la valeur d'une variable dépend du chemin pris par le programme.وللسبب نفسه، يتوقف نشر النسخ وحذف التعابير المشتركة عن البحث بمجرد مصادفة قفزة: بعد القفزة، تتوقف قيمة المتغير على المسار الذي سلكه البرنامج.

Generating 8086 codeGénérer le code 8086توليد شيفرة 8086

The last phase writes an assembly file with the three classic segments: stack, data (one word per variable and temporary) and code. Each quadruplet becomes a few instructions, and gets a label so jumps can reach it. Here is T5 = T3 * T3, now that A + B is computed only once: La dernière phase écrit un fichier assembleur avec les trois segments classiques : pile, données (un mot par variable et par temporaire) et code. Chaque quadruplet devient quelques instructions, avec une étiquette pour que les sauts puissent l'atteindre. Voici T5 = T3 * T3, maintenant que A + B n'est calculé qu'une fois :تكتب المرحلة الأخيرة ملف تجميع بالمقاطع الثلاثة الكلاسيكية: المكدس، والبيانات (كلمة لكل متغير ومتغير مؤقت)، والشيفرة. تتحول كل رباعية إلى بضع تعليمات، مع وسم حتى تتمكن القفزات من بلوغها. وهذه T5 = T3 * T3، بعد أن صار A + B يُحسب مرة واحدة فقط:

LBL_5:
    MOV AX, T3
    MOV BX, T3
    IMUL BX        ; DX:AX = AX * BX
    MOV T5, AX
...
LBL_9:
    JMP LBL_2      ; back to the loop condition
LBL_10:
    MOV AX, Res
    CALL WRITE_INT ; prints AX in decimal (divide by 10, push digits)

The 8086 has no instruction to print a number, so the generated file ships a small WRITE_INT routine that divides by 10, pushes each digit on the stack, then prints them in the right order through DOS interrupt 21h. Le 8086 n'a pas d'instruction pour afficher un nombre : le fichier généré contient donc une petite routine WRITE_INT qui divise par 10, empile chaque chiffre, puis les affiche dans le bon ordre grâce à l'interruption DOS 21h.لا يملك 8086 تعليمة لطباعة عدد، لذا يتضمن الملف المولَّد إجراءً صغيراً WRITE_INT يقسم على 10، ويدفع كل رقم في المكدس، ثم يطبعها بالترتيب الصحيح عبر مقاطعة DOS رقم 21h.

What I would do differentlyCe que je ferais autrementما كنت سأفعله بشكل مختلف

  • Work on basic blocks. The passes stop at jumps, but a line can also be the target of a jump, reached from somewhere else. Cutting the code into basic blocks first (a block starts at every jump target and ends at every jump) would make each optimization safe by construction, instead of safe because temporaries happen to be short-lived.Travailler sur des blocs de base. Les passes s'arrêtent aux sauts, mais une ligne peut aussi être la cible d'un saut, atteinte depuis ailleurs. Découper d'abord le code en blocs de base (un bloc commence à chaque cible de saut et se termine à chaque saut) rendrait chaque optimisation sûre par construction, au lieu de sûre parce que les temporaires vivent peu de temps.العمل على الكتل الأساسية. تتوقف المراحل عند القفزات، لكن السطر قد يكون أيضاً هدفاً لقفزة تأتي من مكان آخر. تقطيع الشيفرة أولاً إلى كتل أساسية (تبدأ الكتلة عند كل هدف قفز وتنتهي عند كل قفزة) سيجعل كل تحسين آمناً بطبيعته، بدل أن يكون آمناً لأن المتغيرات المؤقتة قصيرة العمر.
  • Fuse comparisons and jumps. Today A < 10 computes 0 or 1 into T2, then BZ tests T2. A single CMP followed by JGE to the exit would do the same job in two instructions.Fusionner comparaisons et sauts. Aujourd'hui, A < 10 calcule 0 ou 1 dans T2, puis BZ teste T2. Un seul CMP suivi d'un JGE vers la sortie ferait le même travail en deux instructions.دمج المقارنات والقفزات. حالياً، تحسب A < 10 القيمة 0 أو 1 في T2، ثم تختبر BZ قيمة T2. وتعليمة CMP واحدة تليها JGE نحو المخرج ستؤدي العمل نفسه بتعليمتين.
  • Keep values in registers. Every temporary goes through memory (MOV T3, AX then MOV AX, T3). Even simple register allocation would remove most of those moves.Garder les valeurs dans les registres. Chaque temporaire passe par la mémoire (MOV T3, AX puis MOV AX, T3). Même une allocation de registres simple supprimerait la plupart de ces transferts.إبقاء القيم في السجلات. كل متغير مؤقت يمر عبر الذاكرة (MOV T3, AX ثم MOV AX, T3). وحتى تخصيص بسيط للسجلات سيزيل معظم هذه التنقلات.
  • Real floats. MiniAlgo has a FLOAT type, but the 8086 generator stores floats as integers. Supporting them properly would need the 8087 coprocessor or fixed-point arithmetic.De vrais réels. MiniAlgo a un type FLOAT, mais le générateur 8086 stocke les réels comme des entiers. Les gérer vraiment demanderait le coprocesseur 8087 ou de l'arithmétique à virgule fixe.أعداد حقيقية فعلية. في MiniAlgo نوع FLOAT، لكن مولّد 8086 يخزّن الأعداد الحقيقية كأعداد صحيحة. ودعمها فعلاً يتطلب المعالج المساعد 8087 أو حساب الفاصلة الثابتة.

One honest number: on the full sample program, written by a human, the optimizer only goes from 463 to 459 quadruplets. People rarely write A * 1. These passes matter most on code that a compiler generates itself, such as array index calculations. Un chiffre honnête : sur le programme d'exemple complet, écrit par un humain, l'optimiseur ne passe que de 463 à 459 quadruplets. On écrit rarement A * 1 à la main. Ces passes comptent surtout sur le code que le compilateur génère lui-même, comme les calculs d'indices de tableaux.رقم صريح: على برنامج المثال الكامل، الذي كتبه إنسان، لا ينتقل المحسِّن إلا من 463 إلى 459 رباعية. فنادراً ما يكتب الناس A * 1. وتهم هذه المراحل أكثر في الشيفرة التي يولّدها المترجم نفسه، مثل حسابات فهارس الجداول.

TakeawaysÀ retenirالخلاصة

  • Backpatching solves "jump to a place that does not exist yet": emit now, fill in later.Le backpatching résout le problème du « saut vers un endroit qui n'existe pas encore » : émettre maintenant, compléter plus tard.الترقيع الخلفي يحل مشكلة «القفز إلى مكان لم يوجد بعد»: ولّد الآن، وأكمل لاحقاً.
  • Small optimizations become powerful when you repeat them until nothing changes.De petites optimisations deviennent puissantes quand on les répète jusqu'à ce que plus rien ne change.التحسينات الصغيرة تصبح قوية عندما تُكرَّر حتى لا يتغير شيء.
  • Anything that refers to positions (jump targets, indexes) must be remapped after every deletion. Mark first, delete once, remap everything.Tout ce qui fait référence à des positions (cibles de saut, indices) doit être recalculé après chaque suppression. Marquer d'abord, supprimer une fois, tout recalculer.كل ما يشير إلى مواقع (أهداف القفز، الفهارس) يجب إعادة حسابه بعد كل حذف. علّم أولاً، واحذف مرة واحدة، وأعد حساب كل شيء.

The full source, the sample programs and the build instructions are on GitHub. Open the generated output.asm in emu8086 to watch it run. Le code complet, les programmes d'exemple et les instructions de compilation sont sur GitHub. Ouvrez le fichier output.asm généré dans emu8086 pour le voir tourner.الشيفرة الكاملة وبرامج المثال وتعليمات البناء موجودة على GitHub. افتح الملف المولَّد output.asm في emu8086 لتراه يعمل.