النسق كبنية شبكة
تترجم معالجة الكود المصدر إلى شجرة تحليلية - شجرة ممركة ممركة حيث يمثل كل عقدة قاعدة جبرية تطبق، وكل ورقة تمثيل علامة نهاية (اسم متغير، حرف ثابت، عملية).
هندسة الشجرة
شجرة بn عقدة وn-1 رأس. عمق d: المسافة الأقصى من الجذر إلى أي ورقة. في حالة الشجرة المربعة المتوازنة من عمق d: حتى 2^d أوراق و2^(d+1)-1 عُقدة إجمالية.
شجرات التحليل للتعابير العادية ليست متوازنة: ترتيب العمليات يخلق شجرات مائلة لليمين أو شجرات مائلة لليسار. A + B C تنتج شجرة حيث أعمق من +، مما يعني أن * يربط بشكل أكثر صرامة.
BNF & ALGOL
Backus-Naur Form (BNF)، اخترعها لتحديد ALGOL، ي formalizes الجبر كقواعد إنتاج:
``
<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>
<factor> ::= id | (<expr>)
``
كل قاعدة إنتاج تعريف مستوى من الشجرة. الجبر هو شبكة موجهة على الأعلام غير النهائية؛ فك析 جملة يتبع مسارًا من خلال تلك الشبكة من علامة بداية إلى الأوراق.
عمق شجرة التحليل والتكلفة المعجمية للتعابير
للتعبير (A + B) * (C + D), الشجرة التحليلية لها بنية محددة عند ترتيب العمليات المعياري.
عمق شجرة التحليل يؤثر على أداء المُعالج: الشجرات العميقة تتطلب فروعًا أكثر خلال معالجة تنازلي.
انفطال شانون & التكرار
لاحظ هامنج أن اللغة المكتوبة هي ~ 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%. entropy الفعلي للإنجليزية هو حوالي H ≈ 1.0 بت/شخص (بما في ذلك السياق المستوى الكلمة). entropy الأقصى للعربية 26 حرف: H_max = log₂(26) ≈ 4.70 بت/شخص.
شكلات النمو كجبرية
تتم معالجة خوارزميات المُحول للبرامج بحجم n (رموز، سطور، أو عقد). يحدد خيار الخوارزمية كيف تزداد وقت المُحول مع حجم البرنامج.
الفئات الشائعة للتركيب
| الفئة | وقت التنفيذ | مثال | |---|---|---| | O(n) | خطي | الفحص اللفظي (lexical scanning) | | O(n log n) | quasi-linear | القسمة الأمثل (optimal sorting) | | O(n²) | مربع | الكشف عن التكرار (naive duplicate detection) | | O(n³) | مكعب | ضرب المصفوفة (matrix multiply)، تحليل CYK | | O(2ⁿ) |指数ية | التأكد من النظرية (naive theorem proving) |
الصورة الجبرية: خطة وقت التنفيذ ضد n. O(n) هو خط. O(n²) هو دائرة. O(2ⁿ) هو منحني إكسبويل يبدو مستوياً قرب n = 0 وخطياً قرب n = 50.
تحليل الجبر المنطقي العام (خوارزمية CYK) تستغرق وقتًا O(n³). بالنسبة للغات البرمجة العملية في معظم الحالات، يكون الجبر مصممًا ليتم التحليل بوقت O(n). تحليل الجبر لـ ALGOL كان أكثر تعقيدًا من تحليل FORTRAN، مما ساهم في أسرع المُحولات - إزعاج عملي يهم في 1958 عندما استغرق المُحول وقتًا طويلًا.
نقاط التقاطع
استدلال جدول الرموز البسيط يستخدم عمليات إجمالية تبلغ O(n²) للبرنامج من n تعريفات (بحث خطي لكل من n عمليات البحث). تستخدم طاولة التجزئة O(n) عمليات إجمالية متوقعة.
ت suppose: الخوارزمية O(n²) تعمل بسرعة 10⁶ عملية/ثانية على معدات 1958. الخوارزمية O(n) تعمل بنفس السرعة ولكن تتطلب 100n عملية إعداد (بناء جدول التجزئة).