گرامر

گرامر (زبان های صوری). گرامر G به صورت یک چهارتایی به شکل G = ( V , T , S , P ) {\displaystyle G=(V\,,T\,,S\,,P\,)}  تعریف می شود که در آن:
V مجموعه ای متناهی از اشیاء است که متغیر نامیده می شوند.
T مجموعه ای متناهی از اشیاء است که پایانه نامیده می شوند.
S ∈ V {\displaystyle S\in V}   یک نماد خاص است که متغیر شروع نامیده می شود.
P مجموعه متناهی از قانون های تولید نامیده می شود.
فرض می کنیم مجموعه های V و T دو مجموعه غیر تهی و مجزا هستند.
گرامر (G=(V,T,S,P را در نظر بگیرید.مجموعه ی{L(G)={w € T* : S =*> W زبان تعریف شده توسط G است.اگر(W € L(G باشد، آنگاه توالی S=> w1 =>w2 => ... =>wn => w را یک اشتقاق از رشته w می گویند. به رشته های S, w1,w2,...,wn که شامل متغیرها و پایانه ها هستند فرم های جمله ای اشتقاق می گویند.