# [ptm.h] Type: Parse Tree / Term

## contents

#include "otab.h"
#include "binimg.h"
#include "list.h"
#include "sink.h"

## Parse Tree

       [ptm] implements the parse i.e. derivation tree as special term data type.

       Term representation

         Three forms of term representation are supported by the construction functions.

         C: This is an efficient representation which lacks an explicit list node
            for the childs of a nonterminal node.

         Xaron: This is a Lisp-like representation with an explicit list node
                for the childs of a nonterminal node. ( used by the xaron project )

         ABS: This is a special optimized representation of the abstract parse tree only
              with all keywords and comments discarded. For a traversal of the tree you
              must use the abstract variant of the generated function interface.

       Definition of the symbol position

         1. Terminal         : Position of the first terminal character
         2. Nonterminal      : Position of the first terminal character if exists
         3. Empty production : Position of the first character of the next terminal

## Types

PT_Term | Abstract parse tree type
PT_Itr | Abstract parse tree iterator type

## Construction & Disposing

    PT_Term PT_newTNode(symbol cfgsym, short symcls, symbol value)

C: creates a node for
token 'cfgsym' of type 'symcls' and 'value'

    PT_Term XPT_newTNode(symbol cfgsym, short symcls, symbol value)

Xaron: creates a node for
token 'cfgsym' of type 'symcls' and 'value'

    PT_Term PT_newNtNode(symbol cfgsym, symbol prdsym, PT_Term parts)

C: creates a node for nonterminal 'cfgsym',
production 'prdsym' and child nodes 'parts'

    PT_Term XPT_newNtNode(symbol cfgsym, symbol prdsym, List(PT_Term) parts)

Xaron: creates a node for nonterminal 'cfgsym',
production 'prdsym' and child nodes 'parts'

    PT_Term PT_updVal(PT_Term PTree, Any_T value)

updates token node 'PTree' with 'value'; returns 'PTree'

    PT_Term PT_updPos(PT_Term PTree, symbol file, long row, long col)

updates node 'PTree' with the position 'file', 'row' and 'col';
returns 'PTree'

    PT_Term PT_consT(PT_Term left, PT_Term right)

C: child node concatenation:
child list = cons('left','right')

    List(PT_Term) XPT_consT(PT_Term left, List(PT_Term) right)

Xaron: child node concatenation:
child list = cons('left','right')

    PT_Term PT_copyPos(PT_Term left, PT_Term right)

assigns position of node 'right' to node 'left';
returns 'left'

    PT_Term PT_copyNode(PT_Term PTree)

copies node 'PTree' ( without child nodes )

    void PT_delT(PT_Term PTree)

removes parse tree / term 'PTree'

## Accessing

Recognizer

    c_bool PT_isXaron(PT_Term PTree)

whether 'PTree' is a Xaron-konform parse tree / term

    c_bool PT_isNonTerm(PT_Term PTree)

whether 'PTree' starts with a nonterminal node

    c_bool PT_isCFG(PT_Term PTree)

whether 'PTree' is an embedded language node

    c_bool PT_isToken(PT_Term PTree)

whether 'PTree' is a token node

    c_bool PT_isKey(PT_Term PTree)

whether 'PTree' is a keyword node

    c_bool PT_isComment(PT_Term PTree)

whether 'PTree' is a comment node

    c_bool PT_hasPos(PT_Term PTree)

whether node 'PTree' contains position informations

Selection

    symbol PT_product(PT_Term PTree)

production symbol of node 'PTree';
assertion: PT_isNonTerm(PTree)

    symbol PT_symbol(PT_Term PTree)

symbol of node 'PTree' ( NT,T )

    short PT_symtyp(PT_Term PTree)

symbol type of node 'PTree' ( NT/T, see [cfg_dfn] )

    symbol PT_value(PT_Term PTree)

token value of node 'PTree'
assertion: ! PT_isNonTerm(PTree) && ! PT_isCFG(PTree)

    PT_Term PT_cfg(PT_Term PTree)

embedded language of node 'PTree'
assertion: PT_isCFG(PTree)

    symbol PT_file(PT_Term PTree)

position - source file of node 'PTree'
assertion: PT_hasPos(PTree)

    long PT_row(PT_Term PTree)

position - source line of node 'PTree'
assertion: PT_hasPos(PTree)

    long PT_col(PT_Term PTree)

position - source column of node 'PTree'
assertion: PT_hasPos(PTree)

    PT_Term PT_next(PT_Term PTree)

C: next node / rest of child list 'PTree' or NULL

    PT_Term PT_parts(PT_Term PTree)

C: child list ( first node ) of node 'PTree'
assertion: PT_isNonTerm(PTree)

    List(PT_Term) XPT_parts(PT_Term PTree)

Xaron: child list of node 'PTree'
assertion: PT_isNonTerm(PTree)

    List(PT_Term)* XPT_parts_ref(PT_Term PTree)

Xaron: pointer reference to child list of node 'PTree'
assertion: PT_isNonTerm(PTree)

Convenience macros for identifying a certain nonterminal, token or production

    #define PT_THISNTM(t,s) ( ( PT_isNonTerm(t) && PT_symbol(t)  == (s) ) ? \
                              C_True : C_False )
    #define PT_THISTOK(t,s) ( ( PT_isToken(t)   && PT_symbol(t)  == (s) ) ? \
                              C_True : C_False )
    #define PT_THISPRD(t,p) ( ( PT_isNonTerm(t) && PT_product(t) == (p) ) ? \
                              C_True : C_False )

## Searching

    int PT_cntST_ex
        (
          PT_Term PTree, c_bool (*filter)(PT_Term PTree, Any_T any), Any_T any
        )

number of nodes t within child list of node 'PTree'
sacrifying condition filter(t,any) = False

    int PT_cntST(PT_Term PTree, c_bool (*filter)(PT_Term PTree))

number of nodes t within child list of node 'PTree'
sacrifying condition filter(t) = False

    PT_Term PT_nthST_ex
            (
              PT_Term PTree, int nth,
              c_bool (*filter)(PT_Term PTree, Any_T any), Any_T any
            )

'nth' node t within child list of node 'PTree'
sacrifying condition filter(t,any) = False
[nth=1..PT_cntST_ex]

    PT_Term PT_nthST(PT_Term PTree, int nth, c_bool (*filter)(PT_Term PTree))

'nth' node t within child list of node 'PTree'
sacrifying condition filter(t) = False
[nth=1..PT_cntST]

    int PT_symbolCnt(PT_Term PTree, symbol cfgsym, c_bool filter)

filter --> number of nodes with symbol 'cfgsym'
else --> number of token and nonterminal nodes
( skipping keywords and comments )
within child list of node 'PTree'

    PT_Term PT_nthSymbol(PT_Term PTree, symbol cfgsym, int nth, c_bool filter)

filter --> 'nth' node with symbol 'cfgsym'
else --> 'nth' token or nonterminal node
( skipping keywords and comments )
within child list of node 'PTree' [nth=1..PT_symbolCnt]

    PT_Term PT_nthMember(PT_Term PTree, int nth)

'nth' token, keyword or nonterminal node
( skipping comments )
within child list of node 'PTree' [nth=1..PT_symbolCnt]

    PT_Term PT_r_find
            (
              PT_Term PTree, c_bool (*pred)(PT_Term PTree, StdCPtr any), StdCPtr any
            )

first subterm t of parse tree / term 'PTree'
sacrifying condition pred(t,any) ( recursive )

    PT_Term PT_l_find
            (
              PT_Term PTree, c_bool (*pred)(PT_Term PTree, StdCPtr any), StdCPtr any
            )

first subterm t of parse tree / term 'PTree'
sacrifying condition pred(t,any) ( non-recursive )

## Term Iterator

Traversal order

All nodes will be visited in pre and post order.

    #define PT_ROOT   1 // root / start order
    #define PT_PRAE   2 // pre order
    #define PT_POST   3 // post order

    PT_Itr PT_newIT(PT_Term PTree)

creates an iterator for parse tree / term 'PTree'

    void PT_delIT(PT_Itr iter)

removes term iterator 'iter'

    PT_Itr PT_copyIT(PT_Itr iter)

copies term iterator 'iter'

    short PT_stateIT(PT_Itr iter)

current traversal order of term iterator 'iter'
( PT_PRAE / PT_POST )

    PT_Term PT_termIT(PT_Itr iter)

current node of term iterator 'iter'

    OT_Tab PT_stackIT(PT_Itr iter)

current node stack of term iterator 'iter'

    c_bool PT_df_getIT(PT_Itr iter)

next node of term iterator 'iter'
in depth first, prae/post order ;
returns False on end-of-term

    c_bool PT_bf_getIT(PT_Itr iter)

next node of term iterator 'iter'
in breast first, prae/post order;
returns False on end-of-term

    c_bool PT_filterIT(PT_Itr iter, c_bool (*get)(PT_Itr iter))

next node of term iterator 'iter' in prae/post order
sacrifying filter condition get(iter),
skipping comments and keywords;
returns False on end-of-term i.e. notfound

    void PT_skipIT(PT_Itr iter)

skips subterms of current node in term iterator 'iter'
assertion: current traversal order = PT_PRAE

## Convenient iterator macros

     For - statement with basic iterators. Make sure to
         free the iterator if you leave the loop via break.

    #define PT_FORALL(it,tr)      for( (it)   = PT_newIT(tr);            \
                                       ( PT_df_getIT(it) )               \
                                       ? C_True : ( PT_delIT(it), C_False ); )
    #define PT_FORALL_F(it,tr)    for( (it)   = PT_newIT(tr);            \
                                       ( PT_filterIT(it,PT_df_getIT) )   \
                                       ? C_True : ( PT_delIT(it), C_False ); )
    #define PT_FORALL_BF(it,tr)   for( (it)   = PT_newIT(tr);            \
                                       ( PT_bf_getIT(it) )               \
                                       ? C_True : ( PT_delIT(it), C_False ); )
    #define PT_FORALL_BF_F(it,tr) for( (it)   = PT_newIT(tr);            \
                                       ( PT_filterIT(it,PT_bf_getIT) )   \
                                       ? C_True : ( PT_delIT(it), C_False ); )
    #define PT_BREAK(it)          { PT_delIT(it); break; }

## Hashing & Predicates

    long PT_hash(PT_Term PTree)

hash value of parse tree / term 'PTree'

    c_bool PT_equal(PT_Term left, PT_Term right)

term 'left' = term 'right' ?

    c_bool PT_subterm(PT_Term left, PT_Term right)

term 'left' <= term 'right' ?

## Binary Image

    void PT_fputT(BinImg_T img, PT_Term PTree)

unloads parse tree / term 'PTree'
to binary image 'img' (reentrant)

    void PT_putT(PT_Term PTree)

unloads parse tree / term 'PTree'
to the current ( previously opened ) image

    void PT_fgetT(BinImg_T img, PT_Term* PTree)

loads parse tree / term 'PTree'
from binary image 'img' (reentrant)

    void PT_getT(PT_Term* PTree)

loads parse tree / term 'PTree'
from the current ( previously opened ) image

## Printing

    void PT_prind(PT_Term PTree, int ind)

prints parse tree / term 'PTree' to stdout
( with indent 'ind' )

    void PT_prind_utf8(PT_Term PTree, int ind)

prints utf8 parse tree / term 'PTree' to stdout
( with indent 'ind' )

    void PT_prind_rawutf8(PT_Term PTree, int ind)

prints utf8 parse tree / term 'PTree' to stdout
( printable ascii or hex, with indent 'ind' )

    void PT_print(PT_Term PTree)

prints parse tree / term 'PTree' to stdout

    void PT_print_utf8(PT_Term PTree)

prints utf8 parse tree / term 'PTree' to stdout

    void PT_print_rawutf8(PT_Term PTree)

prints utf8 parse tree / term 'PTree' to stdout
( printable ascii or hex )

    void PT_TermToString(PT_Term PTree)

prints value of parse tree / term 'PTree' to stdout

    void PT_TermToSink(PT_Term PTree, Sink snk)

prints value of parse tree / term 'PTree' to sink 'snk'
( without comments )

## Normalizer

    PT_Term PT_keycom_Skip(PT_Term x)

C: skips comment and keyword nodes in child list 'x';
returns first token / nonterminal node or NULL

    List(PT_Term) XPT_keycom_Skip(List(PT_Term) x)

Xaron: skips comment and keyword nodes in child list 'x';
returns next token / nonterminal node or NULL

    PT_Term PT_ignkey_Skip(PT_Term x, ROW(PT_Term) coms)

skips 'ign#'-production, comment and keyword nodes
in parse tree / term 'x', collecting comment nodes in 'coms';
returns next token / nonterminal node

    PT_Term PT_ign_Skip(PT_Term x)

skips 'ign#'-production, comment and keyword nodes
in parse tree / term 'x';
returns next token / nonterminal node

## Xaron Support

    void PT_references(PT_Term x, StdCPtr (*act)(StdCPtr r))

performs 'act' on all pointer and symbol references in node 'x'
( garbage collection service for xaron )

## Parse Tree (ABS)

       The above mentioned special optimzed form of an abstract parse tree can be
       produced with the following - non-reentrant - unload/load-API.

             parse tree         --- unload --->
                                                  binary image
             parse tree (ABS)  <---  load  ---

## Types & Macros

PT_Abs_Term | Abstract parse tree type [ABS]

    #define PT_Abs_nonterm(X)   ((symbol)(((long __HUGE*)(X))[0]))
    #define PT_Abs_token(X)     ((symbol)(((long __HUGE*)(X))[0]))
    #define PT_Abs_product(X)   ((symbol)(((long __HUGE*)(X))[1]))
    #define PT_Abs_value(X)     ((symbol)(((long __HUGE*)(X))[2]))
    #define PT_Abs_part(X,N)    ((PT_Abs_Term)(((long __HUGE*)(X))[2+(N)]))
    #define PT_Abs_cfg(X)       ((PT_Abs_Term)(((long __HUGE*)(X))[2+(1)]))

    #define PT_Abs_isToken(X)   (PT_Abs_product(X) == (symbol)NULL)
    #define PT_Abs_isNonTerm(X) (PT_Abs_product(X) != (symbol)NULL)
    #define PT_Abs_isCFG(X) \
      (PT_Abs_product(X) == (symbol)NULL && PT_Abs_value(X) == NULL)

## Init & Quit

    void PT_putBgn(void)

initializes abstract term putting

    void PT_putEnd(void)

quits abstract term putting

    void PT_getBgn(void)

initializes abstract term getting

    void PT_getEnd(void)

quits abstract term getting

## Put & Get

    long PT_Symbol_to_Ref(symbol s)

reference corresponding to symbol 's'

    long PT_putSymbol(symbol s)

creates a reference for symbol 's'

    void PT_putAllSymbols(void)

puts all symbol references
to the current ( previously opened ) binary image

    void PT_getAllSymbols(void)

gets all symbol references
from the current ( previously opened ) binary image

    symbol PT_getSymbol(long RefId)

symbol corresponding to reference 'RefId'

    long PT_Term_to_Ref(PT_Term PTree)

abstract term reference corresponding to parse tree 'PTree'
( unload phase )

    PT_Abs_Term PT_Ref_to_Term(long __HUGE* nodes, long RefId)

abstract term in node array 'nodes'
corresponding to reference 'RefId'
( load phase )

    long PT_putAbsNode(PT_Term PTree)

creates an abstract term reference for parse tree 'PTree'

    void PT_putAbsT(void)

puts all abstract term references
to the current ( previously opened ) binary image

    long __HUGE* PT_getAbsT(void)

gets all abstract term references
from the current ( previously opened ) binary image

    long __HUGE* PT_patchAbsT(long __HUGE* nodes)

patches all abstract term references
in node array 'nodes'; returns 'nodes'

## Disposing

    void PT_delAbsT(long __HUGE* nodes)

removes node array 'nodes' with abstract term references