Parsing Theory. Volume 1: Languages and Parsing

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

The theory of parsing is an important application area of the theory of formal languages and automata. The evolution of modem high-level programming languages created a need for a general and theoretically dean methodology for writing compilers for these languages. It was perceived that the compilation process had to be "syntax-directed", that is, the functioning of a programming language compiler had to be defined completely by the underlying formal syntax of the language. A program text to be compiled is "parsed" according to the syntax of the language, and the object code for the program is generated according to the semantics attached to the parsed syntactic entities. Context-free grammars were soon found to be the most convenient formalism for describing the syntax of programming languages, and accordingly methods for parsing context-free languages were devel­ oped. Practical considerations led to the definition of various kinds of restricted context-free grammars that are parsable by means of efficient deterministic linear-time algorithms.