| PEG(1) | General Commands Manual | PEG(1) |
نام (NAME)
peg, leg - مولدهای تجزیه‌کننده
خلاصه دستور (SYNOPSIS)
peg [-hvV -ooutput] [filename ...]
leg [-hvV -ooutput] [filename ...]
توضیحات (DESCRIPTION)
peg و leg ابزارهایی برای تولید تجزیه‌کننده‌های بازگشتی نزولی (recursive-descent) هستند: برنامه‌هایی که تطبیق الگو را روی متن انجام می‌دهند. آن‌ها یک گرامر عبارت تجزیه (Parsing Expression Grammar یا PEG) [Ford 2004] را پردازش می‌کنند تا برنامه‌ای تولید کنند که جملات مجاز آن گرامر را شناسایی کند. peg گرامرهای PEG نوشته‌شده با نحو اصلی توصیف‌شده توسط Ford را پردازش می‌کند؛ leg گرامرهای PEG نوشته‌شده با نحو و قواعد نگارشی کمی متفاوت را پردازش می‌کند که هدف آن‌ها تبدیل شدن به جایگزینی جذاب برای تجزیه‌کننده‌های ساخته‌شده با lex(1) و yacc(1) است. برخلاف lex و yacc، ابزارهای peg و leg از عقب‌گرد (backtracking) نامحدود پشتیبانی می‌کنند، انتخاب مرتب‌شده (ordered choice) را به عنوان روشی برای ابهام‌زدایی فراهم می‌آورند، و می‌توانند پویش (تحلیل واژگانی) و تجزیه (تحلیل نحوی) را در یک فعالیت واحد ترکیب کنند.
ابزار peg فایل‌های مشخص‌شده در filename را (یا در صورت مشخص نشدن filename، ورودی استاندارد را) برای دریافت گرامری که تجزیه‌کنندهٔ مورد نظر را توصیف می‌کند، می‌خواند. سپس peg یک فایل منبع C تولید می‌کند که تابعی با نام yyparse() را تعریف می‌نماید. این فایل منبع C می‌تواند در یک برنامهٔ کلاینت گنجانده (include) شود، یا کامپایل شده و سپس به آن پیوند (link) داده شود. هر بار که برنامهٔ کلاینت تابع yyparse() را فراخوانی می‌کند، تجزیه‌کننده متن ورودی را طبق قواعد تجزیه، با شروع از اولین قاعده در گرامر، مصرف می‌کند. اگر ورودی مطابق با گرامر قابل تجزیه باشد، yyparse() مقداری غیرصفر برمی‌گرداند؛ و اگر ورودی قابل تجزیه نباشد، صفر برمی‌گرداند.
پیشوند 'yy' یا 'YY' به ابتدای تمام نمادهای قابل مشاهده از بیرون در تجزیه‌کنندهٔ تولیدشده اضافه می‌شود. این کار با هدف کاهش خطر تداخل در فضای نام (namespace pollution) در برنامه‌های کلاینت انجام می‌گیرد. (انتخاب 'yy' ریشهٔ تاریخی دارد؛ برای مثال به lex(1) و yacc(1) مراجعه کنید.)
گزینه‌ها (OPTIONS)
peg و leg گزینه‌های زیر را ارائه می‌دهند:
- -h
- خلاصه‌ای از گزینه‌های موجود را چاپ کرده و خارج می‌شود.
- -ooutput
- تجزیه‌کنندهٔ تولیدشده را به جای خروجی استاندارد در فایل output می‌نویسد.
- -P
- دستورهای #line را در خروجی حذف (سرکوب) می‌کند.
- -v
- در حین کار، اطلاعات دقیق و مشروح (verbose) را در خطای استاندارد می‌نویسد.
- -V
- اطلاعات نسخه را در خطای استاندارد نوشته و سپس خارج می‌شود.
مثال ساده (A SIMPLE EXAMPLE)
ورودی peg زیر گرامری با یک قاعدهٔ واحد (به نام 'start') را مشخص می‌کند که در صورت وجود رشتهٔ "username" در ورودی، برآورده می‌شود.
start <- "username"
(علامت‌های نقل‌قول بخشی از متن منطبق‌شده نیستند؛ بلکه برای مشخص کردن یک رشتهٔ لفظی جهت تطبیق به کار می‌روند.) به عبارت دیگر، تابع yyparse() در کد منبع C تولیدشده تنها در صورتی مقداری غیرصفر برمی‌گرداند که هشت نویسهٔ بعدی خوانده‌شده از ورودی، کلمهٔ "username" را تشکیل دهند. اگر ورودی شامل هر چیز دیگری باشد، yyparse() صفر برمی‌گرداند و هیچ ورودی‌ای مصرف نخواهد شد. (فراخوانی‌های بعدی yyparse() نیز صفر برمی‌گردانند، زیرا تجزیه‌کننده عملاً در جستجوی رشتهٔ "username" متوقف مانده است.) برای اطمینان از پیشرفت، می‌توانیم یک بند جایگزین به قاعدهٔ 'start' اضافه کنیم تا در صورت پیدا نشدن "username"، با هر نویسهٔ تکی تطبیق داده شود.
start <- "username"
/ .
اکنون yyparse() همواره مقداری غیرصفر برمی‌گرداند (به‌جز در پایان ورودی). برای انجام کاری مفید، می‌توانیم کنش‌هایی (actions) را به قواعد اضافه کنیم. این کنش‌ها پس از یافتن یک تطبیق کامل (با شروع از اولین قاعده) انجام می‌شوند و بر اساس «مسیری» که در گرامر برای تطبیق با ورودی طی شده است، انتخاب می‌گردند. (زبان‌شناسان این مسیر را یک «نشانگر عبارت» یا phrase marker می‌نامند.)
start <- "username" { printf("%s\n", getlogin()); }
/ < . > { putchar(yytext[0]); }
خط اول به تجزیه‌کننده دستور می‌دهد که هر زمان "username" را در ورودی دید، نام ورود کاربر را چاپ کند. اگر این تطبیق ناموفق باشد، خط دوم به تجزیه‌کننده می‌گوید که نویسهٔ بعدی ورودی را در خروجی استاندارد منعکس کند. اکنون تجزیه‌کنندهٔ ما کار مفیدی انجام می‌دهد: ورودی را در خروجی کپی می‌کند و تمامی موارد وقوع "username" را با نام حساب کاربری کاربر جایگزین می‌نماید.
به علامت‌های قلاب‌مانند ('<' و '>') که به جایگزین دوم اضافه شده‌اند دقت کنید. این‌ها تأثیری بر معنای قاعده ندارند، اما برای تعیین مرز متنی که در متغیر yytext در دسترس کنش بعدی قرار می‌گیرد، به کار می‌روند.
اگر گرامر بالا در فایلی با نام username.peg قرار گیرد، اجرای دستور
peg -o username.c username.pegتجزیه‌کنندهٔ مربوطه را در فایل username.c ذخیره خواهد کرد. برای ایجاد یک برنامهٔ کامل، این تجزیه‌کننده می‌تواند به‌صورت زیر در یک برنامهٔ C گنجانده شود:
#include <stdio.h> /* printf(), putchar() */
#include <unistd.h> /* getlogin() */
#include "username.c" /* yyparse() */
int main()
{
while (yyparse()) /* repeat until EOF */
;
return 0;
}
یک گرامر از مجموعه‌ای از قواعد نام‌گذاری‌شده تشکیل شده است.
name <- pattern
عنصر pattern شامل
یک یا چند
مورد از
عناصر زیر
است.
- name
- این عنصر نمایانگر کل الگو در قاعده‌ای با همان name داده‌شده است.
- "characters"
- نویسه یا رشته‌ای که در جفت‌گیومه قرار گرفته باشد، به صورت لفظی تطبیق داده می‌شود. دنباله‌های گریز ANSI C در میان characters شناسایی می‌شوند.
- 'characters'
- نویسه یا رشته‌ای که در تک‌گیومه قرار گرفته باشد، همانند بالا به صورت لفظی تطبیق داده می‌شود.
- [characters]
- مجموعه‌ای
از
نویسه‌ها
که در
قلاب‌ها
قرار گرفته
باشند با هر
تک‌نویسه‌ای
از آن
مجموعه
مطابقت
می‌یابد؛
نویسه‌های
گریز نیز
همانند
بالا
شناسایی
می‌شوند.
اگر مجموعه
با یک علامت
هشتک (^) شروع
شود،
مجموعه نفی
می‌شود
(عنصر با هر
نویسه‌ای
که در
مجموعه
نباشد
تطبیق
می‌یابد).
هر
جفت‌نویسه
که با یک خط
تیره (-) از هم
جدا شده
باشد،
نمایانگر
بازه‌ای از
نویسه‌ها
از اولی تا
دومی (شامل
هر دو) است.
یک
تک‌نویسه
الفبایی یا
زیرخط با
مجموعه زیر
مطابقت
می‌یابد:
[a-zA-Z_]
به طور مشابه، مورد زیر با هر تک‌نویسه غیررقمی مطابقت دارد:[^0-9]
- .
- نقطه با هر نویسه‌ای مطابقت می‌یابد. توجه داشته باشید تنها زمانی که این تطبیق شکست می‌خورد در انتهای فایل است، جایی که هیچ نویسه‌ای برای تطبیق وجود ندارد.
- ( pattern )
- پرانتزها برای گروه‌بندی (تغییر اولویت عملگرهایی که در ادامه توضیح داده شده‌اند) استفاده می‌شوند.
- { action }
- آکولادها کنش‌ها را در بر می‌گیرند. کنش، کد منبع اختیاری به زبان C است که در پایان تطبیق اجرا می‌شود. هرگونه آکولاد درون کنش باید به درستی تو در تو باشد. هر متن ورودی که پیش از کنش تطبیق داده شده و با علامت‌های کوچکتری و بزرگتری تحدید شده باشد (به پایین مراجعه کنید)، درون کنش به عنوان محتوای آرایه نویسه‌ای yytext در دسترس قرار می‌گیرد. طول (تعداد نویسه‌های موجود در) yytext در متغیر yyleng در دسترس است. (این نام‌های متغیرها جنبه تاریخی دارند؛ به lex(1) مراجعه کنید.)
- <
- علامت کوچکتری باز همیشه مطابقت می‌یابد (بدون مصرف هیچ ورودی) و باعث می‌شود تجزیه‌کننده شروع به انباشت متن تطبیق‌یافته کند. این متن در متغیر yytext در دسترس کنش‌ها قرار خواهد گرفت.
- >
- علامت بزرگتری بسته همیشه مطابقت می‌یابد (بدون مصرف هیچ ورودی) و باعث می‌شود تجزیه‌کننده از انباشت متن برای yytext دست بکشد.
عناصر element فوق را می‌توان با پسوندهای زیر اختیاری و/یا تکرارپذیر کرد:
- element ?
- عنصر اختیاری است. اگر در ورودی موجود باشد، مصرف می‌شود و تطبیق موفقیت‌آمیز است. اگر در ورودی وجود نداشته باشد، هیچ متنی مصرف نمی‌شود و تطبیق در هر حال موفق خواهد بود.
- element +
- عنصر تکرارپذیر است. اگر در ورودی موجود باشد، یک یا چند رخداد از element مصرف شده و تطبیق موفقیت‌آمیز است. اگر هیچ رخدادی از element در ورودی موجود نباشد، تطبیق شکست می‌خورد.
- element *
- عنصر اختیاری و تکرارپذیر است. اگر در ورودی موجود باشد، یک یا چند رخداد از element مصرف می‌شود و تطبیق موفقیت‌آمیز است. اگر هیچ رخدادی از element در ورودی وجود نداشته باشد، تطبیق در هر حال موفق خواهد بود.
عناصر و پسوندهای فوق را می‌توان با پیشوندهای زیر به گزاره‌ها تبدیل کرد (که با متن ورودی دلخواه تطبیق می‌یابند و متعاقباً بدون مصرف آن ورودی، موفق می‌شوند یا شکست می‌خورند):
- & element
- گزاره تنها در صورتی موفق می‌شود که element بتواند تطبیق یابد. متن ورودی که هنگام تطبیق element پویش می‌شود، از ورودی مصرف نشده و برای تطبیق‌های بعدی در دسترس باقی می‌ماند.
- ! element
- گزاره تنها
در صورتی
موفق
می‌شود که
element نتواند
تطبیق یابد.
متن ورودی
که هنگام
تطبیق element
پویش
می‌شود، از
ورودی مصرف
نشده و برای
تطبیق‌های
بعدی در
دسترس باقی
می‌ماند. یک
ساختار
متداول،
!.
است که با پایان فایل، پس از آن‌که آخرین نویسه ورودی قبلاً مصرف شده باشد، تطبیق می‌یابد.
شکل ویژه‌ای از گزاره '&' ارائه شده است:
- &{ expression }
- در این گزاره، expression ساده زبان C (و نه یک عبارت کامل دستوری یا statement) بلافاصله پس از رسیدن تجزیه‌کننده به گزاره ارزیابی می‌شود. اگر expression مقداری غیرصفر (true) به دست دهد، «تطبیق» موفق می‌شود و تجزیه‌کننده با عنصر بعدی در الگو ادامه می‌دهد. اگر expression مقدار صفر (false) به دست دهد، «تطبیق» شکست می‌خورد و تجزیه‌کننده برای یافتن یک تجزیه جایگزین از ورودی به عقب بازمی‌گردد.
چندین عنصر (با یا بدون پیشوندها و پسوندها) را می‌توان با نوشتن آن‌ها پشت سر یکدیگر در یک sequence (توالی) ترکیب کرد. کل توالی تنها در صورتی مطابقت می‌یابد که تک‌تک عناصر درون آن، از چپ به راست تطبیق یابند.
توالی‌ها را می‌توان با عملگر تناوب '/' به گزینه‌های جداگانه تقسیم کرد.
- sequence-1 / sequence-2 / ... / sequence-N
- هر توالی به نوبت امتحان می‌شود تا زمانی که یکی از آن‌ها مطابقت یابد، که در این زمان تطبیق برای کل الگو موفق خواهد بود. اگر هیچ‌یک از توالی‌ها مطابقت نیابد، تطبیق کل الگو شکست می‌خورد.
در نهایت، علامت هش (#) یک توضیح (نادیده‌گرفته‌شده) را مشخص می‌کند که تا انتهای خط ادامه می‌یابد.
برای جمع‌بندی موارد فوق، تجزیه‌کننده تلاش می‌کند متن ورودی را در برابر الگویی شامل مقادیر لفظی، نام‌ها (نمایانگر سایر قواعد) و عملگرهای مختلف (نوشته‌شده به صورت پیشوندها، پسوندها، کنار هم قرار گرفتن برای تشکیل توالی و یک عملگر میانوند تناوب) که نحوه تطبیق عناصر درون الگو را تغییر می‌دهند، تطبیق دهد. تطبیق‌ها از چپ به راست انجام می‌شوند و به محض برخورد با زیرقواعد نام‌گذاری‌شده، به درون آن‌ها «فرود» می‌آیند. اگر فرآیند تطبیق ناموفق باشد، تجزیه‌کننده «عقب‌گرد» می‌کند (و در این فرآیند، ورودی را به اندازه مناسب «به عقب بازمی‌گرداند») تا نزدیک‌ترین «مسیر» جایگزین را در گرامر بیابد. به عبارت دیگر، تجزیه‌کننده یک جستجوی اول‌عمق و چپ‌به‌راست را برای یافتن نخستین مسیر با تطبیق موفقیت‌آمیز در میان قواعد انجام می‌دهد. در صورت یافتن، کنش‌های موجود در مسیر موفقیت‌آمیز (به ترتیبی که با آن‌ها مواجه شده است) اجرا می‌شوند.
توجه داشته باشید که گزاره‌ها در حین جستجو برای یک تطبیق موفق بلافاصله ارزیابی می‌شوند، چرا که در موفقیت یا شکست جستجو نقش دارند. با این حال، کنش‌ها تنها پس از یافتن یک تطبیق موفق ارزیابی و اجرا می‌گردند..SH "گرامر PEG برای گرامرهای PEG (PEG GRAMMAR FOR PEG GRAMMARS)" گرامر مربوط به گرامرهای peg در زیر نشان داده شده است. این گرامر هم توصیف بالا را مصورسازی می‌کند و هم آن را به صورت صوری درمی‌آورد.
Grammar <- Spacing Definition+ EndOfFile
Definition <- Identifier LEFTARROW Expression
Expression <- Sequence ( SLASH Sequence )*
Sequence <- Prefix*
Prefix <- AND Action
/ ( AND | NOT )? Suffix
Suffix <- Primary ( QUERY / STAR / PLUS )?
Primary <- Identifier !LEFTARROW
/ OPEN Expression CLOSE
/ Literal
/ Class
/ DOT
/ Action
/ BEGIN
/ END
Identifier <- < IdentStart IdentCont* > Spacing
IdentStart <- [a-zA-Z_]
IdentCont <- IdentStart / [0-9]
Literal <- ['] < ( !['] Char )* > ['] Spacing
/ ["] < ( !["] Char )* > ["] Spacing
Class <- '[' < ( !']' Range )* > ']' Spacing
Range <- Char '-' Char / Char
Char <- '\\' [abefnrtv'"\[\]\\]
/ '\\' [0-3][0-7][0-7]
/ '\\' [0-7][0-7]?
/ '\\' '-'
/ !'\\' .
LEFTARROW <- '<-' Spacing
SLASH <- '/' Spacing
AND <- '&' Spacing
NOT <- '!' Spacing
QUERY <- '?' Spacing
STAR <- '*' Spacing
PLUS <- '+' Spacing
OPEN <- '(' Spacing
CLOSE <- ')' Spacing
DOT <- '.' Spacing
Spacing <- ( Space / Comment )*
Comment <- '#' ( !EndOfLine . )* EndOfLine
Space <- ' ' / '\t' / EndOfLine
EndOfLine <- '\r\n' / '\n' / '\r'
EndOfFile <- !.
Action <- '{' < [^}]* > '}' Spacing
BEGIN <- '<' Spacing
END <- '>' Spacing
گرامرهای LEG (LEG GRAMMARS)
leg گونه‌ای از peg است که برخی از ویژگی‌های lex(1) و yacc(1) را می‌افزاید. تفاوت‌های آن با peg به شرح زیر است:
- %{ text... %}
- یک بخش اعلان می‌تواند در هر جایی که انتظار تعریف یک قاعده می‌رود قرار گیرد. text (متن) میان جداکننده‌های '%{' و '%}' عیناً به کد پارسر C تولیدشده پیش از کدی که خود پارسر را پیاده‌سازی می‌کند کپی می‌شود.
- name = pattern
- عملگر «انتساب» جایگزین عملگر پیکان چپ '<-' می‌شود.
- rule-name
- خط‌های
پیوند (Hyphen)
می‌توانند
به عنوان
حروف در نام
قواعد ظاهر
شوند. هر خط
پیوند در کد
منبع C
تولیدشده
به یک زیرخط
(underscore) تبدیل
می‌شود. یک
خط پیوند
تکی '-' یک نام
قاعدهٔ
معتبر است.
- = [ \t\n\r]* number = [0-9]+ - name = [a-zA-Z_][a-zA_Z_0-9]* - l-paren = '(' - r-paren = ')' -این مثال نشان می‌دهد که چگونه فاصله‌های خالیِ نادیده‌گرفته‌شده می‌توانند هنگام خواندن گرامر کاملاً آشکار و مشخص باشند و در عین حال هنگامی که آزادانه در انتهای هر قاعدهٔ مرتبط با یک عنصر واژگانی قرار می‌گیرند، مخل خوانایی نباشند. - seq-1 | seq-2
- عملگر
تناوب به
جای اسلش رو
به جلو '/'، خط
عمودی '|' است.
قاعدهٔ peg
name <- sequence-1 / sequence-2 / sequence-3بنابراین در leg به صورت زیر نوشته می‌شود:name = sequence-1 | sequence-2 | sequence-3 ;(با این توضیح که نقطه-ویرگول پایانی اختیاری است، همان‌طور که در ادامه شرح داده شده است). - @{ action }
- کنش‌های دارای پیشوند با علامت «at» (@) در حین تجزیه، در همان زمانی که هنگام تطبیق متن ورودی با یک قاعده مشاهده می‌شوند، اجرا خواهند شد. به دلیل پس‌گرد (back-tracking) در الگوریتم تجزیه PEG، کنش‌های دارای پیشوند '@' ممکن است چندین بار برای یک متن ورودی یکسان اجرا شوند. (رفتار معمول کنش‌ها این است که تا زمان کامل شدن تطبیق ذخیره می‌شوند، و سپس آن‌هایی که بخشی از اشتقاق نهایی هستند به ترتیب از چپ به راست اجرا می‌شوند.) متغیر yytext درون این کنش‌ها در دسترس است.
- exp ~ { action }
- عملگر
پسوندیِ
~{ action }
می‌تواند
پس از هر
عبارتی
قرار گیرد و
مانند یک
کنش عادی
(کد C دلخواه)
رفتار
خواهد کرد،
به جز اینکه
فقط زمانی
فراخوانی
می‌شود که
exp با شکست
مواجه شود.
این عملگر
به جز تناوب
و توالی،
پیوند
ضعیف‌تری
نسبت به هر
عملگر
دیگری دارد
و هدف از آن
ساده‌تر
کردن نگارش
کدهای
مدیریت و
بازیابی
خطا است.
توجه داشته
باشید که yytext
و yyleng درون
این کنش‌ها
در دسترس
نیستند،
اما متغیر
اشاره‌گر yy
برای
دسترسی
دادن کد به
اعضای
تعریف‌شده
توسط کاربر
از وضعیت
پارسر در
دسترس است
(بخش “CUSTOMISING THE PARSER”
در ادامه را
ببینید).
همچنین
توجه داشته
باشید که exp
همواره یک
عبارت واحد
است؛ برای
فراخوانی
یک کنش خطا
برای هر
شکست درون
یک توالی،
باید از
پرانتز جهت
گروه‌بندی
آن توالی در
یک عبارت
واحد
استفاده
شود.
rule = e1 e2 e3 ~{ error("e[12] ok; e3 has failed"); } | ... rule = (e1 e2 e3) ~{ error("one of e[123] has failed"); } | ... - pattern ;
- یک نشانه‌گذار نقطه-ویرگول می‌تواند به صورت اختیاری به یک pattern پایان دهد.
- %% text...
- علامت درصد دوگانه '%%' به بخش قواعد (و اعلان‌های) گرامر پایان می‌دهد. تمامی text پس از '%%' عیناً به کد پارسر C تولیدشده، پس از کد پیاده‌سازی پارسر، کپی می‌شود.
- $$ = value
- یک زیرقاعده می‌تواند با انتساب یک مقدار به شبه‌متغیر '$$'، یک value (مقدار معنایی) را از یک کنش برگرداند. همهٔ مقادیر معنایی باید دارای نوع یکسانی باشند (که به طور پیش‌فرض 'int' است). این نوع را می‌توان با تعریف YYSTYPE در یک بخش اعلان تغییر داد.
- identifier:name
- مقدار معنایی بازگردانده‌شده (با انتساب به '$$') از زیرقاعدهٔ name با identifier مرتبط می‌شود و می‌توان در کنش‌های بعدی به آن ارجاع داد.
مثال ماشین‌حساب رومیزی در ادامه، استفاده از '$$' و ':' را نشان می‌دهد..SH "مثال LEG: یک ماشین‌حساب رومیزی (LEG EXAMPLE: A DESK CALCULATOR)" افزونه‌های leg که در بالا توضیح داده شدند، امکان نگهداری تجزیه‌کننده‌ها و ارزیاب‌های کاربردی (شامل اعلان‌ها، قواعد گرامر و توابع کمکی C نظیر 'main') را درون یک فایل مبدأ واحد فراهم می‌کنند. برای نشان دادن این موضوع، یک ماشین‌حساب رومیزی ساده نمایش داده شده است که از چهار عملگر حسابی رایج و متغیرهای نام‌گذاری‌شده پشتیبانی می‌کند. نتایج میانی ارزیابی حسابی با بازگردانده شدن به عنوان مقادیر معنایی از زیرقواعد، روی یک پشتهٔ ضمنی انباشته می‌شوند.
%{
#include <stdio.h> /* printf() */
#include <stdlib.h> /* atoi() */
int vars[26];
%}
Stmt = - e:Expr EOL { printf("%d\n", e); }
| ( !EOL . )* EOL { printf("error\n"); }
Expr = i:ID ASSIGN s:Sum { $$ = vars[i] = s; }
| s:Sum { $$ = s; }
Sum = l:Product
( PLUS r:Product { l += r; }
| MINUS r:Product { l -= r; }
)* { $$ = l; }
Product = l:Value
( TIMES r:Value { l *= r; }
| DIVIDE r:Value { l /= r; }
)* { $$ = l; }
Value = i:NUMBER { $$ = atoi(yytext); }
| i:ID !ASSIGN { $$ = vars[i]; }
| OPEN i:Expr CLOSE { $$ = i; }
NUMBER = < [0-9]+ > - { $$ = atoi(yytext); }
ID = < [a-z] > - { $$ = yytext[0] - 'a'; }
ASSIGN = '=' -
PLUS = '+' -
MINUS = '-' -
TIMES = '*' -
DIVIDE = '/' -
OPEN = '(' -
CLOSE = ')' -
- = [ \t]*
EOL = '\n' | '\r\n' | '\r' | ';'
%%
int main()
{
while (yyparse())
;
return 0;
}
گرامر LEG برای گرامرهای LEG (LEG GRAMMAR FOR LEG GRAMMARS)
گرامرِ گرامرهای leg در زیر نشان داده شده است. این گرامر هم توضیحات بالا را مصور ساخته و هم آن‌ها را صورت‌بندی می‌کند.
grammar = -
( declaration | definition )+
trailer? end-of-file
declaration = '%{' < ( !'%}' . )* > RPERCENT
trailer = '%%' < .* >
definition = identifier EQUAL expression SEMICOLON?
expression = sequence ( BAR sequence )*
sequence = error+
error = prefix ( TILDE action )?
prefix = AND action
| ( AND | NOT )? suffix
suffix = primary ( QUERY | STAR | PLUS )?
primary = identifier COLON identifier !EQUAL
| identifier !EQUAL
| OPEN expression CLOSE
| literal
| class
| DOT
| action
| BEGIN
| END
identifier = < [-a-zA-Z_][-a-zA-Z_0-9]* > -
literal = ['] < ( !['] char )* > ['] -
| ["] < ( !["] char )* > ["] -
class = '[' < ( !']' range )* > ']' -
range = char '-' char | char
char = '\\' [abefnrtv'"\[\]\\]
| '\\' [0-3][0-7][0-7]
| '\\' [0-7][0-7]?
| !'\\' .
action = '{' < braces* > '}' -
braces = '{' braces* '}'
| !'}' .
EQUAL = '=' -
COLON = ':' -
SEMICOLON = ';' -
BAR = '|' -
AND = '&' -
NOT = '!' -
QUERY = '?' -
STAR = '*' -
PLUS = '+' -
OPEN = '(' -
CLOSE = ')' -
DOT = '.' -
BEGIN = '<' -
END = '>' -
TILDE = '~' -
RPERCENT = '%}' -
- = ( space | comment )*
space = ' ' | '\t' | end-of-line
comment = '#' ( !end-of-line . )* end-of-line
end-of-line = '\r\n' | '\n' | '\r'
end-of-file = !.
نمادهای زیر را می‌توان در بخش‌های اعلان بازتعریف کرد تا کد تجزیه‌گر تولیدشده تغییر یابد.
- YYSTYPE
-
نوع مقدار معنایی (semantic value). متغیر کاذب «$$» و شناسه‌های «متصل‌شده» (bound) به نتایج قواعد با عملگر دونقطه «:» همگی باید دارای این نوع در نظر گرفته شوند. مقدار پیش‌فرض «int» است.
- YYPARSE
-
نام نقطه ورود اصلی به تجزیه‌گر. مقدار پیش‌فرض «yyparse» است.
- YYPARSEFROM
-
نام یک نقطه ورود جایگزین به تجزیه‌گر. این تابع به یک آرگومان نیاز دارد: تابعی متناظر با قاعده‌ای که جستجو برای یافتن تطابق باید از آن آغاز شود. مقدار پیش‌فرض «yyparsefrom» است. توجه داشته باشید که ()yyparse به صورت زیر تعریف شده است: int yyparse() { return yyparsefrom(yy_foo); }که در آن «foo» نام نخستین قاعده در گرامر است. - YY_INPUT(buf, result, max_size)
- این ماکرو
توسط
تجزیه‌گر
برای
دریافت متن
ورودی
بیشتر
فراخوانی
می‌شود. buf
به
ناحیه‌ای
از حافظه
اشاره
می‌کند که
حداکثر
می‌تواند
max_size نویسه را
در خود نگه
دارد. این
ماکرو باید
متن ورودی
را در buf کپی
کرده و سپس
متغیر عدد
صحیح result را
طوری
مقداردهی
کند که
نشان‌دهنده
تعداد
نویسه‌های
کپی‌شده
باشد. اگر
ورودی
دیگری در
دسترس
نباشد،
ماکرو باید
مقدار 0 را
به result
اختصاص دهد.
به طور
پیش‌فرض،
ماکروی YY_INPUT به
شرح زیر
تعریف شده
است:
#define YY_INPUT(buf, result, max_size) \ { \ int yyc= getchar(); \ result= (EOF == yyc) ? 0 : (*(buf)= yyc, 1); \ }توجه داشته باشید که اگر YY_CTX_LOCAL تعریف شده باشد (به ادامه مراجعه کنید)، یک آرگومان نخست اضافی حاوی بافت (context) تجزیه‌گر به YY_INPUT فرستاده می‌شود. - YY_DEBUG
- اگر این نماد تعریف شود، کدهای اضافی به تجزیه‌گر افزوده خواهند شد که مقادیر فراوانی از اطلاعات فنی و پیچیده را هنگام اجرای تجزیه‌گر در خروجی خطای استاندارد (stderr) چاپ می‌کنند.
- YY_BEGIN
- این ماکرو
برای
علامت‌گذاری
آغاز متن
ورودی که در
کنش‌ها به
عنوان «yytext»
در دسترس
خواهد بود
فراخوانی
می‌شود. این
ماکرو
متناظر با
رخدادهای
«<» در
گرامر است.
این موارد
به
گزاره‌هایی
(predicates) تبدیل
می‌شوند که
انتظار
می‌رود با
موفقیت
انجام شوند.
تعریف
پیش‌فرض:
#define YY_BEGIN (yybegin= yypos, 1)
بنابراین موقعیت فعلی ورودی را ذخیره کرده و مقدار 1 («درست») را به عنوان نتیجه گزاره بازمی‌گرداند. - YY_END
- این ماکرو
متناظر با
«>» در
گرامر است.
مجدداً،
این یک
گزاره است،
بنابراین
تعریف
پیش‌فرض،
موقعیت
ورودی را
پیش از
«موفق شدن»
ذخیره
می‌کند.
#define YY_END (yyend= yypos, 1)
- YY_PARSE(T)
- این ماکرو
نقاط ورود
تجزیه‌گر (yyparse
و yyparsefrom) را از
نوع T اعلان
می‌کند.
تعریف
پیش‌فرض:
#define YY_PARSE(T) T
قابلیت دید سراسری (global visibility) را برای ()yyparse و ()yyparsefrom باقی می‌گذارد. اگر آن‌ها نباید در سایر فایل‌های منبع به صورت خارجی قابل مشاهده باشند، این ماکرو می‌تواند بازتعریف شود تا آن‌ها را به صورت «static» اعلان کند:#define YY_PARSE(T) static T
- YY_CTX_LOCAL
- اگر این
نماد در
زمان
کامپایل
تجزیه‌گر
تولیدشده
تعریف شده
باشد،
وضعیت
سراسری
تجزیه‌گر
در ساختاری
از نوع «yycontext»
نگهداری
می‌شود که
می‌تواند
به عنوان یک
متغیر محلی
اعلان گردد.
این قابلیت
اجازه
می‌دهد
چندین
نمونه از
تجزیه‌گرها
در کنار
یکدیگر
همزیستی
داشته
باشند و به
صورت
ریسه‌امن
(thread-safe) عمل کنند.
تابع تجزیه
yyparse() طوری
اعلان
خواهد شد که
انتظار
دریافت یک
آرگومان
نخست از نوع
«* yycontext» را
داشته
باشد، که
نمونه‌ای
از ساختار
نگهدارنده
وضعیت
سراسری
تجزیه‌گر
است. این
نمونه باید
توسط
کلاینت
تخصیص داده
شده و با
صفر
مقداردهی
اولیه شود.
یک مثال
ساده اما
کامل به شرح
زیر است:
#include <stdio.h> #define YY_CTX_LOCAL #include "the-generated-parser.peg.c" int main() { yycontext ctx; memset(&ctx, 0, sizeof(yycontext)); while (yyparse(&ctx)); return 0; }توجه داشته باشید که اگر این نماد تعریف نشده باشد، تجزیه‌گر کامپایل‌شده وضعیت سراسری خود را به صورت ایستا تخصیص می‌دهد و نه بازورودپذیر (reentrant) و نه ریسه‌امن (thread-safe) خواهد بود. همچنین توجه داشته باشید که ساختار yycontext تجزیه‌گر در نخستین باری که yyparse() فراخوانی می‌شود به طور خودکار مقداردهی اولیه می‌گردد؛ بنابراین این ساختار باید حتماً پیش از نخستین فراخوانی yyparse() به درستی با صفر مقداردهی اولیه شده باشد. - YY_CTX_MEMBERS
- اگر YY_CTX_LOCAL تعریف شده باشد (بالا را ببینید)، ماکروی YY_CTX_MEMBERS می‌تواند به گونه‌ای تعریف شود که به هرگونه اعلان فیلد عضو اضافی که کلاینت تمایل دارد در اعلان نوع ساختار «yycontext» گنجانده شود گسترش یابد. این اعضای اضافی در غیر این صورت توسط تجزیه‌گر تولیدشده نادیده گرفته می‌شوند. نمونه‌ای از «yycontext» که با تجزیه‌گر فعال کنونی مرتبط است، درون کنش‌ها به عنوان متغیر اشاره‌گر yy در دسترس خواهد بود.
- YY_BUFFER_SIZE
- اندازه اولیه بافر متن، بر حسب بایت. مقدار پیش‌فرض 1024 است و اندازه بافر هر زمان که برای برآورده کردن تقاضا در طول تجزیه نیاز باشد دو برابر می‌شود. برنامه‌ای که معمولاً رشته‌های بسیار طولانی‌تری را تجزیه می‌کند می‌تواند این مقدار را افزایش دهد تا از تخصیص مجدد غیرضروری بافر جلوگیری شود.
- YY_STACK_SIZE
- اندازه اولیه پشته‌های متغیرها و کنش‌ها. مقدار پیش‌فرض 128 است که در حین تجزیه هر زمان که برای برآورده کردن تقاضا نیاز باشد دو برابر می‌شود. برنامه‌هایی که دارای پشته‌های فراخوانی عمیق با متغیرهای محلی فراوان هستند، یا کنش‌های متعددی را پس از یک تطابق موفق انجام می‌دهند، می‌توانند این مقدار را افزایش دهند تا از تخصیص مجدد غیرضروری بافر جلوگیری کنند.
- YY_MALLOC(YY, SIZE)
- تخصیص‌دهنده حافظه برای تمام فضاهای ذخیره‌سازی مرتبط با تجزیه‌گر. پارامترها عبارتند از ساختار yycontext کنونی و تعداد بایت‌ها برای تخصیص. تعریف پیش‌فرض عبارت است از: malloc(SIZE)
- YY_REALLOC(YY, PTR, SIZE)
- تخصیص‌دهنده مجدد حافظه برای فضاهای ذخیره‌سازی با رشد پویا (مانند بافرهای متن و پشته‌های متغیر). پارامترها عبارتند از ساختار yycontext کنونی، فضای ذخیره‌سازی تخصیص‌یافته قبلی، و تعداد بایت‌هایی که فضا باید به آن اندازه افزایش یابد. تعریف پیش‌فرض عبارت است از: realloc(PTR, SIZE)
- YY_FREE(YY, PTR)
- آزادساز حافظه. پارامترها عبارتند از ساختار yycontext کنونی و حافظه‌ای که باید آزاد شود. تعریف پیش‌فرض عبارت است از: free(PTR)
- YYRELEASE
- نام تابعی که تمام منابع نگه‌داشته‌شده توسط ساختار yycontext را آزاد می‌کند. مقدار پیش‌فرض «yyrelease» است.
درون کنش‌ها می‌توان به متغیرهای زیر ارجاع داد:
- char *yybuf
- این متغیر به بافر ورودی تجزیه‌گر اشاره می‌کند که برای ذخیره متن ورودی تطبیق‌نیافته استفاده می‌شود.
- int yypos
- این آفست (در داخل yybuf) مربوط به نویسه بعدی است که باید تطبیق داده شده و مصرف شود.
- char *yytext
- جدیدترین متن تطبیق‌یافته که بین '<' و '>' محصور شده است، در این متغیر ذخیره می‌شود.
- int yyleng
- این متغیر نشان‌دهنده تعداد نویسه‌ها در «yytext» است.
- yycontext *yy
- این متغیر به نمونه‌ای از «yycontext» اشاره می‌کند که با تجزیه‌گر فعال کنونی مرتبط است..PP برنامه‌هایی که مایلند تمام منابع مرتبط با یک تجزیه‌کننده را آزاد کنند، می‌توانند از تابع زیر استفاده کنند.
- yyrelease(yycontext*yy)
- تمام حافظه تخصیص‌یافته توسط تجزیه‌کننده را که مرتبط با yy است به سیستم بازمی‌گرداند. این حافظه در فراخوانی بعدی yyparse() مجدداً تخصیص خواهد یافت.
توجه داشته باشید که حافظه خودِ ساختار yycontext هرگز به‌طور ضمنی تخصیص داده نشده یا بازپس گرفته نمی‌شود. برنامه باید این ساختارها را در حافظه خودکار (automatic storage) تخصیص دهد، یا از calloc() و free() برای مدیریت صریح آن‌ها استفاده نماید. مثال بخش بعد، یکی از روش‌های مدیریت منابع را نشان می‌دهد.
مثال LEG: گسترش زمینه تجزیه‌کننده (LEG EXAMPLE: EXTENDING THE PARSER'S CONTEXT)
متغیر yy که به کنش‌ها (actions) ارسال می‌شود، شامل وضعیت تجزیه‌کننده به‌همراه هرگونه فیلد اضافی تعریف‌شده توسط YY_CTX_MEMBERS است. این فیلدها می‌توانند برای ذخیره اطلاعات خاص برنامه که برای فراخوانی مشخصی از yyparse() سراسری هستند، به کار روند. در ادامه یک مثال ساده اما کامل از leg آمده است که در آن ساختار yycontext با یک count از تعداد نویسه‌های خط جدید دیده‌شده در ورودی تا این لحظه گسترش می‌یابد (در غیر این صورت، گرامر کل ورودی را مصرف کرده و نادیده می‌گیرد). فراخوانندهٔ yyparse() از count برای چاپ تعداد خطوط ورودی خوانده‌شده استفاده می‌کند.
%{
#define YY_CTX_LOCAL 1
#define YY_CTX_MEMBERS \
int count;
%}
Char = ('\n' | '\r\n' | '\r') { yy->count++ }
| .
%%
#include <stdio.h>
#include <string.h>
int main()
{
/* create a local parser context in automatic storage */
yycontext yy;
/* the context *must* be initialised to zero before first use*/
memset(&yy, 0, sizeof(yy));
while (yyparse(&yy))
;
printf("%d newlines\n", yy.count);
/* release all resources associated with the context */
yyrelease(&yy);
return 0;
}
خطاها (DIAGNOSTICS)
ابزارهای peg و leg هنگام تبدیل یک گرامر به یک تجزیه‌کننده، در شرایط زیر هشدار می‌دهند.
- syntax error
- گرامر ورودی به نحوی نادرست و معیوب بوده است. پیام خطا شامل متنی خواهد بود که قرار بوده تطبیق داده شود (که اغلب به میزان زیادی از مکان واقعی خطا عقب‌تر است) و شماره خط آخرین نویسه بررسی‌شده (که اغلب مکان واقعی مشکل است).
- rule 'foo' used but not defined
- گرامر به قانونی به نام 'foo' ارجاع داده اما هیچ تعریفی برای آن ارائه نشده است. تلاش برای استفاده از تجزیه‌کننده تولیدشده احتمالاً به دلیل نمادهای تعریف‌نشده مرتبط با قانون ناموجود، منجر به خطای پیونددهنده (linker) خواهد شد.
- rule 'foo' defined but not used
- گرامر قانونی به نام 'foo' را تعریف کرده و سپس آن را نادیده گرفته است. کدهای مرتبط با این قانون در تجزیه‌کننده تولیدشده گنجانده می‌شوند و تجزیه‌کننده از هر جهت دیگر بی‌نقص خواهد بود.
- possible infinite left recursion in rule 'foo'
- حداقل یک مسیر در گرامر وجود دارد که از قانون 'foo' بدون مصرف هیچ ورودی، دوباره به (یک فراخوانی بازگشتی از) همان قانون بازمی‌گردد.
بازگشت به چپ، به‌ویژه مواردی که در اسناد استاندارد یافت می‌شوند، اغلب «مستقیم» هستند و بر تکرار ساده دلالت دارند.
# (6.7.6)
direct-abstract-declarator =
LPAREN abstract-declarator RPAREN
| direct-abstract-declarator? LBRACKET assign-expr? RBRACKET
| direct-abstract-declarator? LBRACKET STAR RBRACKET
| direct-abstract-declarator? LPAREN param-type-list? RPAREN
این بازگشت
را می‌توان
به‌سادگی
با تبدیل
بخش‌هایی
از الگو که
پس از
بازگشت
می‌آیند به
یک پسوند
قابل
تکرار، حذف
کرد.
# (6.7.6)
direct-abstract-declarator =
direct-abstract-declarator-head?
direct-abstract-declarator-tail*
direct-abstract-declarator-head =
LPAREN abstract-declarator RPAREN
direct-abstract-declarator-tail =
LBRACKET assign-expr? RBRACKET
| LBRACKET STAR RBRACKET
| LPAREN param-type-list? RPAREN
تجزیه‌کننده‌ای که ورودی خالی را بپذیرد،
همواره
موفق خواهد شد. مثال زیر را در نظر بگیرید که برای اولین تلاش در نوشتن یک تجزیه‌کننده مبتنی بر PEG چندان غیرمعمول نیست:
Program = Expression*
Expression = "whatever"
%%
int main() {
while (yyparse())
puts("success!");
return 0;
}
این برنامه
صرف‌نظر از
اینکه چه
ورودی‌ای
(در صورت
وجود) در stdin
ارائه شود،
تا ابد در
حلقه اجرا
می‌شود.
راه‌حل‌های
متعددی
امکان‌پذیر
است که
ساده‌ترین
آن‌ها
اصرار بر
این است که
تجزیه‌کننده
همواره
مقداری
ورودی
غیرخالی را
مصرف کند.
تغییر خط
اول به
Program = Expression+این هدف را محقق می‌سازد. اگر انتظار می‌رود تجزیه‌کننده کل ورودی را مصرف کند، الزام صریح پایان فایل (end-of-file) نیز اکیداً توصیه می‌شود:
Program = Expression+ !.این روش کار می‌کند چرا که تجزیه‌کننده تنها زمانی در تطبیق گزاره («!») با هر نویسه‌ای (عبارت «.») شکست می‌خورد که تلاش کند فراتر از انتهای ورودی را بخواند.
گزارش باگ‌ها (BUGS)
برای خواندن صفحه راهنمای leg(1) باید عبارت 'man peg' را وارد کنید.
پیشوندهای 'yy' و 'YY' را نمی‌توان تغییر داد.
بازگشت به چپ در گرامر ورودی شناسایی می‌شود، اما در تجزیه‌کننده تولیدشده به‌درستی مدیریت نمی‌شود.
پیام‌های خطایابی برای خطاهای گرامر ورودی مبهم هستند و کمک چندانی نمی‌کنند.
عملگرهای ! و ~ در واقع باید برعکس یکدیگر نام‌گذاری می‌شدند.
چندین قابلیت پرکاربرد lex(1) (نظیر ()yywrap، yyin و غیره) کاملاً غایب هستند.
تجزیه‌کننده تولیدشده حاوی رهنمودهای '#line' برای ارجاع خطاهای کامپایلر C به توصیف گرامر در مواقع مناسب نیست.
همچنین ببینید (SEE ALSO)
D. Val Schorre, META II, a syntax-oriented compiler writing language, 19th ACM National Conference, 1964, pp. 41.301--41.311. یک مولد تجزیه‌کننده خودپیاده‌ساز را برای گرامرهای تحلیلی بدون عقب‌گرد (backtracking) توصیف می‌کند.
Alexander Birman, The TMG Recognition Schema, Ph.D. dissertation, Princeton, 1970. بررسی ریاضی قدرت و پیچیدگی تجزیه بازگشتی-نزولی با عقب‌گرد (backtracking).
Bryan Ford, Parsing Expression Grammars: A Recognition-Based Syntactic Foundation, ACM SIGPLAN Symposium on Principles of Programming Languages, 2004. تعریف PEGها و تحلیل آن‌ها در رابطه با گرامرهای مستقل از متن و منظم. معرفی نحو اتخاذشده در peg.
ابزارهای استاندارد یونیکس lex(1) و yacc(1) که بر نحو و ویژگی‌های leg تأثیر گذاشتند.
کد منبع برای peg و leg که تجزیه‌کننده‌های گرامر آن‌ها با استفاده از خودشان نوشته شده‌اند.
آخرین نسخه این نرم‌افزار و مستندات:
http://piumarta.com/software/pegنویسندگان (AUTHORS)
peg، leg و این صفحه راهنما توسط Ian Piumarta (first-name at last-name dot com) در حین تحقیق پیرامون امکان‌پذیری استفاده از گرامرهای منظم و عبارت تجزیه برای استخراج کارآمد اطلاعات نوع و امضا از فایل‌های سرآیند C نوشته شده‌اند.
لطفاً گزارش باگ‌ها و پیشنهادات بهبود را به نشانی بالا برای نویسنده ارسال کنید.
| September 2013 | Version 0.1 |