6 \newcommand\Constant{\ttfct{Constant}} |
6 \newcommand\Constant{\ttfct{Constant}} |
7 \newcommand\Variable{\ttfct{Variable}} |
7 \newcommand\Variable{\ttfct{Variable}} |
8 \newcommand\Appl[1]{\ttfct{Appl}\,[#1]} |
8 \newcommand\Appl[1]{\ttfct{Appl}\,[#1]} |
9 \index{syntax!transformations|(} |
9 \index{syntax!transformations|(} |
10 |
10 |
11 This chapter is intended for experienced Isabelle users who need to define |
|
12 macros or code their own translation functions. It describes the |
|
13 transformations between parse trees, abstract syntax trees and terms. |
|
14 |
|
15 |
|
16 \section{Abstract syntax trees} \label{sec:asts} |
11 \section{Abstract syntax trees} \label{sec:asts} |
17 \index{ASTs|(} |
12 \index{ASTs|(} |
18 |
|
19 The parser, given a token list from the lexer, applies productions to yield |
|
20 a parse tree\index{parse trees}. By applying some internal transformations |
|
21 the parse tree becomes an abstract syntax tree, or \AST{}. Macro |
|
22 expansion, further translations and finally type inference yields a |
|
23 well-typed term. The printing process is the reverse, except for some |
|
24 subtleties to be discussed later. |
|
25 |
|
26 Figure~\ref{fig:parse_print} outlines the parsing and printing process. |
|
27 Much of the complexity is due to the macro mechanism. Using macros, you |
|
28 can specify most forms of concrete syntax without writing any \ML{} code. |
|
29 |
|
30 \begin{figure} |
|
31 \begin{center} |
|
32 \begin{tabular}{cl} |
|
33 string & \\ |
|
34 $\downarrow$ & lexer, parser \\ |
|
35 parse tree & \\ |
|
36 $\downarrow$ & parse \AST{} translation \\ |
|
37 \AST{} & \\ |
|
38 $\downarrow$ & \AST{} rewriting (macros) \\ |
|
39 \AST{} & \\ |
|
40 $\downarrow$ & parse translation, type inference \\ |
|
41 --- well-typed term --- & \\ |
|
42 $\downarrow$ & print translation \\ |
|
43 \AST{} & \\ |
|
44 $\downarrow$ & \AST{} rewriting (macros) \\ |
|
45 \AST{} & \\ |
|
46 $\downarrow$ & print \AST{} translation \\ |
|
47 string & |
|
48 \end{tabular} |
|
49 |
|
50 \end{center} |
|
51 \caption{Parsing and printing}\label{fig:parse_print} |
|
52 \end{figure} |
|
53 |
13 |
54 Abstract syntax trees are an intermediate form between the raw parse trees |
14 Abstract syntax trees are an intermediate form between the raw parse trees |
55 and the typed $\lambda$-terms. An \AST{} is either an atom (constant or |
15 and the typed $\lambda$-terms. An \AST{} is either an atom (constant or |
56 variable) or a list of {\em at least two\/} subtrees. Internally, they |
16 variable) or a list of {\em at least two\/} subtrees. Internally, they |
57 have type \mltydx{Syntax.ast}: \index{*Constant} \index{*Variable} |
17 have type \mltydx{Syntax.ast}: \index{*Constant} \index{*Variable} |