299 @{ML_struct Scan} defined in the file @{ML_file "Pure/General/scan.ML"} in the Isabelle |
299 @{ML_struct Scan} defined in the file @{ML_file "Pure/General/scan.ML"} in the Isabelle |
300 sources. While these combinators do not make any assumptions about the concrete |
300 sources. While these combinators do not make any assumptions about the concrete |
301 structure of the tokens used, the second part of the library consists of combinators |
301 structure of the tokens used, the second part of the library consists of combinators |
302 for dealing with specific token types. |
302 for dealing with specific token types. |
303 The following is an excerpt from the signature of @{ML_struct Scan}: |
303 The following is an excerpt from the signature of @{ML_struct Scan}: |
304 \begin{mytable} |
304 |
|
305 \begin{table} |
305 @{ML "|| : ('a -> 'b) * ('a -> 'b) -> 'a -> 'b"} \\ |
306 @{ML "|| : ('a -> 'b) * ('a -> 'b) -> 'a -> 'b"} \\ |
306 @{ML "-- : ('a -> 'b * 'c) * ('c -> 'd * 'e) -> 'a -> ('b * 'd) * 'e"} \\ |
307 @{ML "-- : ('a -> 'b * 'c) * ('c -> 'd * 'e) -> 'a -> ('b * 'd) * 'e"} \\ |
307 @{ML "|-- : ('a -> 'b * 'c) * ('c -> 'd * 'e) -> 'a -> 'd * 'e"} \\ |
308 @{ML "|-- : ('a -> 'b * 'c) * ('c -> 'd * 'e) -> 'a -> 'd * 'e"} \\ |
308 @{ML "--| : ('a -> 'b * 'c) * ('c -> 'd * 'e) -> 'a -> 'b * 'e"} \\ |
309 @{ML "--| : ('a -> 'b * 'c) * ('c -> 'd * 'e) -> 'a -> 'b * 'e"} \\ |
309 @{ML "optional: ('a -> 'b * 'a) -> 'b -> 'a -> 'b * 'a" in Scan} \\ |
310 @{ML "optional: ('a -> 'b * 'a) -> 'b -> 'a -> 'b * 'a" in Scan} \\ |
310 @{ML "repeat: ('a -> 'b * 'a) -> 'a -> 'b list * 'a" in Scan} \\ |
311 @{ML "repeat: ('a -> 'b * 'a) -> 'a -> 'b list * 'a" in Scan} \\ |
311 @{ML "repeat1: ('a -> 'b * 'a) -> 'a -> 'b list * 'a" in Scan} \\ |
312 @{ML "repeat1: ('a -> 'b * 'a) -> 'a -> 'b list * 'a" in Scan} \\ |
312 @{ML ">> : ('a -> 'b * 'c) * ('b -> 'd) -> 'a -> 'd * 'c"} \\ |
313 @{ML ">> : ('a -> 'b * 'c) * ('b -> 'd) -> 'a -> 'd * 'c"} \\ |
313 @{ML "!! : ('a * string option -> string) -> ('a -> 'b) -> 'a -> 'b"} |
314 @{ML "!! : ('a * string option -> string) -> ('a -> 'b) -> 'a -> 'b"} |
314 \end{mytable} |
315 \end{table} |
315 Interestingly, the functions shown above are so generic that they do not |
316 Interestingly, the functions shown above are so generic that they do not |
316 even rely on the input and output of the parser being a list of tokens. |
317 even rely on the input and output of the parser being a list of tokens. |
317 If \texttt{p} succeeds, i.e.\ does not raise an exception, the parser |
318 If \texttt{p} succeeds, i.e.\ does not raise an exception, the parser |
318 @{ML "p || q" for p q} returns the result of \texttt{p}, otherwise it returns |
319 @{ML "p || q" for p q} returns the result of \texttt{p}, otherwise it returns |
319 the result of \texttt{q}. The parser @{ML "p -- q" for p q} first parses an |
320 the result of \texttt{q}. The parser @{ML "p -- q" for p q} first parses an |
346 |
347 |
347 So far, we have only looked at combinators that construct more complex parsers |
348 So far, we have only looked at combinators that construct more complex parsers |
348 from simpler parsers. In order for these combinators to be useful, we also need |
349 from simpler parsers. In order for these combinators to be useful, we also need |
349 some basic parsers. As an example, we consider the following two parsers |
350 some basic parsers. As an example, we consider the following two parsers |
350 defined in @{ML_struct Scan}: |
351 defined in @{ML_struct Scan}: |
351 \begin{mytable} |
352 |
|
353 \begin{table} |
352 @{ML "one: ('a -> bool) -> 'a list -> 'a * 'a list" in Scan} \\ |
354 @{ML "one: ('a -> bool) -> 'a list -> 'a * 'a list" in Scan} \\ |
353 @{ML "$$ : string -> string list -> string * string list"} |
355 @{ML "$$ : string -> string list -> string * string list"} |
354 \end{mytable} |
356 \end{table} |
|
357 |
355 The parser @{ML "one pred" for pred in Scan} parses exactly one token that |
358 The parser @{ML "one pred" for pred in Scan} parses exactly one token that |
356 satisfies the predicate \texttt{pred}, whereas @{ML "$$ s" for s} only |
359 satisfies the predicate \texttt{pred}, whereas @{ML "$$ s" for s} only |
357 accepts a token that equals the string \texttt{s}. Note that we can easily |
360 accepts a token that equals the string \texttt{s}. Note that we can easily |
358 express @{ML "$$ s" for s} using @{ML "one" in Scan}: |
361 express @{ML "$$ s" for s} using @{ML "one" in Scan}: |
359 @{ML [display] "one (fn s' => s' = s)" for s in Scan} |
362 @{ML [display] "one (fn s' => s' = s)" for s in Scan} |
369 of proof methods and attributes use the token type @{ML_type OuterParse.token}, |
372 of proof methods and attributes use the token type @{ML_type OuterParse.token}, |
370 which is identical to @{ML_type OuterLex.token}. |
373 which is identical to @{ML_type OuterLex.token}. |
371 The parser functions for the theory syntax are contained in the structure |
374 The parser functions for the theory syntax are contained in the structure |
372 @{ML_struct OuterParse} defined in the file @{ML_file "Pure/Isar/outer_parse.ML"}. |
375 @{ML_struct OuterParse} defined in the file @{ML_file "Pure/Isar/outer_parse.ML"}. |
373 In our parser, we will use the following functions: |
376 In our parser, we will use the following functions: |
374 \begin{mytable} |
377 |
|
378 \begin{table} |
375 @{ML "$$$ : string -> token list -> string * token list" in OuterParse} \\ |
379 @{ML "$$$ : string -> token list -> string * token list" in OuterParse} \\ |
376 @{ML "enum1: string -> (token list -> 'a * token list) -> token list -> |
380 @{ML "enum1: string -> (token list -> 'a * token list) -> token list -> |
377 'a list * token list" in OuterParse} \\ |
381 'a list * token list" in OuterParse} \\ |
378 @{ML "prop: token list -> string * token list" in OuterParse} \\ |
382 @{ML "prop: token list -> string * token list" in OuterParse} \\ |
379 @{ML "opt_target: token list -> string option * token list" in OuterParse} \\ |
383 @{ML "opt_target: token list -> string option * token list" in OuterParse} \\ |
380 @{ML "fixes: token list -> |
384 @{ML "fixes: token list -> |
381 (Binding.T * string option * mixfix) list * token list" in OuterParse} \\ |
385 (Binding.T * string option * mixfix) list * token list" in OuterParse} \\ |
382 @{ML "for_fixes: token list -> |
386 @{ML "for_fixes: token list -> |
383 (Binding.T * string option * mixfix) list * token list" in OuterParse} \\ |
387 (Binding.T * string option * mixfix) list * token list" in OuterParse} \\ |
384 @{ML "!!! : (token list -> 'a) -> token list -> 'a" in OuterParse} |
388 @{ML "!!! : (token list -> 'a) -> token list -> 'a" in OuterParse} |
385 \end{mytable} |
389 \end{table} |
|
390 |
386 The parsers @{ML "$$$" in OuterParse} and @{ML "!!!" in OuterParse} are |
391 The parsers @{ML "$$$" in OuterParse} and @{ML "!!!" in OuterParse} are |
387 defined using the parsers @{ML "one" in Scan} and @{ML "!!"} from |
392 defined using the parsers @{ML "one" in Scan} and @{ML "!!"} from |
388 @{ML_struct Scan}. |
393 @{ML_struct Scan}. |
389 The parser @{ML "enum1 s p" for s p in OuterParse} parses a non-emtpy list of items |
394 The parser @{ML "enum1 s p" for s p in OuterParse} parses a non-emtpy list of items |
390 recognized by the parser \texttt{p}, where the items are separated by \texttt{s}. |
395 recognized by the parser \texttt{p}, where the items are separated by \texttt{s}. |
398 The lists of names of the predicates and parameters, together with optional |
403 The lists of names of the predicates and parameters, together with optional |
399 types and syntax, are parsed using the functions @{ML "fixes" in OuterParse} |
404 types and syntax, are parsed using the functions @{ML "fixes" in OuterParse} |
400 and @{ML for_fixes in OuterParse}, respectively. |
405 and @{ML for_fixes in OuterParse}, respectively. |
401 In addition, the following function from @{ML_struct SpecParse} for parsing |
406 In addition, the following function from @{ML_struct SpecParse} for parsing |
402 an optional theorem name and attribute, followed by a delimiter, will be useful: |
407 an optional theorem name and attribute, followed by a delimiter, will be useful: |
403 \begin{mytable} |
408 |
|
409 \begin{table} |
404 @{ML "opt_thm_name: |
410 @{ML "opt_thm_name: |
405 string -> token list -> Attrib.binding * token list" in SpecParse} |
411 string -> token list -> Attrib.binding * token list" in SpecParse} |
406 \end{mytable} |
412 \end{table} |
|
413 |
407 We now have all the necessary tools to write the parser for our |
414 We now have all the necessary tools to write the parser for our |
408 \isa{\isacommand{simple{\isacharunderscore}inductive}} command: |
415 \isa{\isacommand{simple{\isacharunderscore}inductive}} command: |
409 @{ML_chunk [display] syntax} |
416 @{ML_chunk [display] syntax} |
410 The definition of the parser \verb!ind_decl! closely follows the railroad |
417 The definition of the parser \verb!ind_decl! closely follows the railroad |
411 diagram shown above. In order to make the code more readable, the structures |
418 diagram shown above. In order to make the code more readable, the structures |