×

zbMATH — the first resource for mathematics

XML graphs in program analysis. (English) Zbl 1215.68079
Summary: XML graphs have shown to be a simple and effective formalism for representing sets of XML documents in program analysis. It has evolved through a six year period with variants tailored for a range of applications. We present a unified definition, outline the key properties including validation of XML graphs against different XML schema languages, and provide a software package that enables others to make use of these ideas. We also survey the use of XML graphs for program analysis with four very different languages: Xact (XML in Java), Java Servlets (Web application programming), XSugar (transformations between XML and non-XML data), and XSLT (stylesheets for transforming XML documents).

MSC:
68N99 Theory of software
68N15 Theory of programming languages
68R10 Graph theory (including graph drawing) in computer science
68P05 Data structures
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Vidur Apparao, et al. Document Object Model (DOM) level 1 specification, October 1998. W3C Recommendation. http://www.w3.org/TR/REC-DOM-Level-1/
[2] Philippe Audebaud, Kristoffer Rose, Stylesheet validation. Technical Report RR2000-37, ENS-Lyon, November 2000
[3] Böttger, Henning; Møller, Anders; Schwartzbach, Michael I.: Contracts for cooperation between web service programmers and HTML designers, Journal of web engineering 5, No. 1, 65-89 (2006)
[4] Brabrand, Claus; Giegerich, Robert; Møller, Anders: Analyzing ambiguity of context-free grammars, Lncs 4783 (2007) · Zbl 1139.68348
[5] Claus Brabrand, Anders Møller, Michael I. Schwartzbach, Static validation of dynamically generated HTML, in: Proc. ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, PASTE’01, June 2001, pp. 221–231
[6] Brabrand, Claus; Møller, Anders; Schwartzbach, Michael I.: Dual syntax for XML languages, Information systems 33, No. 4 (2008) · Zbl 1159.68407
[7] Aske Simon Christensen, Anders Møller, Michael I. Schwartzbach, Static analysis for dynamic XML. Technical Report RS-02-24, BRICS, May 2002. Presented at Programming Language Technologies for XML, PLAN-X’02 · Zbl 1067.68541
[8] Christensen, Aske Simon; Møller, Anders; Schwartzbach, Michael I.: Extending Java for high-level web service construction, ACM transactions on programming languages and systems 25, No. 6, 814-875 (2003)
[9] Christensen, Aske Simon; Møller, Anders; Schwartzbach, Michael I.: Precise analysis of string expressions, Lncs 2694, 1-18 (2003) · Zbl 1067.68541
[10] Clark, James; Trang:
[11] James Clark, XSL transformations (XSLT), November 1999, W3C Recommendation. http://www.w3.org/TR/xslt
[12] James Clark, RELAX NG compact syntax, November 2002, OASIS. http://relaxng.org/compact.html
[13] James Clark, Steve DeRose, XML path language, November 1999, W3C Recommendation. http://www.w3.org/TR/xpath
[14] James Clark, Makoto Murata, RELAX NG specification, December 2001, OASIS. http://www.oasis-open.org/committees/relax-ng/
[15] H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison, M. Tommasi, Tree automata techniques and applications, 1999. Available from http://www.grappa.univ-lille3.fr/tata/
[16] Dong, Ce; Bailey, James: Static analysis of XSLT programs, (2004)
[17] Mary Fernández, Ashok Malhotra, Jonathan Marsh, Marton Nagy, Norman Walsh, XQuery 1.0 and XPath 2.0 data model (XDM), November 2006, W3C Proposed Recommendation. http://www.w3.org/TR/xpath-datamodel/
[18] Vidar Bronken Gundersen, Zeger W. Hendrikse, BibTeXML, 2005. http://bibtexml.sourceforge.net/
[19] Hosoya, Haruo; Pierce, Benjamin C.: Xduce: A typed XML processing language, Lncs 1997 (2000) · Zbl 1323.68076
[20] Hosoya, Haruo; Vouillon, Jerome; Pierce, Benjamin C.: Regular expression types for XML, ACM transactions on programming languages and systems 27, No. 1, 46-90 (2005) · Zbl 1321.68197
[21] Kam, John B.; Ullman, Jeffrey D.: Monotone data flow analysis frameworks, Acta informatica 7, 305-317 (1977) · Zbl 0375.68020
[22] Kohsuke Kawaguchi, RELAX NG converter. http://wwws.sun.com/software/xml/developers/relaxngconverter/
[23] Kempa, Martin; Linnemann, Volker: Type checking in XOBE, Lni 26 (2003)
[24] Christian Kirkegaard, Anders Møller, Type checking with XML Schema in Xact. Technical Report RS-05-31, BRICS, 2005. Presented at Programming Language Technologies for XML, PLAN-X’06
[25] Kirkegaard, Christian; Møller, Anders: Static analysis for Java servlets and JSP, Lncs 4134 (2006)
[26] Kirkegaard, Christian; Møller, Anders; Schwartzbach, Michael I.: Static analysis of XML transformations in Java, IEEE transactions on software engineering 30, No. 3, 181-192 (2004)
[27] Christian Kirkegaard, Anders Møller, dk.brics.schematools, 2007. http://www.brics.dk/schematools/
[28] Knuth, Donald E.: A characterization of parenthesis languages, Information and control 11, 269-289 (1967) · Zbl 0196.01703
[29] Søren Kuula, Practical type-safe XSLT 2.0 stylesheet authoring. Master’s thesis, Department of Computer Science, University of Aarhus, 2006
[30] Leuf, Bo; Cunningham, Ward: The wiki way: quick collaboration on the web, (2001)
[31] Sebastian Maneth, Alexandru Berlea, Thomas Perst, Helmut Seidl, XML type checking with macro tree transducers, in: Proc. 24th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS’05, 2005, pp. 283–294
[32] Martens, Wim; Neven, Frank: Typechecking top-down uniform unranked tree transducers, Lncs 2572 (2003) · Zbl 1022.68037
[33] Wim Martens, Frank Neven, Frontiers of tractability for typechecking simple XML transformations, in: Proc. 23rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS’04, 2004, pp. 23–34 · Zbl 1115.68058
[34] Mauborgne, Laurent: An incremental unique representation for regular trees, Nordic journal of computing 7, No. 4, 290-311 (2000) · Zbl 0971.68122
[35] Milo, Tova; Suciu, Dan; Vianu, Victor: Typechecking for XML transformers, Journal of computer and system sciences 66, 66-97 (2002) · Zbl 1026.68045
[36] Mohri, Mehryar; Nederhof, Mark-Jan: Regular approximation of context-free grammars through transformation, (2001) · Zbl 0989.68124
[37] Anders Møller, Static analysis for event-based XML processing. Technical Report RS-06-16, BRICS, October 2006
[38] Møller, Anders; Olesen, Mads østerby; Schwartzbach, Michael I.: Static validation of XSL transformations, ACM transactions on programming languages and systems 29, No. 4 (2007)
[39] Møller, Anders; Schwartzbach, Michael I.: The design space of type checkers for XML transformation languages, Lncs 3363, 17-36 (2005) · Zbl 1112.68372
[40] Anders Møller, Michael I. Schwartzbach, XML graphs in program analysis (invited paper), in: Proc. ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM’07, January 2007 · Zbl 1215.68079
[41] Murata, Makoto; Lee, Dongwon; Mani, Murali; Kawaguchi, Kohsuke: Taxonomy of XML schema languages using formal language theory, ACM transactions on Internet technology 5, No. 4, 660-704 (2005)
[42] Nielson, Flemming; Nielson, Hanne Riis; Hankin, Chris: Principles of program analysis, (1999) · Zbl 0932.68013
[43] Reps, Thomas: Program analysis via graph reachability, Information and software technology 40, No. 11–12, 701-726 (1998)
[44] Henry S. Thompson, David Beech, Murray Maloney, Noah Mendelsohn, XML Schema part 1: Structures second edition, October 2004. W3C Recommendation. http://www.w3.org/TR/xmlschema-1/
[45] Akihiko Tozawa, Towards static type checking for XSLT, in: Proc. ACM Symposium on Document Engineering, DocEng’01, November 2001 · Zbl 1185.68203
[46] Vallee-Rai, Raja; Hendren, Laurie; Sundaresan, Vijay; Lam, Patrick; Gagnon, Etienne; Co, Phong: Soot – a Java optimization framework, (1999)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.