3.7.1 生产者-消费者模型中的解析树

在生产者-消费者模型中,解析器是生产者,而使用解析树的程序是消费者。正如在计算机科学中的生产者-消费者模型,最直接的问题是,哪个是主进程哪个是子进程。

最好的解决方案是将他们视为同等的,然后可以使用协同例程(coroutine)。协同例程在其他的编程语言和编程技术原理中进行了介绍,例如高级程序语言设计,作者R.A. Finkel (Addison-Wesley)。在网络上也有很多的解释。

在协同例程模型中,用户对新解析树的需求和解析器对解析树的提供是由协同例程自动配对的。协同例程的问题是,它们必须被内置到编程语言中,并且没有主流的编程语言适应它们。因此,对解析树表示方法协同例程并不是一个实用的解决方案。

协同例程的现代表现方式,线程,其中配对是由操作系统或编程语言内一个轻量级操作系统来完成的,在一些主要语言中是可用的,但关于并行性概念的介绍并不是解析所固有的。Unix管道有相似的通信属性,单对解析来说却相差更大。

通常解析器是主程序,而消费者是子例程。每当解析器完成解析树的构造时,它就会将树当做参数用一个指针来调用消费者例程。然后消费者就可以决定如何使用解析树:拒绝它、接受它、存储它以备将来的比较,等等。在这个设置中,解析器可以很好的生成解析树,但是消费者可能必须在每次调用之间存储状态数据,以便能够在解析树之间进行选择。这是解析器设计中通常的设置,在这里只有一个解析树,而消费者状态保存则不是一个问题。

还可以将消费者作为主程序,但这会给解析器带来沉重的负担,因为解析器必须在生成解析树的过程中保存全部未完成解析的状态数据。由于堆栈上的状态不能保存为状态数据(除非采用苛刻的方法),这种设置只适用于不使用堆栈的解析方法。

对着这些设置,在大多数情况下用户还有两个问题。首先,当解析器生成多个解析树时,消费者将它们作为独立的解析树接收,然后可能需要做相当大的比较来找出它们之间的差别来进行进一步的决策。第二,如果语法是无限模糊的,并且解析器解析器产生无限多的解析树,那这个过程将不会停止了。

所以生产者-消费者模型对于确定性语法是一个令人满意的方案,但更多的情况下却会有问题。