一个自动构造增量式LR（1）句法分析器的有效方法

本文提出了自动构造增量式LR(1)句法分析器的一个有效方法.用该方法构造得到的分析器不仅允许对原语句作多处修改,而且还允许奠基的LR(1)文法含有右边为空的产生式。为了分析一个经过修改的语句,它们所需的空间和时间分别与该语句的长度和所作修改的总和形成线性比.为了进行实验,本方法已在Motorola-68010机上获得实现。     

一个快速平面性算法

Rubin最近在System/360 Model67上实现了Demoucron等人的平面性算法,发现它在通常大多数情况下要比目前堪称最优的Hopcroft ＆Tarjan算法约快一倍。本文改进了Rubin的算法,使它不再需在整个P(Gk)中而仅需在其任一子等价类中探索可嵌链,且因采用了较恰当的数据结构,也使所需的总存储量从Rubin的约39m剧减到约22m(m是给定图的顶点个数)。     

Three Improvements on an Incremental Algorithm for Automatic Semantic Analysis

The formalism of attribute grammars is a powerful tool for specifying the static semantics of programming languages,and attribute evaluation provides an effective approach to automatic semantic analysis.The author previously proposed a time-optimal algorithm for incremental evaluation of ordered attribute grammars.In this paper,three improvements are suggested upon the algorithm so that it not only allows multiple subtree replacements,but also cancels three auxiliary tables required before,For experimental purposes,the improved algorithm has been implemented in Pascal on Motorola 68010