3 解析简介

根据语法来分析字符串意味着重建生成树,以展示给定字符串是如何通过给定语法生成的。在这方面它有重要意义,第一个解析方面的出版物(Greibach的1963年博士论文[6]),命名为“逆向短语结构生成器”(Inverses of Phrase Structure Generators),而短语结构生成器被理解为一个从短语结构(事实上是上下文无关)语法生成短语的系统 。

虽然基于0型或1型语法生成句子产生的是生成图而不是生成树,并因此解析得到了解析图,我们应该使用2型,上下文无关语法,以专注于解析以及最后的解析树。偶尔我们会触及基于0型或1型语法的解析,例如3.2节,只是为了展示它是一个有意义的概念。