هک لکسر
در برنامه‌نویسی کامپیوتر، هک لکسر (Lexer Hack) یک راه حل معمول برای مشکل تجزیه یا پارس آنسی سی است، از آنجایی که زبان اشاره شده گرامر حساس به متن است. در زبان سی، طبقه‌بندی دنباله ای از اسم متغیر یا نوع اسم نیاز به اطلاعات وابسته به متنی از ساختار عبارت است که از مستقل از متن بودن تحلیل لغوی جلوگیری می‌کند.[۱]
صورت مشکل[ویرایش]
مشکل اینجاست که در کد زیر، کلاس لغوی A بدون اطلاعات بیشتر وابسته به متن قابل تصمیم‌گیری نیست:
(A)*B
این کد می‌تواند ضرب دو متغیر باشد که در این صورت A یک متغیر است، که غیر مبهم نوشته شده:
A * B
در حالتی دیگر، می‌تواند مقدار بی مرجع B را به نوع A بدهد. که در این صورت A یک اسم typedef (ساخت نوعی جدید) است، که غیر مبهم نوشته شده:
(A) (*B)
اگر نیاز باشد که بیشتر توضیح دهیم، در یک کامپایلر، تحلیل لغوی یکی از اولی‌ترین مراحل تبدیل کد منبع یه برنامه است. این فاز متن را می‌خواند و آن را به توکن‌های معنادار تبدیل می‌کند. به کلماتی مثل، "عدد"، "رشته" یا …
پارسر یا فاز تحلیل نحوی دنباله ای از این توکن‌ها را تحلیل و آنالیز کرده تا با قوانین نحو (سینتکس) آن‌ها را تطابق دهد. این قوانین نشانکر ساختارهایی در زبان به مانند حلقه (loops) و تعریف متغیر (variable declarations) است.
مشکلی که اینجا می‌تواند رخ دهد این است که یک دنباله ای از توکن‌ها بتوانند به‌طور مبهم دار با بیش از یک قانون نحو تطابق پیدا کنند.
این ابهام می‌تواند در زبان سی اتفاق بیفتد اگر فاز تحلیل لغوی (لکسر) نتواند بین متغیر و typedef (ساخت نوعی جدید).[۲] فرقی بگذارد.
به عنوان مثال در زبان سی داریم:
(A) * B
فاز تحلیلی امکان دارد این توکن‌ها را پیدا کند:
- پرانتز سمت چپ
- تعیین هویت 'A'
- پرانتز راست
- عملگر '*'
- تعیین هویت 'B'
مشکل دقیقاً اینجاست که کلاس لغوی A بدون اطلاعات بیشتر از متن نمی‌تواند تصمیم‌گیری انجام دهد: فاز تحلیل نحوی می‌تواند این را به عنوان "متغیر A ضربدر متغیر B" یا به صورت "مقدار بی مرجع B به نوع A داده شده" تفسیر کند.
نام این مشکل «typedef-اسم: تعیین هویت» است.
راه‌حل هک[ویرایش]
راه حل به‌طور کلی شامل تغذیه اطلاعات از جدول نمادهای لغوی به فاز تحلیل لغوی (لکسر) است؛ یعنی به جای اینکه شبیه به یک خط لوله یک طرفه فقط از واژگان به تجزیه کننده عمل کند، یک کانال پشتی از تحلیل معنایی به فاز تحلیل لغوی (لکسر) وجود دارد. این ترکیب پارس کردن (از فاز تحلیل نحوی) و تحلیل معنایی عموماً بی‌ظرافت در نظر گرفته می‌شود، به همین دلیل به آن «هک» می‌گویند.
بدون زمینه اطلاعاتی اضافه شده، تحلیل لغوی (لکسر) نمی‌تواند شناسه‌های نوع را از سایر شناسه‌ها تشخیص دهد زیرا همه شناسه‌ها قالب یکسانی دارند. با هک در مثال بالا، زمانی که تحلیل لغوی (لکسر) شناسه A را پیدا می‌کند باید بتواند نشانه را به عنوان یک شناسه نوع طبقه‌بندی کند. قواعد زبان با مشخص کردن اینکه typecastها (اختصاص دادن نوع) به یک شناسه نوع نیاز دارند و ابهام از بین می‌رود، واضح و مشخص می‌شود.
این مشکل در ++C نیز وجود دارد و تجزیه کننده‌ها می‌توانند از همان هک استفاده کنند.[۳]
راه‌حل‌های جایگزین[ویرایش]
این مشکل هنگام استفاده از تکنیک‌های تجزیه بدون lexer به وجود نمی‌آید (و از این رو برای حل کردن نیازی به «هک» نیست، زیرا اینها ذاتاً متنی هستند. با این حال، این طرح‌ها معمولاً به عنوان طرح‌های کمتر ظریف دیده می‌شوند، زیرا فاقد مدولار بودن داشتن یک lexer و تجزیه‌کننده همزمان در یک خط لوله هستند.[نیازمند منبع]
برخی از مولدهای تجزیه کننده، مانند BtYacc مشتق از byacc ("Backtracking Yacc")، به تجزیه کننده تولید شده این توانایی را می‌دهند که تلاش‌های متعددی را برای تجزیه توکن‌ها امتحان کند. در مشکلی که در اینجا توضیح داده شد، اگر تلاشی به دلیل اطلاعات معنایی مربوط به شناسه با شکست مواجه شود، می‌تواند به عقب برگردد و قوانین دیگری را امتحان کند.[۴]
تجزیه کننده Clang وضعیت را به روشی کاملاً متفاوت مدیریت می‌کند، یعنی با استفاده از دستور زبان واژگانی غیر مرجع. لکسر Clang سعی نمی‌کند بین نام نوع و نام متغیر تمایز قائل شود: فقط نشانه فعلی را به عنوان یک شناسه گزارش می‌کند. تجزیه کننده سپس از کتابخانه تحلیل معنایی Clang برای تعیین ماهیت شناسه استفاده می‌کند. این اجازه می‌دهد تا جداسازی بسیار تمیزتر نگرانی‌ها و محصورسازی لکسر و تجزیه کننده اتفاق بیفتد، و بنابراین توسط برخی از توسعه دهندگان کامپایلر به عنوان راه حل بسیار زیباتر از هک لکسر در نظر گرفته می‌شود.[۵] این روشی است که در اکثر زبان‌های مدرن دیگر استفاده می‌شود که طبقات مختلف شناسه‌ها را در دستور زبان واژگانی متمایز نمی‌کنند، اما در عوض آن‌ها را به مرحله تجزیه یا تحلیل معنایی، زمانی که اطلاعات کافی در دسترس است، موکول می‌کنند.
پیوند به بیرون[ویرایش]
- http://www.cs.berkeley.edu/~smcpeak/elkhound/sources/elkhound/index.html
- http://cs.nyu.edu/rgrimm/papers/pldi06.pdf
- http://cens.ioc.ee/local/man/CompaqCompilers/ladebug/ladebug-manual-details.html
- DOI.org
- [۱]
- http://groups.google.com/group/comp.compilers/browse_frm/thread/db7f68e9d8b49002/fa20bf5de9c73472?lnk=st&q=%2B%22the+lexer+hack%22&rnum=1&hl=en#fa20bf5de9c73472
منابع[ویرایش]
- ↑ "Lexer hack". Wikipedia (به انگلیسی). 2020-12-10.
- ↑ Roskind, James A. (1991-07-11). "A YACC-able C++ 2.1 GRAMMAR, AND THE RESULTING AMBIGUITIES". Archived from the original on 2007-06-22. Retrieved 2008-11-27.
- ↑ Roskind, James A. (1991-07-11). "A YACC-able C++ 2.1 GRAMMAR, AND THE RESULTING AMBIGUITIES". Archived from the original on 2007-06-22. Retrieved 2008-11-27.
- ↑ "BtYacc 3.0". Based on Berkeley yacc with modifications by Chris Dodd and Vadim Maslov.
- ↑ Bendersky, Eli. "How Clang handles the type / variable name ambiguity of C/C++".