Abstract:
A representation of parse tree for sentence of context free language (CFL) is presented, which is suitable for a class of applications of CFL, i.e., applications demanding higher space efficiency of parse trees but not requiring tree annotation. A typical application in this class is to use sentences of CFL’s as the operands of algorithms. Compared with the conventional parse tree, this representation not only consumes less space, but also is faster for structure matching. Implementation techniques for this representation are also introduced.