1pt::peg::from::json(n) Parser Tools pt::peg::from::json(n)
2______________________________________________________________________________
6
8 pt::peg::from::json - PEG Conversion. Read JSON format
9
11 package require Tcl 8.5
12 package require pt::peg::from::json ?1?
14 package require pt::peg
16 package require json
18 pt::peg::from::json convert text
20______________________________________________________________________________
22
24 Are you lost ? Do you have trouble understanding this document ? In
25 that case please read the overview provided by the Introduction to
26 Parser Tools. This document is the entrypoint to the whole system the
27 current package is a part of.
28 This package implements the converter from JSON markup to parsing
30 expression grammars.
31 It resides in the Import section of the Core Layer of Parser Tools, and
33 can be used either directly with the other packages of this layer, or
34 indirectly through the import manager provided by pt::peg::import. The
35 latter is intented for use in untrusted environments and done through
36 the corresponding import plugin pt::peg::import::json sitting between
37 converter and import manager.
38 IMAGE: arch_core_iplugins
40
42 The API provided by this package satisfies the specification of the
43 Converter API found in the Parser Tools Import API specification.
44 pt::peg::from::json convert text
46 This command takes the JSON markup encoding a parsing expression
47 grammar and contained in text, and generates the canonical seri‐
48 alization of said grammar, as specified in section PEG serial‐
49 ization format. The created value is then returned as the
50 result of the command.
51
53 The json format for parsing expression grammars was written as a data
54 exchange format not bound to Tcl. It was defined to allow the exchange
55 of grammars with PackRat/PEG based parser generators for other lan‐
56 guages.
57 It is formally specified by the rules below:
59 [1] The JSON of any PEG is a JSON object.
61 [2] This object holds a single key, pt::grammar::peg, and its value.
63 This value holds the contents of the grammar.
64 [3] The contents of the grammar are a JSON object holding the set of
66 nonterminal symbols and the starting expression. The relevant
67 keys and their values are
68 rules The value is a JSON object whose keys are the names of
70 the nonterminal symbols known to the grammar.
71 [1] Each nonterminal symbol may occur only once.
73 [2] The empty string is not a legal nonterminal sym‐
75 bol.
76 [3] The value for each symbol is a JSON object itself.
78 The relevant keys and their values in this dictio‐
79 nary are
80 is The value is a JSON string holding the Tcl
82 serialization of the parsing expression
83 describing the symbols sentennial struc‐
84 ture, as specified in the section PE seri‐
85 alization format.
86 mode The value is a JSON holding holding one of
88 three values specifying how a parser should
89 handle the semantic value produced by the
90 symbol.
91 value The semantic value of the nontermi‐
93 nal symbol is an abstract syntax
94 tree consisting of a single node
95 node for the nonterminal itself,
96 which has the ASTs of the symbol's
97 right hand side as its children.
98 leaf The semantic value of the nontermi‐
100 nal symbol is an abstract syntax
101 tree consisting of a single node
102 node for the nonterminal, without
103 any children. Any ASTs generated by
104 the symbol's right hand side are
105 discarded.
106 void The nonterminal has no semantic
108 value. Any ASTs generated by the
109 symbol's right hand side are dis‐
110 carded (as well).
111 start The value is a JSON string holding the Tcl serialization
113 of the start parsing expression of the grammar, as speci‐
114 fied in the section PE serialization format.
115 [4] The terminal symbols of the grammar are specified implicitly as
117 the set of all terminal symbols used in the start expression and
118 on the RHS of the grammar rules.
119 As an aside to the advanced reader, this is pretty much the same as the
121 Tcl serialization of PE grammars, as specified in section PEG serial‐
122 ization format, except that the Tcl dictionaries and lists of that for‐
123 mat are mapped to JSON objects and arrays. Only the parsing expressions
124 themselves are not translated further, but kept as JSON strings con‐
125 taining a nested Tcl list, and there is no concept of canonicity for
126 the JSON either.
127 EXAMPLE
129 Assuming the following PEG for simple mathematical expressions
130 PEG calculator (Expression)
132 Digit <- '0'/'1'/'2'/'3'/'4'/'5'/'6'/'7'/'8'/'9' ;
133 Sign <- '-' / '+' ;
134 Number <- Sign? Digit+ ;
135 Expression <- Term (AddOp Term)* ;
136 MulOp <- '*' / '/' ;
137 Term <- Factor (MulOp Factor)* ;
138 AddOp <- '+'/'-' ;
139 Factor <- '(' Expression ')' / Number ;
140 END;
141 a JSON serialization for it is
144 {
146 "pt::grammar::peg" : {
147 "rules" : {
148 "AddOp" : {
149 "is" : "\/ {t -} {t +}",
150 "mode" : "value"
151 },
152 "Digit" : {
153 "is" : "\/ {t 0} {t 1} {t 2} {t 3} {t 4} {t 5} {t 6} {t 7} {t 8} {t 9}",
154 "mode" : "value"
155 },
156 "Expression" : {
157 "is" : "\/ {x {t (} {n Expression} {t )}} {x {n Factor} {* {x {n MulOp} {n Factor}}}}",
158 "mode" : "value"
159 },
160 "Factor" : {
161 "is" : "x {n Term} {* {x {n AddOp} {n Term}}}",
162 "mode" : "value"
163 },
164 "MulOp" : {
165 "is" : "\/ {t *} {t \/}",
166 "mode" : "value"
167 },
168 "Number" : {
169 "is" : "x {? {n Sign}} {+ {n Digit}}",
170 "mode" : "value"
171 },
172 "Sign" : {
173 "is" : "\/ {t -} {t +}",
174 "mode" : "value"
175 },
176 "Term" : {
177 "is" : "n Number",
178 "mode" : "value"
179 }
180 },
181 "start" : "n Expression"
182 }
183 }
184 and a Tcl serialization of the same is
187 pt::grammar::peg {
189 rules {
190 AddOp {is {/ {t -} {t +}} mode value}
191 Digit {is {/ {t 0} {t 1} {t 2} {t 3} {t 4} {t 5} {t 6} {t 7} {t 8} {t 9}} mode value}
192 Expression {is {x {n Term} {* {x {n AddOp} {n Term}}}} mode value}
193 Factor {is {/ {x {t (} {n Expression} {t )}} {n Number}} mode value}
194 MulOp {is {/ {t *} {t /}} mode value}
195 Number {is {x {? {n Sign}} {+ {n Digit}}} mode value}
196 Sign {is {/ {t -} {t +}} mode value}
197 Term {is {x {n Factor} {* {x {n MulOp} {n Factor}}}} mode value}
198 }
199 start {n Expression}
200 }
201 The similarity of the latter to the JSON should be quite obvious.
204
206 Here we specify the format used by the Parser Tools to serialize Pars‐
207 ing Expression Grammars as immutable values for transport, comparison,
208 etc.
209 We distinguish between regular and canonical serializations. While a
211 PEG may have more than one regular serialization only exactly one of
212 them will be canonical.
213 regular serialization
215 [1] The serialization of any PEG is a nested Tcl dictionary.
217 [2] This dictionary holds a single key, pt::grammar::peg, and
219 its value. This value holds the contents of the grammar.
220 [3] The contents of the grammar are a Tcl dictionary holding
222 the set of nonterminal symbols and the starting expres‐
223 sion. The relevant keys and their values are
224 rules The value is a Tcl dictionary whose keys are the
226 names of the nonterminal symbols known to the
227 grammar.
228 [1] Each nonterminal symbol may occur only
230 once.
231 [2] The empty string is not a legal nonterminal
233 symbol.
234 [3] The value for each symbol is a Tcl dictio‐
236 nary itself. The relevant keys and their
237 values in this dictionary are
238 is The value is the serialization of
240 the parsing expression describing
241 the symbols sentennial structure, as
242 specified in the section PE serial‐
243 ization format.
244 mode The value can be one of three values
246 specifying how a parser should han‐
247 dle the semantic value produced by
248 the symbol.
249 value The semantic value of the
251 nonterminal symbol is an
252 abstract syntax tree consist‐
253 ing of a single node node for
254 the nonterminal itself, which
255 has the ASTs of the symbol's
256 right hand side as its chil‐
257 dren.
258 leaf The semantic value of the
260 nonterminal symbol is an
261 abstract syntax tree consist‐
262 ing of a single node node for
263 the nonterminal, without any
264 children. Any ASTs generated
265 by the symbol's right hand
266 side are discarded.
267 void The nonterminal has no seman‐
269 tic value. Any ASTs generated
270 by the symbol's right hand
271 side are discarded (as well).
272 start The value is the serialization of the start pars‐
274 ing expression of the grammar, as specified in the
275 section PE serialization format.
276 [4] The terminal symbols of the grammar are specified implic‐
278 itly as the set of all terminal symbols used in the start
279 expression and on the RHS of the grammar rules.
280 canonical serialization
282 The canonical serialization of a grammar has the format as spec‐
283 ified in the previous item, and then additionally satisfies the
284 constraints below, which make it unique among all the possible
285 serializations of this grammar.
286 [1] The keys found in all the nested Tcl dictionaries are
288 sorted in ascending dictionary order, as generated by
289 Tcl's builtin command lsort -increasing -dict.
290 [2] The string representation of the value is the canonical
292 representation of a Tcl dictionary. I.e. it does not con‐
293 tain superfluous whitespace.
294 EXAMPLE
296 Assuming the following PEG for simple mathematical expressions
297 PEG calculator (Expression)
299 Digit <- '0'/'1'/'2'/'3'/'4'/'5'/'6'/'7'/'8'/'9' ;
300 Sign <- '-' / '+' ;
301 Number <- Sign? Digit+ ;
302 Expression <- Term (AddOp Term)* ;
303 MulOp <- '*' / '/' ;
304 Term <- Factor (MulOp Factor)* ;
305 AddOp <- '+'/'-' ;
306 Factor <- '(' Expression ')' / Number ;
307 END;
308 then its canonical serialization (except for whitespace) is
311 pt::grammar::peg {
313 rules {
314 AddOp {is {/ {t -} {t +}} mode value}
315 Digit {is {/ {t 0} {t 1} {t 2} {t 3} {t 4} {t 5} {t 6} {t 7} {t 8} {t 9}} mode value}
316 Expression {is {x {n Term} {* {x {n AddOp} {n Term}}}} mode value}
317 Factor {is {/ {x {t (} {n Expression} {t )}} {n Number}} mode value}
318 MulOp {is {/ {t *} {t /}} mode value}
319 Number {is {x {? {n Sign}} {+ {n Digit}}} mode value}
320 Sign {is {/ {t -} {t +}} mode value}
321 Term {is {x {n Factor} {* {x {n MulOp} {n Factor}}}} mode value}
322 }
323 start {n Expression}
324 }
325
328 Here we specify the format used by the Parser Tools to serialize Pars‐
329 ing Expressions as immutable values for transport, comparison, etc.
330 We distinguish between regular and canonical serializations. While a
332 parsing expression may have more than one regular serialization only
333 exactly one of them will be canonical.
334 Regular serialization
336 Atomic Parsing Expressions
338 [1] The string epsilon is an atomic parsing expres‐
340 sion. It matches the empty string.
341 [2] The string dot is an atomic parsing expression. It
343 matches any character.
344 [3] The string alnum is an atomic parsing expression.
346 It matches any Unicode alphabet or digit charac‐
347 ter. This is a custom extension of PEs based on
348 Tcl's builtin command string is.
349 [4] The string alpha is an atomic parsing expression.
351 It matches any Unicode alphabet character. This is
352 a custom extension of PEs based on Tcl's builtin
353 command string is.
354 [5] The string ascii is an atomic parsing expression.
356 It matches any Unicode character below U0080. This
357 is a custom extension of PEs based on Tcl's
358 builtin command string is.
359 [6] The string control is an atomic parsing expres‐
361 sion. It matches any Unicode control character.
362 This is a custom extension of PEs based on Tcl's
363 builtin command string is.
364 [7] The string digit is an atomic parsing expression.
366 It matches any Unicode digit character. Note that
367 this includes characters outside of the [0..9]
368 range. This is a custom extension of PEs based on
369 Tcl's builtin command string is.
370 [8] The string graph is an atomic parsing expression.
372 It matches any Unicode printing character, except
373 for space. This is a custom extension of PEs based
374 on Tcl's builtin command string is.
375 [9] The string lower is an atomic parsing expression.
377 It matches any Unicode lower-case alphabet charac‐
378 ter. This is a custom extension of PEs based on
379 Tcl's builtin command string is.
380 [10] The string print is an atomic parsing expression.
382 It matches any Unicode printing character, includ‐
383 ing space. This is a custom extension of PEs based
384 on Tcl's builtin command string is.
385 [11] The string punct is an atomic parsing expression.
387 It matches any Unicode punctuation character. This
388 is a custom extension of PEs based on Tcl's
389 builtin command string is.
390 [12] The string space is an atomic parsing expression.
392 It matches any Unicode space character. This is a
393 custom extension of PEs based on Tcl's builtin
394 command string is.
395 [13] The string upper is an atomic parsing expression.
397 It matches any Unicode upper-case alphabet charac‐
398 ter. This is a custom extension of PEs based on
399 Tcl's builtin command string is.
400 [14] The string wordchar is an atomic parsing expres‐
402 sion. It matches any Unicode word character. This
403 is any alphanumeric character (see alnum), and any
404 connector punctuation characters (e.g. under‐
405 score). This is a custom extension of PEs based on
406 Tcl's builtin command string is.
407 [15] The string xdigit is an atomic parsing expression.
409 It matches any hexadecimal digit character. This
410 is a custom extension of PEs based on Tcl's
411 builtin command string is.
412 [16] The string ddigit is an atomic parsing expression.
414 It matches any decimal digit character. This is a
415 custom extension of PEs based on Tcl's builtin
416 command regexp.
417 [17] The expression [list t x] is an atomic parsing
419 expression. It matches the terminal string x.
420 [18] The expression [list n A] is an atomic parsing
422 expression. It matches the nonterminal A.
423 Combined Parsing Expressions
425 [1] For parsing expressions e1, e2, ... the result of
427 [list / e1 e2 ... ] is a parsing expression as
428 well. This is the ordered choice, aka prioritized
429 choice.
430 [2] For parsing expressions e1, e2, ... the result of
432 [list x e1 e2 ... ] is a parsing expression as
433 well. This is the sequence.
434 [3] For a parsing expression e the result of [list *
436 e] is a parsing expression as well. This is the
437 kleene closure, describing zero or more repeti‐
438 tions.
439 [4] For a parsing expression e the result of [list +
441 e] is a parsing expression as well. This is the
442 positive kleene closure, describing one or more
443 repetitions.
444 [5] For a parsing expression e the result of [list &
446 e] is a parsing expression as well. This is the
447 and lookahead predicate.
448 [6] For a parsing expression e the result of [list !
450 e] is a parsing expression as well. This is the
451 not lookahead predicate.
452 [7] For a parsing expression e the result of [list ?
454 e] is a parsing expression as well. This is the
455 optional input.
456 Canonical serialization
458 The canonical serialization of a parsing expression has the for‐
459 mat as specified in the previous item, and then additionally
460 satisfies the constraints below, which make it unique among all
461 the possible serializations of this parsing expression.
462 [1] The string representation of the value is the canonical
464 representation of a pure Tcl list. I.e. it does not con‐
465 tain superfluous whitespace.
466 [2] Terminals are not encoded as ranges (where start and end
468 of the range are identical).
469 EXAMPLE
471 Assuming the parsing expression shown on the right-hand side of the
472 rule
473 Expression <- Term (AddOp Term)*
475 then its canonical serialization (except for whitespace) is
478 {x {n Term} {* {x {n AddOp} {n Term}}}}
480
483 This document, and the package it describes, will undoubtedly contain
484 bugs and other problems. Please report such in the category pt of the
485 Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist]. Please also
486 report any ideas for enhancements you may have for either package
487 and/or documentation.
488 When proposing code changes, please provide unified diffs, i.e the out‐
490 put of diff -u.
491 Note further that attachments are strongly preferred over inlined
493 patches. Attachments can be made by going to the Edit form of the
494 ticket immediately after its creation, and then using the left-most
495 button in the secondary navigation bar.
496
498 EBNF, JSON, LL(k), PEG, TDPL, context-free languages, conversion,
499 expression, format conversion, grammar, matching, parser, parsing
500 expression, parsing expression grammar, push down automaton, recursive
501 descent, serialization, state, top-down parsing languages, transducer
502
504 Parsing and Grammars
505
507 Copyright (c) 2009 Andreas Kupries <andreas_kupries@users.sourceforge.net>
508tcllib 1 pt::peg::from::json(n)