التعبير النمطي

التعبير النمطي (يُختصر إلى regex أو regexp )، ^{[ 1 ]} ويُشار إليه أحيانًا بالتعبير المنطقي ، ^{[ 2 ] [ 3 ]} هو سلسلة من الأحرف تُحدد نمط مطابقة في النص . عادةً ما تُستخدم هذه الأنماط بواسطة خوارزميات البحث عن السلاسل النصية لعمليات "البحث" أو "البحث والاستبدال" ، أو للتحقق من صحة المدخلات . وقد طُوّرت تقنيات التعبير النمطي في علوم الحاسوب النظرية ونظرية اللغات الرسمية .

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

تُستخدم التعابير النمطية في محركات البحث ، وفي مربعات حوار البحث والاستبدال في معالجات النصوص ومحرراتها ، وفي أدوات معالجة النصوص مثل sed و AWK ، وفي التحليل المعجمي . وتدعم العديد من لغات البرمجة التعابير النمطية. وغالبًا ما تُسمى تطبيقات المكتبات " محركًا " ^{[ 4 ] [ 5 ]} ، والعديد منها متاح لإعادة الاستخدام.

ظهرت التعابير النمطية عام 1951، عندما وصف عالم الرياضيات ستيفن كول كلين اللغات المنتظمة باستخدام ترميزه الرياضي المسمى بالأحداث المنتظمة . ^{[ 6 ] [ 7 ]} وقد نشأت هذه التعابير في علوم الحاسوب النظرية ، في فروع نظرية الأوتوماتا (نماذج الحوسبة) ووصف وتصنيف اللغات الرسمية ، مدفوعةً بمحاولة كلين وصف الشبكات العصبية الاصطناعية المبكرة . (قدّم كلين التعابير النمطية كبديل لمصطلح "المفهوم" الذي ابتكره ماكولوتش وبيتس ، لكنه أقرّ قائلاً: "نرحب بأي اقتراحات لمصطلح أكثر وصفًا". ^{[ 8 ]} ) ومن بين التطبيقات المبكرة الأخرى لمطابقة الأنماط لغة SNOBOL ، التي لم تستخدم التعابير النمطية، بل استخدمت بدلاً منها بنيات مطابقة الأنماط الخاصة بها.

بدأ استخدام التعابير النمطية على نطاق واسع منذ عام 1968 في مجالين رئيسيين: مطابقة الأنماط في محررات النصوص ^{[ 9 ]} والتحليل المعجمي في المترجمات ^{[ 10 ]} . ومن أوائل استخدامات التعابير النمطية في البرامج، قيام كين تومسون بتضمين ترميز كلين في محرر QED كوسيلة لمطابقة الأنماط في ملفات النصوص ^{[ 9 ] [ 11 ] [ 12 ] [ 13 ]} . ولتحقيق السرعة، قام تومسون بتطبيق مطابقة التعابير النمطية باستخدام الترجمة الفورية (JIT) على كود IBM 7094 في نظام المشاركة الزمنية المتوافق ، وهو مثال مبكر هام على الترجمة الفورية ^{[ 14 ]} . ثم أضاف هذه الميزة لاحقًا إلى محرر يونكس ed ، مما أدى في النهاية إلى استخدام أداة البحث الشهيرة grep للتعابير النمطية ("grep" كلمة مشتقة من أمر البحث عن التعابير النمطية في محرر ed، وتعني "بحث شامل عن التعابير النمطية وطباعة الأسطر المطابقة"). ^{[ 15 ]} في نفس الفترة التي طور فيها تومسون برنامج QED، قام فريق من الباحثين، من بينهم دوغلاس تي. روس، بتنفيذ أداة تعتمد على التعابير النمطية تُستخدم للتحليل المعجمي في تصميم المترجمات . ^{[ 10 ]}g/re/p

استُخدمت العديد من الصيغ المختلفة لهذه الأشكال الأصلية من التعابير النمطية في برامج يونكس ^{[ 13 ]} في مختبرات بيل خلال سبعينيات القرن الماضي، بما في ذلك lex و sed و AWK و expr ، وفي برامج أخرى مثل vi و Emacs (الذي يتميز ببنية وسلوك خاصين به غير متوافقين). لاحقًا، اعتُمدت التعابير النمطية في نطاق واسع من البرامج، ووُحِّدت هذه الصيغ المبكرة في معيار POSIX.2 عام 1992.

في ثمانينيات القرن العشرين، ظهرت التعابير النمطية الأكثر تعقيدًا في لغة بيرل ، والتي اشتُقت في الأصل من مكتبة تعابير نمطية كتبها هنري سبنسر (1986)، الذي كتب لاحقًا تطبيقًا لها في لغة Tcl يُسمى Advanced Regular Expressions . ^{[ 16 ]} مكتبة Tcl هي تطبيق هجين يجمع بين NFA و DFA ، ويتميز بأداء مُحسّن. من بين مشاريع البرمجيات التي اعتمدت تطبيق سبنسر للتعابير النمطية في Tcl، نذكر PostgreSQL . ^{[ 17 ]} لاحقًا، توسعت بيرل في مكتبة سبنسر الأصلية لإضافة العديد من الميزات الجديدة. ^{[ 18 ]} يهدف جزء من تصميم Raku (المعروفة سابقًا باسم Perl 6) إلى تحسين تكامل التعابير النمطية في بيرل، وزيادة نطاقها وقدراتها للسماح بتعريف قواعد تحليل التعابير . ^{[ 19 ]} والنتيجة هي لغة مصغرة تُسمى قواعد Raku ، تُستخدم لتعريف قواعد Raku، بالإضافة إلى توفير أداة للمبرمجين في هذه اللغة. تحافظ هذه القواعد على الميزات الحالية لتعبيرات Perl 5.x النمطية، ولكنها تسمح أيضًا بتعريف محلل تنازلي متكرر على نمط BNF عبر القواعد الفرعية.

بدأ استخدام التعابير النمطية في معايير المعلومات المهيكلة لنمذجة المستندات وقواعد البيانات في ستينيات القرن الماضي، وتوسع نطاقه في ثمانينياته مع ترسيخ معايير صناعية مثل ISO SGML (التي سبقتها ANSI "GCA 101-1983"). وتُشكل التعابير النمطية جوهر معايير لغة تحديد البنية ، ويتضح استخدامها في صيغة مجموعات عناصر DTD . قبل استخدام التعابير النمطية، كانت العديد من لغات البحث تسمح باستخدام أحرف البدل البسيطة، مثل "*" لمطابقة أي تسلسل من الأحرف، و"؟" لمطابقة حرف واحد. ولا تزال آثار ذلك موجودة حتى اليوم في صيغة glob لأسماء الملفات، وفي عامل SQLLIKE .

بدأ فيليب هازل في عام 1997 بتطوير PCRE (التعبيرات النمطية المتوافقة مع بيرل)، والتي تحاول محاكاة وظائف التعبيرات النمطية في بيرل بشكل وثيق، وتستخدمها العديد من الأدوات الحديثة بما في ذلك PHP وخادم Apache HTTP . ^{[ 20 ]}

اليوم، تحظى التعابير النمطية بدعم واسع في لغات البرمجة، وبرامج معالجة النصوص (وخاصة المحللات المعجمية)، ومحررات النصوص المتقدمة، وبعض البرامج الأخرى. يُعد دعم التعابير النمطية جزءًا من المكتبة القياسية للعديد من لغات البرمجة، بما في ذلك جافا وبايثون ، وهو مُدمج في بنية لغات أخرى، مثل بيرل وإي سي إم إيه سكريبت . في أواخر العقد الثاني من الألفية، بدأت عدة شركات في تقديم تطبيقات للأجهزة، ووحدات FPGA ، ^{[ 21 ]} ووحدات معالجة الرسومات ^{[ 22 ]} لمحركات التعابير النمطية المتوافقة مع PCRE، والتي تتميز بسرعتها مقارنةً بتطبيقات وحدة المعالجة المركزية .

يُستخدم مصطلح " التعابير النمطية " ( regex ) غالبًا للإشارة إلى الصيغة النصية القياسية والمحددة لتمثيل أنماط مطابقة النصوص، وذلك تمييزًا لها عن الصيغة الرياضية الموضحة أدناه. كل حرف في التعبير النمطي (أي كل حرف في السلسلة التي تصف نمطه) إما أن يكون حرفًا خاصًا (metacharacter ) له معنى خاص، أو حرفًا عاديًا له معنى حرفي. على سبيل المثال، في التعبير النمطي b.'b'، يُعد الحرف 'b' حرفًا عاديًا يُطابق الحرف 'b' فقط، بينما يُعد الحرف '.' حرفًا خاصًا يُطابق جميع الأحرف باستثناء سطر جديد. لذلك، يُطابق هذا التعبير النمطي، على سبيل المثال، 'b%' أو 'bx' أو 'b5'. يُمكن استخدام الأحرف الخاصة والأحرف العادية معًا لتحديد نص ذي نمط معين أو لمعالجة عدد من حالاته. قد تتفاوت مطابقة الأنماط من التطابق التام إلى التشابه العام، وذلك وفقًا للأحرف الخاصة. على سبيل المثال، .يُعدّ النمط العام [a-z](يطابق جميع الأحرف الصغيرة من 'a' إلى 'z') نمطًا أقل عمومية ونمطًا bدقيقًا (يطابق الحرف 'b' فقط). صُممت صيغة الأحرف الخاصة خصيصًا لتمثيل الأهداف المحددة بطريقة موجزة ومرنة لتوجيه أتمتة معالجة النصوص لمجموعة متنوعة من بيانات الإدخال، بشكل يسهل كتابته باستخدام لوحة مفاتيح ASCII القياسية .

من أبسط الأمثلة على استخدام التعبيرات النمطية في هذا السياق تحديد كلمة مكتوبة بطريقتين مختلفتين في محرر النصوصseriali[sz]e ؛ على سبيل المثال، يطابق التعبير النمطي كلاً من "serialise" و"serialize". ويمكن استخدام الأحرف البديلة لهذا الغرض أيضاً، ولكنها محدودة في أنماطها، نظراً لقلة الأحرف الخاصة بها وبساطة أساسها اللغوي.

يُستخدم عادةً رمز البدل في مطابقة أسماء الملفات المتشابهة، بينما تُستخدم التعابير النمطية (regex) في التطبيقات التي تُطابق أنماط النصوص بشكل عام. على سبيل المثال، يُطابق التعبير النمطي المسافات البيضاء الزائدة في بداية أو نهاية السطر. ومن التعابير النمطية المتقدمة التي تُطابق أي رقم: .^[ \t]+|[ \t]+$[+-]?(\d+(\.\d*)?|\.\d+)([eE][+-]?\d+)?

يقوم معالج التعبيرات النمطية بترجمة التعبير النمطي المذكور أعلاه إلى تمثيل داخلي يمكن تنفيذه ومطابقته مع سلسلة نصية تمثل النص المراد البحث فيه. أحد الأساليب الممكنة هو خوارزمية تومسون لإنشاء آلة حالة منتهية غير حتمية (NFA)، والتي يتم تحويلها لاحقًا إلى آلة حالة منتهية حتمية (DFA)، ثم يتم تشغيل آلة الحالة المنتهية الحتمية الناتجة على سلسلة النص المستهدفة للتعرف على السلاسل الفرعية التي تطابق التعبير النمطي. يوضح الشكل مخطط آلة الحالة المنتهية غير الحتمية (NFA) المُستمد من التعبير النمطي ، حيث يرمز s بدوره إلى تعبير نمطي أبسط، والذي تمت ترجمته بشكل متكرر إلى آلة الحالة المنتهية غير الحتمية N ( s ).N(s*)s*

يُحدد التعبير النمطي، الذي يُسمى غالبًا بالنمط ، مجموعة من السلاسل النصية المطلوبة لغرض معين. إحدى الطرق البسيطة لتحديد مجموعة محدودة من السلاسل النصية هي سرد ​​عناصرها . مع ذلك، توجد طرق أكثر إيجازًا: على سبيل المثال، يمكن تحديد المجموعة التي تحتوي على السلاسل النصية الثلاث "Handel" و"Händel" و"Haendel" باستخدام النمط `<Handel> H(ä|ae?)ndel`؛ نقول إن هذا النمط يُطابق كل سلسلة من السلاسل الثلاث. مع ذلك، توجد طرق عديدة لكتابة تعبير نمطي لنفس مجموعة السلاسل النصية: على سبيل المثال، (Hän|Han|Haen)delيُحدد التعبير النمطي `<Handel>` أيضًا نفس مجموعة السلاسل الثلاث في هذا المثال.

توفر معظم النماذج الرسمية العمليات التالية لإنشاء التعبيرات النمطية.

"أو" المنطقي

يفصل خط عمودي بين البدائل. على سبيل المثال، يمكن مطابقة "رمادي" أو "رمادي".gray|grey

التجميع

تُستخدم الأقواس لتحديد نطاق وأسبقية المعاملات ( من بين استخدامات أخرى). على سبيل المثال، تُعدّ كل gray|greyمن و نمطين متكافئين يصفان مجموعة "الرمادي" أو "الرمادي".gr(a|e)y

التحديد الكمي

يُحدد المُحدد الكمي الذي يلي عنصرًا ما (مثل رمز أو حرف أو مجموعة) عدد مرات تكرار العنصر السابق. ومن أكثر المحددات الكمية شيوعًا علامة الاستفهام? ، والنجمة* (المشتقة من نجمة كلين )، وعلامة الجمع+ ( كلين بلس ).

?	تشير علامة الاستفهام إلى عدم وجود العنصر السابق أو وجوده مرة واحدة فقطcolou?r . على سبيل المثال، يطابق كلاً من "color" و "colour".
*	تشير علامة النجمة إلى صفر أو أكثر من مرات ظهور العنصر السابق. على سبيل المثال، ab*cيطابق "ac" و"abc" و"abbc" و"abbbc" وهكذا.
+	تشير علامة الجمع إلى ظهور العنصر السابق مرة واحدة أو أكثرab+c . على سبيل المثال، يطابق "abc" و"abbc" و"abbbc" وما إلى ذلك، ولكنه لا يطابق "ac".
{n}[ 23 ]	تمت مطابقة العنصر السابق بالضبط n مرة.
{min,}[ 23 ]	تمت مطابقة العنصر السابق 8 مرات أو أكثر.
{,max}[ 23 ]	تتم مطابقة العنصر السابق حتى الحد الأقصى من المرات.
{min,max}[ 23 ]	تمت مطابقة العنصر السابق على الأقل لعدد أدنى من المرات، ولكن ليس أكثر من عدد أقصى من المرات.

بطاقة جامحة

يُطابق الرمز البديل .أي حرف. على سبيل المثال،

a.bيطابق أي سلسلة تحتوي على "a"، ثم أي حرف، ثم "b".

a.*bيطابق أي سلسلة تحتوي على الحرف "a"، ثم الحرف "b" في نقطة لاحقة.

يمكن دمج هذه التركيبات لتشكيل تعبيرات معقدة بشكل تعسفي، تمامًا كما يمكن للمرء أن يبني تعبيرات حسابية من الأرقام والعمليات + و - و × و ÷.

تختلف الصيغة الدقيقة للتعبيرات النمطية بين الأدوات ومع السياق؛ يتم تقديم المزيد من التفاصيل في قسم  الصيغة .

تصف التعابير النمطية اللغات المنتظمة في نظرية اللغات الرسمية . ولها نفس القدرة التعبيرية للقواعد النحوية المنتظمة . لكن لغة التعابير النمطية نفسها هي لغة خالية من السياق .

يُطابق نمط التعبير النمطي سلسلة نصية مُستهدفة . يتكون النمط من سلسلة من الذرات . الذرة هي نقطة واحدة داخل نمط التعبير النمطي، ويحاول مطابقتها مع السلسلة النصية المُستهدفة. أبسط ذرة هي قيمة حرفية، ولكن تجميع أجزاء من النمط لمطابقة ذرة يتطلب استخدام أحرف خاصة. تُساعد الأحرف الخاصة في تكوين: الذرات ؛ مُحددات الكمية التي تُحدد عدد الذرات (وما إذا كانت مُحددة كمية جشعة أم لا)؛ حرف "أو" المنطقي، الذي يُقدم مجموعة من البدائل، وحرف "ليس" المنطقي، الذي ينفي وجود الذرة؛ ومراجع خلفية للإشارة إلى الذرات السابقة لنمط الذرات المُكمل. تتم المطابقة، ليس عند مطابقة جميع ذرات السلسلة النصية، بل عند مطابقة جميع ذرات النمط في التعبير النمطي. الفكرة هي جعل نمط صغير من الأحرف يُمثل عددًا كبيرًا من السلاسل النصية المُحتملة، بدلاً من تجميع قائمة كبيرة بجميع الاحتمالات الحرفية.( )

يوجد حوالي أربعة عشر حرفًا خاصًا، بحسب معالج التعبيرات النمطية، وهي أحرف قد تحمل معناها الحرفي أو لا ، وذلك تبعًا للسياق، أو ما إذا كانت مسبوقة بتسلسل هروب ، وهو في هذه الحالة الشرطة المائلة العكسية \. تستخدم التعبيرات النمطية الحديثة والموسعة وفقًا لمعيار POSIX الأحرف الخاصة أكثر من معناها الحرفي، ولتجنب "الخطأ الناتج عن الشرطة المائلة العكسية" أو ما يُعرف بـ"متلازمة عود الأسنان " ، فإنها تتضمن آلية هروب للأحرف الخاصة إلى الوضع الحرفي؛ ولكن في البداية، تكون الأحرف الخاصة الأربعة الموجودة بين قوسين حرفية في المقام الأول ، ثم "تتخلص" من هذا المعنى المعتاد لتصبح أحرفًا خاصة. وتُطبق المعايير الشائعة كلا الأمرين. الأحرف الخاصة الشائعة هي و . أما الأحرف الشائعة التي تصبح أحرفًا خاصة عند الهروب منها فهي و .( ){ } {}[]()^$.|*+?\dswDSWN

توفر العديد من الميزات الموجودة في جميع مكتبات التعبيرات النمطية الحديثة تقريبًا قوة تعبيرية تتجاوز اللغات النمطية . على سبيل المثال، تسمح العديد من التطبيقات بتجميع التعبيرات الفرعية باستخدام الأقواس واستدعاء القيمة التي تطابقها في نفس التعبير (المراجع الخلفية ). هذا يعني، من بين أمور أخرى، أن النمط يمكن أن يطابق سلاسل من الكلمات المتكررة مثل "بابا" أو "ويكي ويكي"، والتي تُسمىمربعاتفي نظرية اللغة الرسمية. نمط هذه السلاسل هو(.+)\1.

لغة المربعات ليست منتظمة، وليست خالية من السياق ، وذلك بسبب معضلة الضخ . ومع ذلك، فإن مطابقة الأنماط مع عدد غير محدود من المراجع الخلفية، كما تدعمها العديد من الأدوات الحديثة، لا تزال حساسة للسياق . ^{[ 44 ]} تُعدّ مشكلة مطابقة أي عدد من المراجع الخلفية مشكلةً كاملةً من فئة NP ، ويتزايد وقت تنفيذ الخوارزميات المعروفة أُسّيًا مع ازدياد عدد مجموعات المراجع الخلفية المستخدمة. ^{[ 45 ]}

مع ذلك، لا تزال العديد من الأدوات والمكتبات والمحركات التي توفر هذه البنى تستخدم مصطلح " التعبير النمطي" لوصف أنماطها. وقد أدى ذلك إلى ظهور مصطلحات مختلفة، حيث يحمل مصطلح "التعبير النمطي" معانيَ مختلفة في نظرية اللغات الرسمية ومطابقة الأنماط. ولهذا السبب، لجأ البعض إلى استخدام مصطلحات مثل regex أو regexp أو ببساطة pattern لوصف النمط. يكتب لاري وول ، مؤلف لغة البرمجة بيرل، في مقال عن تصميم راكو:

إنّ مصطلح "التعابير النمطية" [...] لا يرتبط ارتباطًا وثيقًا بالتعابير النمطية الحقيقية. ومع ذلك، فقد تطور هذا المصطلح مع تطور قدرات محركات مطابقة الأنماط لدينا، لذا لن أحاول هنا مخالفة الضرورة اللغوية. ومع ذلك، سأستخدم مصطلح "regex" (أو "regexen" عندما أكون في مزاجٍ لغويٍّ أنجلو-ساكسوني). ^{[ 19 ]}

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

تعتمد الطريقة الأقدم والأسرع على نتيجة في نظرية اللغات الرسمية تسمح بتحويل أي آلة حالة منتهية غير حتمية (NFA) إلى آلة حالة منتهية حتمية (DFA). يمكن إنشاء آلة الحالة المنتهية الحتمية بشكل صريح، ثم تشغيلها على سلسلة الإدخال الناتجة رمزًا رمزًا. يستغرق إنشاء آلة الحالة المنتهية الحتمية لتعبير نمطي بحجم m وقتًا وذاكرة من رتبة O (2^ ^m )، ولكن يمكن تشغيلها على سلسلة بحجم n في زمن O ( n ). تجدر الإشارة إلى أن حجم التعبير هو الحجم بعد توسيع الاختصارات، مثل المحددات الكمية العددية.

يتمثل أحد الأساليب البديلة في محاكاة الأوتوماتا غير القطعية (NFA) مباشرةً، وذلك ببناء كل حالة من حالات الأوتوماتا القطعية (DFA) عند الطلب ثم التخلص منها في الخطوة التالية. يحافظ هذا الأسلوب على الأوتوماتا القطعية ضمنيًا ويتجنب التكلفة الأسية للبناء، لكن تكلفة التشغيل ترتفع إلى O ( mn ). يُطلق على الأسلوب الصريح اسم خوارزمية الأوتوماتا القطعية، بينما يُطلق على الأسلوب الضمني اسم خوارزمية الأوتوماتا غير القطعية. غالبًا ما تُسمى إضافة التخزين المؤقت إلى خوارزمية الأوتوماتا غير القطعية بخوارزمية "الأوتوماتا القطعية الكسولة"، أو ببساطة خوارزمية الأوتوماتا القطعية دون تمييز. تتميز هذه الخوارزميات بالسرعة، لكن استخدامها لاسترجاع التعبيرات الفرعية المجمعة، والقياس الكمي الكسول، والميزات المشابهة يُعد أمرًا معقدًا. ^{[ 50 ] [ 51 ]} تتضمن التطبيقات الحديثة عائلة re1- re2 -sregex المستندة إلى كود كوكس.

تعتمد الخوارزمية الثالثة على مطابقة النمط مع سلسلة الإدخال باستخدام التراجع . تُعرف هذه الخوارزمية عادةً باسم NFA، ولكن هذا المصطلح قد يكون مُربكًا. قد يكون وقت تشغيلها أُسّيًا، وهو ما يظهر في التطبيقات البسيطة عند المطابقة مع تعابير تحتوي على كلٍ من التناوب والكمية غير المحدودة، مما يُجبر الخوارزمية على النظر في عدد متزايد أُسّيًا من الحالات الفرعية. قد يُسبب هذا السلوك مشكلة أمنية تُعرف باسم هجوم حجب الخدمة باستخدام التعابير النمطية (ReDoS).(a|aa)*b

على الرغم من أن تطبيقات التراجع لا توفر سوى ضمان أسي في أسوأ الحالات، إلا أنها توفر مرونة وقدرة تعبيرية أكبر بكثير. على سبيل المثال، أي تطبيق يسمح باستخدام المراجع الخلفية، أو يُنفذ الإضافات المختلفة التي قدمتها لغة بيرل، يجب أن يتضمن نوعًا من التراجع. تحاول بعض التطبيقات الجمع بين أفضل ما في الخوارزميتين من خلال تشغيل خوارزمية DFA سريعة أولًا، ثم اللجوء إلى خوارزمية تراجع أبطأ عند مصادفة مرجع خلفي أثناء المطابقة. يستخدم برنامج GNU grep (وخوارزمية gnulib DFA الأساسية) هذه الاستراتيجية. ^{[ 52 ]}

تم تحقيق خوارزميات ذات زمن تشغيل شبه خطي باستخدام خوارزميات تعتمد على بوير-مور (BM) وتقنيات تحسين DFA ذات الصلة، مثل المسح العكسي. ^{[ 53 ]} يستخدم GNU grep، الذي يدعم مجموعة واسعة من صيغ POSIX وامتداداتها، خوارزمية بوير-مور (BM) للتصفية المسبقة في المرحلة الأولى، ثم يستخدم DFA ضمنيًا. أما Wu agrep ، الذي يُنفذ المطابقة التقريبية، فيجمع التصفية المسبقة في DFA باستخدام BDM (مطابقة DAWG العكسية). ويُوسّع BNDM الخاص بـ NR-grep تقنية BDM باستخدام التوازي على مستوى البتات Shift-Or. ^{[ 54 ]}

توجد بعض البدائل النظرية للتراجع في المراجع الخلفية، وتكون "أسسها" أقل تعقيدًا لأنها مرتبطة فقط بعدد المراجع الخلفية، وهي خاصية ثابتة في بعض لغات التعبير النمطي مثل POSIX. إحدى الطرق البسيطة التي تُكرر آلة الحالة المحدودة غير المتراجعة لكل ملاحظة مرجع خلفي لها تعقيد من${\displaystyle {\mathrm {O} }(n^{2k+2})}$الوقت و​${\displaystyle {\mathrm {O} }(n^{2k+1})}$مساحة لكومة قش بطول n و k مرجعًا خلفيًا في التعبير النمطي. ^{[ 55 ]} يقدم العمل النظري القائم على أتمتة الذاكرة حدًا أدق بناءً على عقد المتغيرات "النشطة" المستخدمة، وإمكانية متعددة الحدود لبعض التعبيرات النمطية ذات المراجع الخلفية. ^{[ 56 ]}

نظريًا، يمكن مطابقة أي مجموعة رموز باستخدام التعابير النمطية طالما أنها مُعرَّفة مسبقًا. أما من الناحية التطبيقية، فقد كُتبت التعابير النمطية في الأصل لاستخدام أحرف ASCII كمجموعة رموز، مع أن مكتبات التعابير النمطية تدعم العديد من مجموعات الأحرف الأخرى . توفر العديد من محركات التعابير النمطية الحديثة دعمًا جزئيًا على الأقل لـ Unicode . في معظم الحالات، لا يهم نوع مجموعة الأحرف، ولكن قد تظهر بعض المشكلات عند توسيع التعابير النمطية لدعم Unicode.

• الترميز المدعوم . تتوقع بعض مكتبات التعبيرات النمطية العمل على ترميز معين بدلاً من أحرف يونيكود المجردة. يتطلب العديد منها ترميز UTF-8 ، بينما قد يتوقع البعض الآخر UTF-16 أو UTF-32 . في المقابل، لا يتقيد كل من بيرل وجافا بترميز معين، بل يعملان داخليًا على الأحرف التي تم فك ترميزها.
• نطاق يونيكود المدعوم . تدعم العديد من محركات التعبيرات النمطية المستوى الأساسي متعدد اللغات فقط ، أي الأحرف التي يمكن ترميزها باستخدام 16 بت فقط. حاليًا (اعتبارًا من عام 2016)) عدد قليل فقط من محركات التعبيرات النمطية (مثل محركات Perl و Java) يمكنها التعامل مع نطاق Unicode الكامل المكون من 21 بت.
• توسيع نطاقات الأحرف الموجهة نحو ASCII لتشمل Unicode . على سبيل المثال، في تطبيقات ASCII، [x-y]تكون نطاقات الأحرف من الشكل صالحةً عندما يكون للحرفين x و y نقاط ترميز في النطاق [0x00,0x7F] ويكون رمز النقطة x ≤ رمز النقطة y . ويتمثل التوسيع الطبيعي لهذه النطاقات إلى Unicode في تغيير شرط أن تكون نقاط النهاية في النطاق [0x00,0x7F] إلى شرط أن تكون في النطاق [0x0000,0x10FFFF]. مع ذلك، لا يكون هذا هو الحال في الواقع العملي. فبعض التطبيقات، مثل تطبيق gawk ، لا تسمح بنطاقات الأحرف التي تعبر كتل Unicode. يُعدّ نطاق مثل [0x61,0x7F] صالحًا لأنّ كلا طرفيه يقعان ضمن كتلة الأحرف اللاتينية الأساسية، وكذلك نطاق [0x0530,0x0560] لأنّ كلا طرفيه يقعان ضمن كتلة الأحرف الأرمنية، بينما يُعدّ نطاق مثل [0x0061,0x0532] غير صالح لأنه يشمل كتلًا متعددة من يونيكود. تسمح محركات أخرى، مثل محرك محرر Vim ، بتجاوز الكتل، ولكن يجب ألا يزيد الفرق بين قيم الأحرف عن 256 حرفًا. ^{[ 57 ]}
• عدم حساسية حالة الأحرف . تؤثر بعض علامات عدم حساسية حالة الأحرف على أحرف ASCII فقط، بينما تؤثر علامات أخرى على جميع الأحرف. تحتوي بعض المحركات على علامتين مختلفتين، إحداهما لـ ASCII والأخرى لـ Unicode. كما يختلف تحديد الأحرف التي تنتمي إلى فئات POSIX.
• تُعدّ خاصية عدم حساسية حالة الأحرف من الخصائص المنطقية في البحث النصي، على غرار خاصية عدم حساسية حالة الأحرف في نظام ASCII. وقد أدخل نظام Unicode أنظمة كتابة أبجدية لا تُراعي حالة الأحرف، مثل ديفاناغاري ، ولذلك لا تنطبق عليها هذه الخاصية. أما بالنسبة لأنظمة الكتابة مثل الصينية، فيبدو التمييز بين الكتابة التقليدية والمبسطة منطقيًا. وفي الكتابة العربية، قد يكون من المرغوب فيه عدم مراعاة موضع الحرف في بداية الكلمة أو وسطها أو نهايتها أو حتى في حالة الأحرف المنفردة . وفي الكتابة اليابانية، قد يكون عدم مراعاة الفرق بين الهيراغانا والكاتاكانا مفيدًا في بعض الأحيان.
• التوحيد القياسي . يحتوي يونيكود على أحرف مركبة . وكما هو الحال في الآلات الكاتبة القديمة، يمكن أن يتبع الأحرف الأساسية (المسافات البيضاء، وعلامات الترقيم، والرموز، والأرقام، أو الحروف) رمز واحد أو أكثر من الرموز غير الفاصلة (عادةً علامات التشكيل، مثل علامات التشكيل التي تُعدّل الحروف) لتشكيل حرف واحد قابل للطباعة؛ ولكن يوفر يونيكود أيضًا مجموعة محدودة من الأحرف المركبة مسبقًا، أي الأحرف التي تتضمن بالفعل حرفًا مركبًا واحدًا أو أكثر. يجب مطابقة تسلسل الحرف الأساسي + الأحرف المركبة مع الحرف المركب المفرد المطابق (لا يمكن تجميع سوى بعض هذه التسلسلات المركبة مسبقًا في حرف يونيكود واحد، ولكن هناك عدد لا نهائي من التسلسلات المركبة الأخرى الممكنة في يونيكود، وهي ضرورية للغات مختلفة، باستخدام حرف مركب واحد أو أكثر بعد الحرف الأساسي الأولي؛ قد تتضمن هذه التسلسلات المركبة حرفًا أساسيًا أو أحرفًا مركبة مركبة جزئيًا مسبقًا، ولكن ليس بالضرورة بالترتيب المتعارف عليه وليس بالضرورة باستخدام التركيبات المتعارف عليها). تُسمى عملية توحيد تسلسلات الحرف الأساسي + الأحرف المركبة عن طريق تحليل هذه التسلسلات المتكافئة بشكل أساسي ، قبل إعادة ترتيبها في الترتيب الأساسي (وإعادة تركيب بعض الأحرف المركبة في الحرف الأساسي الرائد اختيارياً) بالتطبيع.
• رموز تحكم جديدة . أدخلت يونيكود، من بين رموز أخرى، علامات ترتيب البايتات وعلامات اتجاه النص. قد يتطلب التعامل مع هذه الرموز طريقة خاصة.
• تقديم فئات الأحرف لكتل ​​يونيكود، والنصوص، والعديد من خصائص الأحرف الأخرى . خصائص الكتل أقل فائدة بكثير من خصائص النصوص، لأن الكتلة الواحدة قد تحتوي على نقاط ترميز من عدة نصوص مختلفة، والنص الواحد قد يحتوي على نقاط ترميز من عدة كتل مختلفة. ^{[ 58 ]} في لغة بيرل ومكتبتها java.util.regex، تطابق الخصائص من الشكل ` \p{InX}x` أو ` y` \p{Block=X}الأحرف في الكتلة X ، بينما تطابق الخصائص من الشكل `x` أو `y` نقاط الترميز غير الموجودة في تلك الكتلة. وبالمثل، ` x` أو `y` أو ` y` تطابق أي حرف في النص الأرمني. بشكل عام، `x` تطابق أي حرف إما بالخاصية الثنائية X أو بالفئة العامة X. على سبيل المثال، `x` أو `y` أو ` y` تطابق أي حرف كبير. تشمل الخصائص الثنائية التي ليست فئات عامة `x` و`y` و`y` و` y`. ومن أمثلة الخصائص غير الثنائية `x` و`y` و` y` .\P{InX}\P{Block=X}\p{Armenian}\p{IsArmenian}\p{Script=Armenian}\p{X}\p{Lu}\p{Uppercase_Letter}\p{GC=Lu}\p{White_Space}\p{Alphabetic}\p{Math}\p{Dash}\p{Bidi_Class=Right_to_Left}\p{Word_Break=A_Letter}\p{Numeric_Value=10}

تدعم معظم لغات البرمجة ذات الأغراض العامة إمكانيات التعبيرات النمطية، إما بشكل أصلي أو عبر المكتبات .

تُعدّ التعابير النمطية مفيدة في مجموعة واسعة من مهام معالجة النصوص، وبشكل أعم في معالجة السلاسل النصية ، حيث لا يشترط أن تكون البيانات نصية. تشمل التطبيقات الشائعة التحقق من صحة البيانات ، واستخراج البيانات (وخاصةً استخراجها من مواقع الويب )، ومعالجة البيانات ، والتحليل البسيط ، وتطوير أنظمة تمييز بناء الجملة ، والعديد من المهام الأخرى.

تتيح بعض برامج النشر المكتبي المتطورة استخدام التعابير النمطية لتطبيق أنماط النصوص تلقائيًا، مما يوفر على مصمم الصفحات عناء القيام بذلك يدويًا لكل ما يمكن مطابقته بواسطة التعبير النمطي. على سبيل المثال، بتحديد نمط أحرف يحوّل النص إلى أحرف صغيرة ، ثم استخدام التعبير النمطي [A-Z]{4,}لتطبيق هذا النمط، سيتم عرض أي كلمة تتكون من أربعة أحرف كبيرة متتالية أو أكثر تلقائيًا بأحرف صغيرة.

على الرغم من فائدة التعابير النمطية في محركات البحث على الإنترنت ، إلا أن معالجتها على كامل قاعدة البيانات قد تستهلك موارد حاسوبية هائلة، وذلك تبعًا لتعقيد التعابير النمطية وتصميمها. ورغم أن مديري الأنظمة يستطيعون في كثير من الأحيان تشغيل استعلامات تعتمد على التعابير النمطية داخليًا، إلا أن معظم محركات البحث لا توفر دعمًا لها للعامة. ومن الاستثناءات البارزة محركا بحث جوجل البرمجي وإكساليد . مع ذلك، أُغلق محرك بحث جوجل البرمجي في يناير 2012. ^{[ 59 ]}

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

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

تُستخدم الاصطلاحات التالية في الأمثلة. ^{[ 60 ]}

الحرف (الأحرف) الخاص؛ يحدد عمود الأحرف الخاصة صيغة التعبير النمطي التي يتم عرضها =~ m// ;; يشير إلى عملية مطابقة التعبيرات النمطية في لغة بيرل =~ s/// ;; يشير إلى عملية استبدال باستخدام التعبيرات النمطية في لغة بيرل

جميع هذه التعابير النمطية تشبه في تركيبها لغة بيرل. أما التعابير النمطية القياسية في نظام POSIX فهي مختلفة.

ما لم يُذكر خلاف ذلك، فإن الأمثلة التالية تتوافق مع لغة برمجة بيرل ، الإصدار 5.8.8، 31 يناير 2006. وهذا يعني أن التطبيقات الأخرى قد تفتقر إلى دعم بعض أجزاء بناء الجملة الموضحة هنا (مثل التعبير النمطي الأساسي مقابل التعبير النمطي الموسع، \( \)أو ()عدم وجود \dبدلاً من POSIX[:digit:] ).

تتطابق القواعد والاصطلاحات المستخدمة في هذه الأمثلة مع تلك المستخدمة في بيئات البرمجة الأخرى أيضًا. ^{[ 61 ]}

$string1 = "Hello World\n" ; if ( $string1 =~ m/...../ ) { print "$string1 has length >= 5.\n" ; }

يجب أن يكون طول عبارة "Hello World" أكبر من أو يساوي 5.

$string1 = "Hello World\n" ; if ( $string1 =~ m/(H..).(o..)/ ) { print "We matched '$1' and '$2'.\n" ; }

لقد طابقنا كلمتي "Hel" و "o W".

$string1 = "Hello World\n" ; if ( $string1 =~ m/l+/ ) { print "يوجد حرف واحد أو أكثر متتالي "l" في $string1.\n" ; }

يوجد حرف "l" واحد أو أكثر متتالي في عبارة "Hello World".

$string1 = "Hello World\n" ; if ( $string1 =~ m/H.?e/ ) { print "يوجد حرف 'H' وحرف 'e' مفصولان بـ " ; print "0-1 حرف (مثلاً، He Hue Hee).\n" ; }

يوجد حرف "H" وحرف "e" مفصولان بـ 0-1 حرف (على سبيل المثال، He Hue Hee).

$string1 = "Hello World\n" ; if ( $string1 =~ m/ ( l.+?o)/ ) { print "المطابقة غير الجشعة مع 'l' متبوعة بحرف واحد أو أكثر هي 'llo' بدلاً من 'llo Wo'.\n" ; }

المطابقة غير الجشعة مع الحرف 'l' متبوعًا بحرف واحد أو أكثر هي 'llo' بدلاً من 'llo Wo'.

$string1 = "Hello World\n" ; if ( $string1 =~ m/el*o/ ) { print "يوجد حرف 'e' متبوعًا من صفر إلى عدة أحرف" ; print "حرف 'l' متبوعًا بحرف 'o' (مثل: eo، elo، ello، elllo).\n" ; }

يوجد حرف 'e' متبوعًا من صفر إلى العديد من أحرف 'l' متبوعة بحرف 'o' (على سبيل المثال، eo، elo، ello، elllo).

$string1 = "Hello World\n" ; if ( $string1 =~ m/l{1,2}/ ) { print "يوجد جزء فرعي يحتوي على حرف l واحد على الأقل" ; print "وحرفين l على الأكثر في $string1\n" ; }

توجد سلسلة فرعية تحتوي على حرف "l" واحد على الأقل وحرفين على الأكثر في عبارة "Hello World".

$string1 = "Hello World\n" ; if ( $string1 =~ m/[aeiou]+/ ) { print "$string1 contains one or more vowels.\n" ; }

تحتوي عبارة "Hello World" على حرف علة واحد أو أكثر.

$string1 = "Hello World\n" ; if ( $string1 =~ m/(Hello|Hi|Pogo)/ ) { print "$string1 يحتوي على واحد على الأقل من Hello أو Hi أو Pogo." ; }

تحتوي عبارة "Hello World" على واحد على الأقل من الكلمات التالية: Hello أو Hi أو Pogo.

$string1 = "Hello World\n" ; if ( $string1 =~ m/llo\b/ ) { print "هناك كلمة تنتهي بـ 'llo'.\n" ; }

هناك كلمة تنتهي بـ "llo".

$string1 = "Hello World\n" ; if ( $string1 =~ m/\w/ ) { print "يوجد حرف أبجدي رقمي واحد على الأقل" ; print "حرف في $string1 (AZ, az, 0-9, _).\n" ; }

يوجد حرف أبجدي رقمي واحد على الأقل في برنامج Hello World (AZ, az, 0-9, _).

$string1 = "Hello World\n" ; if ( $string1 =~ m/\W/ ) { print "المسافة بين Hello و " ; print "World is not alphanumeric.\n" ; }

المسافة بين كلمتي "Hello" و "World" ليست مسافة أبجدية رقمية.

$string1 = "Hello World\n" ; if ( $string1 =~ m/\s.*\s/ ) { print "يوجد في $string1 حرفان من المسافات البيضاء، والتي قد" ; print " مفصولان بأحرف أخرى.\n" ; }

في عبارة "Hello World" يوجد حرفان للمسافة البيضاء، ويمكن فصلهما بأحرف أخرى.

$string1 = "Hello World\n" ; if ( $string1 =~ m/\S.*\S/ ) { print "يحتوي $string1 على حرفين غير مسافة بيضاء، و" ; print " قد يفصل بينهما أحرف أخرى.\n" ; }

في عبارة "Hello World" يوجد حرفان غير مسافات بيضاء، ويمكن فصلهما بأحرف أخرى.

$string1 = "99 زجاجة بيرة على الحائط." ; if ( $string1 =~ m/(\d+)/ ) { print "$1 هو الرقم الأول في '$string1'\n" ; }

99 هو الرقم الأول في عبارة "99 زجاجة بيرة على الحائط".

$string1 = "Hello World\n" ; if ( $string1 =~ m/\D/ ) { print "At least one character in $string1" ; print " is not a digit.\n" ; }

حرف واحد على الأقل في عبارة "Hello World" ليس رقماً.

$string1 = "Hello World\n" ; if ( $string1 =~ m/^He/ ) { print "$string1 starts with the characters 'He'.\n" ; }

تبدأ عبارة "Hello World" بالحرف "هو".

$string1 = "Hello World\n" ; if ( $string1 =~ m/rld$/ ) { print "$string1 عبارة عن سطر أو سلسلة نصية " ; print "تنتهي بـ 'rld'.\n" ; }

عبارة "Hello World" هي سطر أو سلسلة نصية تنتهي بـ 'rld'.

$string1 = "Hello\nWorld\n" ; if ( $string1 =~ m/\AH/ ) { print "$string1 is a string " ; print "that starts with 'H'.\n" ; }

عبارة "Hello World" هي سلسلة نصية تبدأ بالحرف "H".

$string1 = "Hello\nWorld\n" ; if ( $string1 =~ m/d\n\z/ ) { print "$string1 is a string " ; print "that ends with 'd\\n'.\n" ; }

عبارة "Hello World" هي سلسلة نصية تنتهي بـ 'd\n'.

$string1 = "Hello World\n" ; if ( $string1 =~ m/[^abc]/ ) { print "$string1 contains a character other than " ; print "a, b, and c.\n" ; }

تحتوي عبارة "Hello World" على حرف آخر غير a و b و c.

يمكن غالبًا إنشاء التعابير النمطية ("المستنتجة" أو "المتعلمة") بناءً على مجموعة من سلاسل الأمثلة. يُعرف هذا باستقراء اللغات المنتظمة ، وهو جزء من مشكلة استقراء القواعد النحوية في نظرية التعلم الحاسوبي . رسميًا، عند إعطاء أمثلة لسلاسل نصية في لغة منتظمة، وربما أيضًا أمثلة لسلاسل نصية ليست في تلك اللغة المنتظمة، يُمكن استنتاج قواعد نحوية لتلك اللغة، أي تعبير نمطي يُولّد تلك اللغة. لا يُمكن استنتاج جميع اللغات المنتظمة بهذه الطريقة (انظر تحديد اللغة في النهاية )، ولكن يُمكن استنتاج العديد منها. على سبيل المثال، يُمكن استخدام مجموعة الأمثلة {1، 10، 100}، ومجموعة الأمثلة المضادة {11، 1001، 101، 0} لاستنتاج التعبير النمطي 1⋅0* (1 متبوعًا بصفر أو أكثر من الأصفار).

• مقارنة محركات التعبيرات النمطية
• شكل باكوس-ناور الموسع
• مطابقة الأحرف البديلة
• قواعد الشجرة المنتظمة
• بناء طومسون - يحول التعبير النمطي إلى آلة حالة محدودة غير حتمية مكافئة (NFA).

• الوسائط المتعلقة بالتعبيرات النمطية (Regex) على ويكيميديا ​​كومنز
• ISO/IEC/IEEE 9945:2009 تكنولوجيا المعلومات - المواصفات الأساسية لواجهة نظام التشغيل المحمول (POSIX)، الإصدار 7
• التعبيرات النمطية، معيار IEEE 1003.1-2024، مجموعة Open Group
• قائمة مفتوحة المصدر لموارد التعبيرات النمطية