Vol.9 No (Feb. 2016) DFDL 1,a) , ad-hoc legacy DFDL Data Format Description Language 1 Fisher DFDL The Data Description

Size: px

Start display at page:

Download "Vol.9 No (Feb. 2016) DFDL 1,a) , ad-hoc legacy DFDL Data Format Description Language 1 Fisher DFDL The Data Description"

しょうぶいなくら
4 years ago
Views:

1 DFDL 1,a) , ad-hoc legacy DFDL Data Format Description Language 1 Fisher DFDL The Data Description Language DFDL and Its Semantics Akihiko Tozawa 1,a) Naoto Sato 1 Kiyokuni Kawachiya 1 Received: July 3, 2015, Accepted: October 27, 2015 Abstract: Recently, in modern computer technology, there s increasing need to handle non-standard text and binary data called the ad-hoc or legacy data. The languages that handle such non-standard data are called data description languages, and DFDL (Data Format Description Language) is one example. Such data description languages cannot be captured by existing parser framework, in particular because the nonstandard data is often parsed dependent on the content of the data itself. In order to characterize such feature of data description languages, Fisher et al. proposed the formal system using dependent types. In this paper, based on their work, we give semantics to the DFDL language and discuss its processor. Keywords: data description language, parsers, semantics 1. XML JSON ad-hoc legacy COBOL EDIFACT [9] HL7 [5] 1 IBM Research - Tokyo, Chuo, Tokyo , Japan a) atozawa@jp.ibm.com ad-hoc DFDL Data Format Description Language [8] OGF Open Grid Forum IBM IIB IBM Integration Bus DataPower DFDL DFDL DFDL0 DFDL c 2016 Information Processing Society of Japan 1

2 2. LR(k) LL(k) ad-hoc ad-hoc [7] DDC Fisher [3] PADS DFDL0 DDC DFDL DDC DFDL0 TS [2] PEG [4] DFDL0 DDC + / DFDL0 DDC Σx : τ 1.τ 2 τ 2 x TS PEG TDPL Top Down Parsing Language LL(k) a n b n c n 3. DFDL0 1A2AB3ABC ("A", "AB", "ABC") PL/I ISO8583 [6] DFDL 1 DFDL DFDL XML [10] XML XML DFDL XML <Root> <Item><Length>1</Length><Value>A</Value></Item> <Item><Length>2</Length><Value>AB</Value></Item> <Item><Length>3</Length><Value>ABC</Value></Item> </Root> 1 DFDL XML Root Length Value Item XML DFDL XML DFDL dfdl:format 6 17 XML dfdl:length DFDL DFDL DFDL XML 1 length DFDL 100 DFDL DFDL0 DFDL 3.1 DFDL0 Fisher [3] DFDL DFDL0 b ::= unit bool int string... τ ::= b τ (0) 0- τ + τ c 2016 Information Processing Society of Japan 2

3 1 DFDL Fig. 1 Example of DFDL schema. Σx : τ.τ τ{p := e} 1 DFDL DFDL0 μα (0).Σx : int{length := 1}. Σ : string{length := x}. (α (0) + unit) Σx : τ 1.τ 2 (v 1,v 2 ) v 1 : τ 1 v 2 : τ 2 [x/v 1 ] length := 1 length e unit DFDL0 τ + unit XML τ unit 2 n *1 *1 Fisher Fisher Πx :.τ λx.τ c 2016 Information Processing Society of Japan 3

4 2 n-n 0 Fig. 2 n-ary types (n 0). 4 1A2AB Fig. 4 Parsing 1A2AB. XML 1A2AB3ABC (1, "A", inl(2, "AB", inl(3, "ABC", inr()))) 3 Fig. 3 Example of host programming language. 0 2 A = μα (1).Πx :.τ Ax = τ[α (1) /A] e 3 DFDL0 Fisher DFDL XPath 3.2 DFDL0 DFDL0 DFDL0 inl inr v ::= c (v, v) inl v inr v 4 Σx : int{length := 1}... 1 int x Σ : string{length := x}... x string α (0) + unit DFDL DFDL p ::= length lengthpattern initiator terminator separator discriminator x length lengthpattern *2 *2 DFDL lengthkind length "explicit" lengthpattern "pattern" lengthkind "delimited" c 2016 Information Processing Society of Japan 4

5 τ{p := e} e length int discriminator bool string length DFDL0 LL(k) A M("+" A "") M P ("*" M "") P "(" A ")" IntLiteral A =Σ : M.(A{initiator := "+"} + unit) M =Σ : P.(M{initiator := "*"} + unit) P = A{initiator := "("}{terminator := ")"}} + int{lengthpattern := "[0-9]+"} τ{initiator := e} τ{terminator := e} τ *3 τ μα.(σ : τ.α) + unit [ v 1,v 2,...,v n ] inl(v 1,...inl(v n, inr())...) "(1+2)*3" (([(inr 1, []), (inr 2, []) ], [ inr 3 ]), []) separator Σ A =(μα.(σ : M.α)+unit){separator := "+"} M =(μα.(σ : P.α)+unit){separator := "*"} P = A{initiator := "("}{terminator := ")"} + int{lengthpattern := "[0-9]+"} "1+2" "1+2+" unit separator DFDL 3.4 discriminator Haskell Python [1] *3 DFDL0 DFDL if a: if b: c() d() e() Python if b: e() c() d() if b: if a: c() d() if b: DFDL0 Prog = Stmts 0 Stmts n =Σstmt : Stmt n.(stmts n)+unit Stmt n = Σskip :(string{lengthpattern := "\s+"} {initiator := "\n"} + unit) {discriminator skip := skip of inr true inl indent len indent = n}. Σstmt : string{lengthpattern := "[a-za-z][^\n]+"}. (Block n + unit) Block n = Σindent : string{lengthpattern := "\s+"} {initiator := "\n"} {discriminator indent := len indent >n}. Stmts(len indent) discriminator τ 1 + τ 2 τ 1 τ 1 τ 2 τ{discriminator x := e} x τ bool e Prog Stmts n n Stmt n Stmt n stmt Stmt n "\n" "\s+" skip n discriminator c 2016 Information Processing Society of Japan 5

6 Stmts n unit n stmt Stmt n Block n Block n len indent n discriminator Stmt n unit len indent n Stmts(len indent) Prog Python (([], "if a:", (" ", ([], "if b:", (" ", ([], "c()", []), [(inr " ", "d()", []) ])), [(inr " ", "e()", []) ])), []) 3.5 DFDL DFDL0 DFDL0 DFDL XML DFDL DFDL1.0 DFDL XPath XML 1 dfdl:length="{../length }" DFDL0 DFDL XPath DFDL0 DFDL representation DFDL XML 2 length initiator terminator DFDL0 length τ{p 2 := e 2 }{p 1 := e 1 } p DFDL recursive descent parser ω, S, T τ r ω S T τ DFDL0 r r ::= fail v, ω fail v ω 5 parse b b ω ω ω[n, m] n m delimiter length lengthpattern separator terminator *4 *4 FOLLOW initiator terminator terminator c 2016 Information Processing Society of Japan 6

7 5 Fig. 5 Parsing semantics. e v : b e b v separator separator Σx : τ.τ S length lengthpattern S T Σx : τ.τ (P7.1) (P7.2) separator (P7.3) DFDL separator separator (P7.3) 1 ω τ ω, {}, {} τ v, "" v 4.2 S v : τ r separator S v τ r r r ::= fail ω ω 6 unparse b (v) b v initiator terminator Σx : τ.τ separator c 2016 Information Processing Society of Japan 7

8 6 Fig. 6 Unparsing semantics. lengthpattern disciriminator length length DFDL textstringpadcharacter textnumberpadcharacter 2 v τ {} v : τ ω ω DFDL0 LL(k) (μα.(σ : α. int)+int){separator := "-"} nilable N unit N string N τ 1 N τ 2 N τ 1 + τ 2 N τ 1 N τ 2 N Σx : τ 1.τ 2 N τ N τe N τ N Πx :.τ N. τ[α/μα.τ] N μα.τ N τ N τ{p := e} N p := e length := n n 1 Fischer-Ladner C(τ) ɛ C ɛ (τ) Πx :.τ 1 e C(τ) {τ} τ 1 C(τ) C ɛ (τ) τ 1 e C(τ) {τ} τ 1 C(τ) C ɛ (τ) μα.τ 1 C(τ) {τ} τ 1 [α/μα.τ 1 ] C(τ) C ɛ (τ) τ 1 + τ 2 C(τ) {τ} τ 1,τ 2 C(τ) C ɛ (τ) Σx : τ 1.τ 2 C(τ) {τ} τ 1,τ 2 C(τ) Σx : τ 1.τ 2 C ɛ (τ) {τ} τ 1 C ɛ (τ) τ 1 N τ 2 C ɛ (τ) τ 1 {p := e} C(τ) {τ} τ 1 C(τ) τ 1 {p := e} C ɛ (τ) {τ} p := e initiator := ζ c 2016 Information Processing Society of Japan 8

9 ζ 1 τ 1 C ɛ (τ) N C(τ) τ 5 C ɛ (τ) τ C(τ) 1 τ C(τ) τ / C ɛ (τ ) τ τ C(τ) DFDL 5.2 DFDL0 DFDL DFDL0 DFDL XML round-trip DFDL inr fail DFDL0 DFDL 6. DFDL DFDL0 DFDL0 DFDL DFDL0 [1] Adams, M.D.: Principled parsing for indentationsensitive languages: Revisiting landin s offside rule, 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 13, Rome, Italy - January 23-25, pp (2013). [2] Birman, A.: The Tmg Recognition Schema, PhD Thesis, Princeton University, Princeton, NJ, USA (1970). [3] Fisher, K., Mandelbaum, Y. and Walker, D.: The next 700 data description languages, Proc. 33rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2006, Charleston, South Carolina, USA, January 11-13, pp.2 15 (2006). [4] Ford, B.: Parsing Expression Grammars: A Recognitionbased Syntactic Foundation, Proc. 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 04, New York, NY, USA, pp , ACM (online), DOI: / (2004). [5] Health Level Seven International: HL7, Health Level Seven International, available from (accessed 2015). [6] ISO/TC 68/SC 7 Core banking: ISO :2003, Financial transaction card originated messages Interchange message specifications Part 1: Messages, data elements and code values, Internatioal Orgnization for Standardization, available from iso catalogue/catalogue tc/ catalogue detail.htm?csnumber=31628 (accessed 2015). [7] Leijen, D. and Meijer, E.: Parsec: Direct Style Monadic Parser Combinators For The Real World, Technical Report (2001). [8] OGF DFDL Working Group: Data Format Description Language 1.0, Open Grid Forum, available from (accessed 2015). [9] UN/CEFACT (United Nations Centre for Trade Facilitation and Electronic Business): EDIFACT, United Nations, available from (accessed 2015). [10] W3C XML Schema Working Group: XML Schema 1.0, World Wide Web Consortium, available from (accessed 2015) XML 2014 c 2016 Information Processing Society of Japan 9

10 2001 ACM Java X10 & ACM c 2016 Information Processing Society of Japan 10

& Vol.5 No (Oct. 2015) TV 1,2,a) , Augmented TV TV AR Augmented Reality 3DCG TV Estimation of TV Screen Position and Ro

& Vol.5 No (Oct. 2015) TV 1,2,a) , Augmented TV TV AR Augmented Reality 3DCG TV Estimation of TV Screen Position and Ro TV 1,2,a) 1 2 2015 1 26, 2015 5 21 Augmented TV TV AR Augmented Reality 3DCG TV Estimation of TV Screen Position and Rotation Using Mobile Device Hiroyuki Kawakita 1,2,a) Toshio Nakagawa 1 Makoto Sato