هک لکسر

در برنامه نویسی کامپیوتر‏‏، "هک لکسر"(Lexer Hack) یک راه حل معمول برای مشکل تجزیه و یا پارس آنسی سی است، از آنجایی که زبان اشاره شده گرامر حساس به متن است. در زبان سی، طبقه‌بندی دنباله ای از اسم متغییر یا نوع اسم نیاز به اطلاعات وابسته به متنی از ساختار عبارت است که از مستقل از متن بودن تحلیل لغوی جلوگیری می کند.

صورت مشکل

مشکل اینجاست که در کد زیر، کلاس لغوی A بدون اطلاعات بیشتر وابسته به متن قابل تصمیم‌گیری نیست:

(A)*B

این کد می تواند ضرب دو متغییر باشد که در این صورت A یک متغییر است، که غیر مبهم نوشته شده:

A * B

در حالتی دیگر، می تواند مقدار بی مرجع B را به نوع A بدهد. که در این صورت A یک اسم typedef (ساخت نوعی جدید) است، که غیر مبهم نوشته شده:

(A) (*B)

اگر نیاز باشد که بیشتر توضیح دهیم، در یک کامپایلر، تحلیل لغوی یکی از اولی ترین مراحل تبدیل کد منبع یه برنامه است. این فاز متن را می خواند و آن را به توکن های معنادار تبدیل می کند. به کلماتی مثل، "عدد"، "رشته" یا ...

پارسر یا فاز تحلیل نحوی دنباله ای از این توکن ها را تحلیل و آنالیز کرده تا با قوانین نحو (سینتکس) آن ها را تطابق دهد. این قوانین نشانکر ساختار هایی در زبان به مانند حلقه (loops) و تعریف متغییر (variable declarations) است.

مشکلی که اینجا می تواند رخ دهد این است که یک دنباله ای از توکن ها بتوانند به طور مبهم دار با بیش از یک قانون نحو تطابق پیدا کنند.

این ابهام می تواند در زبان سی اتفاق بیفتد اگر فاز تحلیل لغوی (لکسر) نتواند بین متغییر و typedef (ساخت نوعی جدید) . فرقی بگذارد.

به عنوان مثال در زبان سی داریم:

(A) * B

فاز تحلیلی امکان دارد این توکن ها را پیدا کند:

1. پرانتز سمت چپ
2. تعیین هویت 'A'
3. پرانتز راست
4. عملگر '*'
5. تعیین هویت 'B'

مشکل دقیقا اینجاست که کلاس لغوی A بدون اطلاعات بیشتر از متن نمی تواند تصمیم گیری انجام دهد: فاز تحلیل نحوی می تواند این را به عنوان "متغییر A ضربدر متغییر B" یا به صورت "مقدار بی مرجع B به نوع A داده شده" تفسیر کند.

نام این مشکل "typedef-اسم: تعیین هویت" است.

راه حل هک

راه حل به طور کلی شامل تغذیه اطلاعات از جدول نمادهای لغوی به فاز تحلیل لغوی (لکسر) است. یعنی به جای اینکه شبیه به یک خط لوله یک طرفه فقط از واژگان به تجزیه کننده عمل کند، یک کانال پشتی از تحلیل معنایی به فاز تحلیل لغوی (لکسر) وجود دارد. این ترکیب پارس کردن(‌از فاز تحلیل نحوی)‌ و تحلیل معنایی عموماً بی‌ظرافت در نظر گرفته می‌شود، به همین دلیل به آن « هک » می‌گویند.

بدون زمینه اطلاعاتی اضافه شده، تحلیل لغوی (لکسر) نمی تواند شناسه های نوع را از سایر شناسه ها تشخیص دهد زیرا همه شناسه ها قالب یکسانی دارند. با هک در مثال بالا، زمانی که تحلیل لغوی (لکسر) شناسه A را پیدا می کند باید بتواند نشانه را به عنوان یک شناسه نوع طبقه بندی کند. قواعد زبان با مشخص کردن اینکه typecastها (اختصاص دادن نوع) به یک شناسه نوع نیاز دارند و ابهام از بین می رود، واضح و مشخص می شود.

این مشکل در ++C نیز وجود دارد و تجزیه کننده ها می توانند از همان هک استفاده کنند.

راه حل های جایگزین

این مشکل هنگام استفاده از تکنیک‌های تجزیه بدون lexer به وجود نمی‌آید (و از این رو برای حل کردن نیازی به "هک" نیست، زیرا اینها ذاتاً متنی هستند. با این حال، این طرح‌ها معمولاً به عنوان طرح‌های کمتر ظریف دیده می‌شوند، زیرا فاقد مدولار بودن داشتن یک lexer و تجزیه‌کننده همزمان در یک خط لوله هستند.

برخی از مولدهای تجزیه کننده، مانند BtYacc مشتق از byacc ("Backtracking Yacc")، به تجزیه کننده تولید شده این توانایی را می دهند که تلاش های متعددی را برای تجزیه توکن ها امتحان کند. در مشکلی که در اینجا توضیح داده شد، اگر تلاشی به دلیل اطلاعات معنایی مربوط به شناسه با شکست مواجه شود، می‌تواند به عقب برگردد و قوانین دیگری را امتحان کند.

تجزیه کننده Clang وضعیت را به روشی کاملاً متفاوت مدیریت می کند، یعنی با استفاده از دستور زبان واژگانی غیر مرجع. لکسر Clang سعی نمی کند بین نام نوع و نام متغیر تمایز قائل شود: فقط نشانه فعلی را به عنوان یک شناسه گزارش می کند. تجزیه کننده سپس از کتابخانه تحلیل معنایی Clang برای تعیین ماهیت شناسه استفاده می کند. این اجازه می دهد تا جداسازی بسیار تمیزتر نگرانی ها و محصورسازی لکسر و تجزیه کننده اتفاق بیفتد، و بنابراین توسط برخی از توسعه دهندگان کامپایلر به عنوان راه حل بسیار زیباتر از هک لکسر در نظر گرفته می شود. این روشی است که در اکثر زبان‌های مدرن دیگر استفاده می‌شود که طبقات مختلف شناسه‌ها را در دستور زبان واژگانی متمایز نمی‌کنند، اما در عوض آن‌ها را به مرحله تجزیه یا تحلیل معنایی، زمانی که اطلاعات کافی در دسترس است، موکول می‌کنند.

همچنین ببینید

Dangling else

استناد

• 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

منابع

This article "هک لکسر" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:هک لکسر. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

This page exists already on Wikipedia.

📰 Article(s) of the same category(ies)

• دیلان اپل
• گروه پورتلند
• واحد ترجمه (برنامه نویسی)
• The lexer hack
• Laning and Zierler سیستم
• Zenith Parsing Engine
• سر تیتر از پیش کامپایل شده

---

 Facebook Page

 Follow us on Twitter !

Read or create/edit this page in another language

• هک لکسر in English