النحو كبنية بيانية
يترجم المترجم الكود المصدري ببناء شجرة تحليل — وهي شجرة بجذر حيث يمثل كل عقدة قاعدة نحو مطبقة، وكل ورقة تمثل رمزًا نهائيًا (اسم متغير أو حرف أو عامل).
هندسة الشجرة
شجرة بها n عقدة و n−1 حافة. العمق d: المسافة القصوى من الجذر إلى أي ورقة. لشجرة ثنائية متوازنة بعمق d: حتى 2^d ورقة و 2^(d+1)−1 إجمالي العقد.
أشجار التحليل للتعبيرات النموذجية ليست متوازنة: أسبقية العامل تخلق أشجارًا منحرفة لليمين أو اليسار. A + B C ينتج شجرة حيث أعمق من +، مما يعني أن * يرتبط بقوة أكبر.
BNF و ALGOL
صيغة Backus-Naur (BNF)، المخترعة لتحديد ALGOL، تصيغ النحو كقواعد الإنتاج:
``
<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>
<factor> ::= id | (<expr>)
``
كل قاعدة إنتاج تحدد مستوى واحد من الشجرة. النحو رسم بياني موجه على الرموز غير النهائية؛ تحليل الجملة يتتبع مسارًا عبر هذا الرسم البياني من الرمز الأولي إلى الأوراق.
عمق شجرة التحليل وتعقيد التعبير
بالنسبة للتعبير (A + B) * (C + D)، لشجرة التحليل بنية محددة تحت أسبقية العامل القياسية.
يؤثر عمق شجرة التحليل على أداء المترجم: الأشجار الأعمق تتطلب المزيد من إطارات المكدس أثناء تحليل النزول الموجه.
إنتروبيا شانون والإفادة الزائدة
لاحظ Hamming أن اللغة المنطوقة تتمتع بإفادة زائدة بنسبة ~60٪، واللغة المكتوبة ~40٪. لهذا معنى دقيق نظري للمعلومات.
إنتروبيا شانون
لمصدر ينتج رموزًا من أبجدية A مع احتمالات {p₁, p₂, ..., pₙ}:
H = −Σ pᵢ log₂(pᵢ) (بت لكل رمز)
الإنتروبيا القصوى: التوزيع المنتظم (جميع الرموز محتملة بالتساوي). H_max = log₂(n) لـ n رمز.
الإفادة الزائدة R: كسر البتات التي لا تحمل معلومات (يمكن حذفها دون فقدان المحتوى):
R = 1 − H / H_max
إذا كان R = 0.4 (إفادة زائدة 40٪): 40٪ من البتات قابلة للتنبؤ بها من السياق. القناة التي تحمل نص إنجليزي بـ 8 بت/حرف تستخدم فقط 60٪ من سعتها للمعلومات؛ 40٪ هو البنية التي يعرفها المستقبل بالفعل.
كشف الأخطاء يستخدم الإفادة الزائدة: إذا كان 40٪ من البتات قابلة للتنبؤ بها، قد ينتج خطأ في الإرسال عن تسلسل ينتهك بنية الإفادة الزائدة — قابل للكشف حتى بدون رموز تصحيح الأخطاء.
APL ذات الإفادة الزائدة القريبة من الصفر: تغيير حرف واحد نادرًا ما يكون قابلًا للكشف من السياق وحده. إفادة اللغة الإنجليزية الزائدة 60٪: غالبًا ما يمكنك إعادة بناء كلمة من السياق المحيط حتى إذا كان حرف مفقودًا أو خاطئًا.
حساب الإفادة الزائدة
تكرار الحروف الإنجليزية (تقريبًا): يظهر 'e' ~12.7٪ من الوقت؛ يظهر 'z' ~0.07٪. الإنتروبيا الفعلية للغة الإنجليزية حوالي H ≈ 1.0 بت/حرف (مع احتساب السياق على مستوى الكلمة). الإنتروبيا القصوى لأبجدية 26 حرف: H_max = log₂(26) ≈ 4.70 بت/حرف.
منحنيات النمو كهندسة
تعالج خوارزميات المترجم برامج بحجم n (رموز أو أسطر أو عقد). يحدد اختيار الخوارزمية كيفية توسع وقت الترجمة مع حجم البرنامج.
فئات التعقيد الشائعة
| الفئة | وقت التشغيل | مثال | |---|---|---| | O(n) | خطي | المسح اللغوي | | O(n log n) | شبه خطي | الفرز الأمثل | | O(n²) | تربيعي | كشف التكرارات الساذج | | O(n³) | مكعب | مضاعفة المصفوفة، تحليل CYK | | O(2ⁿ) | أسي | إثبات النظرية الساذج |
الصورة الهندسية: رسم وقت التشغيل مقابل n. O(n) خط. O(n²) قطع مكافئ. O(2ⁿ) منحنى أسي يبدو مسطحًا بالقرب من n=0 وشبه رأسي بالقرب من n=50.
تحليل النحو الخالي من السياق العام (خوارزمية CYK) يعمل في O(n³). بالنسبة لمعظم لغات البرمجة العملية، يتم تصميم النحو ليكون قابلًا للتحليل LR(1)، مما يسمح بتحليل O(n). كان نحو ALGOL أكثر تعقيدًا من FORTRAN، مما ساهم في إبطاء المترجمات — احتكاك عملي مهم في عام 1958 عندما استغرقت الترجمة ساعات.
نقاط التقاطع
يستخدم البحث البسيط عن رموز الجدول O(n²) إجمالي العمليات لبرنامج بـ n معرف (مسح خطي لكل n بحث). جدول الرموز بجدول تجزئة يستخدم O(n) إجمالي العمليات المتوقعة.
افترض: خوارزمية O(n²) تعمل بـ 10⁶ عمليات/ثانية على أجهزة 1958. تعمل خوارزمية O(n) بنفس السرعة لكنها تتطلب 100n عمليات إعداد (بناء جدول التجزئة).