نمادهای پایانی و غیرپایانی

در علوم کامپیوتر، نمادهای پایانی و غیر پایانی عناصر واژگانی مورد استفاده در تعیین قواعد تولید ایجاد یک دستور زبان رسمی است. نمادهای پایانی نویسه‌های ابتدایی از زبان تعریف شده توسط دستور زبان رسمی هستند و نمادهای غیر پایانی (یا متغیرهای نحوی) با گروهی از نمادهای پایانی با توجه به قوانین تولید جایگزین شده است.

نمادهای پایانی و غیر پایانی دو مجموعه مجزا هستند.

نمادهای پایانی

نمادهای پایانی نمادهایی هستند که می‌توانند در ورودی یا خروجی قوانین تولید دستور زبان رسمی ظاهر شوند و با استفاده از قواعد دستور زبان تغییر نمی‌کنند.

دستور زبان تعریف شده توسط دو قانون زیر را در نظر بگیرید:

1. x می‌تواند xa باشد.
2. x می‌تواند a باشد.

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

نمادهای غیرپایانی

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

گرامرهای مستقل از متن گرامرهایی هستند که در آن سمت چپ هر قانون تولید می‌توان تنها یک نماد غیر پایانی قرار داد. همهٔ زبان‌ها را نمی‌توان توسط گرامرهای مستقل از متن تولید کرد. گرامرهای مستقل از متن گرامرهایی هستند که توسط یک ماشین پشته‌ای غیر قطعی قابل تشخیص باشند. زبان‌های مستقل از متن پایه و اساس بسیاری از زبان‌های برنامه‌نویسی امروزی‌اند.

قواعد تولید

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

هر یک از این قوانین دارای یک سر یا سمت چپ هستند، یک رشته که جایگزین، بدنه یا سمت راست نامیده می‌شود تشکیل می‌شود. قوانین اغلب به صورت head → body نوشته شده است، به عنوان مثال، قانون Z0 → Z1 مشخص می‌کند که Z0 می‌تواند توسط Z1 جایگزین شود.

در رسمی سازی کلاسیک از دستور زبان مولد که اولین بار توسط نوام چامسکی در دههٔ ۵۰ پیشنهاد شد، گرامر G شامل اجزای زیر است:

• مجموعهٔ متناهی $N$ که شامل نمادهای غیر پایانی است.
• مجموعهٔ متناهی $\Sigma$ که شامل نمادهای پایانی است و باید از $N$ مجزا باشد.
• مجموعهٔ متناهی $P$ که شامل قواعد تولید است. هر قاعده تولید به شکل زیر تعریف می‌گردد:

$(\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}$

که در آن $^{*}$ نشانهٔ ستاره کلین و $\cup$ نشان دهنده اجتماع مجموعه است.

• یک نماد با نام $S$ به صورتی که $S\in N$ و نماد شروع است.

یک دستور زبان به صورت یک چهارتایی مرتب $<N,\Sigma ,P,S>$ نشان داده می‌شود.

مثال

به عنوان مثال، موارد زیر نشان دهنده یک مقدار صحیح بیان شده در فرم بکوس-نائور است.

<integer> ::= ['-'] <digit> {<digit>}
<digit> ::= '۰' | '۱' | '۲' | '۳' | '۴' | '۵' | '۶' | '۷' | '۸' | '۹'

در این مثال نمادهای (-،۰٬۱،۲٬۳،۴٬۵،۶٬۷،۸٬۹) نمادهای پایانی و <digit> و <integer> غیرپایانی‌ها هستند.

توجه: رشته‌هایی با آغاز صفر مانند "۰۰۵۶" یا "۰۰۰۰" نیز در این زبان جای می گیرند.

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Terminal and nonterminal symbols». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۲ بهمن ۱۳۹۲.