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

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

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

  • دنباله‌ای از نویسه‌های «car» در هر متن، از قبیل «car", "cartoon» یا «bicarbonate»
  • لغت «car» در زمانی که به صورت جداگانه استفاده شود
  • لغت «car» وقتی که قبل از «blue» یا «red» آمده باشد
  • یک نویسهٔ «$» که پس از آن یک یا چند رقم بیاید و پس از آن به صورت اختیاری یک ممیز بیاید و پس از ممیز دقیقاً دو رقم اضافه قرار داشته باشد (مانند ‎ «$۱۰»‎ یا ‎ «$۲۴۵٫۹۹»‎)

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

مفاهیم اولیه

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

بولی «یا» (or)

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

گروه‌بندی

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

سور

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

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

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

تاریخچه

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

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

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

تعریف رسمی

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

  • (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 , تعریف کرد. مثلاً:*{"۰","۱"} مجموعه محدودی از رشته‌های باینری است.

مثال
  • 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[5] آن‌ها را کاراکتر معمولی جلوه دهیم. همچنین به جای کاراکتر 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.

کاربرد

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

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

منابع
  1. Vertical bar
  2. Asterisk
  3. Plus and minus signs
  4. In computer science, a regular grammar is a formal grammar that describes a regular language.
  5. Escape character
  • ویکی‌پدیای انگلیسی
  • 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. ۲۵۵–۳۰۰.
  • "The Single UNIX ® Specification, Version 2". The Open Group. 1997. |contribution= ignored (help)
  • "The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition". The Open Group. 2004. |contribution= ignored (help)

برای مطالعهٔ بیشتر
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.