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

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

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

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

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

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

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

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

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

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

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

${\displaystyle (\mathrm{\Sigma }\cup N{)}^{\ast }N(\mathrm{\Sigma }\cup N{)}^{\ast }\to (\mathrm{\Sigma }\cup N{)}^{\ast }}$

که در آن ${\displaystyle {}^{\ast }}$

نشانهٔ ستاره کلین و ${\displaystyle \cup }$

نشان دهنده اجتماع مجموعه است.

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

یک دستور زبان به صورت یک چهارتایی مرتب

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

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

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

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