xsugar
Dual Syntax for XML Languages
Claus Brabrand
Anders Møller
Michael Schwartzbach
{brabrand,amoeller,[email protected]
BRICS, Department of Computer Science
University of Aarhus, Denmark
DBPL 2005 [ August 28, 2005 ]
Dual Syntax for XML Languages
1 / 30
// Outline (3 parts)
1
Introduction (xsugar)
Introduction
xsugar
Syntax and Semantics
Unifying Syntax Tree
2
Static Analyses
Reversibility Analysis
Info Preservation
Unambiguity
DBPL 2005 [ August 28, 2005 ]
Validation Analysis
DTDs & Summary Graphs
Schema Languages
3
Assessment
Teleportation
More Examples
Related & Future Work
Assessment
Conclusion
Dual Syntax for XML Languages
3 / 30
// Part 1: Introduction
1
Introduction (xsugar)
Introduction
xsugar
Syntax and Semantics
Unifying Syntax Tree
2
Static Analyses
Reversibility Analysis
Info Preservation
Unambiguity
DBPL 2005 [ August 28, 2005 ]
Validation Analysis
DTDs & Summary Graphs
Schema Languages
3
Assessment
Teleportation
More Examples
Related & Future Work
Assessment
Conclusion
Dual Syntax for XML Languages
4 / 30
// Motivation
Relax NG:
Relax RNC
Relax RNG
RNC-to-RNG:
Dynamic issues:
Python script (1,478 lines)
RNG-to-RNC:
XSLT stylesheet (894 lines)
DBPL 2005 [ August 28, 2005 ]
Dual Syntax for XML Languages
• correspondence ?
• maintenance ?
• reversibility ?
• validity (XML) ?
• termination ?
5 / 30
// Motivation (cont’d)
XQuery:
XQuery
XQueryX
XQuery-to-XQueryX:
Non-existent...!
XQueryX-to-XQuery:
XSLT stylesheet (845 lines)
DBPL 2005 [ August 28, 2005 ]
Dual Syntax for XML Languages
Dynamic issues:
• correspondence ?
• maintenance ?
• reversibility ?
• validity (XML) ?
• termination ?
6 / 30
// xsugar
One stylesheet produces:
L
s:LX
X
xsugar
Static guarantees:
L2X:
Transformation:
LX
X2L:
Reverse transformation: X  L
DBPL 2005 [ August 28, 2005 ]
Dual Syntax for XML Languages
• correspondence !
• maintenance !
• reversibility !
• validity (XML) !
• termination !
7 / 30
// Example: Transformation…
<student id=“19920539”>
<name>Claus Brabrand</name>
<email>[email protected]</email>
</student>
x:
unparsing
transformation
l:
Claus Brabrand ([email protected]) 19920539
[Name n]
Name
Email
Id
=
=
=
{ ... }
{ ... }
{ [0-9]+ }
[Email e]
[Id id]
s: L  X
parsing
student
:
[Name n] ( [Email e] ) [Id id] \n
<student id=[Id id]>
<name><[Name n]></name>
<email><[Email e]></email>
</student>
}
unparsing
DBPL 2005 [ August 28, 2005 ]
parsing
Dual Syntax for XML Languages
=
{
8 / 30
// …and Reverse Transformation
[Id id]
[Name n]
[Email e]
<student id=“19920539”>
<name>Claus Brabrand</name>
<email>[email protected]</email>
</student>
x:
parsing
reverse transformation
l:
Name
Email
Id
Claus Brabrand ([email protected]) 19920539
=
=
=
{ ... }
{ ... }
{ [0-9]+ }
s: L  X
unparsing
student
:
[Name n] ( [Email e] ) [Id id] \n
<student id=[Id id]>
<name><[Name n]></name>
<email><[Email e]></email>
</student>
}
parsing
DBPL 2005 [ August 28, 2005 ]
unparsing
Dual Syntax for XML Languages
=
{
9 / 30
// Unifying Grammar
student
:
[Name n] ( [Email e] ) [Id id] \n
<student id=[Id id]>
<name><[Name n]></name>
<email><[Email e]></email>
</student>
}
=
{
G =  N, , s, U,  
N

sN
U
 : N  P(E*  E*),
unification:
2 right-hand sides
DBPL 2005 [ August 28, 2005 ]
finite set of unifying nonterminals
finite alphabet of terminals
start unifying nonterminal
finite set of unification names
unifying production function,
E = (N  U)  
Dual Syntax for XML Languages
10 / 30
// Regular Nonterminal Shorthand
Name
Email
Id
=
=
=
student
...
{ ... }
{ ... }
{ [0-9]+ }
:
[Name n] ( [Email e] ) [Id id] \n
=
{
}
Regular expressions (convenient short-hand) for regular
nonterminals (w/ identity unification):
Id
=
{ [0-9]+ }
desugaring
id
num
:
:
:
…
:
[num n] [id i]
[num n]
0
=
=
=
{ <[num n]> <[id i]> }
{ <[num n]> }
{ 0 }
9
=
{ 9 }
DBPL 2005 [ August 28, 2005 ]
Dual Syntax for XML Languages
11 / 30
// “The Big Picture”
UST
.
.
.
LX
ASTL / ~L
L
ASTX / ~XML

1-1
Reversible ? (i.e.
Parsing / Unparsing (i.e.

1-1
):
.
. ):
.. ..
 ):
Grammar Ambiguity ?
Transformation (i.e.
1-1
Information Preservation ?
DBPL 2005 [ August 28, 2005 ]
Dual Syntax for XML Languages
X
Legend:
Canonical: l  L
Ordered tree
Unordered tree
Partially Ordered
Canonical: x  X
12 / 30
// Part 1: Introduction
1
Introduction (xsugar)
Introduction
xsugar
Syntax and Semantics
Unifying Syntax Tree
2
Static Analyses
Reversibility Analysis
Info Preservation
Unambiguity
DBPL 2005 [ August 28, 2005 ]
Validation Analysis
DTDs & Summary Graphs
Schema Languages
3
Assessment
Teleportation
More Examples
Related & Future Work
Assessment
Conclusion
Dual Syntax for XML Languages
13 / 30
// Part 2: Static Analyses
1
Introduction (xsugar)
Introduction
xsugar
Syntax and Semantics
Unifying Syntax Tree
2
Static Analyses
Reversibility Analysis
Grammar Unambiguity
Information Preservation
DBPL 2005 [ August 28, 2005 ]
Validation Analysis
DTDs & Summary Graphs
Schema Languages
3
Assessment
Teleportation
More Examples
Related & Future Work
Assessment
Conclusion
Dual Syntax for XML Languages
14 / 30
// Motivating Example (Ex. cont’d)
Name
Email
Id
= { [^(\n]+ }
= { [^,) ]+ }
= { [0-9]+ }
student
: [Name n] ( [emails es] ) [Id id] \n = {
<student id=[id]> <name><[n]></name> <emails><[es]></emails> </student>
}
emails
: [Email e] = { <email><[e]></email> }
: [Email e] , [emails es] = { <email><[e]></email> <[es]> }

Anders Moeller ([email protected],[email protected]) 19940392
<student id=“19940392”>
<name>Anders Moeller</name>
<emails>
<email>[email protected]</email>
<email>[email protected]</email>
</emails>
</student>
DBPL 2005 [ August 28, 2005 ]
Dual Syntax for XML Languages
15 / 30
// Motivating Example
Name
Email
Id
2
(cont’d )
= { [^(\n]+ }
= { [^,) ]+ }
= { [0-9]+ }
student
: [Name n] [opt_emails e] [Id id] \n = {
<student id=[id]> <name><[n]></name> <[e]> </student>
}
opt_emails : = {}
: ( [email e] ) = { <[e]> }
: ( [email e] , [emails es] ) = { <emails><[e]><[es]></emails> }
emails
: [email e] = { <[e]> }
: [email e] , [emails es] = { <[e]><[es]> }
email
: [Email e] = { <email><[e]></email> }
DBPL 2005 [ August 28, 2005 ]
Dual Syntax for XML Languages
16 / 30
// Example (cont’d)
Claus Brabrand ([email protected]) 19920539
Anders Moeller ([email protected], [email protected]) 19940392
Michael Schwartzbach 18791398
<student id=“19920539”>
<name>Claus Brabrand</name>
<email>[email protected]</email>
</student>
<student id=“19940392”>
<name>Anders Moeller</name>
<emails>
<email>[email protected]</email>
<email>[email protected]</email>
</emails>
</student>
<student id=“8”>
<name>Michael Schwartzbach 1879139</name>
</student>
DBPL 2005 [ August 28, 2005 ]
Dual Syntax for XML Languages
17 / 30
// Example (cont’d)
Claus Brabrand ([email protected]) 19920539
Anders Moeller ([email protected], [email protected]) 19940392
Michael Schwartzbach 18791398
<student id=“19920539”>
<name>Claus Brabrand</name>
<email>[email protected]</email>
</student>
<student id=“19940392”>
<name>Anders Moeller</name>
<emails>
<email>[email protected]</email>
<email>[email protected]</email>
</emails>
</student>
Ambiguous grammar !
<student id=“8”>
<name>Michael Schwartzbach 1879139</name>
</student>
DBPL 2005 [ August 28, 2005 ]
Dual Syntax for XML Languages
18 / 30
// Approximating CFG Ambiguity
.
.
L
ASTL / ~L
?
Undecidable ?:
unambiguous
However…!:
unambiguous
. . .ambiguous
(over-)approximation
Black-box :
Yes!
Safe (over-)approximation:
DBPL 2005 [ August 28, 2005 ]
ambiguous
Dual Syntax for XML Languages
No?
19 / 30
// Information Preservation
UST
.
UST
.
.
LX
ASTL / ~L
.
LX
ASTL / ~L
“Never throw away or duplicate information”:
i.e. all named arguments must be used exactly once!
DBPL 2005 [ August 28, 2005 ]
Dual Syntax for XML Languages
20 / 30
// Reversible Stylesheets!
1-1 !
.
un-/parsing
Reversibility (proof):
.
1-1 !
transformation
1-1 !
transformation
.
1-1 !
un-/parsing

xsugar 1-1 !
.
xsugar: 1-1 !
.
.
LX
L
DBPL 2005 [ August 28, 2005 ]
ASTL / ~L
ASTX / ~XML
Dual Syntax for XML Languages
X
21 / 30
// Validation Analysis
Given
DTD, D:
 l  L : x(l)  L(D)

L(X)  L(D)

SG(X)  L(D)
Black-box
“Static Validation of Dynamically Generated HTML”
[ Claus Brabrand | Anders Møller | Michael Schwartzbach ]
PASTE, 2001
DBPL 2005 [ August 28, 2005 ]
Dual Syntax for XML Languages
22 / 30
// Summary Graphs
Id
Name
Email
= { [0-9]+
[0-9]+ }
= { [^(\n]+
[^(\n]+ }
= { [^,)
[^,) ]+]+ }
student
: [Name n] ( [emails es] ) [Id id] \n = {
<student id=[
]> <name><[
]></name> <emails><[
]></emails> </student>
id=[id]>
<name><[n]></name>
<emails><[es]></emails>
}
emails
]></email> }
: [Email e] = { <email><[
<email><[e]></email>
: [Email e] , [emails es] = { <email><[e]></email>
<email><[ ]></email> <[es]>
<[ ]> }
SG(X)  L(D)
Black-box
“Static Validation of Dynamically Generated HTML”
[ Claus Brabrand | Anders Møller | Michael Schwartzbach ]
PASTE, 2001
DBPL 2005 [ August 28, 2005 ]
Dual Syntax for XML Languages
23 / 30
// Part 2: Static Analyses
1
Introduction (xsugar)
Introduction
xsugar
Syntax and Semantics
Unifying Syntax Tree
2
Static Analyses
Reversibility Analysis
Grammar Unambiguity
Information Preservation
DBPL 2005 [ August 28, 2005 ]
Validation Analysis
DTDs & Summary Graphs
Schema Languages
3
Assessment
Teleportation
More Examples
Related & Future Work
Assessment
Conclusion
Dual Syntax for XML Languages
24 / 30
// Part 3: Assessment
1
Introduction (xsugar)
Introduction
xsugar
Syntax and Semantics
Unifying Syntax Tree
2
Static Analyses
Reversibility Analysis
Info Preservation
Unambiguity
DBPL 2005 [ August 28, 2005 ]
Validation Analysis
DTDs & Summary Graphs
Schema Languages
3
Assessment
Teleportation
More Examples
Related & Future Work
Assessment
Conclusion
Dual Syntax for XML Languages
25 / 30
// Related Work
“XSLT” (aka. XSL Stylesheets):
However, only one direction
“Presenting XML”:
“Java web application framework for presenting HTML, PDF, WML etc.,
in a device independent manner”.
“It aims to achieve a complete separation of content and presentation”.
Relax RNC
Relax RNG
P1
P2
DBPL 2005 [ August 28, 2005 ]
Dual Syntax for XML Languages
26 / 30
// Related Work (cont’d)
“Bi-directional Transformation Language for XML”
[Kawanaka & Hosoya]
XML <=> XML transformations:
<person>
<name>John Doe</name>
<mail>[email protected]</mail>
<phone>01-2345-6789</phone>
<phone>090-2345-6781</phone>
</person>
<card>
<name>John Doe</name>
<email>[email protected]</email>
<tel>01-2345-6789</tel>
<tel>090-2345-6781</tel>
</card>
relation personcard =
person[name[var x as String],
mail[var y as String]*,
phone[var z as String]*]
DBPL 2005 [ August 28, 2005 ]
card[name[var x as String],
email[var y as String]*,
tel[var z as String]*]
Dual Syntax for XML Languages
27 / 30
// Full On-line Implementation
Impementation (in Java): [ 82 K src ]
[ http://www.brics.dk/xsugar/ ]
Google: “xsugar” :)
On-line demo(!):
[ http://www.brics.dk/xsugar/ ]
DBPL 2005 [ August 28, 2005 ]
Dual Syntax for XML Languages
28 / 30
// Assessment
For “Relax NG”:
lines
Transform
1600
Parse
1400
Total
1200
1000
800
600
Static guarantees:
400
200
0
XSLT
Python
xsugar
Conciseness: [ 1 / 12+ ]
DBPL 2005 [ August 28, 2005 ]
Dual Syntax for XML Languages
• correspondence ? vs !
• maintenance
? vs !
• reversibility
? vs !
• validity (XML) ? vs !
• termination
? vs !
29 / 30
// Conclusion
xsugar: Reversible Stylesheets
L
s:LX
X
xsugar
Static guarantees:
L2X:
Stylesheet: L  X
X2L:
Reverse stylesheet: X  L
DBPL 2005 [ August 28, 2005 ]
Dual Syntax for XML Languages
• correspondence !
• maintenance !
• reversibility !
• validity (XML) !
• termination !
30 / 30
</presentation >
Questions please…
DBPL 2005 [ August 28, 2005 ]
Dual Syntax for XML Languages
31 / 30
Descargar

Document