گرامرهای عبارت قطعی

گرامرهای عبارت قطعی (نام علمی: Definite Clause Grammar (DCG)) روشی است برای توضیح گرامر زبان‌های رسمی و طبیعی، که در برنامه‌نویسی منطقی مورد استفاده قرار می‌گیرد. این مفهوم بسیار به مفاهیم گرامرهای صفتی و گرامرهای مضافی مرتبط است که هر دو توسط زبان Prolog توسعه پیدا کرده‌اند. این گرامرها معمولاً در کنار زبان Prolog مطرح می‌شوند اما زبان‌های شبیه به آن هم مانند مرکوری (Mercury) شامل "DCG"ها هستند.

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

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

بندهای قطعی DCG را می‌توان مجموعه ای از جملات بدیهی در نظر گرفت که می‌توان بر اساس آن‌ها معتبر بودن یک جمله را در گرامر مورد نظر بررسی کرد. به عبارت دیگر این مجموعه جملات بدیهی کمک خواهند کرد که تشخیص دهیم آیا می‌توان برای ورودی یک درخت پارس (Pars tree) یکتا ساخت یا خیر. استفاده از این روش تشخیص عضویت ورودی به زبان و تشکیل درخت پارس آن را به یک مسئله ساده قابل حل تبدیل می‌کند.

تاریخچه

تاریخچه DCGها به تاریخچه زبان برنامه‌نویسی Prolog گره خورده‌است. تاریخچه Prolog نیز به تحقیقات و پژوهش‌های مختلفی برمی‌گردد که مرکزیت آن‌ها به دو شهر مارسی فرانسه و ادینبرو اسکاتلند برمی‌گردد. بر اساس نقل قولی از رابرت کوالسکی که یکی از برنامه نویسان قدیمی زبان Prolog است، اولین ورژن از Prolog در سال ۱۹۷۲ توسط آلاین کلمراویر و فیلیپ راسل ارائه شد. اولین برنامه ای که با این زبان برنامه‌نویسی نوشته شد، یک سیستم پردازش زبان طبیعی بزرگ بود. فرناندو پریرا و دیوید وارن از دانشگاه ادینبرو هم در توسعه نسخه‌های اولیه Prolog نقش مؤثری داشتند.

کلمراویر پیش تر بر روی یک سیستم پردازش زبان به نام سیستم Q کار کرده بود که برای ترجمه متون بین زبان‌های فرانسوی و انگلیسی استفاده می‌شد. درسال ۱۹۷۸ کلمراویر مقاله ای در رابطه با روشی برای بیان کردن گرامرها نوشت و در آن مثال‌هایی از برنامه‌هایی که از آن‌ها استفاده می‌کردند آورد. او نام گرامرهای متامورفوسیس را برای این دسته از گرامرها قرار داد. این گرامرها قسمتی از نسخهٔ مارسی Prolog بودند.

پریرا و وارن از توسعه دهندگان Prolog که قبل‌تر معرفی شدند برای اولین بار گرامر عبارت-قطعی را مطرح کردند و پایه‌گذار عبارت DCG در Prolog بودند. آن‌ها در ادامه ایده گرامرهای متامورفوسیس، گرامرهای عبارت-قطعی را به عنوان زیرمجموعه‌ای از گرامرهای متامورفوسیس معرفی کردند. این ایده در مقاله‌ای تحت عنوان «گرامرهای عبارت-قطعی برای تحلیل زبان ها» منتشر شد و در آن بیان شد که DCGها شکل فرمول گونه گرامرها هستند به طوری که گرامر توسط عبارت‌های قطعی منطق مرتبه اول بیان می‌شود.

توسعه‌دهندگان Prolog در ادامه دربارهٔ ابعاد مختلف DCGها در مقاله‌های مختلفی نوشتند.

مثال‌ها

مثال زیر نمونه ای ساده از قسمتی از گرامر زبان انگلیسی است که در آن یک جمله از دو عبارت اسمی و فعلی تشکیل شده‌است که عبارت اسمی می‌تواند از ترکیب یک حرف اضافه و اسم تشکیل شود و عبارت فعلی از ترکیب یک فعل و یک عبارت اسمی ساخته می‌شود. این گرامر به روش DCG به صورت زیر نمایش داده می‌شود.

 sentence --> noun_phrase, verb_phrase.
 noun_phrase --> det, noun.
 verb_phrase --> verb, noun_phrase.
 det --> [the].
 det --> [a].
 noun --> [cat].
 noun --> [bat].
 verb --> [eats].

جملات “the cat eats the bat” و “a bat eats the cat” مثال‌هایی هستند که با گرامر تعریف شده می‌توان ساخت. برای ساختن تمام جملات حاصل از این گرامر می‌توان از دستور زیر درمفسر Prolog استفاده نمود. برای تشخیص این که جمله‌ای متعلق به این زبان هست یا خیر هم می‌توان از دستور خاصی استفاده کرد که در زیر آمده‌است (در صورتی که جمله مورد بررسی the bat eats the bat باشد).

sentence(X,[])
sentence([the,bat,eats,the,bat],[])

ترجمه به عبارت‌های قطعی

در واقع استفاده از DCG برای بهتر نشان دادن عبارات قطعی ساده در Prolog است. مثال قبل به صورت عملی در Prolog به وسیله DCG به فرم زیر نوشته می‌شود:

 sentence(A,Z) :- noun_phrase(A,B), verb_phrase(B,Z).
 noun_phrase(A,Z) :- det(A,B), noun(B,Z).
 verb_phrase(A,Z) :- verb(A,B), noun_phrase(B,Z).
 det([the|X], X).
 det([a|X], X).
 noun([cat|X], X).
 noun([bat|X], X).
 verb([eats|X], X).

لیست‌های تفاوت

به ورودی‌های هر تابع در بالا (مثل (A,B)) لیست‌های تفاوت گویند. لیست‌های تفاوت روشی برای نشان دادن پیشوند یک لیست (یا یک رشته) هستند که این کار را به وسیله تفاوت بین پسوند دو ورودی انجام می‌دهد.

به‌طور مثال در نمونه زیر یک لیست پیشوندی تکی، به صورت لیست‌های تفاوت نوشته شده‌است.

P = [H] ---> [H|X] and X

گرامرهای وابسته به متن

در Prolog، در واقع DCGهای عادی پارامتر دیگری برای توابع درنظر نمی‌گیرد (همان‌طور که در بالا اشاره شد). به همین دلیل تنها می‌تواند برای استفاده در گرامرهای مستقل از متن به کار گرفته شود. با به کار گرفتن متغیرهای ورودی بیشتر، می‌توان DCGها را برای گرامرهای وابسته به متن نیز به کار برد. مثال زیر همین کاربرد را نشان می‌دهد:

 s --> a(N), b(N), c(N).
 a(0) --> [].
 a(M) --> [a], a(N), {M is N + 1}.
 b(0) --> [].
 b(M) --> [b], b(N), {M is N + 1}.
 c(0) --> [].
 c(M) --> [c], c(N), {M is N + 1}.

عبارات بالا در واقع یک DCG برای گرامر زبانی است که رشته روبرو را تولید می‌کند؛ $a^{n}b^{n}c^{n}$.

نمایش محدودیت زبان‌ها

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

 sentence --> pronoun(subject), verb_phrase.
 verb_phrase --> verb, pronoun(object).
 pronoun(subject) --> [he].
 pronoun(subject) --> [she].
 pronoun(object) --> [him].
 pronoun(object) --> [her].
 verb --> [likes].

در مثال بالا گرامری دیده می‌شود که بر روی جملاتش محدودیت‌هایی دارد. مثلاً "he likes her“ و "he likes him“ مورد قبول هستند ولی "her likes he“ و "him likes him“ پذیرفته نیستند.