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

تاریخچه 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 برای گرامر زبانی است که رشته روبرو را تولید می‌کند؛ ${\displaystyle 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“ پذیرفته نیستند.