A Parser has an Input Stream, a set of rules (generated from an extended **PEG**) that recognise input Structure and generate output structures, an output stream to collect generated output, and a current result (semantic value from the most recent Expression) that can be read and written within rules.
We consider the problem of computing information theoretic functions such as Entropy on a Data Stream, using sublinear space. Our first result deals with a measure we call the “entropy norm” of an input stream: it is closely related to entropy but is structurally similar to the well-studied notion of frequency moments. We give a polylogarithmic space one-pass algorithm for estimating this norm under certain conditions on the input stream. We also prove a lower bound that rules out such an algorithm if these conditions do not hold. Our second group of res