Global index grammar
گلوبل انڈیکس گرائمر (جی آئی جی) گرائمر کی ایک کلاس ہے جسے کاسٹانو (2004) میں متعارف کرایا گیا ہے تاکہ قدرتی زبان کے گرائمر اور جینوم گرائمر سمیت متعدد مظاہر کا نمونہ بنایا جا سکے۔ جی آئی جی کی سب سے آسان وضاحت انڈیکس شدہ گرائمرز کے مقابلے میں ہے۔ جبکہ انڈیکس شدہ گرائمرز میں، انڈیکس کا ایک اسٹیک ہر نان ٹرمینل علامت کے ساتھ وابستہ ہوتا ہے، اور مشتق کے کورس کے لحاظ سے ایک سے دوسرے میں مختلف ہو سکتا ہے، جی آئی جی میں، ایک واحد عالمی انڈیکس اسٹیک ہوتا ہے جو مشتق کے دوران ہیرا پھیری کرتا ہے (جو کسی بھی دوبارہ لکھنے والے آپریشن کے لیے سختی سے بائیں طرف ہوتا ہے جو علامت کو اسٹیک پر دھکیلتا ہے)۔ عالمی اسٹیک کے وجود کی وجہ سے، ایک جی آئی جی مشتق کو مکمل سمجھا جاتا ہے جب دوبارہ لکھنے کے لیے کوئی غیر ٹرمینل علامتیں باقی نہ ہوں، اور اسٹیک خالی ہو۔ قاعدہ تفصیل جی آئی جی کے اصول بنیادی طور پر چار شکلوں میں آتے ہیں: وہ اصول جو کچھ غیر مشروط طور پر کرتے ہیں، وہ اصول جو اسٹیک کی سب سے اوپر کی علامت پر مشروط کچھ کرتے ہیں، وہ اصول جو اسٹیک پر دھکیلتے ہیں، اور وہ اصول جو اسٹیک سے پاپ ہوتے ہیں۔ ہم ان کو بدلے میں اس طرح نوٹ کر سکتے ہیں: {| |-| | (غیر مشروط طور پر A کو دوبارہ لکھیں، اسٹیک پر کچھ نہ کریں) |-| (A کو دوبارہ لکھیں جیسے کہ f سب سے اوپر اسٹیک کی علامت ہے، اسٹیک پر کچھ نہ کریں) |-| (غیر مشروط طور پر A کو دوبارہ لکھیں اور f کو اسٹیک پر دبائیں) |-| (مشروط طور پر A کو دوبارہ لکھیں جیسے کہ f اسٹیک کی سب سے اوپر کی علامت ہے، پھر اسٹیک سے پاپ f) |} جہاں f کوئی انڈیکس علامت ہے، ٹرمینلز اور/یا غیر ٹرمینل علامتوں کی کوئی بھی سٹرنگ ہے، اور x ایک ٹرمینل علامت ہے۔ کیونکہ کبھی کبھار دوبارہ لکھنے کے اصول کو اسٹیک کے کسی لحاظ سے خالی ہونے پر مشروط کرنے کی ضرورت پڑ سکتی ہے، علامت #کو سب سے نیچے اسٹیک کی علامت کے طور پر استعمال کیا جاتا ہے، جس کا مطلب ہے کہ "خالی" اسٹیک بالکل ایک علامت پر مشتمل ہوتا ہے، #۔ تیسرا قاعدہ فارم، پش رول، کی طرف اشارہ کیا جانا چاہیے، کیونکہ یہ پاپ رول سے مختلف ہے جس میں یہ ضروری ہے کہ تمام پش آپریشنز مشتق سٹرنگ میں کم از کم ایک نئی ٹرمینل علامت متعارف کرائیں۔ اس رکاوٹ کے بغیر، گرائمر کی کلاس ٹائپ-0 ہوگی اور اس طرح ٹورنگ کمپلٹ ہوگا۔ مثال اس مثال کے لیے، ہم مشتق سٹرنگ کو اسٹیک پر رکھ کر مشتق میں مراحل کی نشاندہی کریں گے، جیسا کہ اس میں ہے۔ جی آئی جی (لیکن نیچے کے طور پر ٹی آر جی آئی جی نہیں) مندرجہ ذیل گرائمر کا استعمال کرتے ہوئے غیر انڈیکس شدہ زبان تیار کر سکتے ہیں: سٹرنگ کے لیے مشتق مندرجہ ذیل ہے: اسی طرح کی مشتق، اور اس طرح کے دیگر جملوں کے لیے درج ذیل ہے۔ کمپیوٹیشنل طاقت عالمی اشاریہ زبانیں سیاق و سباق کی حساس زبانوں کا ایک ذیلی مجموعہ ہیں، اور سیاق و سباق سے پاک زبانوں کا ایک سپر سیٹ ہیں۔ یہ معلوم ہے کہ جی آئی جی ایم آئی ایکس/باخ زبان تیار کر سکتے ہیں، جہاں پی سٹرنگ پرموٹیشن فنکشن ہے، جس کا اندازہ لگایا جاتا ہے (لیکن ثابت نہیں ہوتا ہے) کہ یہ انڈیکسڈ زبان کے طور پر قابل نمائندگی نہیں ہے۔ یہ معلوم نہیں ہے کہ تمام آئی جی بھی جی آئی جی ہیں یا نہیں۔ یہ مکمل طور پر ممکن ہے کہ جی آئی جی اور آئی جی سی ایس ایل کے محض اوور لیپنگ ذیلی سیٹوں کی وضاحت کریں۔ جی آئی جیز کی ایک ذیلی کلاس ٹی آر جی آئی جیز کی کلاس ہے، جو پاپ اور پش کے قوانین کو یکساں بناتی ہے، اس پاپ کے قواعد کو مشتق میں کم از کم ایک ٹرمینل علامت بھی متعارف کرانے کی ضرورت ہوتی ہے۔ مثال اس طرح کے گرائمر کی ایک مثال، جو زبان کی خصوصیت رکھتی ہے، یہ ہے: اس سٹرنگ کا مشتق یہ ہے: حوالہ جات رسمی زبانیں گرائمر فریم ورک