Attribute Grammars for Unranked Trees as a query language for structured documents

Document specification languages, like for instance XML, model documents using extended context-free grammars. These di#er from standard context-free grammars in that they allow arbitrary regular expressions on the right-hand side of productions. To query such documents, we introduce a new form of attribute grammars (extended AGs) that work directly over extended context-free grammars rather than over standard context-free grammars. Viewed as a query language, extended AGs are particularly relevant as they can take into account the inherent order of the children of a node in a document