پارسنگ اکسپرشن گرامر

یک پارسنگ اکسپرشن گرامر (انگلیسی: parsing expression grammar یا PEG)، یک نوع گرامر صوری نحوی است که یک زبان صوری بر اساس مجموعه‌ای از قواعد برای شناسایی رشته‌های یک زبان تعریف می‌کند. یک PEG در اساس یک پارسر بازگشتی را در شکل خالصش که فقط نحو را نمایش می‌دهد و مستقل از روش پیاده‌سازی است نمایش می‌دهد. PEGها به گرامرهای منظم یا گرامرهای مستقل از زبان شباهت دارند ولی تفسیر متفاوتی دارند. برخلاف گرامرهای مستقل از متن، PEGها مبهم نیستند. اگر یک رشته مورد قبول گرامر واقع شود فقط یک درخت پارس معتبر دارد. این خصوصیت باعث می‌شود تا PEGها برای پارس زبان‌های برنامه سازی رایانه‌ای مناسب باشند نه برای زبان‌های طبیعی.

تعریف

یک گرامر زبان تشکیل شده از مجموعه غیرپایانه‌ها، مجموعه پایانه‌ها جدا از مجموعه غیرپایانه‌ها، و مجموعه‌ای متناهی از قوانین پارس. هر قانون پارس در گرامر P به صورت A ← a است که در آن A یک غیرپایانه‌است و e یک عبارت پارس است. هر عبارت پارس یک عبارت سلسه مراتبی شبیه به عبارات منظم است که به صورت زیر ساخته می‌شود:

1. یک عبارت پارس اتمیک متشکل از:

• هر علامت پایانه
• هر علامت غیرپایانه
• رشته خالی

1. با داشتن هر عبارت پارس مانند e، e۱، e۲ یک عبارت پارس جدید با عملگرهای زیر می‌توان ساخت:

• دنباله: e1 e۲
• انتخاب مرتب: e1/e۲
• هیچ یا بیشتر: *e
• یک یا بیشتر: +e
• اختیاری: ?e
• گزاره وصلی: e&
• گزاره نفی: e!

برخلاف یک گرامر مستقل از متن یا سایر گرامرهای تولیدی، به ازای هر غیر پایانه در یک PEG باید دقیقاً یک قاعده که سمت چپش آن غیرپایانه‌است وجود داشته باشد. یعنی، قاعده‌ها در یک PEG، مانند تعریف عمل می‌کنند، و هر غیرپایانه باید دقیقاً یک تعریف داشته باشد.

تفسیر عبارات پارس

هر غیرپایانه در یک PEG، اساساً معادل یک تابع پارس در یک پارسر بازگشتی است، و عبارت پارس متناظر، نشان دهنده کدی است که تابع را می‌سازد. هر تابع پارس یک رشته ورودی می‌گیرد، و یکی از نتایج زیر را بر می‌گرداند:

• موفقیت، که در آن تابع ممکن است به جلو حرکت کند یا یک یا تعداد بیشتری حرف از رشته ورودی را «مصرف» کند.
• شکست، که در آن هیچ ورودی مصرف نمی‌شود.

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

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

عملگر انتخاب e1/e۲ ابتدا e۱ را فرامی خواند و اگر e۱ موفق شود، نتیجه را بلافاصله برمی گرداند. وگرنه، اگر e۱ شکست بخورد، آن گاه، عبارت انتخاب به موقعیت قبلی ورودی که در آن e۱ فراخوانی شده بود باز می‌گردد. آن گاه e۲ را به جای آن فرا می‌خواند و نتیجه آن را برمی گرداند.

عملگرهای هیچ-یا-بیشتر، یک-یا-بیشتر، و عملگر دلخواه، به ترتیب هیچ یا بیشتر، یک یا بیشتر، یا هیچ یا یک تکرار از زیر رشته e خود را مصرف می‌کنند. بر خلاف گرامرهای مستقل از زبان و گرامرهای منظم، این عملگرها همواره به صورت حریصانه عمل می‌کنند؛ و هر چه قدر بتوانند از ورودی مصرف می‌کنند و هیچ‌گاه به عقب برنمی گردند. (عبارات منظم با تطابق حریصانه آغاز می‌کنند، ولی آن‌ها هم به عقب بازمی گردند و تطبیق‌های کوتاه تری را امتحان می‌کنند اگر آن‌ها تطبیق پیدا نکنند) برای نمونه، عبارت *a همیشه تمام aهای موجود در رشته ورودی را مصرف می‌کند، و عبارت (a*a) همیشه شکست می‌خورد چون بخش (*a) هیچ a -ای را برای تطابق توسط بخش دوم باقی نمی‌گذارد. در پایان، گزاره‌های وصلی و نفی، گزاره‌های نحوی را پیاده می‌کنند. عبارت a& زیررشته a را فرا می‌خواند، و اگر e موفق شود، موفق می‌شود وگرنه شکست می‌خورد؛ ولی در هر حال، هیچ ورودی را مصرف نمی‌کند. برعکس، عبارت e! موفق می‌شود اگر e شکست بخورد و شکست می‌خورد اگر e موفق شود و در هر حال هیچ ورودی را مصرف نمی‌کند. چون این‌ها می‌توانند از یک زیر عبارت پیچیده برای بررسی ورودی استفاده کنند بدون این که چیزی مصرف کنند، یک روش قوی نحوی برای lookahead و رفع ابهام فراهم آورده می‌شود.