Syntax tree - transitional mode

This chapter presents the Camlp5 syntax tree when Camlp5 is installed in transitional mode.

  1. Introduction
  2. Location
  3. Antiquotations
  4. Nodes and Quotations

Introduction

This syntax tree is defined in the module "MLast" provided by Camlp5. Each node corresponds to a syntactic entity of the corresponding type.

For example, the syntax tree of the statement "if" can be written:

  MLast.ExIfe loc e1 e2 e3

where "loc" is the location in the source, and "e1", "e2" and "e3" are respectively the expression after the "if", the one after the "then" and the one after the "else".

If a program needs to manipulate syntax trees, it can use the nodes defined in the module "MLast". The programmer must know how the concrete syntax is transformed into this abstract syntax.

A simpler solution is to use one of the quotation kit "q_MLast.cmo". It proposes quotations which represent the abstract syntax (the nodes of the module "MLast") into concrete syntax with antiquotations to bind variables inside. The example above can be written:

  <:expr< if $e1$ then $e2$ else $e3$ >>

This representation is very interesting when one wants to manipulate complicated syntax trees. Here is an example taken from the Camlp5 sources themselves:

  <:expr<
    match try Some $f$ with [ Stream.Failure -> None ] with
    [ Some $p$ -> $e$
    | _ -> raise (Stream.Error $e2$) ]
  >>

This example was in a position of a pattern. In abstract syntax, it should have been written:

  MLast.ExMat _
    (MLast.ExTry _ (MLast.ExApp _ (MLast.ExUid _ "Some") f)
       [(MLast.PaAcc _ (MLast.PaUid _ "Stream") (MLast.PaUid _ "Failure"),
         None, MLast.ExUid _ "None")])
    [(MLast.PaApp _ (MLast.PaUid _ "Some") p, None, e);
     (MLast.PaAny _, None,
      MLast.ExApp _ (MLast.ExLid _ "raise")
        (MLast.ExApp _
           (MLast.ExAcc _ (MLast.ExUid _ "Stream") (MLast.ExUid _ "Error"))
           e2))]

Which is less readable and much more complicated to build and update.

Instead of thinking of "a syntax tree", the programmer can think of "a piece of program".

Location

In all syntax tree nodes, the first parameter is the source location of the node.

In expressions

When a quotation is in the context of an expression, the location parameter is "loc" in the node and in all its possible sub-nodes. Example: if we consider the quotation:

  <:sig_item< value foo : int -> bool >>

This quotation, in a context of an expression, is equivalent to:

  MLast.SgVal loc "foo"
    (MLast.TyArr loc (MLast.TyLid loc "int") (MLast.TyLid loc "bool"));

The name "loc" is predefined. However, it is possible to change it, using the argument "-loc" of the Camlp5 shell commands.

Consequently, if there is no variable "loc" defined in the context of the quotation, or if it is not of the correct type, a semantic error occur in the OCaml compiler ("Unbound value loc").

Note that in the extensible grammars, the variable "loc" is bound, in all semantic actions, to the location of the rule.

Note that in the extensible grammars, the variable "loc" is bound, in all semantic actions, to the location of the rule.

If the created node has no location, the programmer can define a variable named "loc" equal to "Ploc.dummy".

In patterns

When a quotation is in the context of a pattern, the location parameter of all nodes and possible sub-nodes is set to the wildcard ("_"). The same example above:

  <:sig_item< value foo : int -> bool >>

is equivalent, in a pattern, to:

  MLast.SgVal _ "foo"
    (MLast.TyArr _ (MLast.TyLid _ "int") (MLast.TyLid _ "int"))

Antiquotations

The expressions or patterns between dollar ($) characters are called antiquotations. In opposition to quotations which has its own syntax rules, the antiquotation is an area in the syntax of the enclosing context (expression or pattern). See the chapter about quotations.

If a quotation is in the context of an expression, the antiquotation must be an expression. It can be any expression, including function calls. Examples:

  value f e el = <:expr< [$e$ :: $loop False el$] >>;
  value patt_list p pl = <:patt< ( $list:[p::pl]$) >>;

If a quotation is in the context of an pattern, the antiquotation is a pattern. Any pattern is possible, including the wildcard character ("_"). Examples:

   fun [ <:expr< $lid:op$ $_$ $_$ >> -> op ]
   match p with [ <:patt< $_$ | $_$ >> -> Some p ]

Nodes and Quotations

This section describes all nodes defined in the module "MLast" of Camlp5 and how to write them with quotations. Notice that, inside quotations, one is not restricted to these elementary cases, but any complex value can be used, resulting on possibly complex combined nodes.

Variables names give information of their types:

expr

Expressions of the language.

Node <:expr< ... >> Comment
ExAcc loc e1 e2 $e1$ . $e2$ dot
ExAnt loc e $anti:e$ antiquotation (1)
ExApp loc e1 e2 $e1$ $e2$ application
ExAre loc e1 e2 $e1$ .( $e2$ ) array access
ExArr loc le [| $list:le$ |] array
ExAsr loc e assert $e$ assert
ExAss loc e1 e2 $e1$ := $e2$ assignment
ExBae loc e le $e$ .{ $le$ } big array access
ExChr loc s $chr:s$ character constant
ExCoe loc e (Some t1) t2 ($e$ : $t1$ :> $t2$) coercion
ExCoe loc e None t2 ($e$ :> $t2$) coercion
ExFlo loc s $flo:s$ float constant
ExFor loc s e1 e2 b le for $s$ = $e1$ $to:b$ $e2$ do { $list:le$ } for
ExFun loc lopee fun [ $list:lpoee$ ] function (2)
ExIfe loc e1 e2 e3 if $e1$ then $e2$ else $e3$ if
ExInt loc s "" $int:s$ integer constant
ExInt loc s "l" $int32:s$ integer 32 bits
ExInt loc s "L" $int64:s$ integer 64 bits
ExInt loc s "n" $nativeint:s$ native integer
ExLab loc s None ~ $s$ label
ExLab loc s (Some e) ~ $s$ : $e$ label
ExLaz loc e lazy $e$ lazy
ExLet loc b lpe e let $flag:b$ $list:lpe$ in $e$ let binding
ExLid loc s $lid:s$ lowercase identifier
ExLmd loc s me e let module $s$ = $me$ in $e$ let module
ExMat loc e lpoee match $e$ with [ $list:lpoee$ ] match (2)
ExNew loc ls new $list:ls$ new
ExObj loc op lcstri object $opt:op$ $list:lcstri$ end object expression
ExOlb loc s None ? $s$ option label
ExOlb loc s (Some e) ? $s$ : $e$ option label
ExOvr loc lse {< $lse$ >} override
ExRec loc lpe None { $list:lpe$ } record
ExRec loc lpe (Some e) { ($e$) with $list:lpe$ } record
ExSeq loc le do { $list:le$ } sequence
ExSnd loc e s $e$ # $s$ method call
ExSte loc e1 e2 $e1$ .[ $e2$ ] string element
ExStr loc s $str:s$ string
ExTry loc e lpoee try $e$ with [ $list:lpoee$ ] try (2)
ExTup loc le ($list:le$) t-uple
ExTyc loc e t ($e$ : $t$) type constraint
ExUid loc s $uid:s$ uppercase identifier
ExVrn loc s ` $s$ variant
ExWhi loc e le while $e$ do { $list:le$ } while
(1)

Node used in the quotation expanders to tells at conversion to OCaml compiler syntax tree time, that all locations of the sub-tree is correcty located in the quotation. By default, in quotations, the locations of all generated nodes are the location of the whole quotation. This node allows to make an exception to this rule, since we know that the antiquotation belongs to the universe of the enclosing program. See the chapter about quotations and, in particular, its section about antiquotations.

(2)

The variable "lpoee" found in "function", "match" and "try" statements correspond to a list of "(patt * option expr * expr)" where the "option expr" is the "when" optionally following the pattern:

  p -> e

is represented by:

  (p, None, e)

and

  p when e1 -> e

is represented by:

  (p, Some e1, e)

patt

Patterns of the language.

Node <:patt< ... >> Comment
PaAcc loc p1 p2 $p1$ . $p2$ dot
PaAli loc p1 p2 ($p1$ as $p2$) alias
PaAnt loc p $anti:p$ antiquotation (1)
PaAny loc _ wildcard
PaApp loc p1 p2 $p1$ $p2$ application
PaArr loc lp [| $list:lp$ |] array
PaChr loc s $chr:s$ character
PaInt loc s1 s2 $int:s$ integer
PaFlo loc s $flo:s$ float
PaLab loc s None ~ $s$ label
PaLab loc s (Some p) ~ $s$ : $p$ label
PaLid loc s $lid:s$ lowercase identifier
PaOlb loc s None ? $s$ option label
PaOlb loc s (Some (p, None)) ? $s$ : ($p$) option label
PaOlb loc s (Some (p, Some e)) ? $s$ : ($p$ = $e$) option label
PaOrp loc p1 p2 $p1$ | $p2$ or
PaRng loc p1 p2 $p1$ .. $p2$ range
PaRec loc lpp None { $list:lpp$ } record
PaStr loc s $str:s$ string
PaTup loc lp ($list:lp$) t-uple
PaTyc loc p t ($p$ : $t$) type constraint
PaTyp loc ls # $list:ls$ type pattern
PaUid loc s $uid:s$ uppercase identifier
PaVrn loc s ` $s$ variant
(1) Node used to specify an antiquotation area, like for the equivalent node in expressions. See above.

ctyp

Type expressions of the language.

Node <:ctyp< ... >> Comment
TyAcc loc t1 t2 $t1$ . $t2$ dot
TyAli loc t1 t2 $t1$ as $t2$ alias
TyAny loc _ wildcard
TyApp loc t1 t2 $t1$ $t2$ application
TyArr loc t1 t2 $t1$ -> $t2$ arrow
TyCls loc ls # $list:ls$ class
TyLab loc s t ~ $s$ : $t$ label
TyLid loc s $lid:s$ lowercase identifier
TyMan loc t1 t2 $t1$ == $t2$ manifest
TyObj loc lst False < $list:lst$ > object
TyObj loc lst True < $list:lst$ .. > object
TyObj loc lst b < $list:lst$ $flag:b$ > object (general)
TyOlb loc s t ? $s$ : $t$ option label
TyPol loc ls t ! $list:ls$ . $t$ polymorph
TyQuo loc s ' $s$ variable
TyRec loc llsbt { $list:llsbt$ } record
TySum loc llslt [ $list:llslt$ ] sum
TyTup loc lt ( $list:lt$ ) t-uple
TyUid loc s $uid:s$ uppercase identifier
TyVrn loc lpv None [ = $list:lpv$ ] variant
TyVrn loc lpv (Some None) [ > $list:lpv$ ] variant
TyVrn loc lpv (Some (Some [])) [ < $list:lpv$ ] variant
TyVrn loc lpv (Some (Some ls)) [ < $list:lpv$ > $list:ls$ ] variant

modules...

str_item

Structure items, i.e. phrases in a ".ml" file or "struct"s elements.

Node <:str_item< ... >> Comment
StCls loc lcd class $list:lcd$ class declaration
StClt loc lcdt class type $list:lctd$ class type declaration
StDcl loc lstri declare $list:lstri$ end declare
StDir loc s None # $s$ directive
StDir loc s (Some e) # $s$ $e$ directive
StDir loc s oe # $s$ $opt:oe$ directive (general)
StExc loc s lt [] exception $s$ of $list:lt$ exception
StExc loc s lt ls exception $s$ of $list:lt$ = $list:ls$ exception
StExp loc e $exp:e$ expression
StExt loc s t ls external $s$ : $t$ = $list:ls$ external
StInc loc me include $me$ include
StMod loc b lsme module $flag:b$ $list:lsme$ module
StMty loc s mt module type $s$ = $mt$ module type
StOpn loc ls open $list:ls$ open
StTyp loc ltd type $list:ltd$ type declaration
StUse loc s lstrib ...internal use... (1)
StVal loc b lpe value $flag:b$ $list:lpe$ value
(1)

Node internally used to specify a different file name applying to the whole subtree. This is generated by the directive "use" and used when converting to the OCaml syntax tree which needs the file name in its location type.

sig_item

Signature items, i.e. phrases in a ".mli" file or "sig"s elements.

Node <:sig_item< ... >> Comment
SgCls loc lcd class $list:lcd$ class
SgClt loc lct class type $list:lct$ class type
SgDcl loc lsigi declare $list:lsigi$ end declare
SgDir loc s None # $s$ directive
SgDir loc s (Some e) # $s$ $e$ directive
SgDir loc s oe # $s$ $opt:oe$ directive (general)
SgExc loc s [] exception $s$ exception
SgExc loc s lt exception $s$ of $list:lt$ exception
SgExt loc s t ls external $s$ : $t$ = $list:ls$ external
SgInc loc me include $me$ include
SgMod loc b lsmt module $flag:b$ $list:lsmt$ module
SgMty loc s mt module type $s$ = $mt$ module type
SgOpn loc ls open $list:ls$ open
SgTyp loc ltd type $list:ltd$ type declaration
SgUse loc s lstrib ...internal use... (1)
SgVal loc s t value $s$ : $t$ value
(1)

Same remark as for "str_item" above.

module_expr

Node <:module_expr< ... >> Comment
MeAcc loc me1 me2 $me1$ . $me2$ dot
MeApp loc me1 me2 $me1$ $me2$ application
MeFun loc s mt me functor ( $s$ : $mt$ ) -> $me$ functor
MeStr loc lstri struct $list:lstri$ end struct
MeTyc loc me mt ( $me$ : $mt$ ) module type constraint
MeUid loc s $uid:s$ uppercase identifier

module_type

Node <:module_type< ... >> Comment
MtAcc loc mt1 mt2 $mt1$ . $mt2$ dot
MtApp loc mt1 mt2 $mt1$ $mt2$ application
MtFun loc s mt1 mt2 functor ( $s$ : $mt1$ ) -> $mt2$ functor
MtLid loc s $lid:s$ lowercase identifier
MtQuo loc s ' $s$ abstract
MtSig loc lsigi sig $list:lsigi$ end signature
MtUid loc s $uid:s$ uppercase identifier
MtWit loc mt lwc $mt$ with $list:lwc$ with construction

classes...

class_expr

Node <:class_expr< ... >> Comment
CeApp loc ce e $ce$ $e$ application
CeCon loc ls lt $list:ls$ [ $list:lt$ ] constructor
CeFun loc p ce fun $p$ -> $ce$ function
CeLet loc b lpe ce let $flag:b$ $list:lpe$ in $ce$ let binding
CeStr loc po lcstri object $opt:op$ $list:lcstri$ end object
CeTyc loc ce ct ($ce$ : $ct$) class type constraint

class_type

Node <:class_type< ... >> Comment
CtCon loc ls lt $list:ls$ [ $list:lt$ ] constructor
CtFun loc t ct [ $t$ ] -> $ct$ arrow
CtSig loc pt None lcsigi_item object $list:lcsigi$ end object
CtSig loc pt (Some t) lcsigi_item object ($t$) $list:lcsigi$ end object
CtSig loc pt ot lcsigi_item object $opt:ot$ $list:lcsigi$ end object (general)

class_str_item

Node <:class_str_item< ... >> Comment
CrCtr loc t1 t2 type $t1$ = $t2$ type constraint
CrDcl loc lcstri declare $list:lcstri$ end declaration list
CrInh loc ce None inherit $ce$ inheritance
CrInh loc ce (Some s) inherit $ce$ as $s$ inheritance
CrInh loc ce os inherit $ce$ $opt:s$ inheritance (general)
CrIni loc e initializer $e$ initialization
CrMth loc s False e None method $s$ = $e$ method
CrMth loc s False e (Some t) method $s$ : $t$ = $e$ method
CrMth loc s True e None method private $s$ = $e$ method
CrMth loc s True e (Some t) method private $s$ : $t$ = $e$ method
CrMth loc s b e ot method $flag:b$ $s$ $opt:ot$ = $e$ method (general)
CrVal loc s False e value $s$ = $e$ value
CrVal loc s True e value mutable $s$ = $e$ value
CrVal loc s b e value $flag:b$ $s$ = $e$ value (general)
CrVir loc s False t method virtual $s$ : $t$ virtual method
CrVir loc s True t method virtual private $s$ : $t$ virtual method
CrVir loc s b t method virtual $flag:b$ $s$ : $t$ virtual method (general)

class_sig_item

Node <:class_sig_item< ... >> Comment
CgCtr loc t1 t2 type $t1$ = $t2$ type constraint
CgDcl loc lcsigi declare $list:lcsigi$ end declare
CgInh loc ct inherit $ct$ inheritance
CgMth loc s False t method $s$ : $t$ method
CgMth loc s True t method private $s$ : $t$ method
CgMth loc s b t method $flag:b$ $s$ : $t$ method (general)
CgVal loc s False t value $s$ : $t$ value
CgVal loc s True t value mutable $s$ : $t$ value
CgVal loc s b t value $flag:b$ $s$ : $t$ value (general)
CgVir loc s False t method virtual $s$ : $t$ method virtual
CgVir loc s True t method virtual private $s$ : $t$ method virtual
CgVir loc s b t method virtual $flag:b$ $s$ : $t$ method virtual (general)

other

with_constr

"With" possibly following a module type.

Node <:with_const< ... >> Comment
WcTyp loc s ltv False t type $s$ $list:ltv$ = $t$ with type
WcTyp loc s ltv True t type $s$ $list:ltv$ = private $t$ with type
WcTyp loc s ltv b t type $s$ $list:ltv$ = $flag:b$ $t$ with type (general)
WcMod loc ls me module $list:ls$ = $me$ with module

poly_variant

Polymorphic variants.

Node <:poly_variant< ... >> Comment
PvTag s False [] ` $i$ constructor
PvTag s True lt ` $i$ of & $list:lt$ constructor
PvTag s b lt ` $i$ of $flag:b$ $list:lt$ constructor (general)
PvInh t $t$ type

Copyright 2007 Daniel de Rauglaudre (INRIA)

Valid XHTML 1.1