Parsing Theory. Volume 2: LR(k) and LL(k) Parsing

این اثر جلد دوم از یک تک نگاری دو جلدی درباره تئوری تجزیه قطعی گرامرهای بدون زمینه است. جلد اول، «زبان‌ها و تجزیه» (فصل 1 تا 5)، مقدمه‌ای بر مفاهیم اساسی تئوری زبان رسمی و تجزیه بدون متن بود. جلد دوم (فصل 6 تا 10) شامل بررسی کاملی از نظریه دو روش تجزیه قطعی مهم است: تجزیه LR(k) و LL(k). جلد دوم ادامه جلد اول است. این دو جلد با هم یک اثر یکپارچه را تشکیل می دهند که فصول، قضایا، لم ها و غیره به ترتیب شماره گذاری شده اند. جلد دوم با فصل 6 شروع می شود که در آن ساختارهای کلاسیک مربوط به تجزیه LR(k) ارائه شده است. اینها شامل تجزیه کننده متعارف LR(k) و انواع کاهش یافته آن مانند تجزیه کننده LALR(k) و تجزیه کننده SLR(k) می باشد. کلاس‌های دستور زبانی که این تجزیه‌کننده‌ها برای آنها قطعی هستند، گرامرهای LR(k)، گرامرهای LALR(k) و گرامرهای SLR(k) نامیده می‌شوند. ویژگی‌های این دستور زبان‌ها نیز در فصل 6 مورد بررسی قرار می‌گیرد. توجه زیادی به توسعه دقیق این نظریه شده است: برای اکثر نتایج ارائه‌شده، شواهد ریاضی دقیق ارائه شده است.

This work is Volume II of a two-volume monograph on the theory of deterministic parsing of context-free grammars. Volume I, "Languages and Parsing" (Chapters 1 to 5), was an introduction to the basic concepts of formal language theory and context-free parsing. Volume II (Chapters 6 to 10) contains a thorough treat­ ment of the theory of the two most important deterministic parsing methods: LR(k) and LL(k) parsing. Volume II is a continuation of Volume I; together these two volumes form an integrated work, with chapters, theorems, lemmas, etc. numbered consecutively. Volume II begins with Chapter 6 in which the classical con­ structions pertaining to LR(k) parsing are presented. These include the canonical LR(k) parser, and its reduced variants such as the LALR(k) parser and the SLR(k) parser. The grammarclasses for which these parsers are deterministic are called LR(k) grammars, LALR(k) grammars and SLR(k) grammars; properties of these grammars are also investigated in Chapter 6. A great deal of attention is paid to the rigorous development of the theory: detailed mathematical proofs are provided for most of the results presented.