6.6 递归下降

在前面的小节里,我们已经见过了几种自动机的工作,在处理输入句子时用语法决定解析的步骤。现在有另一种方式的说明:这些自动机将语法作为程序。将一个语法看作解析机器的一个程序并不像看起来那么牵强。毕竟,一个语法是推导其所描述的语言的句子的指示,我们在自顶向下解析中做的就是从一个语法重新推导一个句子。这跟将语法看作生成装置的传统观点的差别仅在于我们现在在尝试重推导一个特定的句子,而不是任意句子。以这种方式看,语法就是程序,以一种描述性的编程语言写成——就是说,这种语言定义结果而不是获得结果需要进行的步骤。

如果想写一个给定的上下文无关语法的解析器,我们有两种选择。第一种是按照前几节里描述的自动机是写一个程序。这个程序可以以一个语法和一个句子为输入。这听起来很完美,而且易于实现。困难来自于当解析器必须在部分输入被识别时进行一些其他操作的时候。比如,当处理了一个声明语句,编译器须要生成符号表。对效率的考量与这一点一起引导出第二个选项:对给定语法写一个专用的解析器。有很多这样的专用解析器,其中的大多数都用了一个叫做递归下降的识别技术。我们将假设读者具有一定的编程经验,明白过程和递归。如果不是,这一节可以跳过。本节没有描述新的解析方法,只描述了一个实现的技术,它常用于手写解析器和一些机器生成的解析器。

results matching ""

    No results matching ""