عبارت باقاعده

در علوم رایانه، عبارت باقاعده، که تحت عنوان regex یا regexp (مخفف عبارت انگلیسی regular expression) نیز نامیده می‌شود به معنی تطبیق رشته در متن است، که از قبیل نویسه‌های خاص، کلمات و الگوهایی از نویسه‌ها می‌باشد. یک عبارت باقاعده با زبان معمولی نوشته می‌شود که می‌تواند توسط یک پردازشگر عبارت باقاعده، یا یک برنامه که به عنوان تولیدکنندهٔ مترجم یا بررسی‌کنندهٔ متن و تشخیص قسمت‌هایی از آن به وسیلهٔ مشخصات استفاده شود.

این نمونه‌ها می‌توانید قابلیت‌ها محدودی که عبارت با قاعده می‌تواند انجام دهد را نشان دهد:

• دنباله‌ای از نویسه‌های «car» در هر متن، از قبیل «car»، «cartoon» یا «bicarbonate»
• لغت «car» در زمانی که به صورت جداگانه استفاده شود
• لغت «car» وقتی که قبل از «blue» یا «red» آمده باشد
• یک نویسهٔ «$» که پس از آن یک یا چند رقم بیاید و پس از آن به صورت اختیاری یک ممیز بیاید و پس از ممیز دقیقاً دو رقم اضافه قرار داشته باشد (مانند ‎«$10»‎ یا ‎«$245.99»‎)

عبارت‌های باقاعده می‌توانند خیلی پیچیده‌تر از این مثال‌ها باشند.

مفاهیم اولیه

عبارت با قاعده مجموعه ای از رشته ها مشخص است.برای مشخص کردن این رشته ها قوانین کوتاهتر از زمانی که لیستی از اعضای این مجموعه است.مثلا, مجموعه که 3 رشته بدین صورت است:Handel, Händel, Haendel , به شکل H(ä|ae?)ndel است.همچنین اگر حاقل یک عبارت منظم موجود باشد که با یک عضو خاص مجموعه یکی باشد آنگاه تعداد نامحدودی از این نوع عبارات داریم.برای ساختن عبارات با قائده میتوان از عملیات های زیر استفاده کرد.

بولی "یا" (or)

یکخط عمودی است که 2 آلترناتیو را جا میکند:gray|grey که همان "gray" or "grey" است.

گروه بندی

کمانک که برای تعریف دامنه واولویت بندی عملگرا به کار میرود. مثلا:gray|grey و gr(a|e)y معادل یکدیگرند و هر دو مجموعه "gray" و "grey" را توصیف میکنند.

سور

سور، در منطق فلسفی و منطق ریاضی، نشانه‌ای است که دایرهٔ مصداق‌ها را مشخص می‌کند. سورها شامل «هر» (∀)، «هیچ» و «برخی» (∃) هستند.سور ها معروف عبارتند از ستاره و علامت سؤال و علامت مثبت و منفی و ستاره کلین است.

این ساختارها میتوانند ترکیبی از چند عبارت دلخواه باشد.

نحو دقیق عبارات با قاعده از نظر علامت و حرف با یکدیگر متفاوت است.

تاریخچه

ریشه عبارات با قاعده درزبان صوری و نظریه اتوماتا است.و هر دوقسمتی از علوم نظری رایانه اند.این رشته به مطالعه مدل های محاسباتی و راه های توضیح وتوصیف زبان ها میپردازند.ریاضیدان معروف استفان کل کلین از این مدل برای توصیف مفاهیم ریاضی به نام مجموعه منظمکه در سال ۱۹۳۰ (میلادی) روش کار میکرد استفاه کرد .زبان اسنبل اجرایی از تطبیق الگو ولی با عبارات با قاعده یکسان نبود.کنت تامسون از مفهوم کلین استفاده کرد و با کمک یکیکردن الگوهای پرونده نوشتاری , ویرایشگر متن را به وجود آورد.او سپس این قابلیت را به یونیکس اضافه کرد که منجر به استفاده عبارت با قاعده گرپ در جستجو ها شد. از آن زمان بسیاری از تغییرات انطباق اصلی تامپسون از عبارات منظم به طور گسترده در یونیکس و AWK وایمکس و لکس استفاده شده است.

فرضیه رسمی زبان

عبارات با قاعده زبان منظم را درزبان صوری توضیح میدهد.قدرت بیان آن ها مانند گرامر منظم یکی است.

تعریف رسمی

عبارات منظم از تعدادی نمادهای ثابت و اپراتور تشکیل شده است که مشخص کننده مجموعه ای از این رشته ها وعملگرا ها در این مجموعه است.این یک تعریف رسمی است و در کتاب های مربوط به ترجمه زبان ها یافت میشود.با توجه به حرف Σ , شرح های زیر به عنوانعبارات با قاعده تعریف میشوند:

• (empty set) با ∅, به معنی مجموعه ∅ است.
• (empty string) با ε , نشان دهنده مجموعه ای است که دارای رشته های خالی است و هیچ کاراکتری ندارد.
• (literal character) مثل a در Σ نشاندهنده مجموعه ای است که فقط دارای کاراکتر aاست.

با توجه به عبارت منظم R,S , عملگرا های زیر برای تعریف عبارت با قاعده تعریف میشوند.

• (الحاق) RS بدین صورت معنی میشوند:

{ αβ | α in set described by expression R and β in set described by S } مثلا:
    {"ab", "c"}{"d", "ef"} = {"abd", "abef", "cd", "cef"}

• (تناوب) R | S که نشان دهنده اجتماع بین مجموعه های R و S است.مثلا:

if R describes {"ab", "c"} and S describes {"ab", "d", "ef"}, expression R | S describes {"ab", "c", "d", "ef.

• (ستاره کلین) نشاندهنده کوچکترین زیرمجموعه R است که و شامل ε و نسبت به عمل الحاق بسته است.این مجموعه ای از رشته هایی است که میتوان با متصل کردن تعداد محدودی از رشته های R , تعریف کرد. مثلا:*{"0","1"} مجموعه محدودی از رشته های باینری است.

مثال

• a|b* نشاندهنده {ε, "a", "b", "bb", "bbb", ...} است.
• (a|b)* نشاندهنده گروهی از مجموعه ها است که فقط دارای "a" و "b" است: {ε, "a", "b", "aa", "ab", "ba", "bb", "aaa", ...}.
• ab*(c|ε) نشاندهنده مجموعه ای از رشته ها است که با "a" شروع میشود.و بعد آن هیچ یا با چندین b ,c می آید: {"a", "ac", "ab", "abc", "abb", "abbc", ...}.

نحو (سینتکس)

مجموعه ای از کاراکتر ها که نشاندهنده فعالیتی هستند.اما میتوانیم با استفاده از کاراکتر Escape آن هارا کاراکتر معمولی جلوه دهیم.همچنین به جای کاراکتر EScape از "\" استفاده کرد.

عبارت باقاعده بر مبنای پازیکس

یونیکس‌های سنتی نیز همان قواعد مشترک را در عبارت با قاعده دارد اما امکان دارد در بعضی از ابزار متفاوت است. پازیکس (POSIX) که مخفف «‎ Portable Operating System Interface [for Unix]‎» است، عبارت است از مجموعه استانداردهایی که برای نامگذاری و تعریف شمایل رابط برنامه‌نویسی کاربردی در محیط‌های شبه-یونیکس در آی‌تریپل‌ایی تعریف شده‌اند. این استانداردها تحت نام کلی IEEE 1003 و نام بین‌المللی ISO/IEC 9945 شناخته می‌شوند، امکان همسان‌سازی و ارتباط و پرت کردن آسان‌تر بین محیط‌های فوق‌الذکر را فراهم می‌آورد. واژهٔ پازیکس پیشنهاد بنیانگذار بنیاد نرم‌افزار آزاد، ریچارد استالمن بود. در سینتکس BREکه مخفف (Basic Regular Expressions) اغلب کاراکتر ها تحت الفظی است و فقط با خودشان برابرند. مثلا a برابر "a" است.استثنا های زیرنیز وجود دارد که متا کاراکتر گویند.

Metacharacter	Description
.	Matches any single character (many applications exclude newlines, and exactly which characters are considered newlines is flavor-, character-encoding-, and platform-specific, but it is safe to assume that the line feed character is included). Within POSIX bracket expressions, the dot character matches a literal dot. For example, a.c matches "abc", etc., but [a.c] matches only "a", ".", or "c".
[ ]	A bracket expression. Matches a single character that is contained within the brackets. For example, [abc] matches "a", "b", or "c". [a-z] specifies a range which matches any lowercase letter from "a" to "z". These forms can be mixed: [abcx-z] matches "a", "b", "c", "x", "y", or "z", as does [a-cx-z]. The - character is treated as a literal character if it is the last or the first (after the ^) character within the brackets: [abc-], [-abc]. Note that backslash escapes are not allowed. The ] character can be included in a bracket expression if it is the first (after the ^) character: []abc].
[^ ]	Matches a single character that is not contained within the brackets. For example, [^abc] matches any character other than "a", "b", or "c". [^a-z] matches any single character that is not a lowercase letter from "a" to "z". Likewise, literal characters and ranges can be mixed.
^	Matches the starting position within the string. In line-based tools, it matches the starting position of any line.
$	Matches the ending position of the string or the position just before a string-ending newline. In line-based tools, it matches the ending position of any line.
BRE: \( \) ERE: ( )	Defines a marked subexpression. The string matched within the parentheses can be recalled later (see the next entry, \n). A marked subexpression is also called a block or capturing group.
\n	Matches what the nth marked subexpression matched, where n is a digit from 1 to 9. This construct is theoretically irregular and was not adopted in the POSIX ERE syntax. Some tools allow referencing more than nine capturing groups.
*	Matches the preceding element zero or more times. For example, ab*c matches "ac", "abc", "abbbc", etc. [xyz]* matches "", "x", "y", "z", "zx", "zyx", "xyzzy", and so on. \(ab\)* matches "", "ab", "abab", "ababab", and so on.
BRE: \{m,n\} ERE: {m,n}	Matches the preceding element at least m and not more than n times. For example, a\{3,5\} matches only "aaa", "aaaa", and "aaaaa". This is not found in a few older instances of regular expressions.

کاربرد

از عبارات با قاعده در مشخص کردن سینتکسو برای اعتبار سنجی داده ها استفاده میشود.همچنین از عبارات با قاعده میتوان درجویشگر و پایگاه دادهها و همچنین در منابع کامپیوتری که بر مبنای پیچیدگی محاسبه اند میتوان استفاده کرد.اگر چه در بسیاری از موضوعات از عبارت منظم مبتنی بر پرس و جو داخلی اجرا میشود، بیشتر موتورهای جستجو از رسانه ها عبارت منظم را به عموم مردم ارائه نمی دهند. البته استثنایی است که : کد های جستجو گوگل و اکسلید.

جستارهای وابسته

• زبان منظم
• فرم بکوس-نائور

منابع

• ویکی‌پدیای انگلیسی
• Aho, Alfred V. (1990). "Algorithms for finding patterns in strings". In van Leeuwen, Jan. Handbook of Theoretical Computer Science, volume A: Algorithms and Complexity. The MIT Press. pp. 255–300 
• "Regular Expressions". The Single UNIX ® Specification, Version 2. The Open Group. 1997. http://pubs.opengroup.org/onlinepubs/007908799/xbd/re.html 
• "Chapter 9: Regular Expressions". The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition. The Open Group. 2004. http://pubs.opengroup.org/onlinepubs/009695399/basedefs/xbd_chap09.html 

مطالعه بیشتر

• Comparison of regular expression engines
• Extended Backus–Naur Form
• List of regular expression software
• Regular tree grammar