== توکن ==
یک توکن دستهای از متن هستند که به اسم lexemes شناخته میشوند. تحلیلگر واژهای lexemsها را پردازش میکند تا آنها را با توجه به کاربردشان دستهبندی کنند و به آنها معنا دهند. این انتساب معنا tokenization نامیده میشود.
به این خط دستور در زبان C توجه کنید: ;sum=۳+۲ که به این صورت توکن بندی شده استشدهاست:
{| class="wikitable"
|+
== توکنسازی (Tokenization) ==
توکنسازی ، فرایند علامتگذاری و کلاس بندی بخشهاییبخشهایی از رشته یرشتهٔ کاراکترهای ورودی است. سپس توکنهای حاصله به فرمهای دیگر پردازش عبور میکنند. این فرایند میتواند به عنوان زیر وظیفه یوظیفهٔ ورودی [[parsing]] درنظر گرفته شود.
توکنسازی در رشته یرشتهٔ امنیت کامپیوتر معنای متفاوتی دارد.
به عنوان مثال ، در یک رشته یرشتهٔ متنی:
<code>The quick brown fox jumps over the lazy dog</code>
این رشته بهطور ضمنی بر روی فضاها بخشبندی نشده ، همان کاری که یک گوینده یگویندهٔ طبیعی زبان انجام میدهد. ورودی خام که 43 کاراکتر است باید بهطور ضمنی به وسیله جداکننده یجداکنندهٔ فاصله(فضای خالی یا <code>" "</code> یا عبارت منظم <code>/\s{1}/</code> ) به 9 تا توکن تقسیم شود.
توکنها میتوانند در [[XML]] نمایش داده شوند،<syntaxhighlight>
(word lazy)
(word dog))
</syntaxhighlight>وقتی یک کلاس توکن بیش از یک واژه یواژهٔ ممکن را نمایش می دهدمیدهد ، تحلیل گر لغوی غالبا اطلاعات کافی را ذخیره میکند تا بتواند وتژه یوتژهٔ اصلی را از نو تولید کند ، بنابراین میتواند در تحلیل معنایی مورد استفاده قرار گیرد. پارسر معمولاً این اطلاعات را از Lexer فراخوانی میکند و آن را در درخت نحو انتزاع ذخیره یم کند. این کار برای جلوگیری از، از دست رفتن اطلاعات در مورد اعدا و شناسه(identifier)ها الزامی است.
توکنها براساس قوانین مشخصی از Lexer معرفی(شناسایی) میشوند. برخی از متدهایی که برای شناسایی توکنها به کاربرده میشوند ، شامل : عبارات منظم ، توالی مشخصی از کاراکترها که [[Flag (computing)|flag]] نامیده میشوند ،کاراکترهای جداکننده یجداکنندهٔ خاصی که جداکننده ([[delimiter]]s) نامیده میشوند ، و تعریف صریح به وسیله یوسیلهٔ یک دیکشنری. کاراکترهای خاص مانند کاراکترهای علامت گذاری، به خاطر استفاده یاستفادهٔ طبیعی آنها در نوشتن و زبانهای برنامهسازی ، معمولاً توسط lexer برای شناسایی توکنها استفاده میشوند.
توکنها معمولاً به وسیله یوسیلهٔ محتوای کاراکتر یا محتویات درون یه جریان داده دسته بندی میشوند. این دستهها به وسیله یوسیلهٔ قوانین lexer تعریف میشوند. این دستهها معمولاً شامل عناصر گرامر زبان استفاده شده در جریان داده میشوند. زبانهای برنامهسازی غالبا توکنها را به عنوان identifierها ، عملگرها ، گروه نمادها ، یا به وسیله یوسیلهٔ نوع داده یدادهٔ آنها ، دسته بندی میکنند. زبانهای نوشتاری معمولاً توکنها را به عنوان اسم ، فعل ، صفت ، یا علائم نشانهگذاری دسته بندی میکنند. دستهها برای پس پردازش ( post-processing ) توکنها چه توسط پارسر چه توسط توابع دیگر در برنامه ، استفاده میشوند. تحلیلگر لغوی معمولاً کاری برای ترکیب توکنها انجتم نمی دهدنمیدهد ، این وظیفه یوظیفهٔ پارسر است. به عنوان مثال ، یک تحلیل گر لغوی معمولی، پرانتزها را به عنوان توکن تشخیص می دهد،میدهد، ولی کاری را برای اطمینان از اینکه هر پرانتز باز با یک پرانتز بسته تطابق داده شود انجام نمی دهدنمیدهد.
زمانی که یک lexer توکنها را به parser می دهد،میدهد، نمایشی که استفاده میشود ، معمولاً لیستی از نمایش اعداد است. به عنوان مثال ، "identifier" با عدد 0 نمایش داده میشود ، "عملگر انتساب" با عدد 1 و "عملگر جمع" با عدد 2 نمایش داده میشود و ... .
توکنها معمولاً با عبارات منظم تعریف میشوند، که توسط مولد تحلیلگر لغوی مانند lex فهمیده میشوند. تحلیگر لغوی (که به صوزت خودکار توسط ابزاری مانند lex یا به صورت دستی تولید میشوند) جریان کاراکترها را می خواند ، واژههای این جراین را شناسایی میکند ، و آنها را به توکنهایی دسته بندی میکند. به این عمل توکنسازی می گویند. اگر lexer توکن نادرستی (invalid) بیابد، خطایی را گزارش میکند.
به دنبال عمل توکنسازی parsing میآید. از آنجا ، داده یدادهٔ تفسیر شده ممکن است، برای استفاده یاستفادهٔ عمومی ، تفسیر ، یا ترجمه (کامپایل) در ساختمان دادههایی بارگذاری شود.
=== اسکنر ===
در مرحله اول، اسکنر، معمولاً مبتنی بر یک [[ماشینهای حالات متناهی|ماشین حالت متناهی]] است که با استفاده از اطلاعات کاراکترهایی با توالی ممکن کدگذاری شدهاست که این کاراکترها میتوانند هر یک از توکنها مورد استفاده باشد. به عنوان مثال، یک توکن عدد صحیح میتواند دارای هر توالی از ارقام باشد.در بسیاری از نمونهها اولین کاراکتری که فضای خالی نباشد، میتواند برای استنباط نوع توکن بعدی مورداستفاده قرار گیرد و زیردنباله یزیردنبالهٔ کارکترهای ورودی بعد از آن در یک زمان پردازش میشوند تاوقتی که به کاراکتری برسد که که در مجموعه یمجموعهٔ کاراکترهای قابل قبول برای توکنها نباشد (که اصطلاحا این عمل ، قانون حداکثر جویدن یا طولانیترین تطبیق نامیده میشود). در بسیاری از زبانها قانین تولید واژه بسیار پیچیده تر است و ممکن است درگیر عقب گرد بر روی کاراکترهای خوانده شده یشدهٔ قبلی شود. به عنوان مثال در C تنها یک کاراکتر 'L' برای تمایز قائل شدن بین یک شناسه که با 'L' شروع میشود و یک کاراکتر از یک رشته کافی نیست.
=== ارزیابیکننده ===
یک واژه، اگرچه یک رشتهای از کاراکترهاست، باید به شکل خاصی(مثلاً رشتهای از لیترال ها، دنبالهای از حروف) باشند. به منظور ساختن یک توکن، تحلیل گر لغوی گام دومی هم نیاز دارد، ارزیابیکننده، که کارکترهای یک وازه را بررسی میکند تا یک مقداری را تولید کند. ترکیب نوع واژه با مقدارش چیزی است که یک توکن را می سازد،میسازد، که میتوان آن را به پارسر(تجزیهکننده) داد. برخی از توکنها مانند پرانتزها درحقیقت مقداری ندارند، بنابراین تابع ارزیابیکننده برای آن میتواند چیزی برنگرداند: فقط نوع آن لازم است. بهطور مشابه، گاهی اوقات ارزیابیکننده کل یک واژه را نادیده میگیرد، آن را از پارسر حذف میکند، که برای فضاهای خالی و commentها مفید است. ارزیابیکننده برای شناسهها عموماً ساده اندسادهاند (عینا خود شناسه را نمایش می دهند).ارزیابیکنندههای لیترالهای اعداد صحیح ممکن است رشته را عبور دهند(ارزیابی را برای فاز تحلیل معنایی به تعویق می اندازد)، یا ممکن است ارزیابی آنها را انجام دهندف که میتوانند درگیر مبناهای مختلف یا اعداد اعشاری شوند. برای لیترالهای رشته یرشتهٔ نقل قول شده یشدهٔ ساده، لازم است که ارزیابیکننده فقط نقل قولها را حذف کند.
به عنوان مثال ف در این کد منبع یک برنامه یبرنامهٔ کامپیوتری، رشته یرشتهٔ <blockquote><code>;(net_worth_future= (assets - liabilities</code></blockquote>ممکن است به جریان توکنهای lexical زیر تبدیل شود; فضاهای خالی نادیده گرفته شده اندشدهاند و کاراکترهای خاص مقداری ندارند:
<syntaxhighlight>
عبارات منظم الگوهایی را که ممکن است کاراکترها در واژهها دنبال کنند به صورت فشرده نمایش می دهند. به عنوان مثال، برای یک زبان مبتنی بر زبان انگلیسی، یک توکن NAME ممکن است هر یک از کاراکترهای الفبای انگلیسی باشد یا یک underscore (_) و به دنبال آن هر تعدادی از نمونههای کدهای alphanumeric اسکی و underscoreهای دیگر باشد. میتوان به صورت مختصر این گونه نمایش داد؛ <code>*[a-zA-Z_][a-zA-Z_0-9]</code> . به این معنی است که "هر تعداد از کاراکترهای a-z ،A-Z یا _ ،و به دنبال آن صفر یا تعداد بیشتری از a-z, A-Z, _ یا 0-9.
عبارات منظم و ماشینهای حالت متناهی ای که آنها تولید میکنند به اندازه کافی برای کنترل الگوهای بازگشتی، مانند "nتا پرانتز باز ، به دنبال آن یک سری عبارت و پس از آن nتا پرانتز بسته "، قوی نیستند. آنها نمی توانند تعداد را ذخیره کنند، و بررسی کنند که n در دوطرف یکسان است، مگر این که یک مجموعه یمجموعهٔ متناهی از مقادیر مجاز برای n موجود باشد. طول می کشد تا یک تجزیهکننده یتجزیهکنندهٔ کامل چنین الگوهایی را در کلیت کامل خود تشخیص دهد. یک پارسر میتواند پرانتزها را به داخل پشته push کند و سپس سعی کند که آنها را pop کند تا ببیند که آیا در آخر پشته خالی میشود یا خیر.
=== موانع ===
توکنسازی خصوصاً برای زبانهای نوشته شده در [[scriptio continua]] دشوار است ، که محدودیتهای کلمه را نمایش نمی دهند، مانند یونانی باستان، چینی، یا تایلندی. زبانهای ترکیبی مانند کرهای نیز توکنسازی را دشوار میکنند.
برخی از راهها برای آدرس دهی به مسائل دشوارتر شامل توسعه یتوسعهٔ تخمینهای پیچیده یپیچیدهٔ بیشتر، پرس جوی یک جدول از موارد خاص متداول، یا مناسب کردن توکنها برای یک مدل زبان که ترتیب را در گامهای پردازش بعدی تشخیص میدهد.
=== نرم افزار ===
[http://opennlp.apache.org/index.html Apache OpenNLP] شامل قوانین پایه و آماری توکنسازی است که زبانهای زیادی را پشتیبانی میکند.
[http://tokenizer.tool.uniwits.com/ U-Tokenizer] یک API روی HTTP است که میتواند جملات ژاپنی و ماندرین را در محدوده یمحدودهٔ کلمه قطع کند.
[https://dev.havenondemand.com/apis/tokenizetext#overview HPE Haven OnDemand Text Tokenization API] (یک محصول تبلیغاتی با دسترسی رایگان) از مدلسازی مفهوم احتمالات پیشرفته استفاده میکند تا وزنی که جمله در شاخص متن مشخص شده ، دارد را تعیین کند.
ابزار [[Lex (software)|Lex]] و کامپایلر آن طراحی شده اندشدهاند تا کد را برای تحلیل لغوی سریعتر بر مبنای یک توصیف رسمی از نحو لغوی تولید کنند. که این عموماً برای برنامههایی که مجموعهای پیچیده از قوانین نحوی و نیازمندیهای عملکردی شدید دارند، ناکافی در نظر گرفته میشود. به عنوان مثال، ([[GNU Compiler Collection]] (GCC از تحلیل گران لغوی دست نوشته استفاده میکند.
== مولد تحلیل گر لغوی (Lexer Generator) ==
تحلیل گرهای لغوی اغلب توسط مولد تحلیل گر لغوی تولید میشوند، مشابه مولد تجزیهکننده (parser) ، و چنین ابزارهایی اغلب گرد هم می آیند. پابرجاترین آنها Lex میباشد، به همراه مولد پارسر Yaccو ابزار معادل رایگان آن Flex .
این مولد شکلی از دامنه یدامنهٔ خاص زبان است، مشخصات واژگانی رامی گیرد-بهطور کلی عبارت منظم با نشانه گذاری- و lexer را به عنوان خروجی تولید میکند.
ابزار عملکرد توسعه یتوسعهٔ سریع،که در توسعه یتوسعهٔ اولیه بسیار مهم اند، هر دو lexer میگیرندمیگیرند زیرا خصوصیات زبان اغلب ممکن است تغییر کند.در ادامه، آنها اغلب ویژگیهای پیشرفتهای را فراهم میکنند ،از جمله شرایط قبل و بعد که برنامهنویسی دستی آنها سخت میباشد. با این حال مولد lexer اتوماتیک ممکن است عدم انعطافپذیری داشته باشد،در نتیجه نیاز به تغییر کاربر،یا یک lexer که کاملاً دستی نوشته شده باشد دارد.
عملکرد lexer دارای اهمیت است و بهینهسازی آن ارزشمند و نیازمند صرف وقت میباشد ، به ویژه در زبانهای پایدار که lexer در آنها غالبا اجرا میشود ( مانند C و Lexer.(HTMLهای تولید شده با lex/flex ، منطقا سریع هستند، اما بیشتر از دو تا سه بار، بهبود آن، امکان پذیرامکانپذیر است. گاهی lexerهای دست نویس استفاده می شدند، اما مولد lexer مدرن اغلب lexerهایی تولید میکنند که سریع تر از lexerهای با دست کدگذاری شده هستند. خانواده یخانوادهٔ lex/flex جدول محورند که کارایی کمتری نسب به مولدهای مستقیما کدگذاری شده دارند. با روش دوم مولد با دستور goto مستقیما به جلو میرود . ابزاری مانندre2c موتورهایی که دو تا سه برابر سریع تر از موتورهای flex می باشد تولید میکند.بهطور کلی تجزیه و تحلیل دست نویس دشوار است که روش دوم برای تولید موتورها بهتر است.
=== لیستی از مولدهای lexer ===
== ساختار عبارت ==
تحلیل لغوی جریان ورودی از کاراکترها را به توکن تبدیل میکند، به سادگی کاراکترها را به بخشهایی گروه بندی میکند و آنها را طبقهبندی میکند. با این حال ممکن است که توکنها حذف میکنند یا اضافه میکنند. در حذف توکن ها، از جمله فضای خالی وCommentها زمانی که کامپایلر هیچ احتیاجی به انهاآنها ندارد، بسیار رایج هستند. معمولا کمتر ، توکنهای اضافه شده ممکن است قرار گرفته شوند. این کار انجام میشود تا توکنها را به عبارات ، یا عبارات را به بلاکها گروه بندی کنند ، تا عمل تجزیه را سادهتر کند.
=== ادامهٔ خط (Line continuation) ===
ادامه یادامهٔ خط یکی از ویژگیهای برخی زبان هاست که خط جدید معمولاً بعد از پایان جمله است.گاهی اوقات پایان خط با backslash (فورا به خط جدید میرود) نشان داده میشود که خط قبلی را به این خط متصل میکند. در تحلیل لغوی این کار انجام میشود : backslash و خط جدید دور انداخته میشوند ، نسبت به خط جدید که توکنسازی میشود.
=== درج نقطه ویرگول (Semicolon insertion) ===
بسیاری از زبانها از نقطه ویرگول برای پایان جمله استفاده میکنند .که اغلب اجباری است،اما در بعضی زبانها استفاده از نقطه ویرگول در متن اختیاری است. این کار در مرحله lexerصورت میگیرد. جایی که lexer یک نقطه ویرگول را به جریانی از توکنها تبدیل میکند ، با این وجود در جریان ورودی کاراکترها آماده نیست ف که درج نقطه ویرگول یا درج خودکار نقطه ویرگول نامیده میشود. در این مورد،نقطه ویرگول یک عبارت نرمال گرامی از زبان هست، اما ممکن است که به عنوان ورودی نباشد که تحلیل گر لغوی آن را اضافه میکند. نقطه ویرگول اختیاری است یا پایان دهنده یا این که بعضی اوقات به عنوان جداکننده از مرحله یمرحلهٔ تجزیه به کار میرود، به ویژه در مورد کامای انتهایی( [[trailing comma]]s ) یا نقطه ویرگول.
درج نقطه ویرگول یکی از خصوصیات BCPL و یکی از نسلهای دور در Go میباشد. هر چند در B یا C وجود ندارد. درج نقطه ویرگول در JavaScript وجود دارد،اگر قوانین پیچیده و مورد انتقاد قرار بگیرند ، برای جلوگیری از مشکلات ، استفاده از نقطه ویرگول توصیه میشود، در حالی که دیگران نقطه ویرگول اولیه، نقطه ویرگول دفاعی، را عمدتا در عبارات مبهم به کار می برند.
درج نقطه ویرگول(در زبانهایی که نقطه ویرگول به معنای پایان عبارت است) و ادامه یادامهٔ خط ( در زبانهایی که خط جدید به معنای پایان عبارت است) مکمل یکدیگرند . درج نقطه ویرگول به عنوان یک توکن اضافه میشود، اگرچه خط جدید بهطور کلی توکن ایجاد نکند، یا ادامه یادامهٔ خط مانع از ایجاد توکن شود و حتی اگر خط جدید بهطور کلی توکن ایجاد کند.
=== قوانین off-side ===
قوانین off-side (بلوکهای تعیین شده توسط تورفتگی) را در lexer می توان پیادهسازی کرد، مانند پایتون ، که افزایش فرورفتگیها نتیجه ینتیجهٔ بیرون ریختن INDENT توکنها در lexer است ، و کاهش فرورفتگیها نتیجه ینتیجهٔ بیرون ریختن DEDENT توکنها در lexer می باشد.این توکنها مربوط به باز کردن آکولاد <code>{</code> و بستن آکولاد <code>}</code> در زبانهایی است که از آکولاد برای بلاکها استفاده میکنند. این بدان معناست که عبارت دستور زبان به این که آکولاد یا فرورفتگی استفاده میشود بستگی ندارد. مستلزم آن است که حالت lexer را نگه دارد، یعنی سطح تورفتگی فعلی ، در نتیجه میتواند زمانی که تغییرات فرورفتگی شناسایی شود تغییر دهد، در نتیجه دستورزبان واژگانی مستقل از متن نیست :INDENT-DEDENT ، به اطلاعات متن که از فررفتگی قبلی میگیرد بستگی دارد.
== تحلیل لغوی حساس به متن ==
بهطورکلی گرامرهای لغوی ، مستقل از متن هستند، یا تقریباً مستقل از متن هستند، که نیازی به نگاه به عقب یا جلو، یا برگشت به عقب(backtracking) هستند، که پیادهسازی ساده ، تمیز و کارآمد را امکان پذیرامکانپذیر میکند. هم چنین یک ارتباط یک طرفه از تحلیل گر لغوی به تجزیهکننده ،بدون نیاز به برگشت اطلاعات را ممکن می سازدمیسازد.
با این حال استثناهایی وجود دارد. مثالهایی ساده شامل : درج نقطه ویرگول در Go، که به نگاه کردن به توکن قبلی نیاز دارد،الحاق رشته یرشتهٔ متوالی در پایتون که نیازدارد قبل از خروج یک توکن محتوای آن در بافرنگه داری شود (برای اینکه ببیند آیا توکن بعدی یکی literal است یا نه)؛ ونقش off-side در پایتون ، که به نگهداری تعدادی از سطوح فرورفتگی نیاز دارد( در واقع پشتهای از هر سطوح فرورفتگی)، این نمونهها فقط نیاز به زمینه یزمینهٔ لغوی دارند، و در حالی که تحلیل گر لغوی تا حدی آنها را پیچیده میکند، برای تجزیهکننده و مراحل بعد قابل دیدن نیستند.
یک مثال پیچیده تر هک تحلیل گر لغوی در C است، که کلاس توکن دنبالهای از کاراکترها تا فاز تحلیل گر معنایی، نمی تواند تعیین شود. اگرچه نامهای نوع متغیر از لحاظ لغوی یکسان اند اما کلاسهای توکن مختلفی را تشکیل میدهد. بنابراین در این هک، تحلیل گر لغوی تجزیه و تحلیل معنایی را صدا می زند(جدول نمادها) و بررسی میکند که آیا دنباله به یک نام نوع متغیر نیاز دارد یا خیر. در این مورد نباید اطلاعات فقط از تجزیهکننده بازگردد بلکه باید از تحلیلگر معنایی به تحلیل گر لغوی برگردد، که طراحی را پیچیده میکند.
|