پردازش زبان طبیعی

Parser

اعظم صفری | 02 January, 2018 18:16

2  تجزیه

تجزیه یا تحلیل نحوی فرایند تحلیل یک رشته از نمادها چه به زبان طبیعی یا به زبان‌های رایانه‌ای برطبق قواعد یک گرامر رسمی است. اصطلاح تجزیه از کلمه لاتین  Pars (orationis) می‌آید که به معنای بخشی از (کلام) است. (2) (1)

این اصطلاح در شاخه‌های مختلف زبان‌شناسی و علم رایانه معانی نسبتاً متفاوتی دارد. تجزیه سنتی جمله، اغلب به‌عنوان روش درک معنای دقیق یک جمله و گاهی‌اوقات با کمک ابزارهایی مانند دیاگرام‌های جمله انجام می‌شد. و معمولاً بر اهمیت تقسیم‌های گرامری از قبیل موضوع و گزاره[1] تاکید دارد.

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

این اصطلاح دراینجا نیز در زمان توصیف و درک مطلب زبان به شکل روان‌زبان‌شناسی به کاربرده می‌شود. دراین بافت تجزیه اشاره دارد به شیوه‌هایی که ابنای بشر یک جمله یا یک عبارت (در زبان گفتاری یا متن) را به اجزای گرامری، بخش‌های کلام، روابط نحوی و.. تحلیل می‌کنند. این اصطلاح بویژه درزمان بحث درباره اینکه چه سرنخ‌های زبان‌شناختی به گویندگان در تفسیر جملات گول‌زننده[2] کمک می‌کند رواج دارد.

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

1.15.1 زبان‌های بشری

رده اصلی: تجزبه زبان طبیعی

روش‌های سنتی

تحلیل گرامری سنتی تجزیه که گاهی به عنوان تحلیل جمله‌واره شناخته شده است شامل شکستن یک متن به بخش‌ها و عناصر کلام به همراه تشریح شکل، کارکرد و روابط نحوی هر بخش است. این تاحدزیادی با مطالعه صرف و تصریف زبان تعیین می‌شود که برای زبان‌های باتصریف سنگین، خیلی پیچیده است. تجزیه یک عبارت مانند 'man bites dog' شامل تشخیص این است که اسم مفرد man فاعل جمله است، فعل bites سوم شخص مفرد زمان حال  to bite است و اسم مفرد dog مفعول جمله است. فنونی مانند دیاگرام‌ها اغلب برای بیان روابط بین عناصر درجمله بکار می‌روند.

سابقاً تجزیه در آموزش گرامر درسراسرجهان گویندگان انگلیسی زبان اهمیت داشت و به طور گسترده‌ای به‌عنوان مبنای استفاده و درک زبان مکتوب درنظرگرفته می‌شد. بااین‌حال تدریس چنین فنونی دیگر رایج نیست.

روش‌های محاسباتی

رده اصلی: تجزیه زبان طبیعی

دربرخی ترجمه‌های ماشینی و نظام‌های پردازش زبان طبیعی، متون مکتوب به زبان‌های انسانی ازطریق برنامه‌های رایانه‌ای تجزیه می‌شوند. جملات انسانی بسادگی ازطریق برنامه‌ها تجزیه نمی‌شوند، چراکه ابهام فراوانی در ساختار زبان انسانی وجود دارد که کاربرد آن انتقال معنا (یا معناشناسی) در میان طیف بالقوه نامحدودی از اجتماعات است که تنها برخی از آنها به مورد خاص مربوط می‌شود. بنابراین گفته 'man bites dog' درمقابل 'dog bites man' ازیک نظر مشخص است. اما در یک زبان دیگر ممکن است این‌گونه ظاهر شود 'man dog bites ' و اگر درواقع این تمایز اهمیت دارد؛ نیازمند یک بافت عظیم‌تر است تا بین دو احتمال تشخیص دهد. ایجاد قواعد رسمی برای توصیف رفتار غیر رسمی، سخت است هرچندکه واضح است که از برخی قواعد پیروی می‌شود.

پژوهشگران برای تجزیه داده‌های زبان طبیعی باید ابتدا بر گرامر مورد استفاده توافق کنند. انتخاب نحو، تحت تاثیر ملاحظات زبان‌شناختی و محاسباتی قرار دارد؛ مثلاً برخی نظام‌های تجزیه را ان‌پی کامل[3] گویند. گرامر ساختاری عبارت هسته‌بنیاد[4]‌ صورت‌گرایی زبان‌شناختی دیگری است که در جامعه تجزیه رواج دارد. اما دیگر تلاش‌های پژوهش بر صورتگرایی‌هایی با پیچیدگی کمتر تمرکز دارند مانند آنچه در   Penn Treebank استفاده می‌شود. هدف تجزیه سطحی تنها یافتن کران‌های اجزای اصلی از قبیل عبارت‌های اسمی است. راهبرد مشهور دیگر برای اجتناب از اختلاف نظر، تجزیه گرامر وابسته است.

اکثر تجزیه‌گرهای نوین حداقل تاحدی آماری هستند؛ یعنی بر پیکره‌ای از داده‌های آموزشی تکیه دارند که قبلا تحشیه شده‌اند (تجزیه با دست). این رویکرد به نظام اجازه جمع‌آوری اطلاعاتی درباره تواتر رخداد ساختارهای مختلف در بافت‌های خاص می‌دهد. (نگاه کنید به یادگیری ماشینی). رویکرد مورد استفاده شامل PCFGs (گرامرهای رها از بافت احتمالاتی[5])، آنتروپی بیشینه، و شبکه‌های عصبی است. اکثر نظام‌های موفق‌تر از آمارهای واژگانی استفاده می‌کنند (یعنی این‌همانی[6] واژگان و نیز عناصر گفتاری آنها را درنظر می‌گیرند. بااین‌حال چنین نظام‌هایی نسبت به تناسب بیش‌برازش[7] آسیب‌پذیر هستند و مستلزم نوعی تلطیف هستند تا کارآمد باشند.

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

الگوریتم‌هایی که از گرامرهای رهاازبافت استفاده می‌کنند معمولا بر گونه‌ای از الگوریتم CYK تکیه می کنند و به همراه مقداری هیوریستیک به کارگرفته می‌شوند تا تحلیل‌های بعید را مانع شوند و زمان هدر نرود. (به تجزیه چارت نگاه کنید). بااین‌حال برخی نظام‌ها‌ با استفاده از نسخه‌های زمان-خطی الگوریتم تغییر-تقلیل، از سرعت به نفع دقت صرف نظر می‌کنند.

یک توسعه نسبتاً جدید، بازرتبه‌بندی تجزیه است که در آن تجزیه‌کننده تعداد نسبتاً زیادی از تحلیل‌ها پیشسنهاد می‌دهد و یک نظام پیچیده‌تر بهترین گزینه را انتخاب می‌کند.

روان‌زبان‌شناسی

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

1.15.2 زبان‌های رایانه‌ای

تجزیه‌گر

یک تجزیه‌گر یک مولفه نرم‌افزاری است که داده‌های درونداد (معمولاً متن) را دریافت می‌کند و یک نوع ساختار داده‌ای می‌سازد-اغلب نوعی درخت تجزیه، درخت نحوی انتزاعی یا ساختار سلسله‌مراتبی دیگر- با دادن یک بازنمون ساختاری از درونداد، و بررسی نحو درست در پردازش. تجزیه کردن ممکن است متقدم باشد یا بعد از دیگر مراحل باشد یا ممکن است اینها در یک مرحله ادغام شوند. اغلب قبل از تجزیه‌گر یک تحلیل‌گر واژگانی مجزا وجود دارد که توکن‌ها را از توالی نویسه‌های درونداد خلق می‌کند. راه دیگر اینکه اینها می‌توانند در تجزیه بدون‌پویشگر[8] ترکیب شوند. تجزیه‌گرها ممکن است دستی یا خودکار برنامه‌ریزی شوند یا شبه‌خودکار ازطریق تولیدکننده تجزیه‌گر[9] تولید شوند. تجزیه‌کردن مکمل قالب‌بندی است که برونداد قالب‌بندی شده تولید می‌کند. اینها می‌توانند در حوزه‌های مختلف بکاربسته شوند اما اغلب باهم ظاهر می‌شوند مانند جفت‌های scanf/printf یا مراحل درونداد (تجزیهfront end) و برونداد (تولید back end) یک مترجم.

درونداد یک تجزیه‌گر اغلب متنی است به زبان رایانه‌ای اما همچنین می‌تواند یک متن در یک زبان طبیعی باشد یا داده‌های متنی کمترساختاریافته، دراین‌صورت معمولاً تنها بخش‌های خاصی از متن استخراج می‌گردند به جای اینکه یک درخت تجزیه ساخته شود.

تجزیه‌گر می‌توانند دامنه‌ای از کارکردهای خیلی ساده مانند Scanf یا برنامه‌های پیچیده مانند frontend یک مترجم C++ یا تجزیه‌گر HTML یک مرورگر وب داشته باشند. یک رده مهم در تجزیه ساده ازطریق استفاده از عبارات منظم انجام می‌شود که در آن یک عبارت منظم یک زبان منظم را تعریف می‌کند و یک موتور عبارت منظم بطور خودکار یک تجزیه‌گر برای آن زبان تولید می‌کند و باعث تطبیق الگو و استخراج متن می‌شود. درعوض در بافت‌های دیگر عبارات منظم قبل از تجزیه‌کردن بکار می‌روند. همانطور که برونداد مرحله واژگانی آن برای تجزیه‌گر بکارگرفته می‌شود. 73

استفاده از تجزیه‌گرها براساس درونداد فرق می‌کند. درمورد زبان‌های داده‌ای یک تجزیه‌گر اغلب به‌عنوان تسهیلگر خواندن فایل یک برنامه ازقبیل خواندن متن HTML یا XML است. اینها مثال‌هایی از زبان‌های نشانه‌گذاری هستند. درمورد زبان‌های برنامه نویسی یک تجزیه‌گر مولفه یک مترجم یا مفسر است که کد منبع یک زبان برنامه‌نویسی رایانه‌ای را برای خلق شکلی از بازنمون داخلی تجزیه می‌کند؛ تجزیه‌گر یک مرحله کلیدی در Frontend مترجم است. زبان‌های برنامه‌نویسی گرایش دارند خاص باشند به شکل یک گرامر رهاازبافت متعین، به همین علت می‌توان تجزیه‌گرهای سریع و کارآمد،  برای آنها نوشت. خود تجزیه برای مترجم‌ها می‌تواند در یک گذر یا گذرهای چندگانه انجم شود-نگاه کنید به مترجم یک‌گذره و مترجم چندگذره

گرامرهای رهاازبافت ازاین‌نظر که همه الزامات یک زبان را بتوانند بیان کنند محدود هستند. بطورغیررسمی دلیل این است که حافظه چنین زبانی محدود است. گرامر نمی‌تواند حضور یک ساختار را در یک درونداد خیلی طولانی دلبخواهی به خاطر آورد؛ این برای یک زبان ضروری است که در آن مثلا نام باید قبل از اینکه مورد ارجاع قرار گیرد بیان شود. گرامرهای قوی‌تری که می‌توانند این قید را بیان کنند بااین‌حال نمی‌توانند بطورکارامدی تجزیه شوند. بنابراین یک راهبرد رایج این است که یک تجزیه‌گر Relaxed برای گرامر رهاازبافتی تولید کنیم که یک ابرمجموعه سازه‌های زبان مطلوب را بپذیرد (یعنی، برخی سازه‌های نامعتبر را می‌پذیرد)؛ بعدا سازه‌های ناخواسته می‌توانند در مرحله تحلیل معناشناختی (تحلیل بافتاری) پالایش شوند. مثلا در پایتون کد ذیل ازنظر نحوی معتبر است:

x = 1 print(x)

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

x = 1 print(y)

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

مروری بر فرایند

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

مثلا یک برنامه ماشین حساب می‌تواند دروندادی مانند“12*(3+4)^2”داشته باشد و آن را به دو توکن تفکیک کند.

12, *, (,3, +, 4, ), ^, 2 هرکدام یک نماد معنادار در بافت یک عبارت ریاضیاتی است.  Lexer شامل قواعدی است که می‌گوید نویسه‌های نشان‌دهنده ابتدایی، یک توکن جدید هستند، بنابراین توکن‌های بی‌معنا مانند 12* یا 3" تولید نخواهند شد.

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

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

1.15.3 انواع تجزیه‌گرها

وظیفه یک تجزیه‌گر اساساً تعیین این است که چگونه درونداد می‌تواند از نماد آغازین گرامر بدست آید. این کار اساساً به دو روش انجام می‌شود.

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

جریان داده در یک تجزیه‌گر نوعی

تجزیه پایین‌به‌بالا- یک تجزیه‌گر می‌تواند با درونداد شروع کند و سعی کند آن را به نماد آغازین بازنویسی کند. بطور شهودی تجزیه‌گر تلاش می‌کند مبنایی‌ترین عناصر را پیدا کند. سپس عناصری که اینها را دارند و به همین ترتیب تجزیه‌گرهای LR مثال‌هایی از تجزیه‌گرهای پایین‌به‌بالا هستند. اصطلاح دیگر مورد استفاده برای این نوع تجزیه‌گر تجزیه تغییر-تقلیل است.

تجزیه‌گرهای LL  و تجزیه‌گرهای بازگشتی-نزولی نمونه‌هایی از تجزیه‌گرهای بالابه‌پایین هستند که نمی‌تواندد با قواعد تولید بازگشتی سمت چپ همراهی کنند. اگر این باور وجود دارد که کاربست ساده تجزیه بالابه‌پایین نمی‌توانند بازگشت چپ مستقیم و غیرمستقیم را همراهی کند و ممکن است مستلزم زمان تصاعدی و پیچیدگی  باشد درحال تجزیه گرامرهای رهاازبافت مبهم، الگوریتمهای خیلی پیچیده‌تری برای تجزیه بالابه‌پایین توسط Frost, Hafiz, and Callaghan[5][6] ایجاد شده‌اند (5) (6) که با ابهام وفق دارند و بازگشت چپ درزمان چندجمله‌ای و بازنمون‌های سایز چندجمله‌ای را از تعدا بالقوه زیادی از دذختهای تجزیه تولید می‌کنند. الگوریتم تنها قادر است هم مشتقات سمت چپ‌ترین و هم سمت راست‌ترین یک درونداد را با توجه به یک گرامر رهااز بافت معین تولید کند.

یک تمایز مهم در مورد تجزی‌گرها این است که آیا یک تجزه‌گر یک مشتق ‌ سمت چپ‌ترین و یا یک مشتق سمت راست‌ترین (نگاه کنید به گرامر رهاازبافت)ایجاد می‌کند. تجزیه‌گرهای LL یک مشتق سمت چپ‌ترین و تجزیه‌گرهای LR یک مشتق سمت راست‌ترین (اگرچه معمولا برعکس) تولید خواهند کرد. (14)

1.15.4 انواع تجزیه‌گرها

تجزیه‌گرهای بالابه‌پایین

برخی تجزیه‌گرها که از تجزیه بالابه‌پایین استفاده می کنند اینها هستند:

_ Recursive descent parser

_ LL parser (Left-to-right, Leftmost derivation)

_ Earley parser

تجزیه‌گرهای ‌پایین‌به‌بالا

برخی تجزیه‌گرها که از تجزیه پایین‌به‌بالا استفاده می کنند اینها هستند:

_ Precedence parser

_ Operator-precedence parser

_ Simple precedence parser

_ BC (bounded context) parsing

_ LR parser (Left-to-right, Rightmost derivation)

_ Simple LR (SLR) parser

_ LALR parser

_ Canonical LR (LR(1)) parser

_ GLR parser

_ CYK parser

_ Recursive ascent parser

_ Shift-Reduce Parser

نرم‌افزارهای ایجاد تجزیه‌گرها

برخی از ابزارهای مشهور ایجاد تجزیه‌گر شامل موارد ذیل هستند. همچنین مقایسه تولیدکننده‌های تجزیه‌گر را ببینید.

_ ANTLR

_ Bison

_ Coco/R

_ GOLD

_ JavaCC

_ Lemon

_ Lex

_ Parboiled

_ Parsec

_ Ragel

_ Spirit Parser Framework

1.15.5  پیش‌بین[1]

پیش‌بین، حداکثر توکن‌های آمدنی مورد استفاده یک تجزیه‌گر در تصمیم گیری درباره بکارگیری قواعد را مشخص می‌کند. پیش‌بین بویژه با تجزیه‌گرهای LL LR LALR مرتبط است جاییکه اغلب صراحتاً ازطریق چسباندن پیش‌بین، به نام الگوریتم در پرانتر ‌ بیان می‌شود مانند LALR(1)  

در اکثر زبان‌های برنامه‌نویسی هدف اولیه تجزیه‌گرها بطور دقیق به شیوه‌ای تعریف می‌شود که یک تجزیه‌گر با تقریبا یک پیش‌بین بتواند آنها را تجزیه کند چراکه تجزیه‌گرهای با پیش‌بین محدود اغلب کارامدتر هستن.د یک تغییر مهم در این گرایش در 1990 رخ داد که ترنس پار[2] ANTLR  را در تز دکتری خود خلق کرد یک تولیدکننده تجزیه‌گر برای تجزیه‌گرهای LL(K) کارا دد جاییکه K می‌تواند هر مقدار ثابتی باشد.

تجزیه‌گرها نوعا بعد از دیدن هر توکن کار چندانی ندارند آنها یا باعث تغییر (این توکن را به پشته[3] برای تقلیل بعدی می‌برند) یا تقلیل (توکن را از پشته در می‌آورند و یک سازه نحوی شکل می‌دهند) یا پایان، یا خطا (هیچ قواعد شناخته شده ای بکار نمی برند) یا تعارض (نمی‌داند تغییر دهد یا تقلیل) می‌شوند.

پیش‌بین دو مزیت دارد:

-به تجزیه‌گرها کمک می‌کند در زمان تعارض تصمیم درست بگیرند مثلا تجزیه جمله شرطی به شکل یک جمله واره

-حالات دوگانه را حذف می‌کند و فشار[4] یک پشته فوق العاده را راحت می‌سازد. تجزیه‌گر غیر پیش‌بین زبان A C حدود 10000حالت خواهد داشت. تجزیه‌گر پیش‌بین A حدود 300 حالت خواهد داشت.

مثال تجزیه عبارت 1 + 2 * 3

اکثر زبان‌های برنامه‌نویسی (به‌جز تعدادی از قبیل APC و Smalltalk) و فرمول‌های جبری، تقدم بالاتری به ضرب نسبت به جمع می دهند. دراین‌صورت تفسیر درست مثال بالا این است (1 +(2*3)). به یادداشته باشید که قاعده 4 بالا یک قاعده معناشناختی است. می‌توانیم گرامر را بازنویسی کنیم تا این نحو را شامل گردد. بااین‌حال همه چنین قواعدی را نمی‌توان به نحو ترجمه کرد.

کارهای تجزیه‌گر غیر پیش‌بین

Initially Input = [1,+,2,*,3]

1. Shift “1” onto stack from input (in anticipation of rule3). Input = [+,2,*,3] Stack = [1]

2. Reduces “1” to expression “E” based on rule3. Stack = [E]

3. Shift "+" onto stack from input (in anticipation of rule1). Input = [2,*,3] Stack = [E,+]

4. Shift “2” onto stack from input (in anticipation of rule3). Input = [*,3] Stack = [E,+,2]

5. Reduce stack element “2” to Expression “E” based on rule3. Stack = [E,+,E]

6. Reduce stack items [E,+] and new input “E” to “E” based on rule1. Stack = [E]

7. Shift "*" onto stack from input (in anticipation of rule2). Input = [3] Stack = [E,*]

8. Shift “3” onto stack from input (in anticipation of rule3). Input = [] (empty) Stack = [E,*,3]

9. Reduce stack element “3” to expression “E” based on rule3. Stack = [E,*,E]

10. Reduce stack items [E,*] and new input E to Ebased on rule2. Stack = [E]

درخت تجزیه و کد منتج از آن برطبق معناشناسی زبان درست نیست.

برای تجزیه درست بدون پیش‌بین سه راه حل وجود دارد:

-کاربر باید عبارات را داخل پرانتز قرار دهد. این اغلب یک راه حل کارآمد نیست.

تجزیه‌گر به منطق بیشتری نیازمند است تا از راه خود برگردد و تلاشی دوباره کند هرگاه یک قاعده نقض شود یا کامل نباشد. روشی مشابه در تجزیه‌گر LL دنبال می شود.

-راه دیگر اینکه تجزیه‌گر یا گرامر باید منطق فوق العاده برای تاخیر تقلیل داشته باشد و تنها وقتی تقلیل یابد که کاملا مطمئن است که چه قاعده ای را اول تقلیل دهد. این روش در تجزیه‌گرهای LR بکار می‌رود. این به درستی عبارت را تجزیه می‌کند اما با حالات بسیار بیشتری و عمق پشته افزایش یافته.

کارهای تجزیه‌گر پیش‌بین

 

1. Shift 1 onto stack on input 1 in anticipation of rule3. It does not reduce immediately.

2. Reduce stack item 1 to simple Expression on input + based on rule3. The lookahead is +, so we are on path to E +, so we can reduce the stack to E.

3. Shift + onto stack on input + in anticipation of rule1.

4. Shift 2 onto stack on input 2 in anticipation of rule3.

5. Reduce stack item 2 to Expression on input * based on rule3. The lookahead * expects only E before it.

6. Now stack has E + E and still the input is *. It has two choices now, either to shift based on rule2 or reduction based on rule1. Since * has more precedence than + based on rule4, so shift * onto stack in anticipation of rule2.

7. Shift 3 onto stack on input 3 in anticipation of rule3.

8. Reduce stack item 3 to Expression after seeing end of input based on rule3.

9. Reduce stack items E * E to E based on rule2. 10. Reduce stack items E + E to E based on rule1.

1.15.16 نیز نگاه کنید به

_ Backtracking

_ Chart parser

_ Compiler-compiler

_ Deterministic parsing

_ Generating strings

_ Grammar checker

_ LALR parser

_ Lexical analysis

_ Pratt parser

_ Shallow parsing

_ Left corner parser

_ Parsing expression grammar

_ ASF+SDF Meta Environment

_ DMS Software Reengineering Toolkit

_ Program transformation

_ Source code generation

 

1.15.7 References

[1] “Bartleby.com homepage”. Retrieved 28 November  2010.

[2] “parse”. dictionary.reference.com. Retrieved 27 November 2010.

[3] “Grammar and Composition”.

[4] Aho, A.V., Sethi, R. and Ullman ,J.D. (1986) " Compilers: principles, techniques, and tools.” Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA.

[5] Frost, R., Hafiz, R. and Callaghan, P. (2007) " Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars .” 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE , Pages: 109 - 120, June 2007, Prague.

[6] Frost, R., Hafiz, R. and Callaghan, P. (2008) " Parser Combinators for Ambiguous Left-Recursive Grammars.”10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN , Volume 4902/2008, Pages: 167 - 181, January 2008, San Francisco.

 

1.15.8 Further reading

_ Chapman, Nigel P., LR Parsing: Theory and Practice, Cambridge University Press, 1987. ISBN 0-521-30413-X

_ Grune, Dick; Jacobs, Ceriel J.H., Parsing Techniques - A Practical Guide, Vrije Universiteit Amsterdam, Amsterdam, The Netherlands. Originally published by Ellis Horwood, Chichester, England, 1990; ISBN 0-

 

1.15.9 External links

_ The Lemon LALR Parser Generator

_ Stanford Parser The Stanford Parser

_ Turin University Parser Natural language parser for the Italian, open source, developed in Common Lisp by Leonardo Lesmo, University of Torino, Italy.

_ Short history of parser construction 13-651431-6



[1] Lookahead

[2] Terence Parr

[3] stack

[4] Burden 



[1] predicate

[2] garden-path

[3] NP-complete

[4] Head- driven  

[5] proba- bilistic context-free grammars

[6] identity

[7] overfitting

[8] scannerless

[9] parser generator

نظرات

ارسال نظر
Info

توجه: از ارسال پيام هاي خصوصي در حالت لاگين براي نويسنده وبلاگ اجتناب نماييد.
در صورتی که در فرم ارسال نظر، نام شما توسط سیستم شناسایی شده باشد(در حالت لاگین) نظر شما بلافاصله منتشر خواهد شد.


در غیر اینصورت نظر شما پس از تایید توسط مالک وبلاگ منتشر خواهد شد.

 authimage
 
Accessible and Valid XHTML 1.0 Strict and CSS
Converted to use with ITS. Powered by FUMblog