موضوع مقاله: دستور صوری | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # دستور صوری | مقدمه: در نظریهٔ زبان صوری، یک گرامر، مجموعه‌ای از قوانین تولید برای رشته‌ها در زبان صوری است. | ## بخش 1: دستور صوری | این قوانین، چگونگی تولید رشته‌ها را از الفبای زبان، که با توجه به ترکیب زبان معتبرند، توضیح می‌دهند. یک گرامر، معنی رشته‌ها یا چگونگی استفاده از آنها را در متن نشان نمی‌دهد، بلکه فقط نشان‌دهندهٔ فرم رشته‌هاست. نظریهٔ زبان صوری، نظمی که گرامرهای صوری و زبان‌ها را مطالعه می‌کند، شاخه‌ای از ریاضیات کاربردی است. کاربرد آن در علوم نظری رایانه، زبان‌شناسی نظری، معناشناسی صوری، منطق ریاضی، سایر حوزه‌های مشاهده می‌شود. یک گرامر صوری، مجموعه‌ای از قوانین برای بازنویسی رشته‌ها همراه با «نماد شروع» است که بازنویسی با آن آغاز می‌شود. اگرچه این می‌تواند گاهی به عنوان پایه‌ای برای شناسنده (تابعی در محاسبه که مشخص می‌کند یک رشته متعلق به زبان است یا از نظر گرامر اشتباه است) استفاده شود. برای توضیح چنین شناسنده‌هایی، نظریه زبان صوری، از صورت‌های مجزا که به نام نظریه اتوماتا شناخته می‌شوند، استفاده می‌کند. یکی از نتایج جالب نظریه اتوماتا، این است که امکان طراحی یک شناسنده برای زبان‌های رسمی صوری وجود ندارد. تجزیه، فرایندی برای شناسایی یک گفتار (رشته‌ای در زبان طبیعی) با شکستن آن به مجموعه‌ای از نمادها و تحلیل هرکدام از آنها دربرابر گرامر زبان است. در نتیجه گام اول برای توضیح معنی یک گفتار در زبان، بخش بخش کردن آن و توجه به فرم تحلیل شده آن (نمودار درختی در علوم کامپیوتر و ساختار عمیق در دستور زایشی) است. سپس قواعد تولید در هر دستور اعمال می‌شوند تا رشته‌ای که نه شامل نماد آغازین و نه نماد طراحی شده غیرپایانی باشد، تولید شود. یک قاعده تولید روی یک رشته، با جابجا کردن یک رخداد سمت چپ قاعده تولید در رشته، با سمت راست آن قاعده، اعمال می‌شود. | ## بخش 2: دستور صوری | زبان تشکیل شده توسط گرامر شامل تمام رشته‌های مجزا که می‌توانند بدین شکل تولید شوند می‌باشد. هر دنباله مشخص از قواعد تولید در نماد آغازین، یک رشته مجزا در زبان را ایجاد می‌کند. برای مثال، الفبای a و b، با نماد آغازین S و قواعد تولید زیر را در نظر بگیرید: S → aSb S → ba با S شروع می‌کنیم و می‌توانیم یک قاعده برای اعمال روی آن انتخاب کنیم. تعریف رسمی نحوهٔ گرامر در تعریف رسمی کلاسیک گرامر مولد، که برای اولین بار توسط نوآم چامسکی مطرح شد، گرامر G شامل اجزاء زیر: یک مجموعه متناهی از نمادهای غیرپایانی که مجموعه‌ای مجزا از رشته‌های تشکیل شده توسط G است. یک مجموعه متناهی P از قواعد تولید که هر قاعده به فرم * (Σ U N) * N (Σ U N) * → (Σ U N) است که * عمل ستاره کلین و U اجتماع مجموعه‌ها را مشخص می‌کند. بدین شکل هر قاعده تولید، یک رشته از نمادها را روی رشته دیگر می‌نگارد به طوری که اولین رشته، شامل تعدادی دلخواه از نمادهاست که حداقل یکی از آنها غیر پایانی می‌باشند. دومین رشته، فقط شامل رشته تهی است که می‌تواند توسط نمادهای مخصوص (اغلب ε یا Λ) نشان داده شود. یک گرامر به طور رسمی توسط یک چهارتایی (N, Σ, P, S) نشان داده می‌شود به طوری که یک گرامر رسمی در ادبیات، اغلب سیستم بازنویسی یا ساختار عبارت گرامر نامیده می‌شود. معناشناسی گرامر عملیات یک گرامر می‌تواند از نظر رابطه‌ها روی رشته‌ها تعریف شود: مثال سلسله مراتب چامسکی وقتی نوآم چامسکی اولین بار گرامرهای مولد را در ۱۹۵۶ رسمی کرد، او آنها را در انواعی طبقه‌بندی کرد که امروزه به نام سلسله مراتب چامسکی شناخته شده هستند. تفاوت بین این انواع، روند فزاینده سخت قواعد تولید است و می‌تواند تعداد کمتری از زبانهای رسمی را بیان کند. زبان‌هایی که بتوانند توسط چنین گرامری توصیف شوند، به ترتیب زبان‌های مستقل از متن و زبان‌های منظم نام دارند. اگرچه از گرامر نامحدود (نوع ۰) که می‌تواند هر زبانی که توسط ماشین تورینگ پذیرفته می‌شود را بیان کند، بسیار کم قدرت ترند، ولی به دلیل اجرای مؤثر تجزیه کننده‌ها بر آنها، این دو نوع گرامر بیشتر استفاده می‌شوند. | ## بخش 3: دستور صوری | برای مثال، همهٔ زبان‌های منظم می‌توانند توسط یک ماشین حالات متناهی شناخته شوند و الگوریتم‌های شناخته شده‌ای برای زیرمجموعه‌های مفید از گرامرهای مستقل از متن برای تولید تجزیه‌کننده ال‌ال و تجزیه‌کننده ال‌آر برای به رسمیت شناختن زبان‌های متناظر با گرامرهای تولید شده، وجود دارند. گرامرهای مستقل از متن یک گرامر مستقل از متن گرامریست که سمت چپ هر قاعده تولید آن شامل یک نماد غیر پایانیست. این محدودیت بیهوده نیست، چرا که همه زبان‌ها را نمی‌توان توسط گرامرهای مستقل از متن تولید کرد، آنهایی که توسط این گرامرها تولید می‌شوند زبان‌های مستقل از متن نام دارند. زبان {L(G) = {anbncn|n≥۱ که در بالا تعریف شد، یک زبان مستقل از متن نیست و این می‌تواند توسط لم تزریق برای زبان‌های مستقل از متن ثابت شود اما برای مثال زبان {anbn|n≥۱} مستقل از متن است از آنجا که می‌تواند آن را توسط گرامر G2 با {N={S و {Σ= {a,b که S نماد آغازین و قوانین تولید به صورت زیرمیباشند، تولید کرد. به همین دلیل، برای هر زبان مستقل از متن ماشینی می‌تواند ساخته شود که یک رشته را به عنوان ورودی بگیرد و در زمان (O(n3 تشخیص دهد که این رشته عضو زبان است یا خیر که n طول آن رشته می‌باشد. زبان مستقل از متن قطعی زیر مجموعه‌ای از زبان‌های مستقل از متن است که می‌تواند در زمان خطی تشخیص داده شود. الگوریتم‌های متعددی با هدف تشخیص این مجموعه از زبان‌ها یا زیر مجموعه از آنها وجود دارد. گرامرهای منظم در گرامرهای منظم هم سمت چپ یک نماد غیر پایانیست با این تفاوت که سمت راست هم محدودیت دارد. سمت راست ممکن است یک رشته تهی یا یک نماد پایانی یا یک نماد پایانی که با یک نماد غیر پایانی همراه است باشد. اگر چه در عمل گرامرهای منظم عموماً با استفاده از عبارتهای منظم توضیح داده می‌شوند، بعضی شکل‌های عبارت منظم که در عمل استفاده می‌شوند قویا زبان‌های منظم تولید نمی‌کنند و تشخیص خطی از اجرای آن اشتقاق‌ها نشان نمی‌دهند. گرامرهای بازگشتی یک گرامر بازگشتی، گرامری است شامل قواعد تولیدی که بازگشتی می‌باشند. | ## جمع‌بندی | برای مثال، یک گرامر برای زبان مستقل از متن، بازگشتی چپ است اگر یک نماد غیر پایانی A وجود داشته باشد که بتوان آنرا میان قواعد تولید طوری قرار داد که رشته‌ای تولید کند که در آن A، چپ‌ترین نماد است.