گرامر صفت

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

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

تاریخچه

دستور زبان صفت توسط دونالد نوت (به انگلیسی: Donald Knuth) و پیتر وگنر (به انگلیسی: Pete Wegner) اختراع شده‌است. درحالیکه دونالد نوت مفهوم کلی گرامر صفت را مطرح کرده بود، پیتر وگنر مفهوم صفت موروثی را اختراع کرد.

مثال

در ادامه یک گرامر مستقل از متن را مشاهده می‌کنید که زبان حاصل از آن، ضرب و جمع اعداد صحیح را توصیف کند.

Expr → Expr + Term
Expr → Term
Term → Term * Factor
Term → Factor
Factor →"("Expr")"
Factor → integer/Expr

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

Expr1 → Expr2 + Term  [Expr1.value = Expr2.value + Term.value]
Expr → Term  [Expr.value = Term.value]
Term1 → Term2 * Factor  [Term1.value = Term2.value * Factor.value]
Term → Factor  [Term.value = Factor.value]
Factor →"("Expr")"  [Factor.value =  Expr.value]
Factor → integer  [Factor.value = strToInt(integer.str)]

صفت ترکیبی

یک صفت ترکیبی از مقادیر صفات گره‌های فرزندانش محاسبه می‌شود. از آنجا که ابتدا باید مقدار صفت گره‌های فرزند محاسبه شود، این فرایند به شکل پایین به بالا است. برای تعریف رسمی یک صفت ترکیبی، فرض کنید:$G=\langle V_{n},V_{t},P,S\rangle$ تعریف صوری یک دستور زبان باشد، تفسیر هر یک از نمادها به شرح زیر است:

• ٰ$V_{n}$ مجموعه نمادهای غیر پایانی یا متغیرها است.
• $V_{t}$ مجموعه نمادهای پایانی است.
• P مجموعه قواعد تولید گرامر است.
• S نماد شروع گرامر است.

حال یک رشته از نمادهای غیر پایانه یا متغیرها(A) و یک صفت به نام a را در نظر بگیرید، A.a در صورت برقراری هر سه شرط زیر یک صفت ترکیبی است:

• $A\rightarrow \alpha \in P$ (به عبارت دیگر $A\rightarrow \alpha$ یکی از قواعد دستور زبان باشد).
• $\alpha =\alpha _{1}\ldots \alpha _{n},\forall i,1\leq i\leq n:\alpha _{i}\in (V_{n}\cup V_{t})$ (یعنی هر نمادی در بدنه یک قاعدهٔ تولید، یا غیر پایانه (متغیر) یا پایانه باشد)
• $A.a=f(\alpha _{j_{1}}.a_{1},\ldots ,\alpha _{j_{m}}.a_{m})$ ، که $\{\alpha _{j_{1}},\ldots ,\alpha _{j_{m}}\}\subseteq \{\alpha _{1},\ldots ,\alpha _{n}\}$ (یعنی مقدار صفت، یک تابع f است، که بر روی برخی از مقادیر نمادهای موجود در بدنهٔ یک قاعده اعمال می‌شود)

صفت موروثی

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

S→ABC

در این قاعده، A می‌تواند مقادیر S ,B و C را بدست آورد، B می‌تواند مقادیر S ,A و C را بدست آورد. به همین ترتیب C می‌تواند مقادیر S ,A و B را بگیرد.

انواع دستور زبان صفت

• گرامر صفت L: این گرامر، هم از صفت‌های موروثی و هم از صفت‌های ترکیبی می‌تواند استفاده کند، با این شرط که صفت‌ها از چپ به راست در درخت نحو تجزیه ارزیابی شده و مقدار گیرند.
• گرامر صفت LR: در این گرامرها مقدار صفات براساس تجزیهٔ LR مورد ارزیابی قرار می‌گیرند. این گرامرها زیر مجموعه ای از گرامرهای صفت L، و گرامر صفت S، زیر مجموعه این گرامرها می‌باشد.
• گرامر صفت ECLR: گرامر صفت ECLR یک نوع از گرامر LR است، که در آن از رابطه هم‌ارزی برای بهینه‌سازی ارزیابی صفات استفاده می‌شود.
• گرامر صفت S: یک نوع ساده از گرامر صفت، که فقط از صفات ترکیبی استفاده می‌کند، و از صفات موروثی استفاده نمی‌کند.