A pushdown machine for recursive XML processing

Keisuke Nakano, Shin Cheng Mu

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 Citations (Scopus)


XML transformations are most naturally defined as recursive functions on trees. A naive implementation, however, would load the entire input XML tree into memory before processing. In contrast, programs in stream processing style minimise memory usage since it may release the memory occupied by the processed prefix of the input, but they are harder to write because the programmer is left with the burden to maintain a state. In this paper, we propose a model for XML stream processing and show that all programs written in a particular style of recursive functions on XML trees, the macro forest transducer, can be automatically translated to our stream processors. The stream processor is declarative in style, but can be implemented efficiently by a pushdown machine. We thus get the best of both worlds - program clarity, and efficiency in execution.

Original languageEnglish
Title of host publicationProgramming Languages and Systems - 4th Asian Symposium, APLAS 2006, Proceedings
PublisherSpringer Verlag
Number of pages17
ISBN (Print)3540489371, 9783540489375
Publication statusPublished - 2006
Event4th Asian Symposium on Programming Languages and Systems, APLAS 2006 - Sydney, Australia
Duration: 2006 Nov 82006 Nov 10

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4279 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference4th Asian Symposium on Programming Languages and Systems, APLAS 2006


Dive into the research topics of 'A pushdown machine for recursive XML processing'. Together they form a unique fingerprint.

Cite this