دستور زبان مبهم

در علوم رایانه یک دستور زبان مبهم گرامر مستقل از متن است که در آن رشته ای وجود دارد که می تواند بیش از یک اشتقاق ازسمت چپ داشته باشد. در حالیکه یک دستور زبان غیر مبهم, یک دستورزبان مستقل از متن است که هر رشتهٔ معتبری در آن زبان تنها یک اشتقاق چپ داشته باشد. برای بیشتر زبانها می توان دو دستور زبان مبهم و غیر مبهم نوشت. اما برای بعضی زبانها تنها دستور زبان مبهم می توان نوشت. برای هر زبان غیر تهی می توان یک دستوز ربان مبهم به وسیله در نظر گرفتن دستور زبان بدون ابهام و معرفی قاعده های تکرار یا مترادف نوشت. ( زبان تهی تنها زبانی است که دستوز ربان مبهم ندارد ) به زبانی که تنها دستورزبان مبهم دارد زبان ذاتاً مبهم گویند و زبان مستقل از متن ذاتاً مبهم وجود دارد. گرامرهای مستقل از متن قطعی همیشه غیر مبهم اند؛ و یک زیرگروه مهمی از CFGهای بدون ابهام هستند. با این حال CFGهای بدون ابهام غیر قطعی نیز وجود دارد.
ساده ترین مثال دستور زبان مبهم زیر برای زبان بی اهمیت است، که تنها متشکل از رشته خالی است:
…به این معنی که رشتهٔ تهی ϵ را می توان با هرکدام از دو معادلهٔ تولید بالا به دست آورد و در نتیجه دارای دو اشتقاق چپ است. دستور زبان دیگر برای زبان بی اهمیت به شکل زیر موجود است:
…به این معنی که تولید می تواند خود رشته یا رشتهٔ تهی باشد؛ بنابراین رشته خالی مشتقات سمت چپ به طول ۱، ۲، ۳ و در واقع از هر طولی است، بسته به اینکه چند بار قاعدهٔ A → استفاده شده است. این زبان دارای دستورزبان غیر مبهم است که تنها شامل یک قاعدهٔ تولید :A → ε است. …به این معنی که تولید یکتا می تواند تنها یک رشتهٔ خالی تولید کند که تنها رشتهٔ موجود در زبان است. به عبارت دیگر به وسیلهٔ اضافه کردن موارد تکراری می توان برای زبان های غیر تهی دستورزبان مبهم ساخت.
گرامر مستقل از متن
چون دو تا اشتقاق چپ برای رشتهٔ a + a + a وجود دارد.
گرامر مثال بعدی نیز مبهم است چون دو نمودار درختی برای رشتهٔ a + a − a وجود دارد.
زبانی که تولید می کند ذاتاً مبهم نیست. دستورزبان زیر دستورزبانی غیرمبهم برای آن است.
به طور کلی نمی توانیم مستقیم بگوییم دستورزبانی مبهم است. راندمان تجزیهٔ دستور زبان مستقل از متن به وسیلهٔ ماشینی که آن را می پذیرد مشخص می شود. گرامرهای مستقل از متن قطعی به وسیلهٔ ماشین قطعی پشته ای پذیرفته می شوند؛ و می توانند در زمان خطی تجزیه شوند. به عنوان مثال می توان تجزیه کنندهٔ LR این یک زیرمجموعه ای از گرامر مستقل از متن است که به وسیلهٔ ماشین پشته ای پذیرفته شده و می تواند در زمان چند جمله ای تجزیه شود. به عنوان مثال می توان الگوریتم سی وای کا را نام برد. دستورزبان مستقل از متن غیر مبهم می تواند غیر قطعی باشد به عنوان مثال زبان واروخوانه با طول زوج که روی الفبای ۰ و ۱تعریف شده است دستورزبان مستقل از متن نامبهمS → 0S0 | 1S1 | ε را دارد نام برد. . یک رشتهٔ دلخواه از این زبان بدون خواندن همهٔ حروف اول نمی تواند تجزیه شود. با این وجود نتیجهٔ از بین بردن ابهام دستور زبان ممکن است دستورزبان مستقل از متن باشد و همین باعث بالارفتن راندمان تجزیه اش شود. تولیدکننده های کامپایلر مانند ( YACC ) شامل امکاناتی برای رفع بعضی از انواع ابهام هستند.