پرش به محتوا

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

از ویکی‌پدیا، دانشنامهٔ آزاد
آبی نتایج تطبیق الگوی عبارت باقاعده: /r[aeiou]+/g (حرف کوچک r که پس از آن یک یا چند واکه کوچک انگلیسی می‌آید) با رنگ آبی نمایش داده شده‌اند.

عبارت باقاعده (به انگلیسی: regular expression) که به‌اختصار regex یا regexp نیز نامیده می‌شود،[۱] و گاهی با عنوان عبارت منطقی (rational expression) نیز شناخته می‌شود،[۲][۳] دنباله‌ای از نویسه‌ها است که یک الگوی تطبیق را در متن مشخص می‌کند. معمولاً این الگوها توسط الگوریتم‌های جستجوی رشته برای عملیات «یافتن» یا «یافتن و جایگزینی» روی رشته‌ها یا برای اعتبارسنجی داده‌های ورودی بهره گرفته می‌شوند. فنون عبارت باقاعده در علوم نظری رایانه و نظریه زبان‌های صوری پدید آمده‌اند.

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

عبارات باقاعده در موتورهای جستجو، در گفتگوهای جستجو و جایگزینی واژه‌پردازها و ویرایشگرهای نوشتار، در ابزارهای پردازش نوشتار مانند Sed و AWK و در تحلیل واژگانی بهره گرفته می‌شوند. عبارات باقاعده در زبان‌های برنامه‌نویسی بسیاری پشتیبانی می‌شوند. پیاده‌سازی‌های کتابخانه‌ای اغلب «موتور» نامیده می‌شوند[۴][۵] و بسیاری از آن‌ها برای بهره‌گیری مجدد در دسترس هستند.

پیشینه

[ویرایش | اشتراک‌گذاری]
استیون کول کلینی، معرفی‌کننده این مفهوم

عبارت‌های باقاعده در سال ۱۹۵۱ پدید آمدند؛ هنگامی که ریاضیدان استیون کول کلینی زبان‌های منظم را با نمادگذاری ریاضی خود با عنوان «رویدادهای منظم» توصیف کرد.[۶][۷] این مفاهیم در علوم نظری رایانه، در زیرشاخه‌های نظریه ماشین‌ها (مدل‌های محاسبات) و توصیف و طبقه‌بندی زبان‌های صوری پدیدار شدند و برانگیخته از تلاش کلینی برای توصیف شبکه‌های عصبی مصنوعی اولیه بودند. (کلینی آن را به‌عنوان جایگزینی برای اصطلاح «prehensible» مک‌کالوک و پیتس معرفی کرد، اما اذعان داشت «از هرگونه پیشنهادی برای اصطلاحی توصیفی‌تر استقبال می‌کنیم.»[۸]) از دیگر پیاده‌سازی‌های اولیه تطبیق الگو می‌توان به زبان اسنوبول اشاره کرد که از عبارت‌های باقاعده بهره نمی‌گرفت، بلکه ساختارهای تطبیق الگوی خود را داشت.

عبارت‌های باقاعده از سال ۱۹۶۸ در دو کاربرد متداول شدند: تطبیق الگو در ویرایشگر نوشتار[۹] و تحلیل واژگانی در کامپایلر.[۱۰] از نخستین نمونه‌های به‌کارگیری عبارت‌های باقاعده در قالب برنامه، هنگامی بود که کن تامسون نمادگذاری کلینی را در ویرایشگر QED جای داد تا الگوها را در پرونده‌های نوشتاری بیابد.[۹][۱۱][۱۲][۱۳] برای افزایش سرعت، تامپسون تطبیق عبارت‌های باقاعده را با کامپایل درجا به کد IBM 7090 بر روی سیستم اشتراک زمانی سازگار پیاده‌سازی کرد که نمونه‌ای مهم و اولیه از کامپایل درجا به‌شمار می‌آید.[۱۴] او بعدها این قابلیت را به ویرایشگر یونیکس ed افزود که سرانجام به بهره‌گیری ابزار جستجوی پرکاربرد گرپ از عبارت‌های باقاعده انجامید («grep» واژه‌ای است برگرفته از دستور جستجو با عبارت باقاعده در ویرایشگر ed: g/re/p به معنای «جستجوی سراسری برای عبارت باقاعده و چاپ خطوط مطابق»).[۱۵] تقریباً همزمان با توسعه QED توسط تامپسون، گروهی از پژوهشگران از جمله دوگلاس راس ابزاری مبتنی بر عبارت‌های باقاعده را برای تحلیل واژگانی در طراحی کامپایلر پیاده‌سازی کردند.[۱۰]

گونه‌های بسیاری از این شکل‌های اولیه عبارت‌های باقاعده در برنامه‌های یونیکس[۱۳] در آزمایشگاه‌های بل در دهه ۱۹۷۰ مورد کاربرد قرار گرفتند؛ از جمله لکس، Sed, AWK و Expr، و همچنین در برنامه‌هایی مانند وی‌آی و ایمکس (که نحو و رفتار خاص و ناسازگار خود را دارد). سپس regexها در طیف گسترده‌ای از برنامه‌ها پذیرفته شدند و این شکل‌های اولیه در استاندارد POSIX.2 در سال ۱۹۹۲ استانداردسازی گردیدند.

در دهه ۱۹۸۰، regexهای پیچیده‌تر در پرل پدید آمدند که در اصل از کتابخانه‌ای برای regex نوشته Henry Spencer (۱۹۸۶) مشتق شده بود؛ او بعدها پیاده‌سازی‌ای برای تی‌سی‌ال با عنوان «عبارت‌های باقاعده پیشرفته» نوشت.[۱۶] کتابخانه Tcl یک پیاده‌سازی ترکیبی از NFA و DFA است با ویژگی‌های کارایی بهبودیافته. پروژه‌های نرم‌افزاری که پیاده‌سازی عبارت باقاعده Tcl اسپنسر را پذیرفته‌اند شامل پستگرس‌کیوال می‌شوند.[۱۷] پرل بعدها کتابخانه اصلی اسپنسر را گسترش داد و ویژگی‌های بسیار جدیدی به آن افزود.[۱۸] بخشی از تلاش در طراحی Raku (که پیش از این Perl 6 نام داشت) بهبود یکپارچگی regex در پرل و گسترش دامنه و توانایی‌های آن برای امکان تعریف پارسنگ اکسپرشن گرامر است.[۱۹] حاصل این تلاش یک زبان کوچک به نام قوانین راکو است که برای تعریف دستور زبان Raku و همچنین فراهم‌آوری ابزاری برای برنامه‌نویسان این زبان بهره‌گیری می‌شود. این قوانین ویژگی‌های موجود regexهای Perl 5.x را حفظ می‌کنند، اما همچنین تعریف به سبک BNF از یک تجزیه‌کننده کاهشی بازگشتی از طریق زیرقوانین را نیز امکان‌پذیر می‌سازند.

کاربرد regexها در استانداردهای اطلاعات ساختاریافته برای مدل‌سازی سند و پایگاه داده از دهه ۱۹۶۰ آغاز شد و در دهه ۱۹۸۰ هنگامی که استانداردهای صنعتی مانند ISO SGML (که پیشتر توسط ANSI به صورت «GCA 101-1983» پایه‌گذاری شده بود) تثبیت شدند، گسترش یافت. هسته استانداردهای زبان مشخصات ساختار از regexها تشکیل شده‌است. کاربرد آن در نحو گروه عنصر DTD آشکار است. پیش از کاربرد عبارت‌های باقاعده، بسیاری از زبان‌های جستجو از جایگزین‌های ساده بهره می‌بردند؛ برای نمونه «*» برای تطبیق با هر دنباله‌ای از نویسه‌ها و «?» برای تطبیق با یک نویسه واحد. نشانه‌هایی از این رویکرد هنوز در نحو گلوب (برنامه‌نویسی) برای نام پرونده‌ها و در عملگر LIKE در اس‌کیوال دیده می‌شوند.

از سال ۱۹۹۷، Philip Hazel PCRE (عبارت‌های باقاعده سازگار با Perl) را توسعه داد که می‌کوشد قابلیت‌های regex پرل را به‌دقت شبیه‌سازی کند و توسط بسیاری از ابزارهای مدرن از جمله پی‌اچ‌پی و وب‌سرور آپاچی بهره‌گیری می‌شود.[۲۰]

امروزه regexها به‌گستردگی در زبان‌های برنامه‌نویسی، برنامه‌های پردازش نوشتار (به‌ویژه تحلیل‌گرهای واژگانی)، ویرایشگرهای نوشتار پیشرفته و برخی برنامه‌های دیگر پشتیبانی می‌شوند. پشتیبانی از regex بخشی از کتابخانه استاندارد بسیاری از زبان‌های برنامه‌نویسی از جمله جاوا و پایتون است و در نحو برخی دیگر مانند پرل و اکما اسکریپت تعبیه شده‌است. در اواخر دهه ۲۰۱۰، شماری از شرکت‌ها شروع به ارائه پیاده‌سازی‌های سخت‌افزاری، FPGA,[۲۱] GPU[۲۲] از موتورهای regex سازگار با PCRE کردند که در مقایسه با پیاده‌سازی‌های CPU سرعت بیشتری دارند.

الگوها

[ویرایش | اشتراک‌گذاری]

عبارت عبارات باقاعده یا ریجکس‌ها (regex) اغلب برای اشاره به نحو متنی استاندارد و خاصی به کار می‌رود که برای نمایش الگوهای تطابق متن بهره‌گیری می‌شود و با نمادگذاری ریاضی که در ادامه توضیح داده می‌شود، تفاوت دارد. هر نویسه در یک عبارت باقاعده (یعنی هر نویسه در رشته‌ای که الگوی آن را توصیف می‌کند) یا یک متاکاراکتر است که معنایی ویژه دارد یا نویسه‌ای معمولی که معنایی تحت‌اللفظی دارد. برای نمونه، در ریجکس b.، نویسه «b» یک نویسه تحت‌اللفظی است که تنها با «b» تطابق دارد، در حالی که «.» یک متاکاراکتر است که با هر نویسه‌ای جز سطر جدید تطابق دارد؛ بنابراین این ریجکس، برای نمونه، با «b%»، «bx» یا «b5» تطابق دارد. متاکاراکترها و نویسه‌های تحت‌اللفظی با هم می‌توانند برای شناسایی متنی با الگوی مشخص یا پردازش تعدادی از نمونه‌های آن بهره‌گیری شوند. تطابق‌های الگو ممکن است از برابری دقیق تا شباهتی بسیار کلی تغییر کنند که توسط متاکاراکترها کنترل می‌شود. برای نمونه، . یک الگوی بسیار کلی است، [a-z] (تطابق با همه حروف کوچک از «a» تا «z») کمتر کلی است و b یک الگوی دقیق است (تنها با «b» تطابق دارد). نحو متاکاراکترها به‌گونه‌ای خاص طراحی شده تا هدف‌های مشخص را به شکلی مختصر و انعطاف‌پذیر برای راهبری خودکارسازی پردازش متن روی داده‌های ورودی گوناگون نمایش دهد، به‌گونه‌ای که تایپ آن با صفحه‌کلید استاندارد ASCII آسان باشد.

یک نمونه بسیار ساده از عبارت باقاعده در این نحو، یافتن کلمه‌ای است که به دو شکل متفاوت نوشته شده در یک ویرایشگر نوشتار است؛ برای نمونه، عبارت باقاعده seriali[sz]e با هر دوی «serialise» و «serialize» تطابق دارد. نویسه‌های جانشین نیز این هدف را برآورده می‌کنند، اما در الگوپردازی محدودیت بیشتری دارند، چون متاکاراکترهای کمتر و پایه زبانی ساده‌تری دارند.

زمینه معمول نویسه‌های جانشین در همتاسازی نام‌های مشابه در فهرستی از پرونده‌هاست، در حالی که ریجکس‌ها معمولاً در برنامه‌هایی بهره‌گیری می‌شوند که الگوهای رشته‌های متنی را به‌طور کلی تطبیق می‌دهند. برای نمونه، ریجکس ^[\t]+|[\t]+$ با فاصله اضافی در ابتدا یا انتهای یک سطر تطابق دارد. یک عبارت باقاعده پیشرفته که با هر عدد اعشاری تطابق دارد، به شکل [+-]?(\d+(\.\d*)?|\.\d+)([eE][+-]?\d+)? است.

برگرداندن ترجمه ستاره کلین
(s* به معنای «صفر یا بیشتر از s»)

یک پردازشگر ریجکس یک عبارت باقاعده را با نحو فوق به یک نمایش داخلی برمی‌گرداند که می‌تواند اجرا شود و با یک رشته نمایانگر متن مورد جستجو تطابق داده شود. یکی از رویکردهای ممکن، الگوریتم ساختمان تامپسون برای ساختن یک اتوماتون تعیین‌ناپذیر متناهی (NFA) است که سپس با ساختمان پاورست قطعی می‌شود و پذیرنده متناهی معین (DFA) حاصل روی رشته متن هدف اجرا می‌شود تا زیررشته‌هایی را که با عبارت باقاعده تطابق دارند شناسایی کند. تصویر طرح NFA به صورت N(s*) را نشان می‌دهد که از عبارت باقاعده s* به دست آمده، جایی که s یک عبارت باقاعده ساده‌تر را نمایش می‌دهد که به‌نوبه خود از پیش به‌صورت بازگشتی به NFA N(s) برگردانده شده‌است.

مفاهیم پایه

[ویرایش | اشتراک‌گذاری]

یک عبارت باقاعده، که اغلب الگو نامیده می‌شود، مجموعه‌ای از رشته‌های متنی را که برای هدفی خاص نیاز است مشخص می‌کند. یک روش ساده برای مشخص کردن یک مجموعه متناهی از رشته‌ها، فهرست کردن عناصر یا اعضای آن است. با این حال، اغلب روش‌های موجزتری وجود دارد: برای مثال، مجموعه‌ای که شامل سه رشته «Handel", "Händel» و «Haendel» است را می‌توان با الگوی H(ä|ae?)ndel مشخص کرد؛ می‌گوییم این الگو با هر یک از آن سه رشته تطبیق دارد. با این حال، ممکن است روش‌های بسیاری برای نوشتن یک عبارت باقاعده برای یک مجموعه یکسان از رشته‌ها وجود داشته باشد: برای مثال، (Hän|Han|Haen)del نیز همان مجموعه سه رشته‌ای را در این مثال مشخص می‌کند.

بیشتر چارچوب‌های صوری عملیات زیر را برای ساختن عبارت‌های باقاعده فراهم می‌آورند:

«یا» بولی
یک خط عمودی گزینه‌های جایگزین را از هم جدا می‌کند. برای مثال، gray|grey می‌تواند با «gray» یا «grey» تطبیق داشته باشد.
گروه‌بندی
پرانتزها برای تعریف محدوده و تقدم عملگرها (در میان کاربردهای دیگر) بهره‌گیری می‌شوند. برای مثال، gray|grey و gr(a|e)y الگوهای معادل هستند که هر دو مجموعه «gray» یا «grey» را توصیف می‌کنند.
کمّی‌سازی
یک کمّی‌ساز پس از یک عنصر (مانند یک نشانه، نویسه یا گروه) مشخص می‌کند که عنصر پیشین چند بار مجاز است تکرار شود. رایج‌ترین کمّی‌سازها علامت پرسش ?، ستاره * (برگرفته از ستاره کلین) و علامت جمع + (کلین پلاس) هستند.
? علامت پرسش نشان‌دهنده صفر یا یک بار تکرار عنصر پیشین است. برای مثال، colou?r هم با «color» و هم با «colour» تطبیق دارد.
* ستاره نشان‌دهنده صفر یا بیشتر بار تکرار عنصر پیشین است. برای مثال، ab*c با «ac", "abc", "abbc", "abbbc» و به همین ترتیب تطبیق دارد.
+ علامت جمع نشان‌دهنده یک یا بیشتر بار تکرار عنصر پیشین است. برای مثال، ab+c با «abc", "abbc", "abbbc» و به همین ترتیب تطبیق دارد، اما با «ac» تطبیق ندارد.
{n}[۲۳] عنصر پیشین دقیقاً n بار تطبیق می‌یابد.
{min,}[۲۳] عنصر پیشین min بار یا بیشتر تطبیق می‌یابد.
{,max}[۲۳] عنصر پیشین حداکثر max بار تطبیق می‌یابد.
{min,max}[۲۳] عنصر پیشین حداقل min بار و حداکثر max بار تطبیق می‌یابد.
کاراکتر جانشین
کاراکتر جانشین . با هر نویسه‌ای تطبیق دارد. برای مثال:
a.b با هر رشته‌ای تطبیق دارد که شامل یک «a» و سپس هر نویسه‌ای و سپس «b» باشد.
a.*b با هر رشته‌ای تطبیق دارد که شامل یک «a» و در نقطه‌ای بعد از آن نویسه «b» باشد.

این ساختارها می‌توانند برای شکل‌دادن به عبارت‌های دلخواه پیچیده با یکدیگر ترکیب شوند، بسیار شبیه به آنکه از اعداد و عملیات +، −، × و ÷ برای ساختن عبارت‌های حسابی بهره می‌گیریم.

نحو دقیق عبارت‌های باقاعده در ابزارهای مختلف و بسته به زمینه متفاوت است؛ جزئیات بیشتر در بخش نحو آمده‌است.

نظریه زبان‌های صوری

[ویرایش | اشتراک‌گذاری]

زبان‌های منظم در نظریه زبان‌های صوری با عبارت‌های باقاعده توصیف می‌شوند. این عبارت‌ها از نظر قدرت بیانی با دستورهای زبان منظم برابرند. اما زبان خود عبارت‌های باقاعده، یک زبان مستقل از متن است.

تعریف صوری

[ویرایش | اشتراک‌گذاری]

عبارت‌های باقاعده از ثوابت — که مجموعه‌هایی از رشته‌ها را نشان می‌دهند — و نمادهای عملگر — که عملیات روی این مجموعه‌ها را نشان می‌دهند — تشکیل می‌شوند. تعریف زیر استاندارد است و در بیشتر کتاب‌های درسی نظریه زبان‌های صوری یافت می‌شود.[۲۴][۲۵] با داشتن یک الفبای متناهی Σ، ثوابت زیر به‌عنوان عبارت‌های باقاعده تعریف می‌شوند:

  • (مجموعه تهی) ∅ که مجموعه ∅ را نشان می‌دهد.
  • (رشته تهی) ε که مجموعه‌ای را نشان می‌دهد که تنها شامل رشته «تهی» است — رشته‌ای که هیچ نویسه‌ای ندارد.
  • (نویسه راستین) a در Σ که مجموعه‌ای را نشان می‌دهد که تنها شامل نویسه a است.

با داشتن عبارت‌های باقاعده R و S، عملیات زیر بر روی آن‌ها تعریف می‌شوند تا عبارت‌های باقاعده تولید کنند:

  • (الحاق) (RS) مجموعه رشته‌هایی را نشان می‌دهد که می‌توان با الحاق یک رشته پذیرفته‌شده توسط R و یک رشته پذیرفته‌شده توسط S (به همین ترتیب) به دست آورد. برای مثال، فرض کنید R نشان‌دهنده {"ab", "c"} و S نشان‌دهنده {"d", "ef"} باشد. آن‌گاه (RS) نشان‌دهنده {"abd", "abef", "cd", "cef"} است.
  • (جایگزینی) (R|S) اجتماع مجموعه‌های توصیف‌شده توسط R و S را نشان می‌دهد. برای مثال، اگر R نشان‌دهنده {"ab", "c"} و S نشان‌دهنده {"ab", "d", "ef"} باشد، عبارت (R|S) نشان‌دهنده {"ab", "c", "d", "ef"} است.
  • (ستاره کلین) (R*) کوچک‌ترین فوق‌مجموعه مجموعه توصیف‌شده توسط R را نشان می‌دهد که شامل ε است و تحت بستار الحاق رشته بسته‌است. این مجموعه تمام رشته‌هایی است که می‌توان با الحاق هر تعداد متناهی (از جمله صفر) از رشته‌های مجموعه توصیف‌شده توسط R ساخت. برای مثال، اگر R نشان‌دهنده {"۰", "۱"} باشد، (R*) مجموعه تمام رشته‌های دودویی متناهی (از جمله رشته تهی) را نشان می‌دهد. اگر R نشان‌دهنده {"ab", "c"} باشد، (R*) نشان‌دهنده {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "abcab", ...} است.

برای جلوگیری از پرانتز، فرض می‌شود که ستاره کلین بالاترین اولویت را دارد و پس از آن الحاق و سپس جایگزینی قرار می‌گیرد. اگر ابهامی وجود نداشته باشد، پرانتزها ممکن است حذف شوند. برای مثال، (ab)c را می‌توان به‌صورت abc نوشت و a|(b(c*)) را می‌توان به‌صورت a|bc* نوشت. بسیاری از کتاب‌های درسی از نمادهای ∪، +، یا ∨ به‌جای خط عمودی برای جایگزینی بهره می‌گیرند.

نمونه‌ها:

  • 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", ...}
  • (0|(1(01*0)*1))* مجموعه اعداد دودویی‌ای را نشان می‌دهد که مضرب ۳ هستند: { ε, "۰", "۰۰", "۱۱", "۰۰۰", "۰۱۱", "۱۱۰", "۰۰۰۰", "۰۰۱۱", "۰۱۱۰", "۱۰۰۱", "۱۱۰۰", "۱۱۱۱", "۰۰۰۰۰", ...}

مشتق یک عبارت باقاعده را می‌توان با بهره‌گیری از مشتق بروزوفسکی تعریف کرد.

قدرت بیانی و فشردگی

[ویرایش | اشتراک‌گذاری]

تعریف صوری عبارت‌های باقاعده به‌عمد کمینه است و از تعریف ? و + پرهیز می‌کند — این‌ها را می‌توان به‌صورت زیر بیان کرد: a+=aa* و a?=(a|ε). گاهی عملگر متمم افزوده می‌شود تا یک عبارت باقاعده تعمیم‌یافته به دست آید؛ در اینجا Rc با تمام رشته‌های Σ* تطبیق می‌یابد که با R تطبیق نمی‌یابند. از نظر نظری، عملگر متمم زاید است، زیرا قدرت بیانی بیشتری نمی‌بخشد. با این حال، می‌تواند یک عبارت باقاعده را بسیار فشرده‌تر کند — حذف یک عملگر متمم می‌تواند موجب انفجار نمایی دوگانه در طول آن شود.[۲۶][۲۷][۲۸]

عبارت‌های باقاعده به این معنا می‌توانند زبان‌های منظم را بیان کنند — دقیقاً همان رده زبان‌هایی که توسط پذیرنده‌های متناهی معین پذیرفته می‌شوند. با این حال، تفاوت قابل توجهی در فشردگی وجود دارد. برخی از رده‌های زبان‌های منظم را تنها می‌توان با پذیرنده‌های متناهی معینی توصیف کرد که اندازه آن‌ها به‌صورت نمایی با اندازه کوتاه‌ترین عبارت‌های باقاعده معادل رشد می‌کند. نمونه استاندارد در اینجا زبان‌های Lk هستند که از تمام رشته‌ها بر روی الفبای {a,b} تشکیل شده‌اند که حرف kام از آخر آن‌ها برابر a است. از یک سو، یک عبارت باقاعده که L4 را توصیف می‌کند به‌صورت زیر داده می‌شود:

تعمیم این الگو به Lk عبارت زیر را می‌دهد:

از سوی دیگر، ثابت شده‌است که هر پذیرنده متناهی معینی که زبان Lk را می‌پذیرد باید حداقل ۲k حالت داشته باشد. خوشبختانه، یک نگاشت ساده از عبارت‌های باقاعده به اتوماتون‌های متناهی غیرقطعی (NFA) وجود دارد که به چنین انفجاری در اندازه منجر نمی‌شود؛ به همین دلیل از NFAها اغلب به‌عنوان نمایش‌های جایگزین زبان‌های منظم بهره گرفته می‌شود. NFAها یک تغییرشکل ساده از دستورهای نوع-۳ سلسله‌مراتب چامسکی هستند.[۲۴]

در جهت مخالف، بسیاری از زبان‌هایی هستند که به‌راحتی با DFA توصیف می‌شوند اما به‌راحتی با عبارت باقاعده توصیف نمی‌شوند. برای نمونه، تعیین اعتبار یک شابک مستلزم محاسبه باقیمانده یک عدد صحیح مُدلو ۱۱ است و می‌توان آن را به‌راحتی با یک DFA یازده‌حالته پیاده‌سازی کرد. با این حال، تبدیل آن به عبارت باقاعده یک پرونده ۲٫۱۴ مگابایتی به دست می‌دهد.[۲۹]

با داشتن یک عبارت باقاعده، الگوریتم ساختمان تامپسون یک اتوماتون متناهی غیرقطعی معادل محاسبه می‌کند. تبدیل در جهت مخالف با الگوریتم کلینی انجام می‌شود.

سرانجام، بسیاری از موتورهای «عبارت باقاعده» در دنیای واقعی ویژگی‌هایی را پیاده‌سازی می‌کنند که نمی‌توان آن‌ها را با عبارت‌های باقاعده به معنای نظریه زبان‌های صوری توصیف کرد؛ بلکه آن‌ها regex‌ها را پیاده‌سازی می‌کنند. برای اطلاعات بیشتر در این مورد، بخش الگوها برای زبان‌های غیرمنظم را ببینید.

تصمیم‌گیری دربارهٔ هم‌ارزی عبارت‌های باقاعده

[ویرایش | اشتراک‌گذاری]

همان‌طور که در بسیاری از نمونه‌های بالا دیده می‌شود، بیش از یک روش برای ساختن یک عبارت باقاعده برای رسیدن به نتایج یکسان وجود دارد.

می‌توان یک الگوریتم نوشت که برای دو عبارت باقاعده داده‌شده تصمیم بگیرد آیا زبان‌های توصیف‌شده برابرند یا نه؛ این الگوریتم هر عبارت را به یک پذیرنده متناهی معین کمینه تقلیل می‌دهد و تعیین می‌کند که آیا آن‌ها یکریخت (معادل) هستند یا نه.

قوانین جبری برای عبارت‌های باقاعده را می‌توان با روشی از گیشر به دست آورد که بهترین توضیح آن از طریق یک نمونه است: برای بررسی اینکه آیا (X+Y)∗ و (X∗ Y∗)∗ زبان منظم یکسانی را برای تمام عبارت‌های باقاعده X, Y نشان می‌دهند یا نه، لازم و کافی است که بررسی شود آیا عبارت‌های باقاعده خاص (a+b)∗ و (a∗ b∗)∗ زبان یکسانی را روی الفبای Σ={a,b} نشان می‌دهند. به‌طور کلی‌تر، یک معادله E=F بین عبارت‌های باقاعده با متغیرها اگر و تنها اگر نمونه‌سازی آن با متغیرهای مختلفی که با ثابت‌های نمادی مختلف جایگزین شده‌اند برقرار باشد.[۳۰][۳۱]

هر عبارت باقاعده را می‌توان صرفاً با ستاره کلین و اجتماع مجموعه روی کلمات متناهی نوشت. این یک مسئله به‌طور شگفت‌انگیزی دشوار است. هر چند عبارت‌های باقاعده ساده هستند، هیچ روشی برای بازنویسی نظام‌مند آن‌ها به یک شکل نرمال وجود ندارد. فقدان اکسیوم در گذشته به مسئله ارتفاع ستاره منجر شد. در سال ۱۹۹۱ (۱۳۷۰)، دکستر کوزن عبارت‌های باقاعده را به‌عنوان یک جبر کلین (Kleene algebra) اکسیوماتیزه کرد و از اکسیوم‌های معادلاتی و عبارات هورن بهره گرفت.[۳۲] پیش از آن، در سال ۱۹۶۴ (۱۳۴۳)، ردکو اثبات کرده بود که هیچ مجموعه متناهی از اکسیوم‌های صرفاً معادلاتی نمی‌تواند جبر زبان‌های منظم را توصیف کند.[۳۳]

نحو

[ویرایش | اشتراک‌گذاری]

یک الگو در عبارت باقاعده با یک رشته هدف تطبیق می‌یابد. الگو از دنباله‌ای از اتم‌ها تشکیل شده‌است. اتم یک نقطه منفرد در الگوی عبارت باقاعده است که سعی می‌کند با رشته هدف تطبیق یابد. ساده‌ترین اتم یک راستین‌نماد است، اما برای گروه‌بندی بخش‌هایی از الگو جهت تطبیق با یک اتم، باید از ( ) به عنوان متاکاراکتر بهره گرفت. متاکاراکترها در ساخت موارد زیر نقش دارند: اتم‌ها؛ سنجه‌ها که نشان می‌دهند چند اتم لازم است (و اینکه آیا سنجه حریصانه است یا نه)؛ عملگر OR منطقی که مجموعه‌ای از گزینه‌ها را ارائه می‌دهد؛ عملگر NOT منطقی که وجود یک اتم را نفی می‌کند؛ و ارجاع‌های برگشتی برای اشاره به اتم‌های پیشین در یک الگوی تکمیل‌شده. تطبیق زمانی رخ نمی‌دهد که همه اتم‌های رشته تطبیق یابند، بلکه وقتی رخ می‌دهد که همه اتم‌های الگو در عبارت باقاعده تطبیق یافته باشند. ایده اصلی این است که یک الگوی کوچک از نویسه‌ها، تعداد زیادی از رشته‌های ممکن را نمایندگی کند، نه اینکه فهرست بزرگی از تمام احتمالات به صورت راستین‌نماد گردآوری شود.

بسته به پردازشگر عبارت باقاعده، حدود چهارده متاکاراکتر وجود دارد؛ نویسه‌هایی که ممکن است بسته به زمینه، یا در صورتی که «گریخته» شده باشند (یعنی پیش از آن‌ها توالی گریز آمده باشد) معنای راستین‌نماد داشته یا نداشته باشند؛ در این حالت، بک‌اسلش \ به عنوان نویسه گریز بهره برده می‌شود. عبارات باقاعده مدرن و POSIX توسعه‌یافته متاکاراکترها را بیشتر از معنای راستین‌نمادشان به کار می‌برند؛ از این رو برای جلوگیری از «بک‌اسلش‌زدگی» یا سندرم خلال‌دندان تکیه‌داده، این عبارات یک حالت گریز از متاکاراکتر به راستین‌نماد دارند؛ با این حال، در ابتدا چهار متاکاراکتر قاب‌بندی ( ) و { } اساساً راستین‌نماد هستند و «گریز» آن‌ها معنای متاکاراکتری می‌دهد. استانداردهای رایج هر دو حالت را پیاده‌سازی می‌کنند. متاکاراکترهای معمول عبارتند از {}[]()^$.|*+?\. نویسه‌های معمولی که با گریز دادن به متاکاراکتر تبدیل می‌شوند عبارتند از dswDSWN.

جداکننده‌ها

[ویرایش | اشتراک‌گذاری]

هنگام وارد کردن یک عبارت باقاعده در یک زبان برنامه‌نویسی، ممکن است به صورت یک رشته متنی معمولی نمایش داده شود و معمولاً در علامت نقل‌قول قرار گیرد؛ این روش در جاوا، C و پایتون رایج است؛ برای مثال عبارت باقاعده re به صورت "re" وارد می‌شود. با این حال، اغلب با اسلش به عنوان جداکننده نوشته می‌شود؛ مانند /re/ برای عبارت باقاعده re. این روش از اد سرچشمه می‌گیرد؛ جایی که / دستور جستجو در ویرایشگر است و عبارت /re/ می‌تواند برای مشخص کردن بازه‌ای از خطوط (منطبق با الگو) بهره برده شود که در ترکیب با دستورها دیگر استفاده می‌شود؛ مشهورترین آن‌ها g/re/p در گرپ («global regex print» یا چاپ عبارت باقاعده سراسری) است که در بیشتر سیستم‌عامل‌های مبتنی بر یونیکس، مانند توزیع‌های لینوکس، گنجانده شده‌است. قراردادی مشابه در Sed بهره برده می‌شود؛ در آن جستجو و جایگزینی با s/re/replacement/ انجام می‌شود و الگوها می‌توانند با کاما برای مشخص کردن بازه‌ای از خطوط پیوند یابند، مانند /re1/,/re2/. این نمادگذاری به ویژه به دلیل استفاده در پرل شناخته شده‌است که بخشی از نحو آن را تشکیل می‌دهد و از رشته‌های متنی عادی متمایز است. در برخی موارد، مانند sed و پرل، می‌توان از جداکننده‌های جایگزین بهره برد تا از تداخل با محتوا و نیاز به گریز دادن نمونه‌های نویسه جداکننده جلوگیری شود. برای مثال، در sed دستور s,/,X, یک / را با X جایگزین می‌کند و از کاما به عنوان جداکننده بهره می‌برد.

استاندارد IEEE POSIX

[ویرایش | اشتراک‌گذاری]

استاندارد IEEE POSIX سه سطح انطباق دارد: BRE (عبارات باقاعده پایه)،[۳۴] ERE (عبارات باقاعده توسعه‌یافته) و SRE (عبارات باقاعده ساده). SRE منسوخ‌شده است[۳۵] و BRE جایگزین آن شده‌است؛ زیرا هر دو سازگاری عقبرو را فراهم می‌کنند. زیربخش زیر که رده‌های نویسه را پوشش می‌دهد برای هر دوی BRE و ERE کاربرد دارد.

BRE و ERE در کنار هم کار می‌کنند. ERE عملگرهای ?، + و | را افزوده و نیاز به گریز دادن متاکاراکترهای ( ) و { } را برطرف می‌کند؛ این گریز دادن در BRE الزامی بود. علاوه بر این، تا زمانی که نحو استاندارد POSIX برای عبارات باقاعده رعایت شود، نحو اضافی برای کاربردهای خاص (اما سازگار با POSIX) می‌تواند وجود داشته و اغلب هم وجود دارد. اگرچه POSIX.2 برخی جزئیات پیاده‌سازی را تعریف نکرده، BRE و ERE یک «استاندارد» ارائه می‌دهند که از آن زمان به عنوان نحو پیش‌فرض ابزارهای بسیاری پذیرفته شده‌است؛ در این ابزارها، انتخاب بین حالت‌های BRE یا ERE معمولاً گزینه‌ای پشتیبانی‌شده‌است. برای مثال، GNU grep گزینه‌های زیر را دارد: «grep -E» برای ERE, "grep -G» برای BRE (پیش‌فرض)، و «grep -P» برای عبارات باقاعده پرل.

عبارات باقاعده پرل به یک استاندارد واقعی تبدیل شده‌اند و مجموعه‌ای غنی و قدرتمند از عبارات اتمی دارند. پرل سطوح «پایه» یا «توسعه‌یافته» ندارد. مانند POSIX ERE, ( ) و { } به عنوان متاکاراکتر در نظر گرفته می‌شوند مگر اینکه گریز داده شوند؛ دیگر متاکاراکترها تنها بر اساس زمینه، راستین‌نماد یا نمادین تلقی می‌شوند. قابلیت‌های اضافی شامل تطبیق تنبل، ارجاع برگشتی، گروه‌های نام‌دار ضبطی و الگوهای بازگشتی هستند.

پایه و توسعه‌یافته POSIX

[ویرایش | اشتراک‌گذاری]

در استاندارد POSIX، نحو عبارت باقاعده پایه (BRE) ایجاب می‌کند که متاکاراکترهای ( ) و { } به صورت \(\) و \{\} نوشته شوند، در حالی که نحو عبارت باقاعده توسعه‌یافته (ERE) این الزام را ندارد.

متاکاراکتر شرح
^ با موقعیت شروع در رشته تطبیق می‌یابد. در ابزارهای مبتنی بر خط، با موقعیت شروع هر خط تطبیق می‌یابد.
. با هر نویسه منفرد تطبیق می‌یابد (بسیاری از برنامه‌ها نوخط‌ها را استثنا می‌کنند؛ اینکه دقیقاً کدام نویسه‌ها نوخط به‌شمار می‌آیند به گونه، کدبندی نویسه و پلتفرم بستگی دارد، اما می‌توان با اطمینان فرض کرد که نویسه تغذیه خط جزو آن‌هاست). در عبارات براکتی POSIX، نویسه نقطه با یک نقطه راستین‌نماد تطبیق می‌یابد. برای مثال، a.c با «abc» و مانند آن تطبیق می‌یابد، اما [a.c] فقط با «a»، «.» یا «c» تطبیق می‌یابد.
[ ] یک عبارت براکتی. با یک نویسه منفرد که در داخل براکت‌ها قرار دارد تطبیق می‌یابد. برای مثال، [abc] با «a", "b» یا «c» تطبیق می‌یابد. [a-z] یک بازه را مشخص می‌کند که با هر حرف کوچک از «a» تا «z» تطبیق می‌یابد. این فرم‌ها می‌توانند ترکیب شوند: [abcx-z] با «a", "b»، «c", "x»، «y» یا «z» تطبیق می‌یابد، همان‌گونه که [a-cx-z] نیز چنین است.

نویسه - به عنوان یک نویسه راستین‌نماد تلقی می‌شود اگر آخرین یا اولین نویسه (پس از ^ در صورت وجود) داخل براکت‌ها باشد: [abc-]، [-abc]، [^-abc]. گریزهای بک‌اسلش مجاز نیستند. نویسه ] می‌تواند در یک عبارت براکتی گنجانده شود اگر اولین نویسه (پس از ^ در صورت وجود) باشد: []abc]، [^]abc].

[^] با یک نویسه منفرد که در داخل براکت‌ها قرار ندارد تطبیق می‌یابد. برای مثال، [^abc] با هر نویسه‌ای غیر از «a", "b» یا «c» تطبیق می‌یابد. [^a-z] با هر نویسه منفرد که حرف کوچک از «a» تا «z» نباشد تطبیق می‌یابد. به همین ترتیب، نویسه‌های راستین‌نماد و بازه‌ها می‌توانند ترکیب شوند.
$ با موقعیت پایانی رشته یا موقعیت درست پیش از نوخط پایان رشته تطبیق می‌یابد. در ابزارهای مبتنی بر خط، با موقعیت پایانی هر خط تطبیق می‌یابد.
( ) یک زیرعبارت نشانه‌دار، همچنین گروه ضبطی نامیده می‌شود، که برای استخراج بخش موردنظر متن ضروری است (همچنین ورودی بعدی، \n، را ببینید). حالت BRE نیاز به \( \) دارد.
\n با آنچه nامین زیرعبارت نشانه‌دار تطبیق یافته تطبیق می‌یابد؛ n یک رقم از ۱ تا ۹ است. این ساختار در استاندارد POSIX تعریف شده‌است.[۳۶] برخی ابزارها اجازه ارجاع به بیش از نه گروه ضبطی را می‌دهند. این ویژگی که به عنوان ارجاع برگشتی نیز شناخته می‌شود در حالت BRE پشتیبانی می‌شود.
* با عنصر پیشین صفر یا چند بار تطبیق می‌یابد. برای مثال، ab*c با «ac", "abc", "abbbc» و مانند آن تطبیق می‌یابد. [xyz]* با «»، «x", "y»، «z", "zx", "zyx", "xyzzy» و موارد دیگر تطبیق می‌یابد. (ab)* با «»، «ab", "abab", "ababab» و موارد دیگر تطبیق می‌یابد.
{m,n} با عنصر پیشین حداقل m و حداکثر n بار تطبیق می‌یابد. برای مثال، a{3,5} فقط با «aaa", "aaaa» و «aaaaa» تطبیق می‌یابد. این در چند نمونه قدیمی‌تر از عبارات باقاعده یافت نمی‌شود. حالت BRE نیاز به \{m,n\} دارد.

نمونه‌ها:

  • .at با هر رشته سه‌نویسه‌ای که به «at» ختم می‌شود تطبیق می‌یابد؛ از جمله «hat", "cat", "bat»، «4at»، «#at» و «at» (شروع با فاصله).
  • [hc]at با «hat» و «cat» تطبیق می‌یابد.
  • [^b]at با همه رشته‌هایی که .at با آن‌ها تطبیق می‌یابد به جز «bat» تطبیق می‌یابد.
  • [^hc]at با همه رشته‌هایی که .at با آن‌ها تطبیق می‌یابد به جز «hat» و «cat» تطبیق می‌یابد.
  • ^[hc]at با «hat» و «cat» تطبیق می‌یابد، اما فقط در ابتدای رشته یا خط.
  • [hc]at$ با «hat» و «cat» تطبیق می‌یابد، اما فقط در پایان رشته یا خط.
  • \[.\] با هر نویسه منفرد احاطه‌شده توسط «[» و «]» تطبیق می‌یابد؛ زیرا براکت‌ها گریز داده شده‌اند؛ برای مثال: «[a]", "[b]»، «[۷]»، «[@]»، «[]]» و «[ ]» (براکت فاصله براکت).
  • s.* با s و به دنبال آن صفر یا چند نویسه تطبیق می‌یابد؛ برای مثال: «s", "saw", "seed", "s3w96.7» و «s6#h%(>>>m n mQ».

بر اساس نظر Russ Cox، مشخصات POSIX نیاز دارد که زیرعبارت‌های مبهم به گونه‌ای متفاوت از پرل مدیریت شوند. کمیته قوانین پرل را با قانونی جایگزین کرد که توضیح آن ساده بود، اما قوانین «ساده» جدید در واقع پیاده‌سازی آن‌ها پیچیده‌تر بود: با ابزارهای از پیش موجود ناسازگار بودند و تعریف یک پسوند «تطبیق تنبل» (ببینید زیر) را عملاً غیرممکن می‌ساختند. در نتیجه، تعداد بسیار کمی از برنامه‌ها قوانین زیرعبارت POSIX را پیاده‌سازی می‌کنند (حتی وقتی بخش‌های دیگر نحو POSIX را پیاده‌سازی می‌کنند).[۳۷]

متاکاراکترها در POSIX توسعه‌یافته

[ویرایش | اشتراک‌گذاری]

معنای متاکاراکترهایی که با بک‌اسلش گریز داده می‌شوند در نحو عبارت باقاعده توسعه‌یافته POSIX (ERE) برای برخی نویسه‌ها معکوس می‌شود. با این نحو، بک‌اسلش سبب می‌شود متاکاراکتر به عنوان نویسه راستین‌نماد تلقی شود؛ بنابراین، برای مثال، \( \) اکنون ( ) می‌شود و \{ \} اکنون { } می‌شود. علاوه بر این، پشتیبانی از ارجاعات برگشتی \n حذف شده و متاکاراکترهای زیر افزوده می‌شوند:

متاکاراکتر شرح
? با عنصر پیشین صفر یا یک بار تطبیق می‌یابد. برای مثال، ab?c فقط با «ac» یا «abc» تطبیق می‌یابد.
+ با عنصر پیشین یک یا چند بار تطبیق می‌یابد. برای مثال، ab+c با «abc", "abbc", "abbbc» و موارد دیگر تطبیق می‌یابد، اما نه با «ac».
| عملگر انتخاب (همچنین به عنوان جایگزینی یا اجتماع مجموعه شناخته می‌شود) با عبارت پیش از عملگر یا عبارت پس از آن تطبیق می‌یابد. برای مثال، abc|def با «abc» یا «def» تطبیق می‌یابد.

نمونه‌ها:

  • [hc]?at با «at", "hat» و «cat» تطبیق می‌یابد.
  • [hc]*at با «at", "hat", "cat", "hhat", "chat", "hcat", "cchchat» و موارد دیگر تطبیق می‌یابد.
  • [hc]+at با «hat", "cat", "hhat", "chat", "hcat", "cchchat» و موارد دیگر تطبیق می‌یابد، اما نه با «at».
  • cat|dog با «cat» یا «dog» تطبیق می‌یابد.

عبارات باقاعده توسعه‌یافته POSIX اغلب می‌توانند با ابزارهای مدرن یونیکس با گنجاندن پرچم خط فرمان -E بهره برده شوند.

رده‌های نویسه

[ویرایش | اشتراک‌گذاری]

رده نویسه پس از تطبیق راستین‌نماد، پایه‌ای‌ترین مفهوم عبارت باقاعده است. این رده یک دنباله کوچک از نویسه‌ها را با مجموعه بزرگ‌تری از نویسه‌ها تطبیق می‌دهد. برای مثال، [A-Z] می‌تواند نماینده هر حرف بزرگ در الفبای انگلیسی باشد و \d می‌تواند به معنای هر رقم باشد. رده‌های نویسه برای هر دو سطح POSIX کاربرد دارند.

هنگام مشخص کردن بازه‌ای از نویسه‌ها، مانند [a-Z] (یعنی حرف کوچک a تا حرف بزرگ Z)، تنظیمات محلی رایانه محتوا را بر اساس ترتیب عددی کدبندی نویسه تعیین می‌کند. ممکن است ارقام در آن دنباله ذخیره شوند، یا ترتیب <dir dir="ltr">abc...zABC...Z</dir> یا <dir dir="ltr">aAbBcC...zZ</dir> باشد. از این رو استاندارد POSIX یک رده نویسه تعریف می‌کند که توسط پردازشگر عبارت باقاعده نصب‌شده شناخته می‌شود. آن تعاریف در جدول زیر آمده‌اند:

شرح POSIXPerl/TclVimJavaASCII
نویسه‌های ASCII \p{ASCII} [\x00-\x7F]
نویسه‌های حرف‌ورقمی [:alnum:] \p{Alnum} [A-Za-z0-9]
نویسه‌های حرف‌ورقمی به علاوه «_» \w \w \w [A-Za-z0-9_]
نویسه‌های غیر کلمه \W \W \W [^A-Za-z0-9_]
نویسه‌های حروف الفبا [:alpha:] \a \p{Alpha} [A-Za-z]
فاصله و تب [:blank:] \s \p{Blank} [\t]
مرزهای کلمه \b \< \> \b (?<=\W)(?=\w)|(?<=\w)(?=\W)
مرزهای غیرکلمه \B (?<=\W)(?=\W)|(?<=\w)(?=\w)
نویسه‌های کنترلی [:cntrl:] \p{Cntrl} [\x00-\x1F\x7F]
ارقام [:digit:] \d \d \p{Digit} یا \d [0-9]
غیر ارقام \D \D \D [^0-9]
نویسه‌های قابل مشاهده [:graph:] \p{Graph} [\x21-\x7E]
حروف کوچک [:lower:] \l \p{Lower} [a-z]
نویسه‌های قابل مشاهده و نویسه فاصله [:print:] \p \p{Print} [\x20-\x7E]
نویسه‌های نگارشی [:punct:] \p{Punct} [][!"#$%&'()*+,./:;<=>?@\^_`{|}~-]
نویسه‌های فاصله خالی [:space:] \s \_s \p{Space} یا \s [ \t\r\n\v\f]
نویسه‌های غیر فاصله خالی \S \S \S [^ \t\r\n\v\f]
حروف بزرگ [:upper:] \u \p{Upper} [A-Z]
ارقام هگزادسیمال [:xdigit:] \x \p{XDigit} [A-Fa-f0-9]

رده‌های نویسه POSIX تنها می‌توانند در داخل عبارات براکتی بهره برده شوند. برای مثال، [[:upper:]ab] با حروف بزرگ و حروف کوچک «a» و «b» تطبیق می‌یابد.

یک رده اضافی غیر POSIX که برخی ابزارها آن را می‌شناسند [:word:] است که معمولاً به صورت [:alnum:] به علاوه زیرخط تعریف می‌شود. این واقعیت را منعکس می‌کند که در بسیاری از زبان‌های برنامه‌نویسی، این نویسه‌ها همان‌هایی هستند که می‌توانند در شناسه‌ها بهره برده شوند. ویرایشگر Vim علاوه بر این بین رده‌های کلمه و سر کلمه (با استفاده از نمادگذاری \w و \h) تمایز قائل می‌شود؛ زیرا در بسیاری از زبان‌های برنامه‌نویسی، نویسه‌هایی که می‌توانند یک شناسه را شروع کنند با نویسه‌هایی که می‌توانند در موقعیت‌های دیگر ظاهر شوند یکسان نیستند: ارقام معمولاً مستثنا هستند، بنابراین یک شناسه در نمادگذاری POSIX شبیه \h\w* یا [[:alpha:]_][[:alnum:]_]* خواهد بود.

توجه داشته باشید که آنچه استانداردهای POSIX regex «رده‌های نویسه» می‌نامند، در سایر گونه‌های regex که از آن‌ها پشتیبانی می‌کنند معمولاً «رده‌های نویسه POSIX» نامیده می‌شوند. در اکثر گونه‌های دیگر regex، اصطلاح «رده نویسه» برای توصیف آن چیزی به کار می‌رود که POSIX آن را «عبارات براکتی» می‌نامد.

پرل و PCRE

[ویرایش | اشتراک‌گذاری]

به دلیل قدرت بیانی و (نسبی) سهولت خواندن، بسیاری از ابزارها و زبان‌های برنامه‌نویسی دیگر نحو مشابه پرل را پذیرفته‌اند؛ برای نمونه جاوا، جاوااسکریپت، جولیا، پایتون، روبی، کیوت، چارچوب دات‌نت مایکروسافت و اسکیمای XML. برخی زبان‌ها و ابزارها مانند بوست و پی‌اچ‌پی از چند گونه regex پشتیبانی می‌کنند. پیاده‌سازی‌های regex مشتق از پرل با یکدیگر یکسان نیستند و معمولاً زیرمجموعه‌ای از ویژگی‌های موجود در Perl 5.0 (منتشرشده در ۱۹۹۴) را پیاده‌سازی می‌کنند. پرل گاهی ویژگی‌هایی را که ابتدا در زبان‌های دیگر یافت می‌شوند در خود جای می‌دهد. برای نمونه، Perl 5.10 گسترش‌های نحوی‌ای را پیاده‌سازی می‌کند که در اصل در PCRE و پایتون توسعه یافته بودند.[۳۸]

تطبیق تنبل

[ویرایش | اشتراک‌گذاری]

در پایتون و برخی پیاده‌سازی‌های دیگر (مثلاً جاوا)، سه کمیت‌ساز متداول (*، + و ?) به‌طور پیش‌فرض حریصانه هستند، زیرا تا آنجا که ممکن است نویسه‌های بیشتری را تطبیق می‌دهند.[۳۹] عبارت باقاعده ".+" (شامل نقل‌قول‌های دوگانه) که بر روی رشته زیر اعمال می‌شود:

"Ganymede," he continued, "is the largest moon in the Solar System."

به جای تطبیق تنها بخش اول یعنی "Ganymede,"، کل خط را تطبیق می‌دهد (چون کل خط با نقل‌قول دوگانه آغاز و پایان می‌یابد). با این حال، کمیت‌سازهای یادشده را می‌توان با افزودن یک علامت سؤال، تنبل، کمینه یا بی‌میل کرد تا تا آنجا که ممکن است نویسه‌های کمتری را تطبیق دهند: ".+?" تنها "Ganymede," را تطبیق می‌دهد.[۳۹]

تطبیق مالکانه

[ویرایش | اشتراک‌گذاری]

در جاوا و پایتون ۳٫۱۱ به بالا،[۴۰] کمیت‌سازها را می‌توان با افزودن یک علامت مثبت، مالکانه کرد؛ این کار بازگشت به عقب (در موتور backtracking) را غیرفعال می‌کند، حتی اگر این کار به موفقیت تطبیق کلی کمک کند:[۴۱] در حالی که عبارت باقاعده ".*" که بر روی رشته زیر اعمال می‌شود:

"Ganymede," he continued, "is the largest moon in the Solar System."

کل خط را تطبیق می‌دهد، عبارت باقاعده ".*+" اصلاً تطبیق نمی‌دهد، زیرا .*+ کل ورودی از جمله " پایانی را مصرف می‌کند. از این‌رو، کمیت‌سازهای مالکانه بیشترین کاربرد را در کنار رده‌های نویسه نفی‌شده دارند؛ مثلاً "[^"]*+" که هنگام اعمال بر همان رشته، "Ganymede," را تطبیق می‌دهد.

گسترش رایج دیگری که همین کارکرد را دارد، گروه‌بندی اتمی است که بازگشت به عقب را برای یک گروه داخل پرانتز غیرفعال می‌کند. نحو معمول آن (?>group) است. برای نمونه، در حالی که ^(wi|w)i$ هر دو wi و wii را تطبیق می‌دهد، ^(?>wi|w)i$ تنها wii را تطبیق می‌دهد، چون موتور از بازگشت به عقب ممنوع است و نمی‌تواند پس از تطبیق «wi» تلاش کند گروه را برابر «w» قرار دهد.[۴۲]

کمیت‌سازهای مالکانه پیاده‌سازی آسان‌تری نسبت به کمیت‌سازهای حریصانه و تنبل دارند و معمولاً در زمان اجرا کارآمدتر هستند.[۴۱]

I-Regexp استاندارد IETF

[ویرایش | اشتراک‌گذاری]

RFC 9485 از IETF, "I-Regexp: یک قالب عبارت باقاعده قابل همکاری» را توصیف می‌کند. این استاندارد زیرمجموعه محدودی از اصطلاحات عبارت باقاعده را مشخص می‌کند که برای همکاری‌پذیری طراحی شده‌اند؛ یعنی در تعداد زیادی از کتابخانه‌های عبارت باقاعده همان اثر را ایجاد می‌کنند. I-Regexp همچنین به تطبیق محدود است؛ یعنی تنها یک نتیجه درست یا نادرست بین عبارت باقاعده و یک قطعه متن ارائه می‌دهد. از این‌رو، فاقد ویژگی‌های پیشرفته‌ای مانند گروه‌های ضبط، نگاه به جلو و ارجاع به عقب است.[۴۳]

الگوهایی برای زبان‌های غیرمنظم

[ویرایش | اشتراک‌گذاری]

بسیاری از ویژگی‌هایی که در تقریباً تمام کتابخانه‌های مدرن عبارات باقاعده یافت می‌شوند، قدرت بیانی‌ای فراتر از زبان‌های منظم فراهم می‌کنند. برای نمونه، بسیاری از پیاده‌سازی‌ها اجازه می‌دهند زیرعبارت‌ها با پرانتز گروه‌بندی شوند و مقداری که با آن‌ها تطبیق می‌یابد در همان عبارت فراخوانی شود (backreferences یا ارجاع پسگرد). این یعنی، از جمله، یک الگو می‌تواند رشته‌هایی مانند «papa» یا «WikiWiki» را که در نظریه زبان‌های صوری «مربع» نامیده می‌شوند، تطبیق دهد. الگو برای این رشته‌ها (.+)\1 است.

زبان مربع‌ها نه منظم است و نه مستقل از متن، به دلیل لم تزریق، اما تطبیق الگو با تعداد نامحدودی ارجاع پسگرد، که ابزارهای مدرن فراوانی از آن پشتیبانی می‌کنند، همچنان حساس‌به‌متن است.[۴۴] مسئله کلی تطبیق با هر تعداد ارجاع پسگرد NP-کامل است و زمان اجرا برای الگوریتم‌های شناخته‌شده به‌صورت نمایی با تعداد گروه‌های ارجاع پسگرد رشد می‌کند.[۴۵]

با این حال، بسیاری از ابزارها، کتابخانه‌ها و موتورهایی که چنین ساختارهایی ارائه می‌دهند همچنان اصطلاح «عبارت باقاعده» را برای الگوهایشان به کار می‌برند. این امر به نامگذاری‌ای انجامیده که در آن اصطلاح «عبارت باقاعده» در نظریه زبان صوری و تطبیق الگو معناهای متفاوتی دارد. به همین دلیل، برخی به کاربرد اصطلاح‌های regex, regexp یا به‌سادگی pattern (الگو) برای توصیف مورد دوم روی آورده‌اند. لری وال، نویسنده زبان برنامه‌نویسی پرل، در مقاله‌ای دربارهٔ طراحی راکو می‌نویسد:

«عبارات باقاعده» […] تنها ارتباطی حاشیه‌ای با عبارات باقاعده واقعی دارند. با این حال، این اصطلاح با توانایی‌های موتورهای تطبیق الگوی ما رشد کرده‌است، پس قصد ندارم در برابر ضرورت زبانی مقاومت کنم. با این حال، معمولاً آن‌ها را «regexes» می‌نامم (یا «regexen» وقتی در حال‌وهوای آنگلوساکسونی هستم).[۱۹]

اعلان‌ها

[ویرایش | اشتراک‌گذاری]
AssertionLookbehindLookahead
مثبت (?<=pattern) (?=pattern)
منفی (?<!pattern) (?!pattern)
اعلان‌های lookbehind و lookahead
در عبارات باقاعده پرل

دیگر ویژگی‌هایی که در توصیف زبان‌های منظم یافت نمی‌شوند، اعلان‌ها (assertions) هستند. از جمله این‌ها ^ و $ همه‌جاحاضر است که حداقل از سال ۱۹۷۰ به کار رفته‌اند،[۴۶] و همچنین برخی افزونه‌های پیچیده‌تر مانند lookaround که در سال ۱۹۹۴ پدیدار شدند.[۴۷] lookaroundها محدوده پیرامون یک تطبیق را تعریف می‌کنند و به خود تطبیق سرریز نمی‌کنند؛ ویژگی‌ای که تنها برای موردکاربرد جستجوی رشته مرتبط است.[نیازمند منبع] برخی از آن‌ها می‌توانند در یک زبان منظم با در نظر گرفتن محدوده‌های پیرامون به‌عنوان بخشی از زبان شبیه‌سازی شوند.[۴۸]

اعلان‌های look-ahead (?=...) و (?!...) حداقل از سال ۱۹۹۴ با شروع از پرل ۵ مستند شده‌اند.[۴۷] اعلان‌های lookbehind (?<=...) و (?<!...) از سال ۱۹۹۷ در یک commit توسط Ilya Zakharevich به Perl 5.005 مستند شده‌اند.[۴۹]

پیاده‌سازی‌ها و زمان‌های اجرا

[ویرایش | اشتراک‌گذاری]

دست‌کم سه الگوریتم متفاوت وجود دارد که تعیین می‌کنند آیا یک عبارت باقاعده با یک رشته تطابق دارد یا خیر و در صورت تطابق، چگونه.

قدیمی‌ترین و سریع‌ترین رویکرد بر پایه نتیجه‌ای در نظریه زبان‌های صوری است که طبق آن هر اتوماتون تعیین‌ناپذیر متناهی (NFA) را می‌توان به پذیرنده متناهی معین (DFA) تبدیل کرد. DFA را می‌توان به‌صورت صریح ساخت و سپس با پردازش یک‌به‌یک نمادهای رشته ورودی اجرا کرد. ساخت DFA برای یک عبارت باقاعده با اندازه m هزینه زمانی و حافظه‌ای برابر O(2m) دارد، اما می‌توان آن را روی رشته‌ای با اندازه n در زمان O(n) اجرا کرد. توجه شود که اندازه عبارت، اندازه‌ای است که پس از گسترش اختصارات مانند سنج‌های عددی به دست می‌آید.

رویکرد جایگزین، شبیه‌سازی مستقیم NFA است؛ به این معنا که هر حالت DFA به‌صورت بر حسب تقاضا ساخته می‌شود و در گام بعدی دور انداخته می‌شود. این روش DFA را ضمنی نگه می‌دارد و از هزینه ساخت نمایی اجتناب می‌کند، اما هزینه اجرا به O(mn) می‌رسد. رویکرد صریح «الگوریتم DFA» و رویکرد ضمنی «الگوریتم NFA» نامیده می‌شود. افزودن حافظه‌پنهان به الگوریتم NFA اغلب «الگوریتم DFA تنبل» یا به‌سادگی الگوریتم DFA نامیده می‌شود. این الگوریتم‌ها سریع هستند، اما کاربرد آن‌ها برای بازیابی زیرعبارات گروه‌بندی‌شده، سنج‌های تنبل و ویژگی‌های مشابه دشوار است.[۵۰][۵۱] پیاده‌سازی‌های مدرن شامل خانواده re1-re2-sregex بر پایه کد Cox هستند.

الگوریتم سوم، تطبیق الگو با رشته ورودی از طریق روش پس‌گرد است. این الگوریتم معمولاً NFA نامیده می‌شود، اما این اصطلاح می‌تواند گمراه‌کننده باشد. زمان اجرای آن می‌تواند نمایی باشد؛ این رفتار در پیاده‌سازی‌های ساده هنگام تطبیق با عباراتی مانند (a|aa)*b که هم ترکیب و هم سنج‌های نامحدود دارند نمایان می‌شود و الگوریتم را وادار می‌کند تعداد نمایی رو به افزایشی از زیرحالت‌ها را بررسی کند. این رفتار می‌تواند به یک مشکل امنیتی موسوم به انکار سرویس با عبارت باقاعده (ReDoS) منجر شود.

گرچه پیاده‌سازی‌های مبتنی بر پس‌گرد تنها در بدترین حالت ضمانت نمایی می‌دهند، انعطاف‌پذیری و قدرت بیانی بسیار بیشتری فراهم می‌کنند. برای نمونه، هر پیاده‌سازی‌ای که امکان کاربرد پس‌ارجاع‌ها را بدهد یا گسترش‌های گوناگون معرفی‌شده توسط پرل را پیاده‌سازی کند، باید نوعی پس‌گرد داشته باشد. برخی پیاده‌سازی‌ها تلاش می‌کنند بهترین هر دو الگوریتم را فراهم کنند: ابتدا الگوریتم DFA سریع را اجرا می‌کنند و تنها هنگامی که پس‌ارجاعی در حین تطابق یافت می‌شود به الگوریتم پس‌گرد که ممکن است کندتر باشد بازمی‌گردند. GNU grep (و gnulib DFA زیرین آن) از چنین راهبردی بهره می‌گیرد.[۵۲]

الگوریتم‌هایی با زمان اجرای زیرخطی با استفاده از الگوریتم‌های مبتنی بر بویر-مور (BM) و تکنیک‌های بهینه‌سازی DFA مرتبط مانند پویش معکوس به دست آمده‌اند.[۵۳] GNU grep که از طیف گسترده‌ای از نحوها و گسترش‌های POSIX پشتیبانی می‌کند، از BM برای پیش‌فیلتر اولیه و سپس از DFA ضمنی بهره می‌گیرد. Wu agrep که تطبیق تقریبی را پیاده‌سازی می‌کند، پیش‌فیلتر را در BDM (تطبیق معکوس DAWG) ادغام می‌کند. BNDM متعلق به NR-grep تکنیک BDM را با موازی‌سازی بیتی Shift-Or گسترش می‌دهد.[۵۴]

چند جایگزین نظری برای پس‌گرد در پس‌ارجاع‌ها وجود دارد و «توان‌های» آن‌ها ملایم‌تر هستند، زیرا تنها به تعداد پس‌ارجاع‌ها وابسته‌اند که ویژگی ثابتی از برخی زبان‌های regexp مانند POSIX است. یک روش ساده که یک NFA بدون پس‌گرد را به ازای هر پس‌ارجاع تکثیر می‌کند، پیچیدگی زمانی و پیچیدگی فضایی برای یک رشته جستجو با طول n و k پس‌ارجاع در عبارت باقاعده دارد.[۵۵] کارهای نظری مبتنی بر اتوماتون‌های حافظه‌دار، کران محکم‌تری بر اساس گره‌های متغیر «فعال» ارائه می‌دهند و امکان‌پذیری چندجمله‌ای را برای برخی عبارات باقاعده دارای پس‌ارجاع نشان می‌دهند.[۵۶]

یونی‌کد

[ویرایش | اشتراک‌گذاری]

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

  • رمزگذاری پشتیبانی‌شده. برخی کتابخانه‌های regex انتظار دارند با رمزگذاری خاصی کار کنند، نه با نویسه‌های انتزاعی یونی‌کد. بسیاری از آن‌ها رمزگذاری یوتی‌اف-۸ را می‌طلبند، در حالی که برخی دیگر ممکن است UTF-16 یا UTF-32 را انتظار داشته باشند. در مقابل، Perl و Java نسبت به رمزگذاری بی‌تفاوت‌اند و در درون خود با نویسه‌های رمزگشایی‌شده کار می‌کنند.
  • محدوده یونی‌کد پشتیبانی‌شده. بسیاری از موتورهای عبارات باقاعده تنها از صفحه پایه چندزبانه پشتیبانی می‌کنند؛ یعنی نویسه‌هایی که با تنها ۱۶ بیت قابل رمزگذاری هستند. در حال حاضر (از سال ۲۰۱۶) تنها چند موتور عبارات باقاعده (مانند Perl و Java) می‌توانند محدوده کامل ۲۱ بیتی یونی‌کد را پردازش کنند.
  • گسترش ساختارهای مبتنی بر اسکی به یونی‌کد. به عنوان نمونه، در پیاده‌سازی‌های مبتنی بر اسکی، بازه‌های نویسه به شکل [x-y] هنگامی معتبرند که x و y دارای موقعیت کد در بازه [0x00, 0x7F] باشند و codepoint(x) ≤ codepoint(y) برقرار باشد. گسترش طبیعی چنین بازه‌های نویسه‌ای به یونی‌کد، تنها شرط را از [0x00, 0x7F] به [0x0000, 0x10FFFF] تغییر می‌دهد. با این حال، در عمل این چنین نیست. برخی پیاده‌سازی‌ها، مانند gawk، اجازه نمی‌دهند بازه‌های نویسه از میان بلوک‌های یونی‌کد عبور کنند. بازه‌ای مانند [0x61, 0x7F] معتبر است چون هر دو انتها در بلوک لاتین پایه قرار دارند، و [0x0530, 0x0560] نیز معتبر است چون هر دو انتها در بلوک ارمنی قرار دارند، اما بازه‌ای مانند [0x0061, 0x0532] نامعتبر است زیرا چندین بلوک یونی‌کد را دربرمی‌گیرد. موتورهای دیگر، مانند ویرایشگر ویم، اجازه عبور از بلوک‌ها را می‌دهند اما مقادیر نویسه‌ها نباید بیش از ۲۵۶ واحد از هم فاصله داشته باشند.[۵۷]
  • بی‌تفاوتی نسبت به حروف بزرگ و کوچک. برخی پرچم‌های بی‌تفاوتی نسبت به حروف تنها بر نویسه‌های اسکی تأثیر می‌گذارند. برخی دیگر همه نویسه‌ها را تحت‌تأثیر قرار می‌دهند. برخی موتورها دو پرچم متمایز دارند: یکی برای اسکی و دیگری برای یونی‌کد. نویسه‌هایی که دقیقاً به رده‌های POSIX تعلق دارند نیز از موتوری به موتور دیگر متفاوت است.
  • مفاهیم مشابه بی‌تفاوتی نسبت به حروف. از آن‌جا که اسکی دارای تمایز حروف بزرگ و کوچک است، بی‌تفاوتی نسبت به حروف ویژگی منطقی‌ای در جستجوی متن شد. یونی‌کد الفباهایی بدون تمایز حروف مانند دیواناگری را معرفی کرد. برای این‌ها، حساسیت موردی کاربردی ندارد. برای خط‌هایی مانند چینی، تمایز منطقی دیگری به ذهن می‌رسد: میان صورت‌های سنتی و ساده‌شده. در خطوط عربی، بی‌تفاوتی نسبت به موقعیت‌های آغازی، میانی، پایانی و مستقل ممکن است مطلوب باشد. در ژاپنی، گاهی بی‌تفاوتی میان هیراگانا و کاتاکانا سودمند است.
  • نرمال‌سازی. یونی‌کد دارای نویسه‌های ترکیبی است. مانند ماشین‌های تحریر قدیمی، نویسه‌های پایه ساده (فاصله‌ها، نویسه‌های نگارشی، نمادها، رقم‌ها یا حروف) می‌توانند با یک یا چند نماد غیرفاصله‌ساز (معمولاً نشانه‌های تلفظی مانند علامت‌های لهجه که حروف را تغییر می‌دهند) همراه شوند تا یک نویسه قابل چاپ واحد بسازند؛ اما یونی‌کد همچنین مجموعه محدودی از نویسه‌های از پیش ترکیب‌شده را فراهم می‌کند، یعنی نویسه‌هایی که از پیش یک یا چند نویسه ترکیبی را دربردارند. یک توالی از نویسه پایه به اضافه نویسه‌های ترکیبی باید با نویسه واحد از پیش ترکیب‌شده یکسان، تطبیق داده شود (تنها برخی از این توالی‌های ترکیبی می‌توانند در یک نویسه یونی‌کدی واحد از پیش ترکیب شوند، اما توالی‌های ترکیبی بی‌شماری در یونی‌کد ممکن‌اند و برای زبان‌های گوناگون با استفاده از یک یا چند نویسه ترکیبی پس از یک نویسه پایه اولیه نیاز هستند؛ این توالی‌های ترکیبی ممکن است شامل یک نویسه پایه یا نویسه‌های ترکیبی به‌صورت جزئی از پیش ترکیب‌شده باشند، اما لزوماً در ترتیب متعارف نیستند و لزوماً از ترکیب‌های متعارف بهره نمی‌برند). فرایند استانداردسازی توالی‌های «نویسه پایه + نویسه‌های ترکیبی» از طریق تجزیه این توالی‌های هم‌ارز متعارف، پیش از مرتب‌سازی آن‌ها به ترتیب متعارف (و به‌صورت اختیاری ترکیب مجدد برخی نویسه‌های ترکیبی با نویسه پایه ابتدایی)، نرمال‌سازی نامیده می‌شود.
  • کدهای کنترلی جدید. یونی‌کد در میان کدهای دیگر، نشان‌های ترتیب بایت و نشانگرهای جهت متن را معرفی کرد. این کدها ممکن است نیاز به پردازش ویژه داشته باشند.
  • معرفی رده‌های نویسه برای بلوک‌های یونی‌کد، خط‌ها، و ویژگی‌های نویسه‌ای فراوان دیگر. ویژگی‌های بلوک بسیار کمتر از ویژگی‌های خط مفیدند، زیرا یک بلوک می‌تواند موقعیت‌های کد از چندین خط مختلف داشته باشد و یک خط می‌تواند موقعیت‌های کد از چندین بلوک مختلف داشته باشد.[۵۸] در پرل و کتابخانه الگو:Javadoc:SE، ویژگی‌هایی به شکل \p{InX} یا \p{Block=X} با نویسه‌های بلوک X تطبیق می‌یابند و \P{InX} یا \P{Block=X} با موقعیت‌های کدی که در آن بلوک نیستند تطبیق می‌یابند. به همین ترتیب، \p{Armenian}، \p{IsArmenian}، یا \p{Script=Armenian} با هر نویسه‌ای در خط ارمنی تطبیق می‌یابد. به‌طور کلی، \p{X} با هر نویسه‌ای تطبیق می‌یابد که دارای ویژگی دودویی X یا رده عمومی 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}.

پشتیبانی زبان‌ها

[ویرایش | اشتراک‌گذاری]

بیشتر زبان‌های برنامه‌نویسی همه‌منظوره از قابلیت‌های عبارت باقاعده پشتیبانی می‌کنند، یا به‌صورت بومی یا از طریق کتابخانه‌ها.

کاربردها

[ویرایش | اشتراک‌گذاری]

عبارت‌های باقاعده در طیف گسترده‌ای از وظایف پردازش نوشتار و به‌طور کلی‌تر پردازش رشته‌ها کاربرد دارند؛ حتی در مواردی که داده‌ها لزوماً متنی نیستند. کاربردهای رایج شامل اعتبارسنجی داده، استخراج داده (به‌ویژه استخراج از وب)، آماده‌سازی داده‌ها، تجزیه ساده، ساخت سامانه‌های برجسته‌سازی نحوی و بسیاری وظایف دیگر می‌شود.

برخی نرم‌افزارهای پیشرفته نشر رومیزی توانایی بهره‌گیری از عبارت‌های باقاعده را برای اعمال خودکار قالب‌بندی متن دارند و بدین ترتیب کسی که طرح‌بندی را انجام می‌دهد از زحمت انجام دستی این کار برای هر چیزی که با عبارت باقاعده قابل تطبیق است رهایی می‌یابد. برای نمونه، با تعریف یک سبک نویسه که متن را به حروف کوچک‌بزرگ (Small Caps) تبدیل می‌کند و سپس بهره‌گیری از عبارت باقاعده [A-Z]{4,} برای اعمال آن سبک، هر واژه‌ای که چهار یا بیش از چهار حرف بزرگ پشت‌سر هم داشته باشد به‌طور خودکار به‌صورت حروف کوچک‌بزرگ نمایش داده می‌شود.

گرچه عبارت‌های باقاعده در موتورهای جستجوی اینترنتی مفید خواهند بود، پردازش آن‌ها روی پایگاه داده کامل بسته به پیچیدگی و طراحی عبارت باقاعده ممکن است منابع رایانه‌ای بیش از حد مصرف کند. هرچند در بسیاری از موارد مدیران سیستم می‌توانند به‌صورت داخلی پرسش‌های مبتنی بر عبارت باقاعده اجرا کنند، اما بیشتر موتورهای جستجو پشتیبانی از عبارت باقاعده را برای عموم ارائه نمی‌دهند. استثناهای قابل توجه شامل جستجوی کد گوگل و Exalead می‌شوند. با این حال، جستجوی کد گوگل در ژانویه ۲۰۱۲ (دی ۱۳۹۰) تعطیل شد.

نمونه‌ها

[ویرایش | اشتراک‌گذاری]

قوانین نحوی خاص بسته به پیاده‌سازی، زبان برنامه‌نویسی یا کتابخانه مورد بهره‌گیری متفاوت است. افزون بر این، قابلیت‌های پیاده‌سازی‌های عبارت باقاعده ممکن است میان نسخه‌های نرم‌افزار گوناگون تفاوت داشته باشد.

از آنجا که توضیح و درک عبارت‌های باقاعده بدون نمونه دشوار است، وب‌سایت‌های تعاملی برای آزمایش عبارت‌های باقاعده منبعی سودمند برای یادگیری آن‌ها از راه آزمایش‌اند. این بخش شرحی پایه‌ای از برخی ویژگی‌های عبارت‌های باقاعده را از راه نمونه ارائه می‌دهد.

در نمونه‌ها از قراردادهای زیر بهره گرفته می‌شود.[۵۹]

metacharacter(s) ;; ستون متاکاراکتر نحو عبارت باقاعده نمایش‌داده‌شده را مشخص می‌کند

=~ m//  ;; نشان‌دهنده عملیات تطبیق عبارت باقاعده در پرل =~ s///  ;; نشان‌دهنده عملیات جایگزینی عبارت باقاعده در پرل

همه این عبارت‌های باقاعده از نحو شبه‌پرل هستند. عبارت‌های باقاعده استاندارد POSIX متفاوت‌اند.

مگر آنکه خلاف آن ذکر شده باشد، نمونه‌های زیر با زبان برنامه‌نویسی پرل، نسخه ۵٫۸٫۸، ۳۱ ژانویه ۲۰۰۶ (۱۱ بهمن ۱۳۸۴) تطابق دارند. این بدان معناست که پیاده‌سازی‌های دیگر ممکن است از بخش‌هایی از نحو نشان‌داده‌شده اینجا پشتیبانی نکنند (مثلاً عبارت باقاعده پایه در برابر توسعه‌یافته، \( \) در برابر () یا نبود \d به‌جای [:digit:] در پازیکس).

نحو و قراردادهای بهره‌گرفته‌شده در این نمونه‌ها با محیط‌های برنامه‌نویسی دیگر نیز مطابقت دارد.[۶۰]

متا­کاراکتر(ها) توضیح نمونه[۶۱]
. معمولاً با هر نویسه‌ای جز سطر جدید تطابق دارد.
درون کروشه، نقطه به‌صورت تحت‌اللفظی است.		 
$string1 = "Hello World\n";
if ($string1 =~ m/...../) {
  print "$string1 has length >= 5.\n";
}

خروجی:

Hello World
 has length >= 5.
( ) مجموعه‌ای از عناصر الگو را به یک عنصر واحد گروه‌بندی می‌کند.
هنگامی که الگویی درون پرانتز تطبیق می‌یابد، می‌توان از $1، $2، … برای ارجاع به الگوی تطبیق‌یافته قبلی بهره گرفت. برخی پیاده‌سازی‌ها ممکن است از نماد بک‌اسلش استفاده کنند، مانند \1، \2.		 
$string1 = "Hello World\n";
if ($string1 =~ m/(H..).(o..)/) {
  print "We matched '$1' and '$2'.\n";
}

خروجی:

We matched 'Hel' and 'o W'.
+ با عنصر الگوی پیشین یک یا چند بار تطابق دارد. 
$string1 = "Hello World\n";
if ($string1 =~ m/l+/) {
  print "There are one or more consecutive letter \"l\"'s in $string1.\n";
}

خروجی:

There are one or more consecutive letter "l"'s in Hello World.
? با عنصر الگوی پیشین صفر یا یک بار تطابق دارد. 
$string1 = "Hello World\n";
if ($string1 =~ m/H.?e/) {
  print "There is an 'H' and a 'e' separated by ";
  print "0-1 characters (e.g., He Hue Hee).\n";
}

خروجی:

There is an 'H' and a 'e' separated by 0-1 characters (e.g., He Hue Hee).
? عبارت باقاعده‌ای که با *، +، ? یا {M,N} پیش از آن آمده را تغییر می‌دهد تا تا حد ممکن کم‌تر تطابق یابد. 
$string1 = "Hello World\n";
if ($string1 =~ m/(l.+?o)/) {
  print "The non-greedy match with 'l' followed by one or ";
  print "more characters is 'llo' rather than 'llo Wo'.\n";
}

خروجی:

The non-greedy match with 'l' followed by one or more characters is 'llo' rather than 'llo Wo'.
* با عنصر الگوی پیشین صفر یا چند بار تطابق دارد. 
$string1 = "Hello World\n";
if ($string1 =~ m/el*o/) {
  print "There is an 'e' followed by zero to many ";
  print "'l' followed by 'o' (e.g., eo, elo, ello, elllo).\n";
}

خروجی:

There is an 'e' followed by zero to many 'l' followed by 'o' (e.g., eo, elo, ello, elllo).
{M,N} حداقل M و حداکثر N بار تطابق را مشخص می‌کند.
N را می‌توان حذف کرد و M می‌تواند ۰ باشد: {M} دقیقاً M بار تطابق می‌یابد؛ {M,} دست‌کم M بار تطابق می‌یابد؛ {0,N} حداکثر N بار تطابق می‌یابد.
x* y+ z? بنابراین معادل x{0,} y{1,} z{0,1} است.		 
$string1 = "Hello World\n";
if ($string1 =~ m/l{1,2}/) {
  print "There exists a substring with at least 1 ";
  print "and at most 2 l's in $string1\n";
}

خروجی:

There exists a substring with at least 1 and at most 2 l's in Hello World
[…] مجموعه‌ای از تطابق‌های نویسه‌ای ممکن را مشخص می‌کند. 
$string1 = "Hello World\n";
if ($string1 =~ m/[aeiou]+/) {
  print "$string1 contains one or more vowels.\n";
}

خروجی:

Hello World
 contains one or more vowels.
| احتمال‌های جایگزین را از هم جدا می‌کند. 
$string1 = "Hello World\n";
if ($string1 =~ m/(Hello|Hi|Pogo)/) {
  print "$string1 contains at least one of Hello, Hi, or Pogo.";
}

خروجی:

Hello World
 contains at least one of Hello, Hi, or Pogo.
\b با مرز پهنای صفر میان یک نویسه از رده کلمه (ببینید بعدی) و یک نویسه غیرکلمه یا لبه تطابق دارد؛ معادل

(^\w|\w$|\W\w|\w\W).

 
$string1 = "Hello World\n";
if ($string1 =~ m/llo\b/) {
  print "There is a word that ends with 'llo'.\n";
}

خروجی:

There is a word that ends with 'llo'.
\w با یک نویسه حرفی-عددی، شامل «_»، تطابق دارد؛
معادل [A-Za-z0-9_] در ASCII و
[\p{Alphabetic}\p{GC=Mark}\p{GC=Decimal_Number}\p{GC=Connector_Punctuation}]

در یونی‌کد،[۵۸] که ویژگی Alphabetic بیش از حروف لاتین را دربرمی‌گیرد و ویژگی Decimal_Number بیش از ارقام عربی را دربرمی‌گیرد.

 
$string1 = "Hello World\n";
if ($string1 =~ m/\w/) {
  print "There is at least one alphanumeric ";
  print "character in $string1 (A-Z, a-z, 0-9, _).\n";
}

خروجی:

There is at least one alphanumeric character in Hello World
 (A-Z, a-z, 0-9, _).
\W با یک نویسه غیرحرفی-عددی، بدون «_»، تطابق دارد؛
معادل [^A-Za-z0-9_] در ASCII و
[^\p{Alphabetic}\p{GC=Mark}\p{GC=Decimal_Number}\p{GC=Connector_Punctuation}]

در یونی‌کد.

 
$string1 = "Hello World\n";
if ($string1 =~ m/\W/) {
  print "The space between Hello and ";
  print "World is not alphanumeric.\n";
}

خروجی:

The space between Hello and World is not alphanumeric.
\s با یک نویسه فاصله خالی تطابق دارد؛
که در ASCII عبارت است از تب، تغذیه خط، تغذیه صفحه، بازگشت کالسکه و فاصله؛
در یونی‌کد همچنین با فاصله‌های غیرقابل‌شکست، سطر بعد و فاصله‌های با پهنای متغیر (در میان دیگران) تطابق دارد.		 
$string1 = "Hello World\n";
if ($string1 =~ m/\s.*\s/) {
  print "In $string1 there are TWO whitespace characters, which may";
  print " be separated by other characters.\n";
}

خروجی:

In Hello World
 there are TWO whitespace characters, which may be separated by other characters.
\S با هر چیزی جز فاصله خالی تطابق دارد. 
$string1 = "Hello World\n";
if ($string1 =~ m/\S.*\S/) {
  print "In $string1 there are TWO non-whitespace characters, which";
  print " may be separated by other characters.\n";
}

خروجی:

In Hello World
 there are TWO non-whitespace characters, which may be separated by other characters.
\d با یک رقم تطابق دارد؛
معادل [0-9] در ASCII;
در یونی‌کد، معادل ویژگی \p{Digit} یا \p{GC=Decimal_Number} است که خود معادل ویژگی \p{Numeric_Type=Decimal} است.		 
$string1 = "99 bottles of beer on the wall.";
if ($string1 =~ m/(\d+)/) {
  print "$1 is the first number in '$string1'\n";
}

خروجی:

99 is the first number in '99 bottles of beer on the wall.'
\D با یک غیررقم تطابق دارد؛
معادل [^0-9] در ASCII یا \P{Digit} در یونی‌کد.		 
$string1 = "Hello World\n";
if ($string1 =~ m/\D/) {
  print "At least one character in $string1";
  print " is not a digit.\n";
}

خروجی:

At least one character in Hello World
 is not a digit.
^ با آغاز یک خط یا رشته تطابق دارد. 
$string1 = "Hello World\n";
if ($string1 =~ m/^He/) {
  print "$string1 starts with the characters 'He'.\n";
}

خروجی:

Hello World
 starts with the characters 'He'.
$ با پایان یک خط یا رشته تطابق دارد. 
$string1 = "Hello World\n";
if ($string1 =~ m/rld$/) {
  print "$string1 is a line or string ";
  print "that ends with 'rld'.\n";
}

خروجی:

Hello World
 is a line or string that ends with 'rld'.
\A با آغاز یک رشته (نه یک خط درونی) تطابق دارد. 
$string1 = "Hello\nWorld\n";
if ($string1 =~ m/\AH/) {
  print "$string1 is a string ";
  print "that starts with 'H'.\n";
}

خروجی:

Hello
World
 is a string that starts with 'H'.
\z با پایان یک رشته (نه یک خط درونی) تطابق دارد.[۶۲] 
$string1 = "Hello\nWorld\n";
if ($string1 =~ m/d\n\z/) {
  print "$string1 is a string ";
  print "that ends with 'd\\n'.\n";
}

خروجی:

Hello
World
 is a string that ends with '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
 contains a character other than a, b, and c.

استقرا

[ویرایش | اشتراک‌گذاری]

عبارت‌های باقاعده را اغلب می‌توان بر پایه مجموعه‌ای از رشته‌های نمونه «استنتاج» یا «یادگیری» کرد. این فرایند به نام استقرای زبان‌های منظم شناخته می‌شود و بخشی از مسئله کلی استقرای دستور زبان در نظریه یادگیری محاسباتی است. به‌طور رسمی، با داشتن نمونه‌هایی از رشته‌های یک زبان منظم و شاید نیز نمونه‌هایی از رشته‌هایی که در آن زبان منظم نیستند، می‌توان یک دستور زبان برای آن زبان استنتاج کرد؛ یعنی یک عبارت باقاعده که آن زبان را تولید می‌کند. همه زبان‌های منظم را نمی‌توان به این شیوه استنتاج کرد (نگاه کنید به تشخیص زبان در حد)، اما بسیاری از آن‌ها را می‌توان. برای نمونه، مجموعه نمونه‌های {۱, ۱۰, ۱۰۰} و مجموعه منفی (نمونه‌های مخالف) {۱۱, ۱۰۰۱, ۱۰۱, ۰} را می‌توان برای استنتاج عبارت باقاعده ۱⋅۰* (عدد ۱ و پس از آن صفر یا بیشتر صفر) به کار برد.

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

[ویرایش | اشتراک‌گذاری]

یادداشت‌ها

[ویرایش | اشتراک‌گذاری]
  1. ↑ Goyvaerts، Jan. «Regular Expression Tutorial - Learn How to Use Regular Expressions». Regular-Expressions.info. بایگانی‌شده از روی نسخهٔ اصلی در ۱ نوامبر ۲۰۱۶. دریافت‌شده در ۳۱ اکتبر ۲۰۱۶.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  2. ↑ Mitkov، Ruslan (۲۰۰۳). The Oxford Handbook of Computational Linguistics. Oxford University Press. ص. ۷۵۴. شابک ۹۷۸-۰-۱۹-۹۲۷۶۳۴-۹. بایگانی‌شده از روی نسخهٔ اصلی در ۲۸ فوریه ۲۰۱۷. دریافت‌شده در ۲۵ ژوئیه ۲۰۱۶.{{cite book}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  3. ↑ Lawson، Mark V. (۱۷ سپتامبر ۲۰۰۳). Finite Automata. CRC Press. صص. ۹۸–۱۰۰. شابک ۹۷۸-۱-۵۸۴۸۸-۲۵۵-۸. بایگانی‌شده از روی نسخهٔ اصلی در ۲۷ فوریه ۲۰۱۷. دریافت‌شده در ۲۵ ژوئیه ۲۰۱۶.{{cite book}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  4. ↑ «How a Regex Engine Works Internally». regular-expressions.info. دریافت‌شده در ۲۴ فوریه ۲۰۲۴.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  5. ↑ Heddings، Anthony (۱۱ مارس ۲۰۲۰). «How Do You Actually Use Regex?». howtogeek.com. دریافت‌شده در ۲۴ فوریه ۲۰۲۴.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  6. ↑ Kleene 1951.
  7. ↑ Leung، Hing (۱۶ سپتامبر ۲۰۱۰). «Regular Languages and Finite Automata» (PDF). دانشگاه ایالتی نیومکزیکو. بایگانی‌شده از اصلی (PDF) در ۵ دسامبر ۲۰۱۳. دریافت‌شده در ۱۳ اوت ۲۰۱۹. The concept of regular events was introduced by Kleene via the definition of regular expressions. {{cite web}}: از پارامتر ناشناخته |فرمت تاریخ= صرف‌نظر شد (کمک)نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  8. ↑ Kleene 1951, pg46
  9. 1 2 Thompson 1968.
  10. 1 2 Johnson et al. 1968.
  11. ↑ Kernighan، Brian (۸ اوت ۲۰۰۷). «A Regular Expressions Matcher». Beautiful Code. اورایلی مدیا. صص. ۱–۲. شابک ۹۷۸-۰-۵۹۶-۵۱۰۰۴-۶. بایگانی‌شده از روی نسخهٔ اصلی در ۷ اکتبر ۲۰۲۰. دریافت‌شده در ۱۵ مه ۲۰۱۳.{{cite book}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  12. ↑ Ritchie، Dennis M. «An incomplete history of the QED Text Editor». بایگانی‌شده از اصلی در ۲۱ فوریه ۱۹۹۹. دریافت‌شده در ۹ اکتبر ۲۰۱۳.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  13. 1 2 Aho & Ullman 1992, 10.11 Bibliographic Notes for Chapter 10, p. 589.
  14. ↑ Aycock 2003, p. 98.
  15. ↑ Raymond, Eric S. citing Dennis Ritchie (۲۰۰۳). «Jargon File 4.4.7: grep». بایگانی‌شده از اصلی در ۵ ژوئن ۲۰۱۱. دریافت‌شده در ۱۷ فوریه ۲۰۰۹.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  16. ↑ «New Regular Expression Features in Tcl 8.1». بایگانی‌شده از روی نسخهٔ اصلی در ۷ اکتبر ۲۰۲۰. دریافت‌شده در ۱۱ اکتبر ۲۰۱۳.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  17. ↑ «Documentation: 9.3: Pattern Matching». PostgreSQL. بایگانی‌شده از روی نسخهٔ اصلی در ۷ اکتبر ۲۰۲۰. دریافت‌شده در ۱۲ اکتبر ۲۰۱۳.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  18. ↑ Wall, Larry (۲۰۰۶). «Perl Regular Expressions». perlre. بایگانی‌شده از روی نسخهٔ اصلی در ۳۱ دسامبر ۲۰۰۹. دریافت‌شده در ۱۰ اکتبر ۲۰۰۶.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  19. 1 2 (Wall 2002)
  20. ↑ «PCRE - Perl Compatible Regular Expressions». www.pcre.org. دریافت‌شده در ۷ آوریل ۲۰۲۴.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  21. ↑ «GRegex – Faster Analytics for Unstructured Text Data». grovf.com. بایگانی‌شده از اصلی در ۷ اکتبر ۲۰۲۰. دریافت‌شده در ۲۰ آوریل ۲۰۲۶.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  22. ↑ «CUDA grep». bkase.github.io. بایگانی‌شده از روی نسخهٔ اصلی در ۷ اکتبر ۲۰۲۰. دریافت‌شده در ۲۲ اکتبر ۲۰۱۹.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  23. 1 2 3 4 Kerrisk، Michael. «grep(1) - Linux manual page». man۷.org. دریافت‌شده در ۳۱ ژانویه ۲۰۲۳.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  24. 1 2 (Hopcroft، Motwani و Ullman 2000)
  25. ↑ (Sipser 1998)
  26. ↑ (Gelade و Neven 2008، ص. 332، Thm.4.1)
  27. ↑ (Gruber و Holzer 2008)
  28. ↑ Based on (Gelade و Neven 2008), a regular expression of length about 850 such that its complement has a length about 232 can be found at File:RegexComplementBlowup.png.
  29. ↑ «Regular expressions for deciding divisibility». s۳.boskent.com. دریافت‌شده در ۲۱ فوریه ۲۰۲۴.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  30. ↑ Gischer، Jay L. (۱۹۸۴). «(Title unknown)» (Technical Report). Stanford Univ. , Dept. of Comp. Sc. {{cite web}}: پارامتر |پیوند= ناموجود یا خالی (کمک)نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)[عنوان مشخص نیست]
  31. ↑ Hopcroft، John E.؛ Motwani، Rajeev & Ullman، Jeffrey D. (۲۰۰۳). Introduction to Automata Theory, Languages, and Computation. Upper Saddle River, New Jersey: Addison Wesley. صص. ۱۱۷–۱۲۰. شابک ۹۷۸-۰-۲۰۱-۴۴۱۲۴-۶. This property need not hold for extended regular expressions, even if they describe no larger class than regular languages; cf. p.۱۲۱.{{cite book}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  32. ↑ (Kozen 1991)[کدام صفحه؟]
  33. ↑ Redko, V.N. (1964). "On defining relations for the algebra of regular events". Ukrainskii Matematicheskii Zhurnal (in Russian). 16 (1): 120–126. Archived from the original on 29 مارس 2018. Retrieved 28 مارس 2018.
  34. ↑ ISO/IEC 9945-2:1993 Information technology – Portable Operating System Interface (POSIX) – Part 2: Shell and Utilities, successively revised as ISO/IEC 9945-2:2002 Information technology – Portable Operating System Interface (POSIX) – Part 2: System Interfaces, ISO/IEC 9945-2:2003, and currently ISO/IEC/IEEE 9945:2009 Information technology – Portable Operating System Interface (POSIX) Base Specifications, Issue 7
  35. ↑ The Single Unix Specification (Version 2)
  36. ↑ «9.3.6 BREs Matching Multiple Characters». The Open Group Base Specifications Issue ۷, ۲۰۱۸ edition. The Open Group. ۲۰۱۷. دریافت‌شده در ۱۰ دسامبر ۲۰۲۳.{{cite book}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  37. ↑ Russ Cox (۲۰۰۹). «Regular Expression Matching: the Virtual Machine Approach». swtch.com. Digression: POSIX Submatching{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  38. ↑ «Perl Regular Expression Documentation». perldoc.perl.org. بایگانی‌شده از روی نسخهٔ اصلی در ۳۱ دسامبر ۲۰۰۹. دریافت‌شده در ۵ نوامبر ۲۰۲۴.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  39. 1 2 «Regular Expression Syntax». Python ۳.۵.۰ documentation. Python Software Foundation. بایگانی‌شده از اصلی در ۱۸ ژوئیه ۲۰۱۸. دریافت‌شده در ۱۰ اکتبر ۲۰۱۵.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  40. ↑ SRE: Atomic Grouping (?>...) is not supported #34627
  41. 1 2 «Essential classes: Regular Expressions: Quantifiers: Differences Among Greedy, Reluctant, and Possessive Quantifiers». The Java Tutorials. Oracle. بایگانی‌شده از روی نسخهٔ اصلی در ۷ اکتبر ۲۰۲۰. دریافت‌شده در ۲۳ دسامبر ۲۰۱۶.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  42. ↑ «Atomic Grouping». Regex Tutorial. بایگانی‌شده از روی نسخهٔ اصلی در ۷ اکتبر ۲۰۲۰. دریافت‌شده در ۲۴ نوامبر ۲۰۱۹.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  43. ↑ Bormann, Carsten; Bray, Tim. I-Regexp: An Interoperable Regular Expression Format. Internet Engineering Task Force. RFC 9485. https://tools.ietf.org/html/rfc9485. Retrieved 11 March 2024.
  44. ↑ Cezar Câmpeanu؛ Kai Salomaa & Sheng Yu (دسامبر ۲۰۰۳). «A Formal Study of Practical Regular Expressions». International Journal of Foundations of Computer Science. ۱۴ (۶): ۱۰۰۷–۱۰۱۸. doi:10.1142/S012905410300214X. بایگانی‌شده از روی نسخهٔ اصلی در ۴ ژوئیه ۲۰۱۵. دریافت‌شده در ۳ ژوئیه ۲۰۱۵.{{cite journal}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده) Theorem 3 (p.9)
  45. ↑ «Perl Regular Expression Matching is NP-Hard». perl.plover.com. بایگانی‌شده از روی نسخهٔ اصلی در ۷ اکتبر ۲۰۲۰. دریافت‌شده در ۲۱ نوامبر ۲۰۱۹.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  46. ↑ Ritchie، D. M.؛ Thompson، K. L. (ژوئن ۱۹۷۰). QED Text Editor (PDF). بایگانی‌شده از اصلی (PDF) در ۳ فوریه ۲۰۱۵. دریافت‌شده در ۵ سپتامبر ۲۰۲۲.{{cite book}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده) Reprinted as "QED Text Editor Reference Manual", MHCC-004, Murray Hill Computing, Bell Laboratories (October 1972).
  47. 1 2 Wall، Larry (۱۸ اکتبر ۱۹۹۴). «Perl 5: perlre.pod». GitHub.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  48. ↑ Wandering Logic. «How to simulate lookaheads and lookbehinds in finite state automata?». Computer Science Stack Exchange. بایگانی‌شده از روی نسخهٔ اصلی در ۷ اکتبر ۲۰۲۰. دریافت‌شده در ۲۴ نوامبر ۲۰۱۹.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  49. ↑ Zakharevich، Ilya (۱۹ نوامبر ۱۹۹۷). «Jumbo Regexp Patch Applied (with Minor Fix-Up Tweaks): Perl/perl5@c277df4». GitHub.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  50. ↑ (Cox 2007)
  51. ↑ (Laurikari 2009)
  52. ↑ «gnulib/lib/dfa.c». بایگانی‌شده از اصلی در ۱۸ اوت ۲۰۲۱. دریافت‌شده در ۱۲ فوریه ۲۰۲۲. If the scanner detects a transition on backref, it returns a kind of "semi-success" indicating that the match will have to be verified with a backtracking matcher.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  53. ↑ Kearns، Steven (اوت ۲۰۱۳). «Sublinear Matching With Finite Automata Using Reverse Suffix Scanning». arXiv:1308.3822. {{cite journal}}: از پارامتر ناشناخته |class= صرف‌نظر شد (کمک); یادکرد journal نیازمند |journal= است (کمک)نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  54. ↑ Navarro، Gonzalo (۱۰ نوامبر ۲۰۰۱). «NR-grep: a fast and flexible pattern-matching tool» (PDF). Software: Practice and Experience. ۳۱ (۱۳): ۱۲۶۵–۱۳۱۲. doi:10.1002/spe.411. S2CID 3175806. بایگانی‌شده (PDF) از روی نسخهٔ اصلی در ۷ اکتبر ۲۰۲۰. دریافت‌شده در ۲۱ نوامبر ۲۰۱۹.{{cite journal}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  55. ↑ «travisdowns/polyregex». گیت‌هاب. ۵ ژوئیه ۲۰۱۹. بایگانی‌شده از روی نسخهٔ اصلی در ۱۴ سپتامبر ۲۰۲۰. دریافت‌شده در ۲۱ نوامبر ۲۰۱۹.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  56. ↑ Schmid، Markus L. (مارس ۲۰۱۹). «Regular Expressions with Backreferences: Polynomial-Time Matching Techniques». arXiv:1903.05896. {{cite journal}}: از پارامتر ناشناخته |class= صرف‌نظر شد (کمک); یادکرد journal نیازمند |journal= است (کمک)نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  57. ↑ «Vim documentation: pattern». Vimdoc.sourceforge.net. بایگانی‌شده از روی نسخهٔ اصلی در ۷ اکتبر ۲۰۲۰. دریافت‌شده در ۲۵ سپتامبر ۲۰۱۳.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  58. 1 2 «UTS#18 on Unicode Regular Expressions, Annex A: Character Blocks». بایگانی‌شده از روی نسخهٔ اصلی در ۷ اکتبر ۲۰۲۰. دریافت‌شده در ۵ فوریه ۲۰۱۰.{{cite web}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
  59. ↑ نویسه «m» همیشه برای مشخص کردن عملیات تطبیق در پرل لازم نیست. برای مثال، m/[^abc]/ را می‌توان به صورت /[^abc]/ نیز نوشت. «m» تنها هنگامی لازم است که کاربر بخواهد عملیات تطبیق را بدون بهره‌گیری از اسلش به‌عنوان حائل عبارت باقاعده مشخص کند. گاهی مشخص کردن یک حائل جایگزین برای عبارت باقاعده سودمند است تا از «برخورد حائل» پرهیز شود. برای جزئیات بیشتر، perldoc perlre بایگانی‌شده در ۲۰۰۹-۱۲-۳۱ توسط Wayback Machine را ببینید.
  60. ↑ برای نمونه، ببینید Java in a Nutshell، ص. ۲۱۳؛ Python Scripting for Computational Science، ص. ۳۲۰؛ Programming PHP، ص. ۱۰۶.
  61. ↑ همه عبارت‌های شرطی مقدار درست (TRUE) برمی‌گردانند
  62. ↑ Conway، Damian (۲۰۰۵). «Regular Expressions, End of String». Perl Best Practices. O'Reilly. ص. ۲۴۰. شابک ۹۷۸-۰-۵۹۶-۰۰۱۷۳-۵. بایگانی‌شده از روی نسخهٔ اصلی در ۷ اکتبر ۲۰۲۰. دریافت‌شده در ۱۰ سپتامبر ۲۰۱۷.{{cite book}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)

منابع

[ویرایش | اشتراک‌گذاری]

پیوند به بیرون

[ویرایش | اشتراک‌گذاری]

برگرفته از «https://fa.wikipedia.org/w/index.php?title=عبارت_باقاعده&oldid=43833430»