src/Doc/Isar_Ref/Inner_Syntax.thy
changeset 61493 0debd22f0c0e
parent 61477 e467ae7aa808
child 61494 63b18f758874
equal deleted inserted replaced
61492:3480725c71d2 61493:0debd22f0c0e
     3 begin
     3 begin
     4 
     4 
     5 chapter \<open>Inner syntax --- the term language \label{ch:inner-syntax}\<close>
     5 chapter \<open>Inner syntax --- the term language \label{ch:inner-syntax}\<close>
     6 
     6 
     7 text \<open>The inner syntax of Isabelle provides concrete notation for
     7 text \<open>The inner syntax of Isabelle provides concrete notation for
     8   the main entities of the logical framework, notably @{text
     8   the main entities of the logical framework, notably \<open>\<lambda>\<close>-terms with types and type classes.  Applications may either
     9   "\<lambda>"}-terms with types and type classes.  Applications may either
       
    10   extend existing syntactic categories by additional notation, or
     9   extend existing syntactic categories by additional notation, or
    11   define new sub-languages that are linked to the standard term
    10   define new sub-languages that are linked to the standard term
    12   language via some explicit markers.  For example @{verbatim
    11   language via some explicit markers.  For example @{verbatim
    13   FOO}~@{text "foo"} could embed the syntax corresponding for some
    12   FOO}~\<open>foo\<close> could embed the syntax corresponding for some
    14   user-defined nonterminal @{text "foo"} --- within the bounds of the
    13   user-defined nonterminal \<open>foo\<close> --- within the bounds of the
    15   given lexical syntax of Isabelle/Pure.
    14   given lexical syntax of Isabelle/Pure.
    16 
    15 
    17   The most basic way to specify concrete syntax for logical entities
    16   The most basic way to specify concrete syntax for logical entities
    18   works via mixfix annotations (\secref{sec:mixfix}), which may be
    17   works via mixfix annotations (\secref{sec:mixfix}), which may be
    19   usually given as part of the original declaration or via explicit
    18   usually given as part of the original declaration or via explicit
    32 
    31 
    33 subsection \<open>Diagnostic commands \label{sec:print-diag}\<close>
    32 subsection \<open>Diagnostic commands \label{sec:print-diag}\<close>
    34 
    33 
    35 text \<open>
    34 text \<open>
    36   \begin{matharray}{rcl}
    35   \begin{matharray}{rcl}
    37     @{command_def "typ"}@{text "\<^sup>*"} & : & @{text "context \<rightarrow>"} \\
    36     @{command_def "typ"}\<open>\<^sup>*\<close> & : & \<open>context \<rightarrow>\<close> \\
    38     @{command_def "term"}@{text "\<^sup>*"} & : & @{text "context \<rightarrow>"} \\
    37     @{command_def "term"}\<open>\<^sup>*\<close> & : & \<open>context \<rightarrow>\<close> \\
    39     @{command_def "prop"}@{text "\<^sup>*"} & : & @{text "context \<rightarrow>"} \\
    38     @{command_def "prop"}\<open>\<^sup>*\<close> & : & \<open>context \<rightarrow>\<close> \\
    40     @{command_def "thm"}@{text "\<^sup>*"} & : & @{text "context \<rightarrow>"} \\
    39     @{command_def "thm"}\<open>\<^sup>*\<close> & : & \<open>context \<rightarrow>\<close> \\
    41     @{command_def "prf"}@{text "\<^sup>*"} & : & @{text "context \<rightarrow>"} \\
    40     @{command_def "prf"}\<open>\<^sup>*\<close> & : & \<open>context \<rightarrow>\<close> \\
    42     @{command_def "full_prf"}@{text "\<^sup>*"} & : & @{text "context \<rightarrow>"} \\
    41     @{command_def "full_prf"}\<open>\<^sup>*\<close> & : & \<open>context \<rightarrow>\<close> \\
    43     @{command_def "print_state"}@{text "\<^sup>*"} & : & @{text "any \<rightarrow>"} \\
    42     @{command_def "print_state"}\<open>\<^sup>*\<close> & : & \<open>any \<rightarrow>\<close> \\
    44   \end{matharray}
    43   \end{matharray}
    45 
    44 
    46   These diagnostic commands assist interactive development by printing
    45   These diagnostic commands assist interactive development by printing
    47   internal logical entities in a human-readable fashion.
    46   internal logical entities in a human-readable fashion.
    48 
    47 
    60     @@{command print_state} @{syntax modes}?
    59     @@{command print_state} @{syntax modes}?
    61     ;
    60     ;
    62     @{syntax_def modes}: '(' (@{syntax name} + ) ')'
    61     @{syntax_def modes}: '(' (@{syntax name} + ) ')'
    63   \<close>}
    62   \<close>}
    64 
    63 
    65   \<^descr> @{command "typ"}~@{text \<tau>} reads and prints a type expression
    64   \<^descr> @{command "typ"}~\<open>\<tau>\<close> reads and prints a type expression
    66   according to the current context.
    65   according to the current context.
    67 
    66 
    68   \<^descr> @{command "typ"}~@{text "\<tau> :: s"} uses type-inference to
    67   \<^descr> @{command "typ"}~\<open>\<tau> :: s\<close> uses type-inference to
    69   determine the most general way to make @{text "\<tau>"} conform to sort
    68   determine the most general way to make \<open>\<tau>\<close> conform to sort
    70   @{text "s"}.  For concrete @{text "\<tau>"} this checks if the type
    69   \<open>s\<close>.  For concrete \<open>\<tau>\<close> this checks if the type
    71   belongs to that sort.  Dummy type parameters ``@{text "_"}''
    70   belongs to that sort.  Dummy type parameters ``\<open>_\<close>''
    72   (underscore) are assigned to fresh type variables with most general
    71   (underscore) are assigned to fresh type variables with most general
    73   sorts, according the the principles of type-inference.
    72   sorts, according the the principles of type-inference.
    74 
    73 
    75   \<^descr> @{command "term"}~@{text t} and @{command "prop"}~@{text \<phi>}
    74   \<^descr> @{command "term"}~\<open>t\<close> and @{command "prop"}~\<open>\<phi>\<close>
    76   read, type-check and print terms or propositions according to the
    75   read, type-check and print terms or propositions according to the
    77   current theory or proof context; the inferred type of @{text t} is
    76   current theory or proof context; the inferred type of \<open>t\<close> is
    78   output as well.  Note that these commands are also useful in
    77   output as well.  Note that these commands are also useful in
    79   inspecting the current environment of term abbreviations.
    78   inspecting the current environment of term abbreviations.
    80 
    79 
    81   \<^descr> @{command "thm"}~@{text "a\<^sub>1 \<dots> a\<^sub>n"} retrieves
    80   \<^descr> @{command "thm"}~\<open>a\<^sub>1 \<dots> a\<^sub>n\<close> retrieves
    82   theorems from the current theory or proof context.  Note that any
    81   theorems from the current theory or proof context.  Note that any
    83   attributes included in the theorem specifications are applied to a
    82   attributes included in the theorem specifications are applied to a
    84   temporary context derived from the current theory or proof; the
    83   temporary context derived from the current theory or proof; the
    85   result is discarded, i.e.\ attributes involved in @{text "a\<^sub>1,
    84   result is discarded, i.e.\ attributes involved in \<open>a\<^sub>1,
    86   \<dots>, a\<^sub>n"} do not have any permanent effect.
    85   \<dots>, a\<^sub>n\<close> do not have any permanent effect.
    87 
    86 
    88   \<^descr> @{command "prf"} displays the (compact) proof term of the
    87   \<^descr> @{command "prf"} displays the (compact) proof term of the
    89   current proof state (if present), or of the given theorems. Note
    88   current proof state (if present), or of the given theorems. Note
    90   that this requires proof terms to be switched on for the current
    89   that this requires proof terms to be switched on for the current
    91   object logic (see the ``Proof terms'' section of the Isabelle
    90   object logic (see the ``Proof terms'' section of the Isabelle
    92   reference manual for information on how to do this).
    91   reference manual for information on how to do this).
    93 
    92 
    94   \<^descr> @{command "full_prf"} is like @{command "prf"}, but displays
    93   \<^descr> @{command "full_prf"} is like @{command "prf"}, but displays
    95   the full proof term, i.e.\ also displays information omitted in the
    94   the full proof term, i.e.\ also displays information omitted in the
    96   compact proof term, which is denoted by ``@{text _}'' placeholders
    95   compact proof term, which is denoted by ``\<open>_\<close>'' placeholders
    97   there.
    96   there.
    98 
    97 
    99   \<^descr> @{command "print_state"} prints the current proof state (if
    98   \<^descr> @{command "print_state"} prints the current proof state (if
   100   present), including current facts and goals.
    99   present), including current facts and goals.
   101 
   100 
   102 
   101 
   103   All of the diagnostic commands above admit a list of @{text modes}
   102   All of the diagnostic commands above admit a list of \<open>modes\<close>
   104   to be specified, which is appended to the current print mode; see
   103   to be specified, which is appended to the current print mode; see
   105   also \secref{sec:print-modes}.  Thus the output behavior may be
   104   also \secref{sec:print-modes}.  Thus the output behavior may be
   106   modified according particular print mode features.  For example,
   105   modified according particular print mode features.  For example,
   107   @{command "print_state"}~@{text "(latex xsymbols)"} prints the
   106   @{command "print_state"}~\<open>(latex xsymbols)\<close> prints the
   108   current proof state with mathematical symbols and special characters
   107   current proof state with mathematical symbols and special characters
   109   represented in {\LaTeX} source, according to the Isabelle style
   108   represented in {\LaTeX} source, according to the Isabelle style
   110   @{cite "isabelle-system"}.
   109   @{cite "isabelle-system"}.
   111 
   110 
   112   Note that antiquotations (cf.\ \secref{sec:antiq}) provide a more
   111   Note that antiquotations (cf.\ \secref{sec:antiq}) provide a more
   117 
   116 
   118 subsection \<open>Details of printed content\<close>
   117 subsection \<open>Details of printed content\<close>
   119 
   118 
   120 text \<open>
   119 text \<open>
   121   \begin{tabular}{rcll}
   120   \begin{tabular}{rcll}
   122     @{attribute_def show_markup} & : & @{text attribute} \\
   121     @{attribute_def show_markup} & : & \<open>attribute\<close> \\
   123     @{attribute_def show_types} & : & @{text attribute} & default @{text false} \\
   122     @{attribute_def show_types} & : & \<open>attribute\<close> & default \<open>false\<close> \\
   124     @{attribute_def show_sorts} & : & @{text attribute} & default @{text false} \\
   123     @{attribute_def show_sorts} & : & \<open>attribute\<close> & default \<open>false\<close> \\
   125     @{attribute_def show_consts} & : & @{text attribute} & default @{text false} \\
   124     @{attribute_def show_consts} & : & \<open>attribute\<close> & default \<open>false\<close> \\
   126     @{attribute_def show_abbrevs} & : & @{text attribute} & default @{text true} \\
   125     @{attribute_def show_abbrevs} & : & \<open>attribute\<close> & default \<open>true\<close> \\
   127     @{attribute_def show_brackets} & : & @{text attribute} & default @{text false} \\
   126     @{attribute_def show_brackets} & : & \<open>attribute\<close> & default \<open>false\<close> \\
   128     @{attribute_def names_long} & : & @{text attribute} & default @{text false} \\
   127     @{attribute_def names_long} & : & \<open>attribute\<close> & default \<open>false\<close> \\
   129     @{attribute_def names_short} & : & @{text attribute} & default @{text false} \\
   128     @{attribute_def names_short} & : & \<open>attribute\<close> & default \<open>false\<close> \\
   130     @{attribute_def names_unique} & : & @{text attribute} & default @{text true} \\
   129     @{attribute_def names_unique} & : & \<open>attribute\<close> & default \<open>true\<close> \\
   131     @{attribute_def eta_contract} & : & @{text attribute} & default @{text true} \\
   130     @{attribute_def eta_contract} & : & \<open>attribute\<close> & default \<open>true\<close> \\
   132     @{attribute_def goals_limit} & : & @{text attribute} & default @{text 10} \\
   131     @{attribute_def goals_limit} & : & \<open>attribute\<close> & default \<open>10\<close> \\
   133     @{attribute_def show_main_goal} & : & @{text attribute} & default @{text false} \\
   132     @{attribute_def show_main_goal} & : & \<open>attribute\<close> & default \<open>false\<close> \\
   134     @{attribute_def show_hyps} & : & @{text attribute} & default @{text false} \\
   133     @{attribute_def show_hyps} & : & \<open>attribute\<close> & default \<open>false\<close> \\
   135     @{attribute_def show_tags} & : & @{text attribute} & default @{text false} \\
   134     @{attribute_def show_tags} & : & \<open>attribute\<close> & default \<open>false\<close> \\
   136     @{attribute_def show_question_marks} & : & @{text attribute} & default @{text true} \\
   135     @{attribute_def show_question_marks} & : & \<open>attribute\<close> & default \<open>true\<close> \\
   137   \end{tabular}
   136   \end{tabular}
   138   \<^medskip>
   137   \<^medskip>
   139 
   138 
   140   These configuration options control the detail of information that
   139   These configuration options control the detail of information that
   141   is displayed for types, terms, theorems, goals etc.  See also
   140   is displayed for types, terms, theorems, goals etc.  See also
   180   @{attribute names_unique} control the way of printing fully
   179   @{attribute names_unique} control the way of printing fully
   181   qualified internal names in external form.  See also
   180   qualified internal names in external form.  See also
   182   \secref{sec:antiq} for the document antiquotation options of the
   181   \secref{sec:antiq} for the document antiquotation options of the
   183   same names.
   182   same names.
   184 
   183 
   185   \<^descr> @{attribute eta_contract} controls @{text "\<eta>"}-contracted
   184   \<^descr> @{attribute eta_contract} controls \<open>\<eta>\<close>-contracted
   186   printing of terms.
   185   printing of terms.
   187 
   186 
   188   The @{text \<eta>}-contraction law asserts @{prop "(\<lambda>x. f x) \<equiv> f"},
   187   The \<open>\<eta>\<close>-contraction law asserts @{prop "(\<lambda>x. f x) \<equiv> f"},
   189   provided @{text x} is not free in @{text f}.  It asserts
   188   provided \<open>x\<close> is not free in \<open>f\<close>.  It asserts
   190   \<^emph>\<open>extensionality\<close> of functions: @{prop "f \<equiv> g"} if @{prop "f x \<equiv>
   189   \<^emph>\<open>extensionality\<close> of functions: @{prop "f \<equiv> g"} if @{prop "f x \<equiv>
   191   g x"} for all @{text x}.  Higher-order unification frequently puts
   190   g x"} for all \<open>x\<close>.  Higher-order unification frequently puts
   192   terms into a fully @{text \<eta>}-expanded form.  For example, if @{text
   191   terms into a fully \<open>\<eta>\<close>-expanded form.  For example, if \<open>F\<close> has type \<open>(\<tau> \<Rightarrow> \<tau>) \<Rightarrow> \<tau>\<close> then its expanded form is @{term
   193   F} has type @{text "(\<tau> \<Rightarrow> \<tau>) \<Rightarrow> \<tau>"} then its expanded form is @{term
       
   194   "\<lambda>h. F (\<lambda>x. h x)"}.
   192   "\<lambda>h. F (\<lambda>x. h x)"}.
   195 
   193 
   196   Enabling @{attribute eta_contract} makes Isabelle perform @{text
   194   Enabling @{attribute eta_contract} makes Isabelle perform \<open>\<eta>\<close>-contractions before printing, so that @{term "\<lambda>h. F (\<lambda>x. h x)"}
   197   \<eta>}-contractions before printing, so that @{term "\<lambda>h. F (\<lambda>x. h x)"}
   195   appears simply as \<open>F\<close>.
   198   appears simply as @{text F}.
   196 
   199 
   197   Note that the distinction between a term and its \<open>\<eta>\<close>-expanded
   200   Note that the distinction between a term and its @{text \<eta>}-expanded
       
   201   form occasionally matters.  While higher-order resolution and
   198   form occasionally matters.  While higher-order resolution and
   202   rewriting operate modulo @{text "\<alpha>\<beta>\<eta>"}-conversion, some other tools
   199   rewriting operate modulo \<open>\<alpha>\<beta>\<eta>\<close>-conversion, some other tools
   203   might look at terms more discretely.
   200   might look at terms more discretely.
   204 
   201 
   205   \<^descr> @{attribute goals_limit} controls the maximum number of
   202   \<^descr> @{attribute goals_limit} controls the maximum number of
   206   subgoals to be printed.
   203   subgoals to be printed.
   207 
   204 
   227   Note that the @{attribute tagged} and @{attribute untagged}
   224   Note that the @{attribute tagged} and @{attribute untagged}
   228   attributes provide low-level access to the collection of tags
   225   attributes provide low-level access to the collection of tags
   229   associated with a theorem.
   226   associated with a theorem.
   230 
   227 
   231   \<^descr> @{attribute show_question_marks} controls printing of question
   228   \<^descr> @{attribute show_question_marks} controls printing of question
   232   marks for schematic variables, such as @{text ?x}.  Only the leading
   229   marks for schematic variables, such as \<open>?x\<close>.  Only the leading
   233   question mark is affected, the remaining text is unchanged
   230   question mark is affected, the remaining text is unchanged
   234   (including proper markup for schematic variables that might be
   231   (including proper markup for schematic variables that might be
   235   relevant for user interfaces).
   232   relevant for user interfaces).
   236 \<close>
   233 \<close>
   237 
   234 
   253   \<^descr> @{ML "print_mode_value ()"} yields the list of currently
   250   \<^descr> @{ML "print_mode_value ()"} yields the list of currently
   254   active print mode names.  This should be understood as symbolic
   251   active print mode names.  This should be understood as symbolic
   255   representation of certain individual features for printing (with
   252   representation of certain individual features for printing (with
   256   precedence from left to right).
   253   precedence from left to right).
   257 
   254 
   258   \<^descr> @{ML Print_Mode.with_modes}~@{text "modes f x"} evaluates
   255   \<^descr> @{ML Print_Mode.with_modes}~\<open>modes f x\<close> evaluates
   259   @{text "f x"} in an execution context where the print mode is
   256   \<open>f x\<close> in an execution context where the print mode is
   260   prepended by the given @{text "modes"}.  This provides a thread-safe
   257   prepended by the given \<open>modes\<close>.  This provides a thread-safe
   261   way to augment print modes.  It is also monotonic in the set of mode
   258   way to augment print modes.  It is also monotonic in the set of mode
   262   names: it retains the default print mode that certain
   259   names: it retains the default print mode that certain
   263   user-interfaces might have installed for their proper functioning!
   260   user-interfaces might have installed for their proper functioning!
   264 
   261 
   265 
   262 
   317     template: string
   314     template: string
   318     ;
   315     ;
   319     prios: '[' (@{syntax nat} + ',') ']'
   316     prios: '[' (@{syntax nat} + ',') ']'
   320   \<close>}
   317   \<close>}
   321 
   318 
   322   The string given as @{text template} may include literal text,
   319   The string given as \<open>template\<close> may include literal text,
   323   spacing, blocks, and arguments (denoted by ``@{text _}''); the
   320   spacing, blocks, and arguments (denoted by ``\<open>_\<close>''); the
   324   special symbol ``@{verbatim "\<index>"}'' (printed as ``@{text "\<index>"}'')
   321   special symbol ``@{verbatim "\<index>"}'' (printed as ``\<open>\<index>\<close>'')
   325   represents an index argument that specifies an implicit @{keyword
   322   represents an index argument that specifies an implicit @{keyword
   326   "structure"} reference (see also \secref{sec:locale}).  Only locally
   323   "structure"} reference (see also \secref{sec:locale}).  Only locally
   327   fixed variables may be declared as @{keyword "structure"}.
   324   fixed variables may be declared as @{keyword "structure"}.
   328 
   325 
   329   Infix and binder declarations provide common abbreviations for
   326   Infix and binder declarations provide common abbreviations for
   333 
   330 
   334 
   331 
   335 subsection \<open>The general mixfix form\<close>
   332 subsection \<open>The general mixfix form\<close>
   336 
   333 
   337 text \<open>In full generality, mixfix declarations work as follows.
   334 text \<open>In full generality, mixfix declarations work as follows.
   338   Suppose a constant @{text "c :: \<tau>\<^sub>1 \<Rightarrow> \<dots> \<tau>\<^sub>n \<Rightarrow> \<tau>"} is annotated by
   335   Suppose a constant \<open>c :: \<tau>\<^sub>1 \<Rightarrow> \<dots> \<tau>\<^sub>n \<Rightarrow> \<tau>\<close> is annotated by
   339   @{text "(mixfix [p\<^sub>1, \<dots>, p\<^sub>n] p)"}, where @{text "mixfix"} is a string
   336   \<open>(mixfix [p\<^sub>1, \<dots>, p\<^sub>n] p)\<close>, where \<open>mixfix\<close> is a string
   340   @{text "d\<^sub>0 _ d\<^sub>1 _ \<dots> _ d\<^sub>n"} consisting of delimiters that surround
   337   \<open>d\<^sub>0 _ d\<^sub>1 _ \<dots> _ d\<^sub>n\<close> consisting of delimiters that surround
   341   argument positions as indicated by underscores.
   338   argument positions as indicated by underscores.
   342 
   339 
   343   Altogether this determines a production for a context-free priority
   340   Altogether this determines a production for a context-free priority
   344   grammar, where for each argument @{text "i"} the syntactic category
   341   grammar, where for each argument \<open>i\<close> the syntactic category
   345   is determined by @{text "\<tau>\<^sub>i"} (with priority @{text "p\<^sub>i"}), and the
   342   is determined by \<open>\<tau>\<^sub>i\<close> (with priority \<open>p\<^sub>i\<close>), and the
   346   result category is determined from @{text "\<tau>"} (with priority @{text
   343   result category is determined from \<open>\<tau>\<close> (with priority \<open>p\<close>).  Priority specifications are optional, with default 0 for
   347   "p"}).  Priority specifications are optional, with default 0 for
       
   348   arguments and 1000 for the result.\footnote{Omitting priorities is
   344   arguments and 1000 for the result.\footnote{Omitting priorities is
   349   prone to syntactic ambiguities unless the delimiter tokens determine
   345   prone to syntactic ambiguities unless the delimiter tokens determine
   350   fully bracketed notation, as in @{text "if _ then _ else _ fi"}.}
   346   fully bracketed notation, as in \<open>if _ then _ else _ fi\<close>.}
   351 
   347 
   352   Since @{text "\<tau>"} may be again a function type, the constant
   348   Since \<open>\<tau>\<close> may be again a function type, the constant
   353   type scheme may have more argument positions than the mixfix
   349   type scheme may have more argument positions than the mixfix
   354   pattern.  Printing a nested application @{text "c t\<^sub>1 \<dots> t\<^sub>m"} for
   350   pattern.  Printing a nested application \<open>c t\<^sub>1 \<dots> t\<^sub>m\<close> for
   355   @{text "m > n"} works by attaching concrete notation only to the
   351   \<open>m > n\<close> works by attaching concrete notation only to the
   356   innermost part, essentially by printing @{text "(c t\<^sub>1 \<dots> t\<^sub>n) \<dots> t\<^sub>m"}
   352   innermost part, essentially by printing \<open>(c t\<^sub>1 \<dots> t\<^sub>n) \<dots> t\<^sub>m\<close>
   357   instead.  If a term has fewer arguments than specified in the mixfix
   353   instead.  If a term has fewer arguments than specified in the mixfix
   358   template, the concrete syntax is ignored.
   354   template, the concrete syntax is ignored.
   359 
   355 
   360   \<^medskip>
   356   \<^medskip>
   361   A mixfix template may also contain additional directives
   357   A mixfix template may also contain additional directives
   362   for pretty printing, notably spaces, blocks, and breaks.  The
   358   for pretty printing, notably spaces, blocks, and breaks.  The
   363   general template format is a sequence over any of the following
   359   general template format is a sequence over any of the following
   364   entities.
   360   entities.
   365 
   361 
   366   \<^descr> @{text "d"} is a delimiter, namely a non-empty sequence of
   362   \<^descr> \<open>d\<close> is a delimiter, namely a non-empty sequence of
   367   characters other than the following special characters:
   363   characters other than the following special characters:
   368 
   364 
   369   \<^medskip>
   365   \<^medskip>
   370   \begin{tabular}{ll}
   366   \begin{tabular}{ll}
   371     @{verbatim "'"} & single quote \\
   367     @{verbatim "'"} & single quote \\
   372     @{verbatim "_"} & underscore \\
   368     @{verbatim "_"} & underscore \\
   373     @{text "\<index>"} & index symbol \\
   369     \<open>\<index>\<close> & index symbol \\
   374     @{verbatim "("} & open parenthesis \\
   370     @{verbatim "("} & open parenthesis \\
   375     @{verbatim ")"} & close parenthesis \\
   371     @{verbatim ")"} & close parenthesis \\
   376     @{verbatim "/"} & slash \\
   372     @{verbatim "/"} & slash \\
   377   \end{tabular}
   373   \end{tabular}
   378   \<^medskip>
   374   \<^medskip>
   386   here.
   382   here.
   387 
   383 
   388   \<^descr> @{verbatim "_"} is an argument position, which stands for a
   384   \<^descr> @{verbatim "_"} is an argument position, which stands for a
   389   certain syntactic category in the underlying grammar.
   385   certain syntactic category in the underlying grammar.
   390 
   386 
   391   \<^descr> @{text "\<index>"} is an indexed argument position; this is the place
   387   \<^descr> \<open>\<index>\<close> is an indexed argument position; this is the place
   392   where implicit structure arguments can be attached.
   388   where implicit structure arguments can be attached.
   393 
   389 
   394   \<^descr> @{text "s"} is a non-empty sequence of spaces for printing.
   390   \<^descr> \<open>s\<close> is a non-empty sequence of spaces for printing.
   395   This and the following specifications do not affect parsing at all.
   391   This and the following specifications do not affect parsing at all.
   396 
   392 
   397   \<^descr> @{verbatim "("}@{text n} opens a pretty printing block.  The
   393   \<^descr> @{verbatim "("}\<open>n\<close> opens a pretty printing block.  The
   398   optional number specifies how much indentation to add when a line
   394   optional number specifies how much indentation to add when a line
   399   break occurs within the block.  If the parenthesis is not followed
   395   break occurs within the block.  If the parenthesis is not followed
   400   by digits, the indentation defaults to 0.  A block specified via
   396   by digits, the indentation defaults to 0.  A block specified via
   401   @{verbatim "(00"} is unbreakable.
   397   @{verbatim "(00"} is unbreakable.
   402 
   398 
   403   \<^descr> @{verbatim ")"} closes a pretty printing block.
   399   \<^descr> @{verbatim ")"} closes a pretty printing block.
   404 
   400 
   405   \<^descr> @{verbatim "//"} forces a line break.
   401   \<^descr> @{verbatim "//"} forces a line break.
   406 
   402 
   407   \<^descr> @{verbatim "/"}@{text s} allows a line break.  Here @{text s}
   403   \<^descr> @{verbatim "/"}\<open>s\<close> allows a line break.  Here \<open>s\<close>
   408   stands for the string of spaces (zero or more) right after the
   404   stands for the string of spaces (zero or more) right after the
   409   slash.  These spaces are printed if the break is \<^emph>\<open>not\<close> taken.
   405   slash.  These spaces are printed if the break is \<^emph>\<open>not\<close> taken.
   410 
   406 
   411 
   407 
   412   The general idea of pretty printing with blocks and breaks is also
   408   The general idea of pretty printing with blocks and breaks is also
   420   abbreviate general mixfix annotations as follows:
   416   abbreviate general mixfix annotations as follows:
   421 
   417 
   422   \begin{center}
   418   \begin{center}
   423   \begin{tabular}{lll}
   419   \begin{tabular}{lll}
   424 
   420 
   425   @{verbatim "("}@{keyword_def "infix"}~@{verbatim \<open>"\<close>}@{text sy}@{verbatim \<open>"\<close>} @{text "p"}@{verbatim ")"}
   421   @{verbatim "("}@{keyword_def "infix"}~@{verbatim \<open>"\<close>}\<open>sy\<close>@{verbatim \<open>"\<close>} \<open>p\<close>@{verbatim ")"}
   426   & @{text "\<mapsto>"} &
   422   & \<open>\<mapsto>\<close> &
   427   @{verbatim \<open>("(_\<close>}~@{text sy}@{verbatim \<open>/ _)" [\<close>}@{text "p + 1"}@{verbatim ","}~@{text "p + 1"}@{verbatim "]"}~@{text "p"}@{verbatim ")"} \\
   423   @{verbatim \<open>("(_\<close>}~\<open>sy\<close>@{verbatim \<open>/ _)" [\<close>}\<open>p + 1\<close>@{verbatim ","}~\<open>p + 1\<close>@{verbatim "]"}~\<open>p\<close>@{verbatim ")"} \\
   428   @{verbatim "("}@{keyword_def "infixl"}~@{verbatim \<open>"\<close>}@{text sy}@{verbatim \<open>"\<close>} @{text "p"}@{verbatim ")"}
   424   @{verbatim "("}@{keyword_def "infixl"}~@{verbatim \<open>"\<close>}\<open>sy\<close>@{verbatim \<open>"\<close>} \<open>p\<close>@{verbatim ")"}
   429   & @{text "\<mapsto>"} &
   425   & \<open>\<mapsto>\<close> &
   430   @{verbatim \<open>("(_\<close>}~@{text sy}@{verbatim \<open>/ _)" [\<close>}@{text "p"}@{verbatim ","}~@{text "p + 1"}@{verbatim "]"}~@{text "p"}@{verbatim ")"} \\
   426   @{verbatim \<open>("(_\<close>}~\<open>sy\<close>@{verbatim \<open>/ _)" [\<close>}\<open>p\<close>@{verbatim ","}~\<open>p + 1\<close>@{verbatim "]"}~\<open>p\<close>@{verbatim ")"} \\
   431   @{verbatim "("}@{keyword_def "infixr"}~@{verbatim \<open>"\<close>}@{text sy}@{verbatim \<open>"\<close>}~@{text "p"}@{verbatim ")"}
   427   @{verbatim "("}@{keyword_def "infixr"}~@{verbatim \<open>"\<close>}\<open>sy\<close>@{verbatim \<open>"\<close>}~\<open>p\<close>@{verbatim ")"}
   432   & @{text "\<mapsto>"} &
   428   & \<open>\<mapsto>\<close> &
   433   @{verbatim \<open>("(_\<close>}~@{text sy}@{verbatim \<open>/ _)" [\<close>}@{text "p + 1"}@{verbatim ","}~@{text "p"}@{verbatim "]"}~@{text "p"}@{verbatim ")"} \\
   429   @{verbatim \<open>("(_\<close>}~\<open>sy\<close>@{verbatim \<open>/ _)" [\<close>}\<open>p + 1\<close>@{verbatim ","}~\<open>p\<close>@{verbatim "]"}~\<open>p\<close>@{verbatim ")"} \\
   434 
   430 
   435   \end{tabular}
   431   \end{tabular}
   436   \end{center}
   432   \end{center}
   437 
   433 
   438   The mixfix template @{verbatim \<open>"(_\<close>}~@{text sy}@{verbatim \<open>/ _)"\<close>}
   434   The mixfix template @{verbatim \<open>"(_\<close>}~\<open>sy\<close>@{verbatim \<open>/ _)"\<close>}
   439   specifies two argument positions; the delimiter is preceded by a
   435   specifies two argument positions; the delimiter is preceded by a
   440   space and followed by a space or line break; the entire phrase is a
   436   space and followed by a space or line break; the entire phrase is a
   441   pretty printing block.
   437   pretty printing block.
   442 
   438 
   443   The alternative notation @{verbatim "op"}~@{text sy} is introduced
   439   The alternative notation @{verbatim "op"}~\<open>sy\<close> is introduced
   444   in addition.  Thus any infix operator may be written in prefix form
   440   in addition.  Thus any infix operator may be written in prefix form
   445   (as in ML), independently of the number of arguments in the term.
   441   (as in ML), independently of the number of arguments in the term.
   446 \<close>
   442 \<close>
   447 
   443 
   448 
   444 
   449 subsection \<open>Binders\<close>
   445 subsection \<open>Binders\<close>
   450 
   446 
   451 text \<open>A \<^emph>\<open>binder\<close> is a variable-binding construct such as a
   447 text \<open>A \<^emph>\<open>binder\<close> is a variable-binding construct such as a
   452   quantifier.  The idea to formalize @{text "\<forall>x. b"} as @{text "All
   448   quantifier.  The idea to formalize \<open>\<forall>x. b\<close> as \<open>All
   453   (\<lambda>x. b)"} for @{text "All :: ('a \<Rightarrow> bool) \<Rightarrow> bool"} already goes back
   449   (\<lambda>x. b)\<close> for \<open>All :: ('a \<Rightarrow> bool) \<Rightarrow> bool\<close> already goes back
   454   to @{cite church40}.  Isabelle declarations of certain higher-order
   450   to @{cite church40}.  Isabelle declarations of certain higher-order
   455   operators may be annotated with @{keyword_def "binder"} annotations
   451   operators may be annotated with @{keyword_def "binder"} annotations
   456   as follows:
   452   as follows:
   457 
   453 
   458   \begin{center}
   454   \begin{center}
   459   @{text "c :: "}@{verbatim \<open>"\<close>}@{text "(\<tau>\<^sub>1 \<Rightarrow> \<tau>\<^sub>2) \<Rightarrow> \<tau>\<^sub>3"}@{verbatim \<open>"  (\<close>}@{keyword "binder"}~@{verbatim \<open>"\<close>}@{text "sy"}@{verbatim \<open>" [\<close>}@{text "p"}@{verbatim "]"}~@{text "q"}@{verbatim ")"}
   455   \<open>c :: \<close>@{verbatim \<open>"\<close>}\<open>(\<tau>\<^sub>1 \<Rightarrow> \<tau>\<^sub>2) \<Rightarrow> \<tau>\<^sub>3\<close>@{verbatim \<open>"  (\<close>}@{keyword "binder"}~@{verbatim \<open>"\<close>}\<open>sy\<close>@{verbatim \<open>" [\<close>}\<open>p\<close>@{verbatim "]"}~\<open>q\<close>@{verbatim ")"}
   460   \end{center}
   456   \end{center}
   461 
   457 
   462   This introduces concrete binder syntax @{text "sy x. b"}, where
   458   This introduces concrete binder syntax \<open>sy x. b\<close>, where
   463   @{text x} is a bound variable of type @{text "\<tau>\<^sub>1"}, the body @{text
   459   \<open>x\<close> is a bound variable of type \<open>\<tau>\<^sub>1\<close>, the body \<open>b\<close> has type \<open>\<tau>\<^sub>2\<close> and the whole term has type \<open>\<tau>\<^sub>3\<close>.
   464   b} has type @{text "\<tau>\<^sub>2"} and the whole term has type @{text "\<tau>\<^sub>3"}.
   460   The optional integer \<open>p\<close> specifies the syntactic priority of
   465   The optional integer @{text p} specifies the syntactic priority of
   461   the body; the default is \<open>q\<close>, which is also the priority of
   466   the body; the default is @{text "q"}, which is also the priority of
       
   467   the whole construct.
   462   the whole construct.
   468 
   463 
   469   Internally, the binder syntax is expanded to something like this:
   464   Internally, the binder syntax is expanded to something like this:
   470   \begin{center}
   465   \begin{center}
   471   @{text "c_binder :: "}@{verbatim \<open>"\<close>}@{text "idts \<Rightarrow> \<tau>\<^sub>2 \<Rightarrow> \<tau>\<^sub>3"}@{verbatim \<open>"  ("(3\<close>}@{text sy}@{verbatim \<open>_./ _)" [0,\<close>}~@{text "p"}@{verbatim "]"}~@{text "q"}@{verbatim ")"}
   466   \<open>c_binder :: \<close>@{verbatim \<open>"\<close>}\<open>idts \<Rightarrow> \<tau>\<^sub>2 \<Rightarrow> \<tau>\<^sub>3\<close>@{verbatim \<open>"  ("(3\<close>}\<open>sy\<close>@{verbatim \<open>_./ _)" [0,\<close>}~\<open>p\<close>@{verbatim "]"}~\<open>q\<close>@{verbatim ")"}
   472   \end{center}
   467   \end{center}
   473 
   468 
   474   Here @{syntax (inner) idts} is the nonterminal symbol for a list of
   469   Here @{syntax (inner) idts} is the nonterminal symbol for a list of
   475   identifiers with optional type constraints (see also
   470   identifiers with optional type constraints (see also
   476   \secref{sec:pure-grammar}).  The mixfix template @{verbatim
   471   \secref{sec:pure-grammar}).  The mixfix template @{verbatim
   477   \<open>"(3\<close>}@{text sy}@{verbatim \<open>_./ _)"\<close>} defines argument positions
   472   \<open>"(3\<close>}\<open>sy\<close>@{verbatim \<open>_./ _)"\<close>} defines argument positions
   478   for the bound identifiers and the body, separated by a dot with
   473   for the bound identifiers and the body, separated by a dot with
   479   optional line break; the entire phrase is a pretty printing block of
   474   optional line break; the entire phrase is a pretty printing block of
   480   indentation level 3.  Note that there is no extra space after @{text
   475   indentation level 3.  Note that there is no extra space after \<open>sy\<close>, so it needs to be included user specification if the binder
   481   "sy"}, so it needs to be included user specification if the binder
       
   482   syntax ends with a token that may be continued by an identifier
   476   syntax ends with a token that may be continued by an identifier
   483   token at the start of @{syntax (inner) idts}.
   477   token at the start of @{syntax (inner) idts}.
   484 
   478 
   485   Furthermore, a syntax translation to transforms @{text "c_binder x\<^sub>1
   479   Furthermore, a syntax translation to transforms \<open>c_binder x\<^sub>1
   486   \<dots> x\<^sub>n b"} into iterated application @{text "c (\<lambda>x\<^sub>1. \<dots> c (\<lambda>x\<^sub>n. b)\<dots>)"}.
   480   \<dots> x\<^sub>n b\<close> into iterated application \<open>c (\<lambda>x\<^sub>1. \<dots> c (\<lambda>x\<^sub>n. b)\<dots>)\<close>.
   487   This works in both directions, for parsing and printing.\<close>
   481   This works in both directions, for parsing and printing.\<close>
   488 
   482 
   489 
   483 
   490 section \<open>Explicit notation \label{sec:notation}\<close>
   484 section \<open>Explicit notation \label{sec:notation}\<close>
   491 
   485 
   492 text \<open>
   486 text \<open>
   493   \begin{matharray}{rcll}
   487   \begin{matharray}{rcll}
   494     @{command_def "type_notation"} & : & @{text "local_theory \<rightarrow> local_theory"} \\
   488     @{command_def "type_notation"} & : & \<open>local_theory \<rightarrow> local_theory\<close> \\
   495     @{command_def "no_type_notation"} & : & @{text "local_theory \<rightarrow> local_theory"} \\
   489     @{command_def "no_type_notation"} & : & \<open>local_theory \<rightarrow> local_theory\<close> \\
   496     @{command_def "notation"} & : & @{text "local_theory \<rightarrow> local_theory"} \\
   490     @{command_def "notation"} & : & \<open>local_theory \<rightarrow> local_theory\<close> \\
   497     @{command_def "no_notation"} & : & @{text "local_theory \<rightarrow> local_theory"} \\
   491     @{command_def "no_notation"} & : & \<open>local_theory \<rightarrow> local_theory\<close> \\
   498     @{command_def "write"} & : & @{text "proof(state) \<rightarrow> proof(state)"} \\
   492     @{command_def "write"} & : & \<open>proof(state) \<rightarrow> proof(state)\<close> \\
   499   \end{matharray}
   493   \end{matharray}
   500 
   494 
   501   Commands that introduce new logical entities (terms or types)
   495   Commands that introduce new logical entities (terms or types)
   502   usually allow to provide mixfix annotations on the spot, which is
   496   usually allow to provide mixfix annotations on the spot, which is
   503   convenient for default notation.  Nonetheless, the syntax may be
   497   convenient for default notation.  Nonetheless, the syntax may be
   513       (@{syntax nameref} @{syntax mixfix} + @'and')
   507       (@{syntax nameref} @{syntax mixfix} + @'and')
   514     ;
   508     ;
   515     @@{command write} @{syntax mode}? (@{syntax nameref} @{syntax mixfix} + @'and')
   509     @@{command write} @{syntax mode}? (@{syntax nameref} @{syntax mixfix} + @'and')
   516   \<close>}
   510   \<close>}
   517 
   511 
   518   \<^descr> @{command "type_notation"}~@{text "c (mx)"} associates mixfix
   512   \<^descr> @{command "type_notation"}~\<open>c (mx)\<close> associates mixfix
   519   syntax with an existing type constructor.  The arity of the
   513   syntax with an existing type constructor.  The arity of the
   520   constructor is retrieved from the context.
   514   constructor is retrieved from the context.
   521 
   515 
   522   \<^descr> @{command "no_type_notation"} is similar to @{command
   516   \<^descr> @{command "no_type_notation"} is similar to @{command
   523   "type_notation"}, but removes the specified syntax annotation from
   517   "type_notation"}, but removes the specified syntax annotation from
   524   the present context.
   518   the present context.
   525 
   519 
   526   \<^descr> @{command "notation"}~@{text "c (mx)"} associates mixfix
   520   \<^descr> @{command "notation"}~\<open>c (mx)\<close> associates mixfix
   527   syntax with an existing constant or fixed variable.  The type
   521   syntax with an existing constant or fixed variable.  The type
   528   declaration of the given entity is retrieved from the context.
   522   declaration of the given entity is retrieved from the context.
   529 
   523 
   530   \<^descr> @{command "no_notation"} is similar to @{command "notation"},
   524   \<^descr> @{command "no_notation"} is similar to @{command "notation"},
   531   but removes the specified syntax annotation from the present
   525   but removes the specified syntax annotation from the present
   568     @{syntax_def (inner) var} & = & @{syntax_ref var} \\
   562     @{syntax_def (inner) var} & = & @{syntax_ref var} \\
   569     @{syntax_def (inner) tid} & = & @{syntax_ref typefree} \\
   563     @{syntax_def (inner) tid} & = & @{syntax_ref typefree} \\
   570     @{syntax_def (inner) tvar} & = & @{syntax_ref typevar} \\
   564     @{syntax_def (inner) tvar} & = & @{syntax_ref typevar} \\
   571     @{syntax_def (inner) num_token} & = & @{syntax_ref nat} \\
   565     @{syntax_def (inner) num_token} & = & @{syntax_ref nat} \\
   572     @{syntax_def (inner) float_token} & = & @{syntax_ref nat}@{verbatim "."}@{syntax_ref nat} \\
   566     @{syntax_def (inner) float_token} & = & @{syntax_ref nat}@{verbatim "."}@{syntax_ref nat} \\
   573     @{syntax_def (inner) str_token} & = & @{verbatim "''"} @{text "\<dots>"} @{verbatim "''"} \\
   567     @{syntax_def (inner) str_token} & = & @{verbatim "''"} \<open>\<dots>\<close> @{verbatim "''"} \\
   574     @{syntax_def (inner) string_token} & = & @{verbatim \<open>"\<close>} @{text "\<dots>"} @{verbatim \<open>"\<close>} \\
   568     @{syntax_def (inner) string_token} & = & @{verbatim \<open>"\<close>} \<open>\<dots>\<close> @{verbatim \<open>"\<close>} \\
   575     @{syntax_def (inner) cartouche} & = & @{verbatim "\<open>"} @{text "\<dots>"} @{verbatim "\<close>"} \\
   569     @{syntax_def (inner) cartouche} & = & @{verbatim "\<open>"} \<open>\<dots>\<close> @{verbatim "\<close>"} \\
   576   \end{supertabular}
   570   \end{supertabular}
   577   \end{center}
   571   \end{center}
   578 
   572 
   579   The token categories @{syntax (inner) num_token}, @{syntax (inner)
   573   The token categories @{syntax (inner) num_token}, @{syntax (inner)
   580   float_token}, @{syntax (inner) str_token}, @{syntax (inner) string_token},
   574   float_token}, @{syntax (inner) str_token}, @{syntax (inner) string_token},
   591 
   585 
   592 subsection \<open>Priority grammars \label{sec:priority-grammar}\<close>
   586 subsection \<open>Priority grammars \label{sec:priority-grammar}\<close>
   593 
   587 
   594 text \<open>A context-free grammar consists of a set of \<^emph>\<open>terminal
   588 text \<open>A context-free grammar consists of a set of \<^emph>\<open>terminal
   595   symbols\<close>, a set of \<^emph>\<open>nonterminal symbols\<close> and a set of
   589   symbols\<close>, a set of \<^emph>\<open>nonterminal symbols\<close> and a set of
   596   \<^emph>\<open>productions\<close>.  Productions have the form @{text "A = \<gamma>"},
   590   \<^emph>\<open>productions\<close>.  Productions have the form \<open>A = \<gamma>\<close>,
   597   where @{text A} is a nonterminal and @{text \<gamma>} is a string of
   591   where \<open>A\<close> is a nonterminal and \<open>\<gamma>\<close> is a string of
   598   terminals and nonterminals.  One designated nonterminal is called
   592   terminals and nonterminals.  One designated nonterminal is called
   599   the \<^emph>\<open>root symbol\<close>.  The language defined by the grammar
   593   the \<^emph>\<open>root symbol\<close>.  The language defined by the grammar
   600   consists of all strings of terminals that can be derived from the
   594   consists of all strings of terminals that can be derived from the
   601   root symbol by applying productions as rewrite rules.
   595   root symbol by applying productions as rewrite rules.
   602 
   596 
   603   The standard Isabelle parser for inner syntax uses a \<^emph>\<open>priority
   597   The standard Isabelle parser for inner syntax uses a \<^emph>\<open>priority
   604   grammar\<close>.  Each nonterminal is decorated by an integer priority:
   598   grammar\<close>.  Each nonterminal is decorated by an integer priority:
   605   @{text "A\<^sup>(\<^sup>p\<^sup>)"}.  In a derivation, @{text "A\<^sup>(\<^sup>p\<^sup>)"} may be rewritten
   599   \<open>A\<^sup>(\<^sup>p\<^sup>)\<close>.  In a derivation, \<open>A\<^sup>(\<^sup>p\<^sup>)\<close> may be rewritten
   606   using a production @{text "A\<^sup>(\<^sup>q\<^sup>) = \<gamma>"} only if @{text "p \<le> q"}.  Any
   600   using a production \<open>A\<^sup>(\<^sup>q\<^sup>) = \<gamma>\<close> only if \<open>p \<le> q\<close>.  Any
   607   priority grammar can be translated into a normal context-free
   601   priority grammar can be translated into a normal context-free
   608   grammar by introducing new nonterminals and productions.
   602   grammar by introducing new nonterminals and productions.
   609 
   603 
   610   \<^medskip>
   604   \<^medskip>
   611   Formally, a set of context free productions @{text G}
   605   Formally, a set of context free productions \<open>G\<close>
   612   induces a derivation relation @{text "\<longrightarrow>\<^sub>G"} as follows.  Let @{text
   606   induces a derivation relation \<open>\<longrightarrow>\<^sub>G\<close> as follows.  Let \<open>\<alpha>\<close> and \<open>\<beta>\<close> denote strings of terminal or nonterminal symbols.
   613   \<alpha>} and @{text \<beta>} denote strings of terminal or nonterminal symbols.
   607   Then \<open>\<alpha> A\<^sup>(\<^sup>p\<^sup>) \<beta> \<longrightarrow>\<^sub>G \<alpha> \<gamma> \<beta>\<close> holds if and only if \<open>G\<close>
   614   Then @{text "\<alpha> A\<^sup>(\<^sup>p\<^sup>) \<beta> \<longrightarrow>\<^sub>G \<alpha> \<gamma> \<beta>"} holds if and only if @{text G}
   608   contains some production \<open>A\<^sup>(\<^sup>q\<^sup>) = \<gamma>\<close> for \<open>p \<le> q\<close>.
   615   contains some production @{text "A\<^sup>(\<^sup>q\<^sup>) = \<gamma>"} for @{text "p \<le> q"}.
       
   616 
   609 
   617   \<^medskip>
   610   \<^medskip>
   618   The following grammar for arithmetic expressions
   611   The following grammar for arithmetic expressions
   619   demonstrates how binding power and associativity of operators can be
   612   demonstrates how binding power and associativity of operators can be
   620   enforced by priorities.
   613   enforced by priorities.
   621 
   614 
   622   \begin{center}
   615   \begin{center}
   623   \begin{tabular}{rclr}
   616   \begin{tabular}{rclr}
   624   @{text "A\<^sup>(\<^sup>1\<^sup>0\<^sup>0\<^sup>0\<^sup>)"} & @{text "="} & @{verbatim "("} @{text "A\<^sup>(\<^sup>0\<^sup>)"} @{verbatim ")"} \\
   617   \<open>A\<^sup>(\<^sup>1\<^sup>0\<^sup>0\<^sup>0\<^sup>)\<close> & \<open>=\<close> & @{verbatim "("} \<open>A\<^sup>(\<^sup>0\<^sup>)\<close> @{verbatim ")"} \\
   625   @{text "A\<^sup>(\<^sup>1\<^sup>0\<^sup>0\<^sup>0\<^sup>)"} & @{text "="} & @{verbatim 0} \\
   618   \<open>A\<^sup>(\<^sup>1\<^sup>0\<^sup>0\<^sup>0\<^sup>)\<close> & \<open>=\<close> & @{verbatim 0} \\
   626   @{text "A\<^sup>(\<^sup>0\<^sup>)"} & @{text "="} & @{text "A\<^sup>(\<^sup>0\<^sup>)"} @{verbatim "+"} @{text "A\<^sup>(\<^sup>1\<^sup>)"} \\
   619   \<open>A\<^sup>(\<^sup>0\<^sup>)\<close> & \<open>=\<close> & \<open>A\<^sup>(\<^sup>0\<^sup>)\<close> @{verbatim "+"} \<open>A\<^sup>(\<^sup>1\<^sup>)\<close> \\
   627   @{text "A\<^sup>(\<^sup>2\<^sup>)"} & @{text "="} & @{text "A\<^sup>(\<^sup>3\<^sup>)"} @{verbatim "*"} @{text "A\<^sup>(\<^sup>2\<^sup>)"} \\
   620   \<open>A\<^sup>(\<^sup>2\<^sup>)\<close> & \<open>=\<close> & \<open>A\<^sup>(\<^sup>3\<^sup>)\<close> @{verbatim "*"} \<open>A\<^sup>(\<^sup>2\<^sup>)\<close> \\
   628   @{text "A\<^sup>(\<^sup>3\<^sup>)"} & @{text "="} & @{verbatim "-"} @{text "A\<^sup>(\<^sup>3\<^sup>)"} \\
   621   \<open>A\<^sup>(\<^sup>3\<^sup>)\<close> & \<open>=\<close> & @{verbatim "-"} \<open>A\<^sup>(\<^sup>3\<^sup>)\<close> \\
   629   \end{tabular}
   622   \end{tabular}
   630   \end{center}
   623   \end{center}
   631   The choice of priorities determines that @{verbatim "-"} binds
   624   The choice of priorities determines that @{verbatim "-"} binds
   632   tighter than @{verbatim "*"}, which binds tighter than @{verbatim
   625   tighter than @{verbatim "*"}, which binds tighter than @{verbatim
   633   "+"}.  Furthermore @{verbatim "+"} associates to the left and
   626   "+"}.  Furthermore @{verbatim "+"} associates to the left and
   639   \<^item> All priorities must lie between 0 and 1000.
   632   \<^item> All priorities must lie between 0 and 1000.
   640 
   633 
   641   \<^item> Priority 0 on the right-hand side and priority 1000 on the
   634   \<^item> Priority 0 on the right-hand side and priority 1000 on the
   642   left-hand side may be omitted.
   635   left-hand side may be omitted.
   643 
   636 
   644   \<^item> The production @{text "A\<^sup>(\<^sup>p\<^sup>) = \<alpha>"} is written as @{text "A = \<alpha>
   637   \<^item> The production \<open>A\<^sup>(\<^sup>p\<^sup>) = \<alpha>\<close> is written as \<open>A = \<alpha>
   645   (p)"}, i.e.\ the priority of the left-hand side actually appears in
   638   (p)\<close>, i.e.\ the priority of the left-hand side actually appears in
   646   a column on the far right.
   639   a column on the far right.
   647 
   640 
   648   \<^item> Alternatives are separated by @{text "|"}.
   641   \<^item> Alternatives are separated by \<open>|\<close>.
   649 
   642 
   650   \<^item> Repetition is indicated by dots @{text "(\<dots>)"} in an informal
   643   \<^item> Repetition is indicated by dots \<open>(\<dots>)\<close> in an informal
   651   but obvious way.
   644   but obvious way.
   652 
   645 
   653 
   646 
   654   Using these conventions, the example grammar specification above
   647   Using these conventions, the example grammar specification above
   655   takes the form:
   648   takes the form:
   656   \begin{center}
   649   \begin{center}
   657   \begin{tabular}{rclc}
   650   \begin{tabular}{rclc}
   658     @{text A} & @{text "="} & @{verbatim "("} @{text A} @{verbatim ")"} \\
   651     \<open>A\<close> & \<open>=\<close> & @{verbatim "("} \<open>A\<close> @{verbatim ")"} \\
   659               & @{text "|"} & @{verbatim 0} & \qquad\qquad \\
   652               & \<open>|\<close> & @{verbatim 0} & \qquad\qquad \\
   660               & @{text "|"} & @{text A} @{verbatim "+"} @{text "A\<^sup>(\<^sup>1\<^sup>)"} & @{text "(0)"} \\
   653               & \<open>|\<close> & \<open>A\<close> @{verbatim "+"} \<open>A\<^sup>(\<^sup>1\<^sup>)\<close> & \<open>(0)\<close> \\
   661               & @{text "|"} & @{text "A\<^sup>(\<^sup>3\<^sup>)"} @{verbatim "*"} @{text "A\<^sup>(\<^sup>2\<^sup>)"} & @{text "(2)"} \\
   654               & \<open>|\<close> & \<open>A\<^sup>(\<^sup>3\<^sup>)\<close> @{verbatim "*"} \<open>A\<^sup>(\<^sup>2\<^sup>)\<close> & \<open>(2)\<close> \\
   662               & @{text "|"} & @{verbatim "-"} @{text "A\<^sup>(\<^sup>3\<^sup>)"} & @{text "(3)"} \\
   655               & \<open>|\<close> & @{verbatim "-"} \<open>A\<^sup>(\<^sup>3\<^sup>)\<close> & \<open>(3)\<close> \\
   663   \end{tabular}
   656   \end{tabular}
   664   \end{center}
   657   \end{center}
   665 \<close>
   658 \<close>
   666 
   659 
   667 
   660 
   668 subsection \<open>The Pure grammar \label{sec:pure-grammar}\<close>
   661 subsection \<open>The Pure grammar \label{sec:pure-grammar}\<close>
   669 
   662 
   670 text \<open>The priority grammar of the @{text "Pure"} theory is defined
   663 text \<open>The priority grammar of the \<open>Pure\<close> theory is defined
   671   approximately like this:
   664   approximately like this:
   672 
   665 
   673   \begin{center}
   666   \begin{center}
   674   \begin{supertabular}{rclr}
   667   \begin{supertabular}{rclr}
   675 
   668 
   676   @{syntax_def (inner) any} & = & @{text "prop  |  logic"} \\\\
   669   @{syntax_def (inner) any} & = & \<open>prop  |  logic\<close> \\\\
   677 
   670 
   678   @{syntax_def (inner) prop} & = & @{verbatim "("} @{text prop} @{verbatim ")"} \\
   671   @{syntax_def (inner) prop} & = & @{verbatim "("} \<open>prop\<close> @{verbatim ")"} \\
   679     & @{text "|"} & @{text "prop\<^sup>(\<^sup>4\<^sup>)"} @{verbatim "::"} @{text type} & @{text "(3)"} \\
   672     & \<open>|\<close> & \<open>prop\<^sup>(\<^sup>4\<^sup>)\<close> @{verbatim "::"} \<open>type\<close> & \<open>(3)\<close> \\
   680     & @{text "|"} & @{text "any\<^sup>(\<^sup>3\<^sup>)"} @{verbatim "=="} @{text "any\<^sup>(\<^sup>3\<^sup>)"} & @{text "(2)"} \\
   673     & \<open>|\<close> & \<open>any\<^sup>(\<^sup>3\<^sup>)\<close> @{verbatim "=="} \<open>any\<^sup>(\<^sup>3\<^sup>)\<close> & \<open>(2)\<close> \\
   681     & @{text "|"} & @{text "any\<^sup>(\<^sup>3\<^sup>)"} @{text "\<equiv>"} @{text "any\<^sup>(\<^sup>3\<^sup>)"} & @{text "(2)"} \\
   674     & \<open>|\<close> & \<open>any\<^sup>(\<^sup>3\<^sup>)\<close> \<open>\<equiv>\<close> \<open>any\<^sup>(\<^sup>3\<^sup>)\<close> & \<open>(2)\<close> \\
   682     & @{text "|"} & @{text "prop\<^sup>(\<^sup>3\<^sup>)"} @{verbatim "&&&"} @{text "prop\<^sup>(\<^sup>2\<^sup>)"} & @{text "(2)"} \\
   675     & \<open>|\<close> & \<open>prop\<^sup>(\<^sup>3\<^sup>)\<close> @{verbatim "&&&"} \<open>prop\<^sup>(\<^sup>2\<^sup>)\<close> & \<open>(2)\<close> \\
   683     & @{text "|"} & @{text "prop\<^sup>(\<^sup>2\<^sup>)"} @{verbatim "==>"} @{text "prop\<^sup>(\<^sup>1\<^sup>)"} & @{text "(1)"} \\
   676     & \<open>|\<close> & \<open>prop\<^sup>(\<^sup>2\<^sup>)\<close> @{verbatim "==>"} \<open>prop\<^sup>(\<^sup>1\<^sup>)\<close> & \<open>(1)\<close> \\
   684     & @{text "|"} & @{text "prop\<^sup>(\<^sup>2\<^sup>)"} @{text "\<Longrightarrow>"} @{text "prop\<^sup>(\<^sup>1\<^sup>)"} & @{text "(1)"} \\
   677     & \<open>|\<close> & \<open>prop\<^sup>(\<^sup>2\<^sup>)\<close> \<open>\<Longrightarrow>\<close> \<open>prop\<^sup>(\<^sup>1\<^sup>)\<close> & \<open>(1)\<close> \\
   685     & @{text "|"} & @{verbatim "[|"} @{text prop} @{verbatim ";"} @{text "\<dots>"} @{verbatim ";"} @{text prop} @{verbatim "|]"} @{verbatim "==>"} @{text "prop\<^sup>(\<^sup>1\<^sup>)"} & @{text "(1)"} \\
   678     & \<open>|\<close> & @{verbatim "[|"} \<open>prop\<close> @{verbatim ";"} \<open>\<dots>\<close> @{verbatim ";"} \<open>prop\<close> @{verbatim "|]"} @{verbatim "==>"} \<open>prop\<^sup>(\<^sup>1\<^sup>)\<close> & \<open>(1)\<close> \\
   686     & @{text "|"} & @{text "\<lbrakk>"} @{text prop} @{verbatim ";"} @{text "\<dots>"} @{verbatim ";"} @{text prop} @{text "\<rbrakk>"} @{text "\<Longrightarrow>"} @{text "prop\<^sup>(\<^sup>1\<^sup>)"} & @{text "(1)"} \\
   679     & \<open>|\<close> & \<open>\<lbrakk>\<close> \<open>prop\<close> @{verbatim ";"} \<open>\<dots>\<close> @{verbatim ";"} \<open>prop\<close> \<open>\<rbrakk>\<close> \<open>\<Longrightarrow>\<close> \<open>prop\<^sup>(\<^sup>1\<^sup>)\<close> & \<open>(1)\<close> \\
   687     & @{text "|"} & @{verbatim "!!"} @{text idts} @{verbatim "."} @{text prop} & @{text "(0)"} \\
   680     & \<open>|\<close> & @{verbatim "!!"} \<open>idts\<close> @{verbatim "."} \<open>prop\<close> & \<open>(0)\<close> \\
   688     & @{text "|"} & @{text "\<And>"} @{text idts} @{verbatim "."} @{text prop} & @{text "(0)"} \\
   681     & \<open>|\<close> & \<open>\<And>\<close> \<open>idts\<close> @{verbatim "."} \<open>prop\<close> & \<open>(0)\<close> \\
   689     & @{text "|"} & @{verbatim OFCLASS} @{verbatim "("} @{text type} @{verbatim ","} @{text logic} @{verbatim ")"} \\
   682     & \<open>|\<close> & @{verbatim OFCLASS} @{verbatim "("} \<open>type\<close> @{verbatim ","} \<open>logic\<close> @{verbatim ")"} \\
   690     & @{text "|"} & @{verbatim SORT_CONSTRAINT} @{verbatim "("} @{text type} @{verbatim ")"} \\
   683     & \<open>|\<close> & @{verbatim SORT_CONSTRAINT} @{verbatim "("} \<open>type\<close> @{verbatim ")"} \\
   691     & @{text "|"} & @{verbatim TERM} @{text logic} \\
   684     & \<open>|\<close> & @{verbatim TERM} \<open>logic\<close> \\
   692     & @{text "|"} & @{verbatim PROP} @{text aprop} \\\\
   685     & \<open>|\<close> & @{verbatim PROP} \<open>aprop\<close> \\\\
   693 
   686 
   694   @{syntax_def (inner) aprop} & = & @{verbatim "("} @{text aprop} @{verbatim ")"} \\
   687   @{syntax_def (inner) aprop} & = & @{verbatim "("} \<open>aprop\<close> @{verbatim ")"} \\
   695     & @{text "|"} & @{text "id  |  longid  |  var  |  "}@{verbatim "_"}@{text "  |  "}@{verbatim "..."} \\
   688     & \<open>|\<close> & \<open>id  |  longid  |  var  |  \<close>@{verbatim "_"}\<open>  |  \<close>@{verbatim "..."} \\
   696     & @{text "|"} & @{verbatim CONST} @{text "id  |  "}@{verbatim CONST} @{text "longid"} \\
   689     & \<open>|\<close> & @{verbatim CONST} \<open>id  |  \<close>@{verbatim CONST} \<open>longid\<close> \\
   697     & @{text "|"} & @{verbatim XCONST} @{text "id  |  "}@{verbatim XCONST} @{text "longid"} \\
   690     & \<open>|\<close> & @{verbatim XCONST} \<open>id  |  \<close>@{verbatim XCONST} \<open>longid\<close> \\
   698     & @{text "|"} & @{text "logic\<^sup>(\<^sup>1\<^sup>0\<^sup>0\<^sup>0\<^sup>)  any\<^sup>(\<^sup>1\<^sup>0\<^sup>0\<^sup>0\<^sup>) \<dots> any\<^sup>(\<^sup>1\<^sup>0\<^sup>0\<^sup>0\<^sup>)"} & @{text "(999)"} \\\\
   691     & \<open>|\<close> & \<open>logic\<^sup>(\<^sup>1\<^sup>0\<^sup>0\<^sup>0\<^sup>)  any\<^sup>(\<^sup>1\<^sup>0\<^sup>0\<^sup>0\<^sup>) \<dots> any\<^sup>(\<^sup>1\<^sup>0\<^sup>0\<^sup>0\<^sup>)\<close> & \<open>(999)\<close> \\\\
   699 
   692 
   700   @{syntax_def (inner) logic} & = & @{verbatim "("} @{text logic} @{verbatim ")"} \\
   693   @{syntax_def (inner) logic} & = & @{verbatim "("} \<open>logic\<close> @{verbatim ")"} \\
   701     & @{text "|"} & @{text "logic\<^sup>(\<^sup>4\<^sup>)"} @{verbatim "::"} @{text type} & @{text "(3)"} \\
   694     & \<open>|\<close> & \<open>logic\<^sup>(\<^sup>4\<^sup>)\<close> @{verbatim "::"} \<open>type\<close> & \<open>(3)\<close> \\
   702     & @{text "|"} & @{text "id  |  longid  |  var  |  "}@{verbatim "_"}@{text "  |  "}@{verbatim "..."} \\
   695     & \<open>|\<close> & \<open>id  |  longid  |  var  |  \<close>@{verbatim "_"}\<open>  |  \<close>@{verbatim "..."} \\
   703     & @{text "|"} & @{verbatim CONST} @{text "id  |  "}@{verbatim CONST} @{text "longid"} \\
   696     & \<open>|\<close> & @{verbatim CONST} \<open>id  |  \<close>@{verbatim CONST} \<open>longid\<close> \\
   704     & @{text "|"} & @{verbatim XCONST} @{text "id  |  "}@{verbatim XCONST} @{text "longid"} \\
   697     & \<open>|\<close> & @{verbatim XCONST} \<open>id  |  \<close>@{verbatim XCONST} \<open>longid\<close> \\
   705     & @{text "|"} & @{text "logic\<^sup>(\<^sup>1\<^sup>0\<^sup>0\<^sup>0\<^sup>)  any\<^sup>(\<^sup>1\<^sup>0\<^sup>0\<^sup>0\<^sup>) \<dots> any\<^sup>(\<^sup>1\<^sup>0\<^sup>0\<^sup>0\<^sup>)"} & @{text "(999)"} \\
   698     & \<open>|\<close> & \<open>logic\<^sup>(\<^sup>1\<^sup>0\<^sup>0\<^sup>0\<^sup>)  any\<^sup>(\<^sup>1\<^sup>0\<^sup>0\<^sup>0\<^sup>) \<dots> any\<^sup>(\<^sup>1\<^sup>0\<^sup>0\<^sup>0\<^sup>)\<close> & \<open>(999)\<close> \\
   706     & @{text "|"} & @{text "\<struct> index\<^sup>(\<^sup>1\<^sup>0\<^sup>0\<^sup>0\<^sup>)"} \\
   699     & \<open>|\<close> & \<open>\<struct> index\<^sup>(\<^sup>1\<^sup>0\<^sup>0\<^sup>0\<^sup>)\<close> \\
   707     & @{text "|"} & @{verbatim "%"} @{text pttrns} @{verbatim "."} @{text "any\<^sup>(\<^sup>3\<^sup>)"} & @{text "(3)"} \\
   700     & \<open>|\<close> & @{verbatim "%"} \<open>pttrns\<close> @{verbatim "."} \<open>any\<^sup>(\<^sup>3\<^sup>)\<close> & \<open>(3)\<close> \\
   708     & @{text "|"} & @{text \<lambda>} @{text pttrns} @{verbatim "."} @{text "any\<^sup>(\<^sup>3\<^sup>)"} & @{text "(3)"} \\
   701     & \<open>|\<close> & \<open>\<lambda>\<close> \<open>pttrns\<close> @{verbatim "."} \<open>any\<^sup>(\<^sup>3\<^sup>)\<close> & \<open>(3)\<close> \\
   709     & @{text "|"} & @{verbatim op} @{verbatim "=="}@{text "  |  "}@{verbatim op} @{text "\<equiv>"}@{text "  |  "}@{verbatim op} @{verbatim "&&&"} \\
   702     & \<open>|\<close> & @{verbatim op} @{verbatim "=="}\<open>  |  \<close>@{verbatim op} \<open>\<equiv>\<close>\<open>  |  \<close>@{verbatim op} @{verbatim "&&&"} \\
   710     & @{text "|"} & @{verbatim op} @{verbatim "==>"}@{text "  |  "}@{verbatim op} @{text "\<Longrightarrow>"} \\
   703     & \<open>|\<close> & @{verbatim op} @{verbatim "==>"}\<open>  |  \<close>@{verbatim op} \<open>\<Longrightarrow>\<close> \\
   711     & @{text "|"} & @{verbatim TYPE} @{verbatim "("} @{text type} @{verbatim ")"} \\\\
   704     & \<open>|\<close> & @{verbatim TYPE} @{verbatim "("} \<open>type\<close> @{verbatim ")"} \\\\
   712 
   705 
   713   @{syntax_def (inner) idt} & = & @{verbatim "("} @{text idt} @{verbatim ")"}@{text "  |  id  |  "}@{verbatim "_"} \\
   706   @{syntax_def (inner) idt} & = & @{verbatim "("} \<open>idt\<close> @{verbatim ")"}\<open>  |  id  |  \<close>@{verbatim "_"} \\
   714     & @{text "|"} & @{text id} @{verbatim "::"} @{text type} & @{text "(0)"} \\
   707     & \<open>|\<close> & \<open>id\<close> @{verbatim "::"} \<open>type\<close> & \<open>(0)\<close> \\
   715     & @{text "|"} & @{verbatim "_"} @{verbatim "::"} @{text type} & @{text "(0)"} \\\\
   708     & \<open>|\<close> & @{verbatim "_"} @{verbatim "::"} \<open>type\<close> & \<open>(0)\<close> \\\\
   716 
   709 
   717   @{syntax_def (inner) index} & = & @{verbatim "\<^bsub>"} @{text "logic\<^sup>(\<^sup>0\<^sup>)"} @{verbatim "\<^esub>"}@{text "  |  |  \<index>"} \\\\
   710   @{syntax_def (inner) index} & = & @{verbatim "\<^bsub>"} \<open>logic\<^sup>(\<^sup>0\<^sup>)\<close> @{verbatim "\<^esub>"}\<open>  |  |  \<index>\<close> \\\\
   718 
   711 
   719   @{syntax_def (inner) idts} & = & @{text "idt  |  idt\<^sup>(\<^sup>1\<^sup>) idts"} & @{text "(0)"} \\\\
   712   @{syntax_def (inner) idts} & = & \<open>idt  |  idt\<^sup>(\<^sup>1\<^sup>) idts\<close> & \<open>(0)\<close> \\\\
   720 
   713 
   721   @{syntax_def (inner) pttrn} & = & @{text idt} \\\\
   714   @{syntax_def (inner) pttrn} & = & \<open>idt\<close> \\\\
   722 
   715 
   723   @{syntax_def (inner) pttrns} & = & @{text "pttrn  |  pttrn\<^sup>(\<^sup>1\<^sup>) pttrns"} & @{text "(0)"} \\\\
   716   @{syntax_def (inner) pttrns} & = & \<open>pttrn  |  pttrn\<^sup>(\<^sup>1\<^sup>) pttrns\<close> & \<open>(0)\<close> \\\\
   724 
   717 
   725   @{syntax_def (inner) type} & = & @{verbatim "("} @{text type} @{verbatim ")"} \\
   718   @{syntax_def (inner) type} & = & @{verbatim "("} \<open>type\<close> @{verbatim ")"} \\
   726     & @{text "|"} & @{text "tid  |  tvar  |  "}@{verbatim "_"} \\
   719     & \<open>|\<close> & \<open>tid  |  tvar  |  \<close>@{verbatim "_"} \\
   727     & @{text "|"} & @{text "tid"} @{verbatim "::"} @{text "sort  |  tvar  "}@{verbatim "::"} @{text "sort  |  "}@{verbatim "_"} @{verbatim "::"} @{text "sort"} \\
   720     & \<open>|\<close> & \<open>tid\<close> @{verbatim "::"} \<open>sort  |  tvar  \<close>@{verbatim "::"} \<open>sort  |  \<close>@{verbatim "_"} @{verbatim "::"} \<open>sort\<close> \\
   728     & @{text "|"} & @{text "type_name  |  type\<^sup>(\<^sup>1\<^sup>0\<^sup>0\<^sup>0\<^sup>) type_name"} \\
   721     & \<open>|\<close> & \<open>type_name  |  type\<^sup>(\<^sup>1\<^sup>0\<^sup>0\<^sup>0\<^sup>) type_name\<close> \\
   729     & @{text "|"} & @{verbatim "("} @{text type} @{verbatim ","} @{text "\<dots>"} @{verbatim ","} @{text type} @{verbatim ")"} @{text type_name} \\
   722     & \<open>|\<close> & @{verbatim "("} \<open>type\<close> @{verbatim ","} \<open>\<dots>\<close> @{verbatim ","} \<open>type\<close> @{verbatim ")"} \<open>type_name\<close> \\
   730     & @{text "|"} & @{text "type\<^sup>(\<^sup>1\<^sup>)"} @{verbatim "=>"} @{text type} & @{text "(0)"} \\
   723     & \<open>|\<close> & \<open>type\<^sup>(\<^sup>1\<^sup>)\<close> @{verbatim "=>"} \<open>type\<close> & \<open>(0)\<close> \\
   731     & @{text "|"} & @{text "type\<^sup>(\<^sup>1\<^sup>)"} @{text "\<Rightarrow>"} @{text type} & @{text "(0)"} \\
   724     & \<open>|\<close> & \<open>type\<^sup>(\<^sup>1\<^sup>)\<close> \<open>\<Rightarrow>\<close> \<open>type\<close> & \<open>(0)\<close> \\
   732     & @{text "|"} & @{verbatim "["} @{text type} @{verbatim ","} @{text "\<dots>"} @{verbatim ","} @{text type} @{verbatim "]"} @{verbatim "=>"} @{text type} & @{text "(0)"} \\
   725     & \<open>|\<close> & @{verbatim "["} \<open>type\<close> @{verbatim ","} \<open>\<dots>\<close> @{verbatim ","} \<open>type\<close> @{verbatim "]"} @{verbatim "=>"} \<open>type\<close> & \<open>(0)\<close> \\
   733     & @{text "|"} & @{verbatim "["} @{text type} @{verbatim ","} @{text "\<dots>"} @{verbatim ","} @{text type} @{verbatim "]"} @{text "\<Rightarrow>"} @{text type} & @{text "(0)"} \\
   726     & \<open>|\<close> & @{verbatim "["} \<open>type\<close> @{verbatim ","} \<open>\<dots>\<close> @{verbatim ","} \<open>type\<close> @{verbatim "]"} \<open>\<Rightarrow>\<close> \<open>type\<close> & \<open>(0)\<close> \\
   734   @{syntax_def (inner) type_name} & = & @{text "id  |  longid"} \\\\
   727   @{syntax_def (inner) type_name} & = & \<open>id  |  longid\<close> \\\\
   735 
   728 
   736   @{syntax_def (inner) sort} & = & @{syntax class_name}~@{text "  |  "}@{verbatim "{}"} \\
   729   @{syntax_def (inner) sort} & = & @{syntax class_name}~\<open>  |  \<close>@{verbatim "{}"} \\
   737     & @{text "|"} & @{verbatim "{"} @{syntax class_name} @{verbatim ","} @{text "\<dots>"} @{verbatim ","} @{syntax class_name} @{verbatim "}"} \\
   730     & \<open>|\<close> & @{verbatim "{"} @{syntax class_name} @{verbatim ","} \<open>\<dots>\<close> @{verbatim ","} @{syntax class_name} @{verbatim "}"} \\
   738   @{syntax_def (inner) class_name} & = & @{text "id  |  longid"} \\
   731   @{syntax_def (inner) class_name} & = & \<open>id  |  longid\<close> \\
   739   \end{supertabular}
   732   \end{supertabular}
   740   \end{center}
   733   \end{center}
   741 
   734 
   742   \<^medskip>
   735   \<^medskip>
   743   Here literal terminals are printed @{verbatim "verbatim"};
   736   Here literal terminals are printed @{verbatim "verbatim"};
   748   \<^descr> @{syntax_ref (inner) any} denotes any term.
   741   \<^descr> @{syntax_ref (inner) any} denotes any term.
   749 
   742 
   750   \<^descr> @{syntax_ref (inner) prop} denotes meta-level propositions,
   743   \<^descr> @{syntax_ref (inner) prop} denotes meta-level propositions,
   751   which are terms of type @{typ prop}.  The syntax of such formulae of
   744   which are terms of type @{typ prop}.  The syntax of such formulae of
   752   the meta-logic is carefully distinguished from usual conventions for
   745   the meta-logic is carefully distinguished from usual conventions for
   753   object-logics.  In particular, plain @{text "\<lambda>"}-term notation is
   746   object-logics.  In particular, plain \<open>\<lambda>\<close>-term notation is
   754   \<^emph>\<open>not\<close> recognized as @{syntax (inner) prop}.
   747   \<^emph>\<open>not\<close> recognized as @{syntax (inner) prop}.
   755 
   748 
   756   \<^descr> @{syntax_ref (inner) aprop} denotes atomic propositions, which
   749   \<^descr> @{syntax_ref (inner) aprop} denotes atomic propositions, which
   757   are embedded into regular @{syntax (inner) prop} by means of an
   750   are embedded into regular @{syntax (inner) prop} by means of an
   758   explicit @{verbatim PROP} token.
   751   explicit @{verbatim PROP} token.
   763   the printed version will appear like @{syntax (inner) logic} and
   756   the printed version will appear like @{syntax (inner) logic} and
   764   cannot be parsed again as @{syntax (inner) prop}.
   757   cannot be parsed again as @{syntax (inner) prop}.
   765 
   758 
   766   \<^descr> @{syntax_ref (inner) logic} denotes arbitrary terms of a
   759   \<^descr> @{syntax_ref (inner) logic} denotes arbitrary terms of a
   767   logical type, excluding type @{typ prop}.  This is the main
   760   logical type, excluding type @{typ prop}.  This is the main
   768   syntactic category of object-logic entities, covering plain @{text
   761   syntactic category of object-logic entities, covering plain \<open>\<lambda>\<close>-term notation (variables, abstraction, application), plus
   769   \<lambda>}-term notation (variables, abstraction, application), plus
       
   770   anything defined by the user.
   762   anything defined by the user.
   771 
   763 
   772   When specifying notation for logical entities, all logical types
   764   When specifying notation for logical entities, all logical types
   773   (excluding @{typ prop}) are \<^emph>\<open>collapsed\<close> to this single category
   765   (excluding @{typ prop}) are \<^emph>\<open>collapsed\<close> to this single category
   774   of @{syntax (inner) logic}.
   766   of @{syntax (inner) logic}.
   775 
   767 
   776   \<^descr> @{syntax_ref (inner) index} denotes an optional index term for
   768   \<^descr> @{syntax_ref (inner) index} denotes an optional index term for
   777   indexed syntax.  If omitted, it refers to the first @{keyword_ref
   769   indexed syntax.  If omitted, it refers to the first @{keyword_ref
   778   "structure"} variable in the context.  The special dummy ``@{text
   770   "structure"} variable in the context.  The special dummy ``\<open>\<index>\<close>'' serves as pattern variable in mixfix annotations that
   779   "\<index>"}'' serves as pattern variable in mixfix annotations that
       
   780   introduce indexed notation.
   771   introduce indexed notation.
   781 
   772 
   782   \<^descr> @{syntax_ref (inner) idt} denotes identifiers, possibly
   773   \<^descr> @{syntax_ref (inner) idt} denotes identifiers, possibly
   783   constrained by types.
   774   constrained by types.
   784 
   775 
   785   \<^descr> @{syntax_ref (inner) idts} denotes a sequence of @{syntax_ref
   776   \<^descr> @{syntax_ref (inner) idts} denotes a sequence of @{syntax_ref
   786   (inner) idt}.  This is the most basic category for variables in
   777   (inner) idt}.  This is the most basic category for variables in
   787   iterated binders, such as @{text "\<lambda>"} or @{text "\<And>"}.
   778   iterated binders, such as \<open>\<lambda>\<close> or \<open>\<And>\<close>.
   788 
   779 
   789   \<^descr> @{syntax_ref (inner) pttrn} and @{syntax_ref (inner) pttrns}
   780   \<^descr> @{syntax_ref (inner) pttrn} and @{syntax_ref (inner) pttrns}
   790   denote patterns for abstraction, cases bindings etc.  In Pure, these
   781   denote patterns for abstraction, cases bindings etc.  In Pure, these
   791   categories start as a merely copy of @{syntax (inner) idt} and
   782   categories start as a merely copy of @{syntax (inner) idt} and
   792   @{syntax (inner) idts}, respectively.  Object-logics may add
   783   @{syntax (inner) idts}, respectively.  Object-logics may add
   797   \<^descr> @{syntax_ref (inner) sort} denotes meta-level sorts.
   788   \<^descr> @{syntax_ref (inner) sort} denotes meta-level sorts.
   798 
   789 
   799 
   790 
   800   Here are some further explanations of certain syntax features.
   791   Here are some further explanations of certain syntax features.
   801 
   792 
   802   \<^item> In @{syntax (inner) idts}, note that @{text "x :: nat y"} is
   793   \<^item> In @{syntax (inner) idts}, note that \<open>x :: nat y\<close> is
   803   parsed as @{text "x :: (nat y)"}, treating @{text y} like a type
   794   parsed as \<open>x :: (nat y)\<close>, treating \<open>y\<close> like a type
   804   constructor applied to @{text nat}.  To avoid this interpretation,
   795   constructor applied to \<open>nat\<close>.  To avoid this interpretation,
   805   write @{text "(x :: nat) y"} with explicit parentheses.
   796   write \<open>(x :: nat) y\<close> with explicit parentheses.
   806 
   797 
   807   \<^item> Similarly, @{text "x :: nat y :: nat"} is parsed as @{text "x ::
   798   \<^item> Similarly, \<open>x :: nat y :: nat\<close> is parsed as \<open>x ::
   808   (nat y :: nat)"}.  The correct form is @{text "(x :: nat) (y ::
   799   (nat y :: nat)\<close>.  The correct form is \<open>(x :: nat) (y ::
   809   nat)"}, or @{text "(x :: nat) y :: nat"} if @{text y} is last in the
   800   nat)\<close>, or \<open>(x :: nat) y :: nat\<close> if \<open>y\<close> is last in the
   810   sequence of identifiers.
   801   sequence of identifiers.
   811 
   802 
   812   \<^item> Type constraints for terms bind very weakly.  For example,
   803   \<^item> Type constraints for terms bind very weakly.  For example,
   813   @{text "x < y :: nat"} is normally parsed as @{text "(x < y) ::
   804   \<open>x < y :: nat\<close> is normally parsed as \<open>(x < y) ::
   814   nat"}, unless @{text "<"} has a very low priority, in which case the
   805   nat\<close>, unless \<open><\<close> has a very low priority, in which case the
   815   input is likely to be ambiguous.  The correct form is @{text "x < (y
   806   input is likely to be ambiguous.  The correct form is \<open>x < (y
   816   :: nat)"}.
   807   :: nat)\<close>.
   817 
   808 
   818   \<^item> Dummy variables (written as underscore) may occur in different
   809   \<^item> Dummy variables (written as underscore) may occur in different
   819   roles.
   810   roles.
   820 
   811 
   821     \<^descr> A type ``@{text "_"}'' or ``@{text "_ :: sort"}'' acts like an
   812     \<^descr> A type ``\<open>_\<close>'' or ``\<open>_ :: sort\<close>'' acts like an
   822     anonymous inference parameter, which is filled-in according to the
   813     anonymous inference parameter, which is filled-in according to the
   823     most general type produced by the type-checking phase.
   814     most general type produced by the type-checking phase.
   824 
   815 
   825     \<^descr> A bound ``@{text "_"}'' refers to a vacuous abstraction, where
   816     \<^descr> A bound ``\<open>_\<close>'' refers to a vacuous abstraction, where
   826     the body does not refer to the binding introduced here.  As in the
   817     the body does not refer to the binding introduced here.  As in the
   827     term @{term "\<lambda>x _. x"}, which is @{text "\<alpha>"}-equivalent to @{text
   818     term @{term "\<lambda>x _. x"}, which is \<open>\<alpha>\<close>-equivalent to \<open>\<lambda>x y. x\<close>.
   828     "\<lambda>x y. x"}.
   819 
   829 
   820     \<^descr> A free ``\<open>_\<close>'' refers to an implicit outer binding.
   830     \<^descr> A free ``@{text "_"}'' refers to an implicit outer binding.
   821     Higher definitional packages usually allow forms like \<open>f x _
   831     Higher definitional packages usually allow forms like @{text "f x _
   822     = x\<close>.
   832     = x"}.
   823 
   833 
   824     \<^descr> A schematic ``\<open>_\<close>'' (within a term pattern, see
   834     \<^descr> A schematic ``@{text "_"}'' (within a term pattern, see
       
   835     \secref{sec:term-decls}) refers to an anonymous variable that is
   825     \secref{sec:term-decls}) refers to an anonymous variable that is
   836     implicitly abstracted over its context of locally bound variables.
   826     implicitly abstracted over its context of locally bound variables.
   837     For example, this allows pattern matching of @{text "{x. f x = g
   827     For example, this allows pattern matching of \<open>{x. f x = g
   838     x}"} against @{text "{x. _ = _}"}, or even @{text "{_. _ = _}"} by
   828     x}\<close> against \<open>{x. _ = _}\<close>, or even \<open>{_. _ = _}\<close> by
   839     using both bound and schematic dummies.
   829     using both bound and schematic dummies.
   840 
   830 
   841   \<^descr> The three literal dots ``@{verbatim "..."}'' may be also
   831   \<^descr> The three literal dots ``@{verbatim "..."}'' may be also
   842   written as ellipsis symbol @{verbatim "\<dots>"}.  In both cases this
   832   written as ellipsis symbol @{verbatim "\<dots>"}.  In both cases this
   843   refers to a special schematic variable, which is bound in the
   833   refers to a special schematic variable, which is bound in the
   857 
   847 
   858 subsection \<open>Inspecting the syntax\<close>
   848 subsection \<open>Inspecting the syntax\<close>
   859 
   849 
   860 text \<open>
   850 text \<open>
   861   \begin{matharray}{rcl}
   851   \begin{matharray}{rcl}
   862     @{command_def "print_syntax"}@{text "\<^sup>*"} & : & @{text "context \<rightarrow>"} \\
   852     @{command_def "print_syntax"}\<open>\<^sup>*\<close> & : & \<open>context \<rightarrow>\<close> \\
   863   \end{matharray}
   853   \end{matharray}
   864 
   854 
   865   \<^descr> @{command "print_syntax"} prints the inner syntax of the
   855   \<^descr> @{command "print_syntax"} prints the inner syntax of the
   866   current context.  The output can be quite large; the most important
   856   current context.  The output can be quite large; the most important
   867   sections are explained below.
   857   sections are explained below.
   868 
   858 
   869     \<^descr> @{text "lexicon"} lists the delimiters of the inner token
   859     \<^descr> \<open>lexicon\<close> lists the delimiters of the inner token
   870     language; see \secref{sec:inner-lex}.
   860     language; see \secref{sec:inner-lex}.
   871 
   861 
   872     \<^descr> @{text "prods"} lists the productions of the underlying
   862     \<^descr> \<open>prods\<close> lists the productions of the underlying
   873     priority grammar; see \secref{sec:priority-grammar}.
   863     priority grammar; see \secref{sec:priority-grammar}.
   874 
   864 
   875     The nonterminal @{text "A\<^sup>(\<^sup>p\<^sup>)"} is rendered in plain text as @{text
   865     The nonterminal \<open>A\<^sup>(\<^sup>p\<^sup>)\<close> is rendered in plain text as \<open>A[p]\<close>; delimiters are quoted.  Many productions have an extra
   876     "A[p]"}; delimiters are quoted.  Many productions have an extra
   866     \<open>\<dots> => name\<close>.  These names later become the heads of parse
   877     @{text "\<dots> => name"}.  These names later become the heads of parse
       
   878     trees; they also guide the pretty printer.
   867     trees; they also guide the pretty printer.
   879 
   868 
   880     Productions without such parse tree names are called \<^emph>\<open>copy
   869     Productions without such parse tree names are called \<^emph>\<open>copy
   881     productions\<close>.  Their right-hand side must have exactly one
   870     productions\<close>.  Their right-hand side must have exactly one
   882     nonterminal symbol (or named token).  The parser does not create a
   871     nonterminal symbol (or named token).  The parser does not create a
   886     If the right-hand side of a copy production consists of a single
   875     If the right-hand side of a copy production consists of a single
   887     nonterminal without any delimiters, then it is called a \<^emph>\<open>chain
   876     nonterminal without any delimiters, then it is called a \<^emph>\<open>chain
   888     production\<close>.  Chain productions act as abbreviations: conceptually,
   877     production\<close>.  Chain productions act as abbreviations: conceptually,
   889     they are removed from the grammar by adding new productions.
   878     they are removed from the grammar by adding new productions.
   890     Priority information attached to chain productions is ignored; only
   879     Priority information attached to chain productions is ignored; only
   891     the dummy value @{text "-1"} is displayed.
   880     the dummy value \<open>-1\<close> is displayed.
   892 
   881 
   893     \<^descr> @{text "print modes"} lists the alternative print modes
   882     \<^descr> \<open>print modes\<close> lists the alternative print modes
   894     provided by this grammar; see \secref{sec:print-modes}.
   883     provided by this grammar; see \secref{sec:print-modes}.
   895 
   884 
   896     \<^descr> @{text "parse_rules"} and @{text "print_rules"} relate to
   885     \<^descr> \<open>parse_rules\<close> and \<open>print_rules\<close> relate to
   897     syntax translations (macros); see \secref{sec:syn-trans}.
   886     syntax translations (macros); see \secref{sec:syn-trans}.
   898 
   887 
   899     \<^descr> @{text "parse_ast_translation"} and @{text
   888     \<^descr> \<open>parse_ast_translation\<close> and \<open>print_ast_translation\<close> list sets of constants that invoke
   900     "print_ast_translation"} list sets of constants that invoke
       
   901     translation functions for abstract syntax trees, which are only
   889     translation functions for abstract syntax trees, which are only
   902     required in very special situations; see \secref{sec:tr-funs}.
   890     required in very special situations; see \secref{sec:tr-funs}.
   903 
   891 
   904     \<^descr> @{text "parse_translation"} and @{text "print_translation"}
   892     \<^descr> \<open>parse_translation\<close> and \<open>print_translation\<close>
   905     list the sets of constants that invoke regular translation
   893     list the sets of constants that invoke regular translation
   906     functions; see \secref{sec:tr-funs}.
   894     functions; see \secref{sec:tr-funs}.
   907 \<close>
   895 \<close>
   908 
   896 
   909 
   897 
   910 subsection \<open>Ambiguity of parsed expressions\<close>
   898 subsection \<open>Ambiguity of parsed expressions\<close>
   911 
   899 
   912 text \<open>
   900 text \<open>
   913   \begin{tabular}{rcll}
   901   \begin{tabular}{rcll}
   914     @{attribute_def syntax_ambiguity_warning} & : & @{text attribute} & default @{text true} \\
   902     @{attribute_def syntax_ambiguity_warning} & : & \<open>attribute\<close> & default \<open>true\<close> \\
   915     @{attribute_def syntax_ambiguity_limit} & : & @{text attribute} & default @{text 10} \\
   903     @{attribute_def syntax_ambiguity_limit} & : & \<open>attribute\<close> & default \<open>10\<close> \\
   916   \end{tabular}
   904   \end{tabular}
   917 
   905 
   918   Depending on the grammar and the given input, parsing may be
   906   Depending on the grammar and the given input, parsing may be
   919   ambiguous.  Isabelle lets the Earley parser enumerate all possible
   907   ambiguous.  Isabelle lets the Earley parser enumerate all possible
   920   parse trees, and then tries to make the best out of the situation.
   908   parse trees, and then tries to make the best out of the situation.
   941 section \<open>Syntax transformations \label{sec:syntax-transformations}\<close>
   929 section \<open>Syntax transformations \label{sec:syntax-transformations}\<close>
   942 
   930 
   943 text \<open>The inner syntax engine of Isabelle provides separate
   931 text \<open>The inner syntax engine of Isabelle provides separate
   944   mechanisms to transform parse trees either via rewrite systems on
   932   mechanisms to transform parse trees either via rewrite systems on
   945   first-order ASTs (\secref{sec:syn-trans}), or ML functions on ASTs
   933   first-order ASTs (\secref{sec:syn-trans}), or ML functions on ASTs
   946   or syntactic @{text "\<lambda>"}-terms (\secref{sec:tr-funs}).  This works
   934   or syntactic \<open>\<lambda>\<close>-terms (\secref{sec:tr-funs}).  This works
   947   both for parsing and printing, as outlined in
   935   both for parsing and printing, as outlined in
   948   \figref{fig:parse-print}.
   936   \figref{fig:parse-print}.
   949 
   937 
   950   \begin{figure}[htbp]
   938   \begin{figure}[htbp]
   951   \begin{center}
   939   \begin{center}
   952   \begin{tabular}{cl}
   940   \begin{tabular}{cl}
   953   string          & \\
   941   string          & \\
   954   @{text "\<down>"}     & lexer + parser \\
   942   \<open>\<down>\<close>     & lexer + parser \\
   955   parse tree      & \\
   943   parse tree      & \\
   956   @{text "\<down>"}     & parse AST translation \\
   944   \<open>\<down>\<close>     & parse AST translation \\
   957   AST             & \\
   945   AST             & \\
   958   @{text "\<down>"}     & AST rewriting (macros) \\
   946   \<open>\<down>\<close>     & AST rewriting (macros) \\
   959   AST             & \\
   947   AST             & \\
   960   @{text "\<down>"}     & parse translation \\
   948   \<open>\<down>\<close>     & parse translation \\
   961   --- pre-term ---    & \\
   949   --- pre-term ---    & \\
   962   @{text "\<down>"}     & print translation \\
   950   \<open>\<down>\<close>     & print translation \\
   963   AST             & \\
   951   AST             & \\
   964   @{text "\<down>"}     & AST rewriting (macros) \\
   952   \<open>\<down>\<close>     & AST rewriting (macros) \\
   965   AST             & \\
   953   AST             & \\
   966   @{text "\<down>"}     & print AST translation \\
   954   \<open>\<down>\<close>     & print AST translation \\
   967   string          &
   955   string          &
   968   \end{tabular}
   956   \end{tabular}
   969   \end{center}
   957   \end{center}
   970   \caption{Parsing and printing with translations}\label{fig:parse-print}
   958   \caption{Parsing and printing with translations}\label{fig:parse-print}
   971   \end{figure}
   959   \end{figure}
  1032 text \<open>Depending on the situation --- input syntax, output syntax,
  1020 text \<open>Depending on the situation --- input syntax, output syntax,
  1033   translation patterns --- the distinction of atomic ASTs as @{ML
  1021   translation patterns --- the distinction of atomic ASTs as @{ML
  1034   Ast.Constant} versus @{ML Ast.Variable} serves slightly different
  1022   Ast.Constant} versus @{ML Ast.Variable} serves slightly different
  1035   purposes.
  1023   purposes.
  1036 
  1024 
  1037   Input syntax of a term such as @{text "f a b = c"} does not yet
  1025   Input syntax of a term such as \<open>f a b = c\<close> does not yet
  1038   indicate the scopes of atomic entities @{text "f, a, b, c"}: they
  1026   indicate the scopes of atomic entities \<open>f, a, b, c\<close>: they
  1039   could be global constants or local variables, even bound ones
  1027   could be global constants or local variables, even bound ones
  1040   depending on the context of the term.  @{ML Ast.Variable} leaves
  1028   depending on the context of the term.  @{ML Ast.Variable} leaves
  1041   this choice still open: later syntax layers (or translation
  1029   this choice still open: later syntax layers (or translation
  1042   functions) may capture such a variable to determine its role
  1030   functions) may capture such a variable to determine its role
  1043   specifically, to make it a constant, bound variable, free variable
  1031   specifically, to make it a constant, bound variable, free variable
  1045   constants would rather do it via @{ML Ast.Constant} to prevent
  1033   constants would rather do it via @{ML Ast.Constant} to prevent
  1046   accidental re-interpretation later on.
  1034   accidental re-interpretation later on.
  1047 
  1035 
  1048   Output syntax turns term constants into @{ML Ast.Constant} and
  1036   Output syntax turns term constants into @{ML Ast.Constant} and
  1049   variables (free or schematic) into @{ML Ast.Variable}.  This
  1037   variables (free or schematic) into @{ML Ast.Variable}.  This
  1050   information is precise when printing fully formal @{text "\<lambda>"}-terms.
  1038   information is precise when printing fully formal \<open>\<lambda>\<close>-terms.
  1051 
  1039 
  1052   \<^medskip>
  1040   \<^medskip>
  1053   AST translation patterns (\secref{sec:syn-trans}) that
  1041   AST translation patterns (\secref{sec:syn-trans}) that
  1054   represent terms cannot distinguish constants and variables
  1042   represent terms cannot distinguish constants and variables
  1055   syntactically.  Explicit indication of @{text "CONST c"} inside the
  1043   syntactically.  Explicit indication of \<open>CONST c\<close> inside the
  1056   term language is required, unless @{text "c"} is known as special
  1044   term language is required, unless \<open>c\<close> is known as special
  1057   \<^emph>\<open>syntax constant\<close> (see also @{command syntax}).  It is also
  1045   \<^emph>\<open>syntax constant\<close> (see also @{command syntax}).  It is also
  1058   possible to use @{command syntax} declarations (without mixfix
  1046   possible to use @{command syntax} declarations (without mixfix
  1059   annotation) to enforce that certain unqualified names are always
  1047   annotation) to enforce that certain unqualified names are always
  1060   treated as constant within the syntax machinery.
  1048   treated as constant within the syntax machinery.
  1061 
  1049 
  1062   The situation is simpler for ASTs that represent types or sorts,
  1050   The situation is simpler for ASTs that represent types or sorts,
  1063   since the concrete syntax already distinguishes type variables from
  1051   since the concrete syntax already distinguishes type variables from
  1064   type constants (constructors).  So @{text "('a, 'b) foo"}
  1052   type constants (constructors).  So \<open>('a, 'b) foo\<close>
  1065   corresponds to an AST application of some constant for @{text foo}
  1053   corresponds to an AST application of some constant for \<open>foo\<close>
  1066   and variable arguments for @{text "'a"} and @{text "'b"}.  Note that
  1054   and variable arguments for \<open>'a\<close> and \<open>'b\<close>.  Note that
  1067   the postfix application is merely a feature of the concrete syntax,
  1055   the postfix application is merely a feature of the concrete syntax,
  1068   while in the AST the constructor occurs in head position.\<close>
  1056   while in the AST the constructor occurs in head position.\<close>
  1069 
  1057 
  1070 
  1058 
  1071 subsubsection \<open>Authentic syntax names\<close>
  1059 subsubsection \<open>Authentic syntax names\<close>
  1076   Since syntax transformations do not know about this later name
  1064   Since syntax transformations do not know about this later name
  1077   resolution, there can be surprises in boundary cases.
  1065   resolution, there can be surprises in boundary cases.
  1078 
  1066 
  1079   \<^emph>\<open>Authentic syntax names\<close> for @{ML Ast.Constant} avoid this
  1067   \<^emph>\<open>Authentic syntax names\<close> for @{ML Ast.Constant} avoid this
  1080   problem: the fully-qualified constant name with a special prefix for
  1068   problem: the fully-qualified constant name with a special prefix for
  1081   its formal category (@{text "class"}, @{text "type"}, @{text
  1069   its formal category (\<open>class\<close>, \<open>type\<close>, \<open>const\<close>, \<open>fixed\<close>) represents the information faithfully
  1082   "const"}, @{text "fixed"}) represents the information faithfully
       
  1083   within the untyped AST format.  Accidental overlap with free or
  1070   within the untyped AST format.  Accidental overlap with free or
  1084   bound variables is excluded as well.  Authentic syntax names work
  1071   bound variables is excluded as well.  Authentic syntax names work
  1085   implicitly in the following situations:
  1072   implicitly in the following situations:
  1086 
  1073 
  1087   \<^item> Input of term constants (or fixed variables) that are
  1074   \<^item> Input of term constants (or fixed variables) that are
  1106 
  1093 
  1107 subsection \<open>Raw syntax and translations \label{sec:syn-trans}\<close>
  1094 subsection \<open>Raw syntax and translations \label{sec:syn-trans}\<close>
  1108 
  1095 
  1109 text \<open>
  1096 text \<open>
  1110   \begin{tabular}{rcll}
  1097   \begin{tabular}{rcll}
  1111     @{command_def "nonterminal"} & : & @{text "theory \<rightarrow> theory"} \\
  1098     @{command_def "nonterminal"} & : & \<open>theory \<rightarrow> theory\<close> \\
  1112     @{command_def "syntax"} & : & @{text "theory \<rightarrow> theory"} \\
  1099     @{command_def "syntax"} & : & \<open>theory \<rightarrow> theory\<close> \\
  1113     @{command_def "no_syntax"} & : & @{text "theory \<rightarrow> theory"} \\
  1100     @{command_def "no_syntax"} & : & \<open>theory \<rightarrow> theory\<close> \\
  1114     @{command_def "translations"} & : & @{text "theory \<rightarrow> theory"} \\
  1101     @{command_def "translations"} & : & \<open>theory \<rightarrow> theory\<close> \\
  1115     @{command_def "no_translations"} & : & @{text "theory \<rightarrow> theory"} \\
  1102     @{command_def "no_translations"} & : & \<open>theory \<rightarrow> theory\<close> \\
  1116     @{attribute_def syntax_ast_trace} & : & @{text attribute} & default @{text false} \\
  1103     @{attribute_def syntax_ast_trace} & : & \<open>attribute\<close> & default \<open>false\<close> \\
  1117     @{attribute_def syntax_ast_stats} & : & @{text attribute} & default @{text false} \\
  1104     @{attribute_def syntax_ast_stats} & : & \<open>attribute\<close> & default \<open>false\<close> \\
  1118   \end{tabular}
  1105   \end{tabular}
  1119   \<^medskip>
  1106   \<^medskip>
  1120 
  1107 
  1121   Unlike mixfix notation for existing formal entities
  1108   Unlike mixfix notation for existing formal entities
  1122   (\secref{sec:notation}), raw syntax declarations provide full access
  1109   (\secref{sec:notation}), raw syntax declarations provide full access
  1141     mode: ('(' ( @{syntax name} | @'output' | @{syntax name} @'output' ) ')')
  1128     mode: ('(' ( @{syntax name} | @'output' | @{syntax name} @'output' ) ')')
  1142     ;
  1129     ;
  1143     transpat: ('(' @{syntax nameref} ')')? @{syntax string}
  1130     transpat: ('(' @{syntax nameref} ')')? @{syntax string}
  1144   \<close>}
  1131   \<close>}
  1145 
  1132 
  1146   \<^descr> @{command "nonterminal"}~@{text c} declares a type
  1133   \<^descr> @{command "nonterminal"}~\<open>c\<close> declares a type
  1147   constructor @{text c} (without arguments) to act as purely syntactic
  1134   constructor \<open>c\<close> (without arguments) to act as purely syntactic
  1148   type: a nonterminal symbol of the inner syntax.
  1135   type: a nonterminal symbol of the inner syntax.
  1149 
  1136 
  1150   \<^descr> @{command "syntax"}~@{text "(mode) c :: \<sigma> (mx)"} augments the
  1137   \<^descr> @{command "syntax"}~\<open>(mode) c :: \<sigma> (mx)\<close> augments the
  1151   priority grammar and the pretty printer table for the given print
  1138   priority grammar and the pretty printer table for the given print
  1152   mode (default @{verbatim \<open>""\<close>}). An optional keyword @{keyword_ref
  1139   mode (default @{verbatim \<open>""\<close>}). An optional keyword @{keyword_ref
  1153   "output"} means that only the pretty printer table is affected.
  1140   "output"} means that only the pretty printer table is affected.
  1154 
  1141 
  1155   Following \secref{sec:mixfix}, the mixfix annotation @{text "mx =
  1142   Following \secref{sec:mixfix}, the mixfix annotation \<open>mx =
  1156   template ps q"} together with type @{text "\<sigma> = \<tau>\<^sub>1 \<Rightarrow> \<dots> \<tau>\<^sub>n \<Rightarrow> \<tau>"} and
  1143   template ps q\<close> together with type \<open>\<sigma> = \<tau>\<^sub>1 \<Rightarrow> \<dots> \<tau>\<^sub>n \<Rightarrow> \<tau>\<close> and
  1157   specify a grammar production.  The @{text template} contains
  1144   specify a grammar production.  The \<open>template\<close> contains
  1158   delimiter tokens that surround @{text "n"} argument positions
  1145   delimiter tokens that surround \<open>n\<close> argument positions
  1159   (@{verbatim "_"}).  The latter correspond to nonterminal symbols
  1146   (@{verbatim "_"}).  The latter correspond to nonterminal symbols
  1160   @{text "A\<^sub>i"} derived from the argument types @{text "\<tau>\<^sub>i"} as
  1147   \<open>A\<^sub>i\<close> derived from the argument types \<open>\<tau>\<^sub>i\<close> as
  1161   follows:
  1148   follows:
  1162 
  1149 
  1163     \<^item> @{text "prop"} if @{text "\<tau>\<^sub>i = prop"}
  1150     \<^item> \<open>prop\<close> if \<open>\<tau>\<^sub>i = prop\<close>
  1164 
  1151 
  1165     \<^item> @{text "logic"} if @{text "\<tau>\<^sub>i = (\<dots>)\<kappa>"} for logical type
  1152     \<^item> \<open>logic\<close> if \<open>\<tau>\<^sub>i = (\<dots>)\<kappa>\<close> for logical type
  1166     constructor @{text "\<kappa> \<noteq> prop"}
  1153     constructor \<open>\<kappa> \<noteq> prop\<close>
  1167 
  1154 
  1168     \<^item> @{text any} if @{text "\<tau>\<^sub>i = \<alpha>"} for type variables
  1155     \<^item> \<open>any\<close> if \<open>\<tau>\<^sub>i = \<alpha>\<close> for type variables
  1169 
  1156 
  1170     \<^item> @{text "\<kappa>"} if @{text "\<tau>\<^sub>i = \<kappa>"} for nonterminal @{text "\<kappa>"}
  1157     \<^item> \<open>\<kappa>\<close> if \<open>\<tau>\<^sub>i = \<kappa>\<close> for nonterminal \<open>\<kappa>\<close>
  1171     (syntactic type constructor)
  1158     (syntactic type constructor)
  1172 
  1159 
  1173   Each @{text "A\<^sub>i"} is decorated by priority @{text "p\<^sub>i"} from the
  1160   Each \<open>A\<^sub>i\<close> is decorated by priority \<open>p\<^sub>i\<close> from the
  1174   given list @{text "ps"}; missing priorities default to 0.
  1161   given list \<open>ps\<close>; missing priorities default to 0.
  1175 
  1162 
  1176   The resulting nonterminal of the production is determined similarly
  1163   The resulting nonterminal of the production is determined similarly
  1177   from type @{text "\<tau>"}, with priority @{text "q"} and default 1000.
  1164   from type \<open>\<tau>\<close>, with priority \<open>q\<close> and default 1000.
  1178 
  1165 
  1179   \<^medskip>
  1166   \<^medskip>
  1180   Parsing via this production produces parse trees @{text
  1167   Parsing via this production produces parse trees \<open>t\<^sub>1, \<dots>, t\<^sub>n\<close> for the argument slots.  The resulting parse tree is
  1181   "t\<^sub>1, \<dots>, t\<^sub>n"} for the argument slots.  The resulting parse tree is
  1168   composed as \<open>c t\<^sub>1 \<dots> t\<^sub>n\<close>, by using the syntax constant \<open>c\<close> of the syntax declaration.
  1182   composed as @{text "c t\<^sub>1 \<dots> t\<^sub>n"}, by using the syntax constant @{text
       
  1183   "c"} of the syntax declaration.
       
  1184 
  1169 
  1185   Such syntactic constants are invented on the spot, without formal
  1170   Such syntactic constants are invented on the spot, without formal
  1186   check wrt.\ existing declarations.  It is conventional to use plain
  1171   check wrt.\ existing declarations.  It is conventional to use plain
  1187   identifiers prefixed by a single underscore (e.g.\ @{text
  1172   identifiers prefixed by a single underscore (e.g.\ \<open>_foobar\<close>).  Names should be chosen with care, to avoid clashes
  1188   "_foobar"}).  Names should be chosen with care, to avoid clashes
       
  1189   with other syntax declarations.
  1173   with other syntax declarations.
  1190 
  1174 
  1191   \<^medskip>
  1175   \<^medskip>
  1192   The special case of copy production is specified by @{text
  1176   The special case of copy production is specified by \<open>c = \<close>@{verbatim \<open>""\<close>} (empty string).  It means that the
  1193   "c = "}@{verbatim \<open>""\<close>} (empty string).  It means that the
  1177   resulting parse tree \<open>t\<close> is copied directly, without any
  1194   resulting parse tree @{text "t"} is copied directly, without any
       
  1195   further decoration.
  1178   further decoration.
  1196 
  1179 
  1197   \<^descr> @{command "no_syntax"}~@{text "(mode) decls"} removes grammar
  1180   \<^descr> @{command "no_syntax"}~\<open>(mode) decls\<close> removes grammar
  1198   declarations (and translations) resulting from @{text decls}, which
  1181   declarations (and translations) resulting from \<open>decls\<close>, which
  1199   are interpreted in the same manner as for @{command "syntax"} above.
  1182   are interpreted in the same manner as for @{command "syntax"} above.
  1200 
  1183 
  1201   \<^descr> @{command "translations"}~@{text rules} specifies syntactic
  1184   \<^descr> @{command "translations"}~\<open>rules\<close> specifies syntactic
  1202   translation rules (i.e.\ macros) as first-order rewrite rules on
  1185   translation rules (i.e.\ macros) as first-order rewrite rules on
  1203   ASTs (\secref{sec:ast}).  The theory context maintains two
  1186   ASTs (\secref{sec:ast}).  The theory context maintains two
  1204   independent lists translation rules: parse rules (@{verbatim "=>"}
  1187   independent lists translation rules: parse rules (@{verbatim "=>"}
  1205   or @{text "\<rightharpoonup>"}) and print rules (@{verbatim "<="} or @{text "\<leftharpoondown>"}).
  1188   or \<open>\<rightharpoonup>\<close>) and print rules (@{verbatim "<="} or \<open>\<leftharpoondown>\<close>).
  1206   For convenience, both can be specified simultaneously as parse~/
  1189   For convenience, both can be specified simultaneously as parse~/
  1207   print rules (@{verbatim "=="} or @{text "\<rightleftharpoons>"}).
  1190   print rules (@{verbatim "=="} or \<open>\<rightleftharpoons>\<close>).
  1208 
  1191 
  1209   Translation patterns may be prefixed by the syntactic category to be
  1192   Translation patterns may be prefixed by the syntactic category to be
  1210   used for parsing; the default is @{text logic} which means that
  1193   used for parsing; the default is \<open>logic\<close> which means that
  1211   regular term syntax is used.  Both sides of the syntax translation
  1194   regular term syntax is used.  Both sides of the syntax translation
  1212   rule undergo parsing and parse AST translations
  1195   rule undergo parsing and parse AST translations
  1213   \secref{sec:tr-funs}, in order to perform some fundamental
  1196   \secref{sec:tr-funs}, in order to perform some fundamental
  1214   normalization like @{text "\<lambda>x y. b \<leadsto> \<lambda>x. \<lambda>y. b"}, but other AST
  1197   normalization like \<open>\<lambda>x y. b \<leadsto> \<lambda>x. \<lambda>y. b\<close>, but other AST
  1215   translation rules are \<^emph>\<open>not\<close> applied recursively here.
  1198   translation rules are \<^emph>\<open>not\<close> applied recursively here.
  1216 
  1199 
  1217   When processing AST patterns, the inner syntax lexer runs in a
  1200   When processing AST patterns, the inner syntax lexer runs in a
  1218   different mode that allows identifiers to start with underscore.
  1201   different mode that allows identifiers to start with underscore.
  1219   This accommodates the usual naming convention for auxiliary syntax
  1202   This accommodates the usual naming convention for auxiliary syntax
  1223 
  1206 
  1224   Atomic ASTs are distinguished as @{ML Ast.Constant} versus @{ML
  1207   Atomic ASTs are distinguished as @{ML Ast.Constant} versus @{ML
  1225   Ast.Variable} as follows: a qualified name or syntax constant
  1208   Ast.Variable} as follows: a qualified name or syntax constant
  1226   declared via @{command syntax}, or parse tree head of concrete
  1209   declared via @{command syntax}, or parse tree head of concrete
  1227   notation becomes @{ML Ast.Constant}, anything else @{ML
  1210   notation becomes @{ML Ast.Constant}, anything else @{ML
  1228   Ast.Variable}.  Note that @{text CONST} and @{text XCONST} within
  1211   Ast.Variable}.  Note that \<open>CONST\<close> and \<open>XCONST\<close> within
  1229   the term language (\secref{sec:pure-grammar}) allow to enforce
  1212   the term language (\secref{sec:pure-grammar}) allow to enforce
  1230   treatment as constants.
  1213   treatment as constants.
  1231 
  1214 
  1232   AST rewrite rules @{text "(lhs, rhs)"} need to obey the following
  1215   AST rewrite rules \<open>(lhs, rhs)\<close> need to obey the following
  1233   side-conditions:
  1216   side-conditions:
  1234 
  1217 
  1235     \<^item> Rules must be left linear: @{text "lhs"} must not contain
  1218     \<^item> Rules must be left linear: \<open>lhs\<close> must not contain
  1236     repeated variables.\footnote{The deeper reason for this is that AST
  1219     repeated variables.\footnote{The deeper reason for this is that AST
  1237     equality is not well-defined: different occurrences of the ``same''
  1220     equality is not well-defined: different occurrences of the ``same''
  1238     AST could be decorated differently by accidental type-constraints or
  1221     AST could be decorated differently by accidental type-constraints or
  1239     source position information, for example.}
  1222     source position information, for example.}
  1240 
  1223 
  1241     \<^item> Every variable in @{text "rhs"} must also occur in @{text
  1224     \<^item> Every variable in \<open>rhs\<close> must also occur in \<open>lhs\<close>.
  1242     "lhs"}.
  1225 
  1243 
  1226   \<^descr> @{command "no_translations"}~\<open>rules\<close> removes syntactic
  1244   \<^descr> @{command "no_translations"}~@{text rules} removes syntactic
       
  1245   translation rules, which are interpreted in the same manner as for
  1227   translation rules, which are interpreted in the same manner as for
  1246   @{command "translations"} above.
  1228   @{command "translations"} above.
  1247 
  1229 
  1248   \<^descr> @{attribute syntax_ast_trace} and @{attribute
  1230   \<^descr> @{attribute syntax_ast_trace} and @{attribute
  1249   syntax_ast_stats} control diagnostic output in the AST normalization
  1231   syntax_ast_stats} control diagnostic output in the AST normalization
  1276   an intermediate form according to \figref{fig:parse-print}.  The AST
  1258   an intermediate form according to \figref{fig:parse-print}.  The AST
  1277   is normalized by applying translation rules in the manner of a
  1259   is normalized by applying translation rules in the manner of a
  1278   first-order term rewriting system.  We first examine how a single
  1260   first-order term rewriting system.  We first examine how a single
  1279   rule is applied.
  1261   rule is applied.
  1280 
  1262 
  1281   Let @{text "t"} be the abstract syntax tree to be normalized and
  1263   Let \<open>t\<close> be the abstract syntax tree to be normalized and
  1282   @{text "(lhs, rhs)"} some translation rule.  A subtree @{text "u"}
  1264   \<open>(lhs, rhs)\<close> some translation rule.  A subtree \<open>u\<close>
  1283   of @{text "t"} is called \<^emph>\<open>redex\<close> if it is an instance of @{text
  1265   of \<open>t\<close> is called \<^emph>\<open>redex\<close> if it is an instance of \<open>lhs\<close>; in this case the pattern \<open>lhs\<close> is said to match the
  1284   "lhs"}; in this case the pattern @{text "lhs"} is said to match the
  1266   object \<open>u\<close>.  A redex matched by \<open>lhs\<close> may be
  1285   object @{text "u"}.  A redex matched by @{text "lhs"} may be
  1267   replaced by the corresponding instance of \<open>rhs\<close>, thus
  1286   replaced by the corresponding instance of @{text "rhs"}, thus
  1268   \<^emph>\<open>rewriting\<close> the AST \<open>t\<close>.  Matching requires some notion
  1287   \<^emph>\<open>rewriting\<close> the AST @{text "t"}.  Matching requires some notion
       
  1288   of \<^emph>\<open>place-holders\<close> in rule patterns: @{ML Ast.Variable} serves
  1269   of \<^emph>\<open>place-holders\<close> in rule patterns: @{ML Ast.Variable} serves
  1289   this purpose.
  1270   this purpose.
  1290 
  1271 
  1291   More precisely, the matching of the object @{text "u"} against the
  1272   More precisely, the matching of the object \<open>u\<close> against the
  1292   pattern @{text "lhs"} is performed as follows:
  1273   pattern \<open>lhs\<close> is performed as follows:
  1293 
  1274 
  1294   \<^item> Objects of the form @{ML Ast.Variable}~@{text "x"} or @{ML
  1275   \<^item> Objects of the form @{ML Ast.Variable}~\<open>x\<close> or @{ML
  1295   Ast.Constant}~@{text "x"} are matched by pattern @{ML
  1276   Ast.Constant}~\<open>x\<close> are matched by pattern @{ML
  1296   Ast.Constant}~@{text "x"}.  Thus all atomic ASTs in the object are
  1277   Ast.Constant}~\<open>x\<close>.  Thus all atomic ASTs in the object are
  1297   treated as (potential) constants, and a successful match makes them
  1278   treated as (potential) constants, and a successful match makes them
  1298   actual constants even before name space resolution (see also
  1279   actual constants even before name space resolution (see also
  1299   \secref{sec:ast}).
  1280   \secref{sec:ast}).
  1300 
  1281 
  1301   \<^item> Object @{text "u"} is matched by pattern @{ML
  1282   \<^item> Object \<open>u\<close> is matched by pattern @{ML
  1302   Ast.Variable}~@{text "x"}, binding @{text "x"} to @{text "u"}.
  1283   Ast.Variable}~\<open>x\<close>, binding \<open>x\<close> to \<open>u\<close>.
  1303 
  1284 
  1304   \<^item> Object @{ML Ast.Appl}~@{text "us"} is matched by @{ML
  1285   \<^item> Object @{ML Ast.Appl}~\<open>us\<close> is matched by @{ML
  1305   Ast.Appl}~@{text "ts"} if @{text "us"} and @{text "ts"} have the
  1286   Ast.Appl}~\<open>ts\<close> if \<open>us\<close> and \<open>ts\<close> have the
  1306   same length and each corresponding subtree matches.
  1287   same length and each corresponding subtree matches.
  1307 
  1288 
  1308   \<^item> In every other case, matching fails.
  1289   \<^item> In every other case, matching fails.
  1309 
  1290 
  1310 
  1291 
  1311   A successful match yields a substitution that is applied to @{text
  1292   A successful match yields a substitution that is applied to \<open>rhs\<close>, generating the instance that replaces \<open>u\<close>.
  1312   "rhs"}, generating the instance that replaces @{text "u"}.
       
  1313 
  1293 
  1314   Normalizing an AST involves repeatedly applying translation rules
  1294   Normalizing an AST involves repeatedly applying translation rules
  1315   until none are applicable.  This works yoyo-like: top-down,
  1295   until none are applicable.  This works yoyo-like: top-down,
  1316   bottom-up, top-down, etc.  At each subtree position, rules are
  1296   bottom-up, top-down, etc.  At each subtree position, rules are
  1317   chosen in order of appearance in the theory definitions.
  1297   chosen in order of appearance in the theory definitions.
  1327   concrete syntax.  Recall that AST constants appear as quoted strings
  1307   concrete syntax.  Recall that AST constants appear as quoted strings
  1328   and variables without quotes.
  1308   and variables without quotes.
  1329   \end{warn}
  1309   \end{warn}
  1330 
  1310 
  1331   \begin{warn}
  1311   \begin{warn}
  1332   If @{attribute_ref eta_contract} is set to @{text "true"}, terms
  1312   If @{attribute_ref eta_contract} is set to \<open>true\<close>, terms
  1333   will be @{text "\<eta>"}-contracted \<^emph>\<open>before\<close> the AST rewriter sees
  1313   will be \<open>\<eta>\<close>-contracted \<^emph>\<open>before\<close> the AST rewriter sees
  1334   them.  Thus some abstraction nodes needed for print rules to match
  1314   them.  Thus some abstraction nodes needed for print rules to match
  1335   may vanish.  For example, @{text "Ball A (\<lambda>x. P x)"} would contract
  1315   may vanish.  For example, \<open>Ball A (\<lambda>x. P x)\<close> would contract
  1336   to @{text "Ball A P"} and the standard print rule would fail to
  1316   to \<open>Ball A P\<close> and the standard print rule would fail to
  1337   apply.  This problem can be avoided by hand-written ML translation
  1317   apply.  This problem can be avoided by hand-written ML translation
  1338   functions (see also \secref{sec:tr-funs}), which is in fact the same
  1318   functions (see also \secref{sec:tr-funs}), which is in fact the same
  1339   mechanism used in built-in @{keyword "binder"} declarations.
  1319   mechanism used in built-in @{keyword "binder"} declarations.
  1340   \end{warn}
  1320   \end{warn}
  1341 \<close>
  1321 \<close>
  1343 
  1323 
  1344 subsection \<open>Syntax translation functions \label{sec:tr-funs}\<close>
  1324 subsection \<open>Syntax translation functions \label{sec:tr-funs}\<close>
  1345 
  1325 
  1346 text \<open>
  1326 text \<open>
  1347   \begin{matharray}{rcl}
  1327   \begin{matharray}{rcl}
  1348     @{command_def "parse_ast_translation"} & : & @{text "theory \<rightarrow> theory"} \\
  1328     @{command_def "parse_ast_translation"} & : & \<open>theory \<rightarrow> theory\<close> \\
  1349     @{command_def "parse_translation"} & : & @{text "theory \<rightarrow> theory"} \\
  1329     @{command_def "parse_translation"} & : & \<open>theory \<rightarrow> theory\<close> \\
  1350     @{command_def "print_translation"} & : & @{text "theory \<rightarrow> theory"} \\
  1330     @{command_def "print_translation"} & : & \<open>theory \<rightarrow> theory\<close> \\
  1351     @{command_def "typed_print_translation"} & : & @{text "theory \<rightarrow> theory"} \\
  1331     @{command_def "typed_print_translation"} & : & \<open>theory \<rightarrow> theory\<close> \\
  1352     @{command_def "print_ast_translation"} & : & @{text "theory \<rightarrow> theory"} \\
  1332     @{command_def "print_ast_translation"} & : & \<open>theory \<rightarrow> theory\<close> \\
  1353     @{ML_antiquotation_def "class_syntax"} & : & @{text "ML antiquotation"} \\
  1333     @{ML_antiquotation_def "class_syntax"} & : & \<open>ML antiquotation\<close> \\
  1354     @{ML_antiquotation_def "type_syntax"} & : & @{text "ML antiquotation"} \\
  1334     @{ML_antiquotation_def "type_syntax"} & : & \<open>ML antiquotation\<close> \\
  1355     @{ML_antiquotation_def "const_syntax"} & : & @{text "ML antiquotation"} \\
  1335     @{ML_antiquotation_def "const_syntax"} & : & \<open>ML antiquotation\<close> \\
  1356     @{ML_antiquotation_def "syntax_const"} & : & @{text "ML antiquotation"} \\
  1336     @{ML_antiquotation_def "syntax_const"} & : & \<open>ML antiquotation\<close> \\
  1357   \end{matharray}
  1337   \end{matharray}
  1358 
  1338 
  1359   Syntax translation functions written in ML admit almost arbitrary
  1339   Syntax translation functions written in ML admit almost arbitrary
  1360   manipulations of inner syntax, at the expense of some complexity and
  1340   manipulations of inner syntax, at the expense of some complexity and
  1361   obscurity in the implementation.
  1341   obscurity in the implementation.
  1390   @{command print_ast_translation} : \\
  1370   @{command print_ast_translation} : \\
  1391   \quad @{ML_type "(string * (Proof.context -> Ast.ast list -> Ast.ast)) list"} \\
  1371   \quad @{ML_type "(string * (Proof.context -> Ast.ast list -> Ast.ast)) list"} \\
  1392   \end{tabular}}
  1372   \end{tabular}}
  1393   \<^medskip>
  1373   \<^medskip>
  1394 
  1374 
  1395   The argument list consists of @{text "(c, tr)"} pairs, where @{text
  1375   The argument list consists of \<open>(c, tr)\<close> pairs, where \<open>c\<close> is the syntax name of the formal entity involved, and \<open>tr\<close> a function that translates a syntax form \<open>c args\<close> into
  1396   "c"} is the syntax name of the formal entity involved, and @{text
  1376   \<open>tr ctxt args\<close> (depending on the context).  The Isabelle/ML
  1397   "tr"} a function that translates a syntax form @{text "c args"} into
  1377   naming convention for parse translations is \<open>c_tr\<close> and for
  1398   @{text "tr ctxt args"} (depending on the context).  The Isabelle/ML
  1378   print translations \<open>c_tr'\<close>.
  1399   naming convention for parse translations is @{text "c_tr"} and for
       
  1400   print translations @{text "c_tr'"}.
       
  1401 
  1379 
  1402   The @{command_ref print_syntax} command displays the sets of names
  1380   The @{command_ref print_syntax} command displays the sets of names
  1403   associated with the translation functions of a theory under @{text
  1381   associated with the translation functions of a theory under \<open>parse_ast_translation\<close> etc.
  1404   "parse_ast_translation"} etc.
  1382 
  1405 
  1383   \<^descr> \<open>@{class_syntax c}\<close>, \<open>@{type_syntax c}\<close>,
  1406   \<^descr> @{text "@{class_syntax c}"}, @{text "@{type_syntax c}"},
  1384   \<open>@{const_syntax c}\<close> inline the authentic syntax name of the
  1407   @{text "@{const_syntax c}"} inline the authentic syntax name of the
       
  1408   given formal entities into the ML source.  This is the
  1385   given formal entities into the ML source.  This is the
  1409   fully-qualified logical name prefixed by a special marker to
  1386   fully-qualified logical name prefixed by a special marker to
  1410   indicate its kind: thus different logical name spaces are properly
  1387   indicate its kind: thus different logical name spaces are properly
  1411   distinguished within parse trees.
  1388   distinguished within parse trees.
  1412 
  1389 
  1413   \<^descr> @{text "@{const_syntax c}"} inlines the name @{text "c"} of
  1390   \<^descr> \<open>@{const_syntax c}\<close> inlines the name \<open>c\<close> of
  1414   the given syntax constant, having checked that it has been declared
  1391   the given syntax constant, having checked that it has been declared
  1415   via some @{command syntax} commands within the theory context.  Note
  1392   via some @{command syntax} commands within the theory context.  Note
  1416   that the usual naming convention makes syntax constants start with
  1393   that the usual naming convention makes syntax constants start with
  1417   underscore, to reduce the chance of accidental clashes with other
  1394   underscore, to reduce the chance of accidental clashes with other
  1418   names occurring in parse trees (unqualified constants etc.).
  1395   names occurring in parse trees (unqualified constants etc.).
  1422 subsubsection \<open>The translation strategy\<close>
  1399 subsubsection \<open>The translation strategy\<close>
  1423 
  1400 
  1424 text \<open>The different kinds of translation functions are invoked during
  1401 text \<open>The different kinds of translation functions are invoked during
  1425   the transformations between parse trees, ASTs and syntactic terms
  1402   the transformations between parse trees, ASTs and syntactic terms
  1426   (cf.\ \figref{fig:parse-print}).  Whenever a combination of the form
  1403   (cf.\ \figref{fig:parse-print}).  Whenever a combination of the form
  1427   @{text "c x\<^sub>1 \<dots> x\<^sub>n"} is encountered, and a translation function
  1404   \<open>c x\<^sub>1 \<dots> x\<^sub>n\<close> is encountered, and a translation function
  1428   @{text "f"} of appropriate kind is declared for @{text "c"}, the
  1405   \<open>f\<close> of appropriate kind is declared for \<open>c\<close>, the
  1429   result is produced by evaluation of @{text "f [x\<^sub>1, \<dots>, x\<^sub>n]"} in ML.
  1406   result is produced by evaluation of \<open>f [x\<^sub>1, \<dots>, x\<^sub>n]\<close> in ML.
  1430 
  1407 
  1431   For AST translations, the arguments @{text "x\<^sub>1, \<dots>, x\<^sub>n"} are ASTs.  A
  1408   For AST translations, the arguments \<open>x\<^sub>1, \<dots>, x\<^sub>n\<close> are ASTs.  A
  1432   combination has the form @{ML "Ast.Constant"}~@{text "c"} or @{ML
  1409   combination has the form @{ML "Ast.Constant"}~\<open>c\<close> or @{ML
  1433   "Ast.Appl"}~@{text "["}@{ML Ast.Constant}~@{text "c, x\<^sub>1, \<dots>, x\<^sub>n]"}.
  1410   "Ast.Appl"}~\<open>[\<close>@{ML Ast.Constant}~\<open>c, x\<^sub>1, \<dots>, x\<^sub>n]\<close>.
  1434   For term translations, the arguments are terms and a combination has
  1411   For term translations, the arguments are terms and a combination has
  1435   the form @{ML Const}~@{text "(c, \<tau>)"} or @{ML Const}~@{text "(c, \<tau>)
  1412   the form @{ML Const}~\<open>(c, \<tau>)\<close> or @{ML Const}~\<open>(c, \<tau>)
  1436   $ x\<^sub>1 $ \<dots> $ x\<^sub>n"}.  Terms allow more sophisticated transformations
  1413   $ x\<^sub>1 $ \<dots> $ x\<^sub>n\<close>.  Terms allow more sophisticated transformations
  1437   than ASTs do, typically involving abstractions and bound
  1414   than ASTs do, typically involving abstractions and bound
  1438   variables. \<^emph>\<open>Typed\<close> print translations may even peek at the type
  1415   variables. \<^emph>\<open>Typed\<close> print translations may even peek at the type
  1439   @{text "\<tau>"} of the constant they are invoked on, although some
  1416   \<open>\<tau>\<close> of the constant they are invoked on, although some
  1440   information might have been suppressed for term output already.
  1417   information might have been suppressed for term output already.
  1441 
  1418 
  1442   Regardless of whether they act on ASTs or terms, translation
  1419   Regardless of whether they act on ASTs or terms, translation
  1443   functions called during the parsing process differ from those for
  1420   functions called during the parsing process differ from those for
  1444   printing in their overall behaviour:
  1421   printing in their overall behaviour:
  1491   translation functions, parse trees are transformed to ASTs by
  1468   translation functions, parse trees are transformed to ASTs by
  1492   stripping out delimiters and copy productions, while retaining some
  1469   stripping out delimiters and copy productions, while retaining some
  1493   source position information from input tokens.
  1470   source position information from input tokens.
  1494 
  1471 
  1495   The Pure syntax provides predefined AST translations to make the
  1472   The Pure syntax provides predefined AST translations to make the
  1496   basic @{text "\<lambda>"}-term structure more apparent within the
  1473   basic \<open>\<lambda>\<close>-term structure more apparent within the
  1497   (first-order) AST representation, and thus facilitate the use of
  1474   (first-order) AST representation, and thus facilitate the use of
  1498   @{command translations} (see also \secref{sec:syn-trans}).  This
  1475   @{command translations} (see also \secref{sec:syn-trans}).  This
  1499   covers ordinary term application, type application, nested
  1476   covers ordinary term application, type application, nested
  1500   abstraction, iterated meta implications and function types.  The
  1477   abstraction, iterated meta implications and function types.  The
  1501   effect is illustrated on some representative input strings is as
  1478   effect is illustrated on some representative input strings is as
  1503 
  1480 
  1504   \begin{center}
  1481   \begin{center}
  1505   \begin{tabular}{ll}
  1482   \begin{tabular}{ll}
  1506   input source & AST \\
  1483   input source & AST \\
  1507   \hline
  1484   \hline
  1508   @{text "f x y z"} & @{verbatim "(f x y z)"} \\
  1485   \<open>f x y z\<close> & @{verbatim "(f x y z)"} \\
  1509   @{text "'a ty"} & @{verbatim "(ty 'a)"} \\
  1486   \<open>'a ty\<close> & @{verbatim "(ty 'a)"} \\
  1510   @{text "('a, 'b)ty"} & @{verbatim "(ty 'a 'b)"} \\
  1487   \<open>('a, 'b)ty\<close> & @{verbatim "(ty 'a 'b)"} \\
  1511   @{text "\<lambda>x y z. t"} & @{verbatim \<open>("_abs" x ("_abs" y ("_abs" z t)))\<close>} \\
  1488   \<open>\<lambda>x y z. t\<close> & @{verbatim \<open>("_abs" x ("_abs" y ("_abs" z t)))\<close>} \\
  1512   @{text "\<lambda>x :: 'a. t"} & @{verbatim \<open>("_abs" ("_constrain" x 'a) t)\<close>} \\
  1489   \<open>\<lambda>x :: 'a. t\<close> & @{verbatim \<open>("_abs" ("_constrain" x 'a) t)\<close>} \\
  1513   @{text "\<lbrakk>P; Q; R\<rbrakk> \<Longrightarrow> S"} & @{verbatim \<open>("Pure.imp" P ("Pure.imp" Q ("Pure.imp" R S)))\<close>} \\
  1490   \<open>\<lbrakk>P; Q; R\<rbrakk> \<Longrightarrow> S\<close> & @{verbatim \<open>("Pure.imp" P ("Pure.imp" Q ("Pure.imp" R S)))\<close>} \\
  1514    @{text "['a, 'b, 'c] \<Rightarrow> 'd"} & @{verbatim \<open>("fun" 'a ("fun" 'b ("fun" 'c 'd)))\<close>} \\
  1491    \<open>['a, 'b, 'c] \<Rightarrow> 'd\<close> & @{verbatim \<open>("fun" 'a ("fun" 'b ("fun" 'c 'd)))\<close>} \\
  1515   \end{tabular}
  1492   \end{tabular}
  1516   \end{center}
  1493   \end{center}
  1517 
  1494 
  1518   Note that type and sort constraints may occur in further places ---
  1495   Note that type and sort constraints may occur in further places ---
  1519   translations need to be ready to cope with them.  The built-in
  1496   translations need to be ready to cope with them.  The built-in
  1566   For the actual printing process, the priority grammar
  1543   For the actual printing process, the priority grammar
  1567   (\secref{sec:priority-grammar}) plays a vital role: productions are
  1544   (\secref{sec:priority-grammar}) plays a vital role: productions are
  1568   used as templates for pretty printing, with argument slots stemming
  1545   used as templates for pretty printing, with argument slots stemming
  1569   from nonterminals, and syntactic sugar stemming from literal tokens.
  1546   from nonterminals, and syntactic sugar stemming from literal tokens.
  1570 
  1547 
  1571   Each AST application with constant head @{text "c"} and arguments
  1548   Each AST application with constant head \<open>c\<close> and arguments
  1572   @{text "t\<^sub>1"}, \dots, @{text "t\<^sub>n"} (for @{text "n = 0"} the AST is
  1549   \<open>t\<^sub>1\<close>, \dots, \<open>t\<^sub>n\<close> (for \<open>n = 0\<close> the AST is
  1573   just the constant @{text "c"} itself) is printed according to the
  1550   just the constant \<open>c\<close> itself) is printed according to the
  1574   first grammar production of result name @{text "c"}.  The required
  1551   first grammar production of result name \<open>c\<close>.  The required
  1575   syntax priority of the argument slot is given by its nonterminal
  1552   syntax priority of the argument slot is given by its nonterminal
  1576   @{text "A\<^sup>(\<^sup>p\<^sup>)"}.  The argument @{text "t\<^sub>i"} that corresponds to the
  1553   \<open>A\<^sup>(\<^sup>p\<^sup>)\<close>.  The argument \<open>t\<^sub>i\<close> that corresponds to the
  1577   position of @{text "A\<^sup>(\<^sup>p\<^sup>)"} is printed recursively, and then put in
  1554   position of \<open>A\<^sup>(\<^sup>p\<^sup>)\<close> is printed recursively, and then put in
  1578   parentheses \<^emph>\<open>if\<close> its priority @{text "p"} requires this.  The
  1555   parentheses \<^emph>\<open>if\<close> its priority \<open>p\<close> requires this.  The
  1579   resulting output is concatenated with the syntactic sugar according
  1556   resulting output is concatenated with the syntactic sugar according
  1580   to the grammar production.
  1557   to the grammar production.
  1581 
  1558 
  1582   If an AST application @{text "(c x\<^sub>1 \<dots> x\<^sub>m)"} has more arguments than
  1559   If an AST application \<open>(c x\<^sub>1 \<dots> x\<^sub>m)\<close> has more arguments than
  1583   the corresponding production, it is first split into @{text "((c x\<^sub>1
  1560   the corresponding production, it is first split into \<open>((c x\<^sub>1
  1584   \<dots> x\<^sub>n) x\<^sub>n\<^sub>+\<^sub>1 \<dots> x\<^sub>m)"} and then printed recursively as above.
  1561   \<dots> x\<^sub>n) x\<^sub>n\<^sub>+\<^sub>1 \<dots> x\<^sub>m)\<close> and then printed recursively as above.
  1585 
  1562 
  1586   Applications with too few arguments or with non-constant head or
  1563   Applications with too few arguments or with non-constant head or
  1587   without a corresponding production are printed in prefix-form like
  1564   without a corresponding production are printed in prefix-form like
  1588   @{text "f t\<^sub>1 \<dots> t\<^sub>n"} for terms.
  1565   \<open>f t\<^sub>1 \<dots> t\<^sub>n\<close> for terms.
  1589 
  1566 
  1590   Multiple productions associated with some name @{text "c"} are tried
  1567   Multiple productions associated with some name \<open>c\<close> are tried
  1591   in order of appearance within the grammar.  An occurrence of some
  1568   in order of appearance within the grammar.  An occurrence of some
  1592   AST variable @{text "x"} is printed as @{text "x"} outright.
  1569   AST variable \<open>x\<close> is printed as \<open>x\<close> outright.
  1593 
  1570 
  1594   \<^medskip>
  1571   \<^medskip>
  1595   White space is \<^emph>\<open>not\<close> inserted automatically.  If
  1572   White space is \<^emph>\<open>not\<close> inserted automatically.  If
  1596   blanks (or breaks) are required to separate tokens, they need to be
  1573   blanks (or breaks) are required to separate tokens, they need to be
  1597   specified in the mixfix declaration (\secref{sec:mixfix}).
  1574   specified in the mixfix declaration (\secref{sec:mixfix}).