جدول نمادها

جدول نمادها، در علم کامپیوتر، ساختمان داده‌ای است که برای ذخیره کردن اطلاعات توکن‌ها در همگردانی (کامپایل کردن) بکار می‌رود.

معمولاً ابتدای این جدول با اطلاعاتی مثل کلمات کلیدی و رزرو شده زبان پر می‌شود. مابقی جدول نیز با اسم متغیرها، اسم توابع و ... پر می‌شود.

معمولاً به خاطر اینکه این جدوای و هم توسط بخش‌های ترکیبی کامپایلر مورد استفاده قرار می‌گیرد.

زمینه

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

شرح

حداقل اطلاعات موجود در یک جدول نماد که توسط یک مترجم استفاده می شود، شامل نام نماد و محل یا آدرس آن است. جدول نماد برای یک کامپایلر با هدف گذاری برای دارا بودن قابلیت جابجایی جدول نماد شامل ویژگی هایی برای برای قابلیت جابجایی خواهد بود. جدول نماد برای زبان های برنامه نویسی سطح بالا ممکن است نوع نماد، محدوده ها، اندازه و ابعاد آن را ذخیره کند. همه این اطلاعات در فایل خروجی نخواهند بود بلکه برای اشکال زدایی احتمالی محیا شده اند.

پیاده سازی

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

یک کامپایلر ممکن است از یک جدول نماد بزرگ برای همه نمادها استفاده کند یا از جداول نماد سلسله مراتبی جداگانه برای دامنه های مختلف استفاده کند. برای نمونه در یک زبان دامنه دار مثل Algol و یا PL/I یک نماد "p" می تواند به صورت مجزا در چندین دامنه و احتمالاً با ویژگی های متفاوت اعلان گردد. دامنه هر اعلان بخشی از برنامه است که در آن ارجاع به "p" به آن اشاره دارد. هر اعلان یک "p" خاص را بازنمائی می کند.

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

براي كامپايلر مفيد است كه بتواند در صورت لزوم در زمان كامپايل اندازه جدول نماد را به صورت پويا افزايش دهد. اگر در زمان نوشتن كامپايلر، اندازه جدول نماد ثابت باشد، اندازه آن بايد به اندازه كافی بزرگ انتخاب شود تا بتواند هر برنامه مبدا ممكن را اداره نمايد. اين چنين اندازه ثابتی براي اكثر برنامه ها بسيار بزرگ و براي بعضی نامناسب است.

از آنجا که تحلیل گر واژگان بخش زیادی از زمان خود را برای جستجو در جدول نمادها مصرف می کند، این فعالیت تأثیر بسزایی در سرعت کلی کامپایلر دارد. جدول نمادها باید به گونه ای سازماندهی شود که ورودی ها در اسرع وقت پیدا شوند. جداول درهم سازی معمولاً برای سازماندهی یک جدول نماد استفاده می شود، جایی که کلمه کلیدی یا شناسه برای تولید یک زیرنویس آرایه "هش" می شود. برخوردها در جدول درهم سازی اجتناب ناپذیر است و روش معمول رسیدگی به آنها ذخیره مترادف در فضای آزاد بعدی موجود در جدول است.

کاربردها

یک جدول نماد بسته به زبان مورد استفاده برای مقاصد زیر استفاده می‌شود:

• ذخیره‌سازی نام‌های همه گزاره‌ها دریک محل، به شکل ساخت‌یافته
• تأیید این که متغیری اعلان شده است یا نه
• پیاده‌سازی بررسی نوع که تأیید می‌کند انتساب و عبارت‌ها در کد منبع از نظر معناشناختی صحیح هستند
• تعیین دامنه نام (تحلیل دامنه)

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

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

عملیات‌ها

یک جدول نماد چه خطی و چه هَش باید عملیات‌های زیر را ارائه کرده باشد:

()Insert

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

یک خصوصیت برای یک نماد در کد منبع معادل اطلاعاتی است که در مورد آن نماد وجود دارد. این اطلاعات شامل مقدار، وضعیت، دامنه و نوع نماد است. تابع ()insert نماد و خصوصیت‌های آن را به صورت آرگومان‌هایی می‌گیرد و اطلاعات آن را در جدول نماد ذخیره می‌کند.

()lookup

عملیات ()lookup برای جستجوی یک نام در جدول نماد برای تعیین موارد زیر استفاده می‌شود:

• آیا نمادی در جدول وجود دارد؟
• آیا نماد پیش از استفاده اعلان شده است؟
• آیا نام در دامنه خود استفاده شده است؟
• آیا نماد، مقداردهی اولیه شده است؟
• آیا نماد، چندین بار اعلان شده است؟

نمايش اطلاعات محدوده

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

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

هنگامی كه براي نام تازه پويش شده به جدول نماد مراجعه می شود، تنها هنگامی كه انطباق رخ می دهد كه كاراكترهای نام به صورت كاراكتر به كاراكتر با وارده منطبق گردد و شماره همراه آن در وارده جدول نماد با شماره رويه ای كه در حال پردازش است برابر باشد.

نمونه

برنامه زیر را که به زبان C نوشته شده را درنظر بگیرید:

// Declare an external function
extern double bar(double x);

// Define a public function
double foo(int count)
{
    double sum = 0.0;

    // Sum all the values bar(1) to bar(count)
    for (int i = 1; i <= count; i++)
        sum += bar((double) i);
    return sum;
}

یک کامپایلر C که کد بالا را پارس می کند دست کم جدول زیر را تولید می کند:

Scope	Type	Symbol name
extern	double, function	bar
function parameter	double	x
global	double, function	foo
function parameter	int	count
block local	double	sum
for-loop statement	int	i

علاوه بر این، جدول نمادها شامل ورودی هایی است که توسط کامپایلر برای بیان مقادیر میانی تولید می شود.