كيف يعمل محرك التعبير المنتظم REGEX Engine

في الحقيقة ربما لايكون ظاهراً الآن مدى أهمية فهم كيفية عمل محرك التعبير المنتظم، ولكن لاحقاً ربما تكتب نمط ما لكنه لا يأتي بالنتيجة المطلوبة لأنك لم تفهم بالظبط ما هي الخطوات التي يأخذها المحرك للبحث عن شيء ما. لذلك سأقوم بشرح بعض التفاصيل البسيطة التي تساعدك على فهم الموضوع.

مبدئياً محركات التعبير المنتظمة بالتأكيد مبنية على نظريات علمية،ومن هذه النظريات نظرية تسمى Automata Theory وهي نظرية تم استخدامها في بناء مجموعة من النماذج النظرية لتنفيذ العمليات المعقدة. وهي من أصعب المواد في علوم الحاسب ولكن لحسن خظنا فلانحتاج للتعمق فيها وإنما جزء بسييط جداً منها.

من هذه النماذج ما يسمى بالآلة ذات الحالات المنتهية Finite state machine وهي ليست آلة حقيقية ملموسة وإنما آلة نظرية، (أنصحك بالقراءة عنها كلما أمكن فهذا ليس موضوعنا الأساسي والخوض فيه يحتاج شروحات منفصلة). لكن ما يهمنا الأن أن نعرف أن هناك نوعان من محركات التعبيرات المنتظمة التي تعتمد على الآلة ذات الحالات المنتهية FSM وهما:

• محرك الحالات المنتهية المحسوبة/المعروفة Deterministic finite Automata ويتم اختصارها إلى DFA ويطلق على هذا النوع من المحركات! المحركات الموجهة بالنص Text directed engines. وباختصار هو أن هذه الآلة تقوم بالبحث بخطوات معروفة/محسوبة العدد.
• محرك الحالات المنتهية الغير محسوبة/الغير معروفة Non-deterministic finite Automata ويتم اختصارها إلى NFA ويطلق على هذا النوع من المحركات! المحركات الموجهة بالنمط التعبيري Regex directed engines. وكما يظهر من خلال الإسم فهي آلة تستخدم لعمليات البحث الغيرة محسوبة الخطوات (غير محسوبة الحالات) وهذا هو النوع الأكثر شيوعاً واستخداماً في محركات التعبيرات المنتظمة الحديثة وبالطبع لغات البرمجة الحالية.لما توفره هذه النوعية من مميزات تساعد في عمليات البحث المعقد مثل المراجع Regex references وغيرها.

مالفائدة من التعرف على FSA؟

إذا كان هناك شيء ما مبنى على نظرية فيجب أن تفهم النظرية وإلا لن تعرف كيف يتم تحديد صحة التطبيق من عدمه، ولاحقاً سوف تجد خلال الشرح أننا نتطرق لشرح الخطوات التي يأخذها المحرك للبحث عن تطابق ما في النص وبالتأكيد من هذه الخطوات ما يكون واضح ومباشر، أما بعضها الآخر يوجد به بعض التعقيد والذي سيظل مبهماً/صعب تحليله حتى تعرف النظرية التي يعتمد عليها المحرك في اتخاذ القرارات. لذا أنصحك إذا شعرت أنك وصلت لمرحلة من التشويش وليس عندك اساس معين تبني عليه فرضياتك وأنك تائه في دراسة التعبيرات النمطية فأنصحك بالبحث عن دورة مصغرة تعطيك مقدمة عن الـ FSA وهذا ما اضطررت أنا شخصياً لفعله حتى تتضح الصورة.

مقدمة بسيطة عن FSA

الآلة ذات الحالات المنتهية Finite state machine أو FSA كما ذكرنا سابقاً هي آلة نظرية وليست محسوسة،الهدف منها هو تحليل النتائج عن طريق بعض المدخلات بحيث نتحقق من إمكانية الوصول للنتائج من عدمها.

بشكل بسيط تخيل كما لو أنك اخترعت آلة لصناعة شيء ما، هذه الصناعة تحتاج لمكونات معينة، هذه المكونات يجب إضافتها بترتيب معين، لذلك قمت بإضافة جزء للماكينة يقوم بفحص المكونات وترتيبها لكي تبدأ عملية الإنتاج، بحيث إن كانت المكونات كاملة وتم إضافتها بنفس الترتيب تبدأ عملية الإنتاج، وأي تغير في هذه الشروط يتم رفض عملية الإنتاج.

هذا ما تفعله آلة الحالات المنتهية، حيث تقوم بتحليل المدخلات وفحص إمكانية الوصول للنتائج، لكن ما علاقة الحالات المنتهية بتحليل المدخلات والنتائج؟

نتخيل أن الماكينة تحتاج للمكونات (a,b,c) ويتم إضافة المكونات بنفس الترتيب والعدد، وبعد إضافة كل مكون يتم فحص مطابقته للمواصفات المطلوبة، فيتم الفحص كالآتي:

• إضافة a، تقوم الماكينة بالفحص هل a من المكونات المطلوبة وبنفس الكمية المطلوبة؟، إن كان نعم انتقل للفحص التالي وإن كان لا، فتوقف
• عند التأكد من مواصفات a يتم الفحص الخاص بالمكون b، هل هي من المكونات المطلوبة وبنفس الكمية المطلوبة؟، إن كان نعم انتقل للفحص التالي وإن كان لا، فتوقف
• عند التأكد من مواصفات c فتكون الماكينة تحققت من تطابق المكونات وتبدأ عملية الإنتاج

وهنا يمكننا توصيف منطق التحقق بأنه مجموعة من الحالات، فالماكينة في حالة البداية تفحص a وعند نجاح التحقق انتقلت لحالة جديدة لفحص b ثم انتقلت لحالة أخرى وهي فحص c وعند التحقق منها تكون قد تحققت الشروط المطلوبة فتسمى الحالة النهائية. أي أن عمليات التحقق معتمدة على مجموعة من الحالات التي تنتهي إما بالنجاح أو الفشل، لذل سميت بالحالات المنتهية.

ونستطيع تمثيل ذلك بالرسم هكذا

وفي الرسم السابق نقول للماكينة عند بداية التشغيل q0 إذا تم إضافة a إنتقل للحالة الثانية q1،وإذا تم إضافة b إنتقل للحالة الثالثة q2،وإذا تم إضافة c إنتقل للحالة الرابعة q3.

هذا الرسم هو مجرد تصور لما ستقوم به الماكينة عند إضافة المكونات، واعتمدنا في الرسم على مجموعة قواعد بسيطة بحيث نستطيع تمثيل أي شيء بنفس المنطق.

بحيث:

• نمثل الحالات بالحرف q مرقم حسب الحالات
• الإنتقال بين كل حالة وأخرى بالسهم
• حالة البداية دائما يأتي لها سهم من العدم وهي الآن q0
• الحالة النهائية عبارة عن دائرتان متداخلتان وهي الآن q3

ولكن فيما سبق تصورنا أن المكونات دائما ما سيتم إضافتها بنفس الترتيب وبنفس المواصفات، ولكن هذا غير منطقي، لأن الماكينة يجب أن تتعامل مع جميع الحالات، بمعنى:

• إذا قمنا بإضافة b أو c في البداية بدلاً عن a تفشل الآلة
• إذا تم إضافة a او c بعد a (بدلاً عن b) تفشل الآلة
• إذا تم إضافة a او b بعد b (بدلاً عن c) تفشل الآلة

وهنا يكون للآلة خمس حالات منهم 4 حالات وصولاً للحالة النهائية  الناجحة والتي مثلناها بدائرتان متداخلتان وحالة الفشل التي تذهب إليها الماكينة عند إضافة الكميات الغير المناسبة وسنكتبها q4، فتصبح الرسمة السابقة كالآتي

عندما تصل الماكينة لحالة الفشل فمهما يتم يتم إضافة مكونات فلايوجد تغير في الحالة فلا استجابة من الماكينة بعد الفشل، ويمكننا توضيح ذلك على الرسم بعمل سهم يخرج من حالة الفشل q4 ويعود إليها أياً كانت المكونات

من ما سبق فقد تصورنا ماكينة نظرية تأخذ مدخلات a,b,c هذه المدخلات يجب أن تدخل بنفس الترتيب والعدد، وهذا التصور عبارة عن مجموعة من الحالات المعروفة لتوصيف عمل الماكينة ونطلق على هذه العملية آلة الحالات المنتهية Finite state machine. ويمكن للماكينة أن يوجد أكثر من حالة نهائية.

دعنا ننتقل إلى صلب الموضوع وهو التعبيرات المنتظمة Regex، والتي ذكرنا أنها عبارة عن محرك فكرة عمله معتمدة على الآلة الحالات المنتهية. وكما نعرف أنها تستخدم للبحث في النصوص عن نصوص معينة، بحيث يقوم المحرك بتطبيق النمط على أي سلسلة نصية للبحث عن أي عدد من المطابقات، ولكن اختلافاً عن ما قمنا بتوصيفه مسبقاً (على الماكينة التي تصورناها) والتي كانت حازمة بالنسبة لعدد المدخلات وترتيبها، فمحرك التعبيرات المنتظمة أكثر مرونة من ذلك فلايشترط عدد المدخلات ولا نوعها فمحرك التعبير المنتظم يبحث عن شيء ما (نمط) مهما كانت المدخلات.

وكما قلنا النمط عبارة عن مجموعة من الأحرف والرموز، فإذا تصورنا نمط بسيط جداً عبارة عن أحرف فقط، فالنمط abbc يقوم باسترجاع مطابقتان من abbc في النص abbcacabbc بحيث:

• يقوم المحرك بمطابقة abbc الأولى
• يبدأ المحرك ببدء بحث جديد بداية من الحرف a قبل c الثانية (حرف a الثاني)
• يستمر المحرك في البحث في باقي النص لفحص ما إذا كانت هناك مطابقات
• يحدث تطابق آخر بعد c الثانية

لفهم كيف يقوم المحرك بتنفيذ ذلك علينا أولا رسم نموذج الآلة منتهية الحدود الخاصة بالنمط abbc . إليكم الرسم وشرحه بالأسفل

شرح الرسم:

• إذا كنا النمط abbc سيقوم بالبحث عن abbc داخل أي نص فلا يشترط أن يبدأ النص بالحرف a لربما abbc توجد في منتصف النص، وبالتالي إذا قمنا بإدخال أي من b,c أو أي حرف آخر فهذا لايعتبر فشلاً لأن النص لم ينتهي ومازالت احتمالية حدوث تطابق موجوده، فنقوم بعمل سهم مقوس على حالة البداية q0 لنمثل أنه مهما كانت البداية سيظل المحرك عند نفس الحالة. (المحرك ينتقل لحالة جديدة إذا تحقق من الحالة الحالية وبما أننا نبحث عن a فهو لاينتقل للحالة الثانية إلا بإدخال a)
• بمجرد ظهور a في النص يعرف المحرك أنه ربما يحدث تطابق فينتقل للحالة q1 وهذه الحالة يفترض بعدها يظهر bbc
• عند هذه الحالة هناك أكثر من احتمال وهم إما يظهر في النص a or b or c أو غيرها
  • إذا كانت a فمازلنا عن نفس الحالة التي من المحتمل أن يأتي بعدها bbc لذلك قمنا بعمل سهم مقوس على الحالة q1 لنوضح أنه عند إدخال a عند هذه الحالة لايحدث تغيير في الحالة.(يخرج منها ويعود إليها)
  • إذا كانت b فهذا هو المطلوب وينتقل إلى الحالة q2
  • إذا كانت c فهنا يفشل المحرك ويذهب للحالة q5
• عند نجاح المحرك في الإنتقال للحالة q2 فهو يتوقع أن يكون التالي هو bc، ولكن أيضاً هناك احتمالات
  • إذا كانت a يعرف المحرك أنه لايمكن المطابقة لأنه وصل إلى aba ولكن في نفس الوقت هناك احتمال تطابق آخر بسبب وجود a لربما يأتي بعدها bbc  فيعود للحالة التي يفترض أن يأتي بعدها bbc وهي q1
  • إذا كانت b فهذا هو المطلوب وينتقل إلى الحالة q3
  • إذا كانت c فهنا يفشل المحرك ويذهب للحالة q5
• عند نجاح المحرك في الإنتقال للحالة q3 فهو يتوقع أن يكون التالي هو c، ولكن أيضاً هناك احتمالات
  • إذا كانت a يعرف المحرك أنه لايمكن المطابقة لأنه وصل إلى abba ولكن في نفس الوقت هناك احتمال تطابق آخر بسبب وجود a لربما يأتي بعدها bbc  فيعود للحالة التي يفترض أن يأتي بعدها bbc وهي q1
  • إذا كانت b فهنا يفشل المحرك ويذهب للحالة q5
  • إذا كانت c فهذا هو المطلوب وينتقل إلى الحالة q4 وهي الحالة النهائية

الآن انتهينا من عمل الآلة، ولكن لم نناقش ما الذي يحدث عن الفشل في المطابقة، آي بعد الوصول للحالة q5، ولكن الأمر بسيط فالفشل هنا لايعني توقف الآلة ولكن هناك أكثر من حالة للفشل:

• فشل المحرك في مطابقة أول رمز في النمط نهائياً في كامل النص: هنا يتوقف المحرك نهائياً ولايسترجع شيء
• قام المحرك بمطابقة جزء من النص وليكن ab ثم اكتشف أنه لم يجد bc بعده: هنا يعرف المحرك أنه ربما بدأ من مكان خاطيء وهناك احتمال بأن يحصل على مطابقات في باقي النص، فيقوم بالبدء من بعد المكان الذي وجد عنده التطابق السابق مع مع أول رمز في النمط، وفي حالة abbc يبدأ النمط مرة أخرى في تطبيق النمط a أي يعتبر النص كأنه bbc.

نتخيل أننا نبحث عن abbc داخل النص aabbc

• هل a في النمط تتطابق مع a في النص؟ نعم
• ينتقل لمطابقة b، هل b في النمط تتطابق مع a في النص؟ لا
• يعرف النمط أنه بدأ من المكان الخطأ
• يبدأ النمط من جديد بعد حرف a الأول (أي أن النص بالنسبة له abbc)
• هل a في النمط تتطابق مع a في النص؟ نعم
• ينتقل لمطابقة b، هل b في النمط تتطابق مع b في النص؟ نعم
• ينتقل لمطابقة b الثانية في النمط، هل b في النمط تتطابق مع b في النص؟ نعم
• ينتقل لمطابقة c في النمط، هل c في النمط تتطابق مع c في النص؟ نعم
• إكتملت المطابقة

يقوم المحرك بإعادة تطبيق النمط مع تغيير البدايات إذا حدث تطابق جزئي ثم بعد ذلك بعد ذلك فشل استطمال مطابقة باقي النمط، لكن هناك حالات لايكون المحرك متأكد من الإستحالة، وهي الحالات التي يستخددم فيها محددات الكميات Regex quantifiers أو البدائل Regex alternations، وهي حالات لايضطر فيها المحرك للبدء من جديد عند الفشل وإنما يجرب خيارات أخرى في النمط. وسنتحدث عن ذلك باستفاضة ولكن للتوضيح فقط سنشرح مثال بسيط على ذلك.

المثال التالي أستخدم فيه جزء لم نتحدث عنه حتى الآن، لذلك لاتهتم بتفاصيله ولكن ما أريد منك معرفته أن .* تقوم بمطابقة كل شيء بغض النظر عن نوعه. ستعرف كيف ذلك في المواضيع الخاصة بها.

في النمط a.*d نطلب من النمط البحث عن كل شيء يبدأ بـ a وينتهي بـ d وعند تطبيق النمط على النص a-sd فيقوم المحرك بالتالي:

• هل a في النمط تتطابق مع a في النص؟ نعم
• ينتقل المحرك لتطبيق النمط .* والذي يقوم بمطابقة أي شيء صفر أو أكثر من مرة
• فيقوم .* بمطابقة باقي النص بالكامل [ien]-sd[/ien]
• ينتقل المحرك لرمز d في النمط ثم يبحث في النص فلايجد شيء فالنص انتهى لأن .* قامت بذلك
• في هذه الحالة لايعتبر المحرك أنه فشل بالكامل ولكنه يعتبر أن مطابقة باقي النص بالكامل مع النمط .* ليس بالشيء الحكيم، فيمكنه أن يتخلى عن جزء من المطابقة بحيث يطابق [ien]-s[/ien] فقط
• ثم ينتقل مرة أخرى للحرف d في النمط ويطابقه مع d في النص فيحدث تطابق.

هذه الحالة من التخلي عن جزء من المطابقة لصالح مطابقة شيء آخر تسمى عملية التتبع الخلفي Regex backtracking ولهذه العملية تفصيل خاص نشرحها في موضوع منفصل، ولكن حتى هذا الحد لابد أن تفرق بين إعادة النمط بالكامل عند التأكد من الاستحالة وبين التتبع الخلفي.

إلى هنا نكون قد وضحنا كيفية عمل محركات التعبيرات المنتظمة، وما هو المنطق المتبع في اتخاذ القرار، ويمكننا الآن أن نتحدث عن خصائص وإمكانيات وأساليب محركات التعبيرات المنتظمة في البحث عن النصوص.

محركات ترجمة التعبيرات المنتظمة في PHP

محركات ترجمة التعبيرات المنتظمة في اللغات الحديثة كما ذكرنا من النوع NFA، وهناك العديد من المحركات الخاصة بمعالجة التعبيرات المنتظمة، وكل محرك له خواصه وأسلوبهه في ترجمة ومعالجة التعبير المنتظمة، يسمى هذا الأسلوب بالنكهة الخاصة بالمحرك Regex flavor، وتدعم php نوعان من محركات ترجمة الـ Regex:

• PCRE: Perl compatible regular expressions
• POSIX: Portable Operating System Implementation

وكل منها له ما يميزه من الخصائص والتي يمكن الاستفادة منها بسهولة في php ، والأكثر شيوعا هو محرك PCRE.