{============================================================================}
{=                                                                          =}
{=      'PTree.Pas'                                                         =}
{=                                                                          =}
{=          Pascal compiler parse tree routines.                            =}
{=                                                                          =}
{=              12/13/86 - Bruce Tomlin                                     =}
{=                                                                          =}
{============================================================================}

{$R+}   { Turn on range checking in this module }

UNIT PTree;

INTERFACE

USES
    MacDefs,
    Files,
    SymTab,
    Error;  { Error is needed for 'Pause' }

TYPE
    PNodeType = (pAssign,pFOR,pWHILE,pProcCall,pFuncCall,pIF,
                 pInfLoop,pVariable,pArrayRef,pFieldRef,pAdd,
                 pSub,pMult,pIDiv,pRDiv,pNeg,pRealConst,pIntConst,
                 pEq,pNeq,pLt,pLeq,pGt,pGeq,pReal2Int,pInt2Real);

    PNodePtr = ^PNode;
    PTree = PNodePtr;
    PExpr = PNodePtr;

    PNode = RECORD
                typ:        PNodeType;  { The type of the parse tree node }
                next:       PNodePtr;   { Next parse tree node on same level }
                exprType:   SymPtr;     { Variable type of an expression node }

                sym1:       SymPtr;     { Generic symbol pointers }
                sym2:       SymPtr;     { See 'Compiler.Doc' for info }

                tree1:      PNodePtr;   { Generic parse tree node pointers }
                tree2:      PNodePtr;   { See 'Compiler.Doc' for info }
                tree3:      PNodePtr;
                tree4:      PNodePtr;

                intValue:   INTEGER;    { Value for integer constant node }
                realValue:  REAL;       { Value for real constant node }
            END;

FUNCTION  NewPNode(pNodeTyp: PNodeType): PNodePtr;
PROCEDURE FreePTree(VAR tree: PTree);
PROCEDURE DumpPTree(tree: PTree);
PROCEDURE AddTree(VAR tree1: PTree; tree2: PTree);



IMPLEMENTATION

{============================================================================}
{=                                                                          =}
{=      NEWPNODE                                                            =}
{=                                                                          =}
{=          Returns a new parse tree node.                                  =}
{=                                                                          =}
{=      Parameters                                                          =}
{=                                                                          =}
{=          PNODETYP    The type of the new node                            =}
{=                                                                          =}
{============================================================================}

FUNCTION NewPNode(pNodeTyp: PNodeType): PNodePtr;

VAR
    p:      PNodePtr;

BEGIN
    New(p);
    WITH p^ DO BEGIN
        typ  := pNodeTyp;   { Set up the node type }
        next := NIL;        { Clear out all of the other fields }
        exprType := NIL;

        sym1 := NIL;
        sym2 := NIL;

        tree1 := NIL;
        tree2 := NIL;
        tree3 := NIL;
        tree4 := NIL;

        intValue  := 0;
        realValue := 0.0;
    END;
    NewPNode := p;
END;



{============================================================================}
{=                                                                          =}
{=      FREEPTREE                                                           =}
{=                                                                          =}
{=          Frees up the heap memory occupied by a parse tree and sets the  =}
{=          pointer that used to point to it to NIL.                        =}
{=                                                                          =}
{=      Parameters                                                          =}
{=                                                                          =}
{=          TREE        The tree to free up                                 =}
{=                                                                          =}
{============================================================================}

PROCEDURE FreePTree(VAR tree: PTree);

BEGIN
    IF tree<>NIL THEN WITH tree^ DO BEGIN
        FreePTree(tree1);
        FreePTree(tree2);
        FreePTree(tree3);
        FreePTree(tree4);
        FreePTree(next);
        Dispose(tree);
        tree := NIL;
    END;
END;



{============================================================================}
{=                                                                          =}
{=      TABIT                                                               =}
{=                                                                          =}
{=          Tabs in a specified level for PrintPNodes                       =}
{=                                                                          =}
{=      Parameters                                                          =}
{=                                                                          =}
{=          LEVEL       The number of levels to tab                         =}
{=                                                                          =}
{============================================================================}

PROCEDURE TabIt(level: INTEGER);

VAR
    i:      INTEGER;

BEGIN
    FOR i := 1 TO level DO Write(outFile,'':4);
END;



{============================================================================}
{=                                                                          =}
{=      PNODENAME                                                           =}
{=                                                                          =}
{=          Returns the name of each parse tree node type.                  =}
{=                                                                          =}
{=      Parameters                                                          =}
{=                                                                          =}
{=          TYP         The type to get the name of                         =}
{=          STR         The name is returned in this parameter              =}
{=                                                                          =}
{============================================================================}

PROCEDURE PNodeName(typ: PNodeType; VAR str: Str255);

BEGIN
    CASE typ OF
        pAssign:    str := 'pAssign   ';
        pFOR:       str := 'pFOR      ';
        pWHILE:     str := 'pWHILE    ';
        pProcCall:  str := 'pProcCall ';
        pFuncCall:  str := 'pFuncCall ';
        pIF:        str := 'pIF       ';
        pVariable:  str := 'pVariable ';
        pArrayRef:  str := 'pArrayRef ';
        pFieldRef:  str := 'pFieldRef ';
        pAdd:       str := 'pAdd      ';
        pSub:       str := 'pSub      ';
        pMult:      str := 'pMult     ';
        pIDiv:      str := 'pIDiv     ';
        pRDiv:      str := 'pRDiv     ';
        pNeg:       str := 'pNeg      ';
        pRealConst: str := 'pRealConst';
        pIntConst:  str := 'pIntConst ';
        pReal2Int:  str := 'pReal2Int ';
        pInt2Real:  str := 'pInt2Real ';
        pEq:        str := 'pEq       ';
        pNeq:       str := 'pNeq      ';
        pLt:        str := 'pLt       ';
        pGeq:       str := 'pGeq      ';
        pGt:        str := 'pGt       ';
        pLeq:       str := 'pLeq      ';
        OTHERWISE   str := '??????????';
    END;
END;



{============================================================================}
{=                                                                          =}
{=      PRINTPNODES                                                         =}
{=                                                                          =}
{=          Prints out all the nodes in a part of a parse tree.             =}
{=                                                                          =}
{=      Parameters                                                          =}
{=                                                                          =}
{=          NODE        The head of the parse tree to print                 =}
{=          LEVEL       The current tab level                               =}
{=                                                                          =}
{============================================================================}

PROCEDURE PrintPNodes(node: PNodePtr; level: INTEGER);

VAR
    str: Str255;


    {========================================================================}
    {=                                                                      =}
    {=      BRANCH                                                          =}
    {=                                                                      =}
    {=          Prints out a tree branch (a subtree)                        =}
    {=                                                                      =}
    {=      Parameters                                                      =}
    {=                                                                      =}
    {=          BRANCH      The branch to print out                         =}
    {=          DSCR        The description of what the branch is for       =}
    {=                                                                      =}
    {========================================================================}

    PROCEDURE Branch(branch: PTree; dscr: Str255);

    BEGIN
        TabIt(level+1);
        WriteLn(outFile,dscr);
        Pause;
        PrintPNodes(branch,level+2);
        Pause;
    END;


    {========================================================================}
    {=                                                                      =}
    {=      LEAF                                                            =}
    {=                                                                      =}
    {=          Prints out a tree leaf (a symbol pointer)                   =}
    {=                                                                      =}
    {=      Parameters                                                      =}
    {=                                                                      =}
    {=          LEAF        The symbol pointer to print out                 =}
    {=          DSCR        The description of what the branch is for       =}
    {=                                                                      =}
    {========================================================================}

    PROCEDURE Leaf(leaf: SymPtr; dscr: Str255);

    BEGIN
        Tabit(level+1);
        WriteLn(outFile,dscr);
        Pause;
        Tabit(level+2);
        IF leaf=NIL THEN WriteLn(outFile,'NIL')
                    ELSE WriteLn(outFile,leaf^.name^);
        Pause;
    END;


BEGIN { of PrintPNodes }
    WITH node^ DO BEGIN
        IF node=NIL THEN BEGIN
            TabIt(level);
            WriteLn(outFile,'NIL');
            Pause;
        END
        ELSE BEGIN
            TabIt(level);
            PNodeName(typ,str);
            WriteLn(outFile,str);
            Pause;
            CASE typ OF
                pAssign:    BEGIN;
                                Branch(tree1,'tree1 = variable being assigned');
                                Branch(tree2,'tree2 = expression to assign');
                            END;
                pFOR:       BEGIN;
                                Branch(tree1,'tree1 = index variable');
                                Branch(tree2,'tree2 = starting value expression');
                                Branch(tree3,'tree3 = ending value expression');
                                Branch(tree4,'tree4 = statements to execute');
                            END;
                pWHILE:     BEGIN;
                                Branch(tree1,'tree1 = test expression');
                                Branch(tree2,'tree2 = statements to execute');
                            END;
                pProcCall:  BEGIN
                                Leaf(sym1,'sym1 = procedure''s symbol table entry');
                                Branch(tree1,'tree1 = parameter expressions');
                            END;
                pFuncCall:  BEGIN
                                Leaf(sym1,'sym1 = function''s symbol table entry');
                                Branch(tree1,'tree1 = parameter expressions');
                            END;
                pIF:        BEGIN
                                Branch(tree1,'tree1 = test expression');
                                Branch(tree2,'tree2 = true branch statements');
                                Branch(tree3,'tree3 = false branch statements');
                            END;
                pVariable:  BEGIN
                                Leaf(sym1,'sym1 = variable''s symbol table entry');
                            END;
                pArrayRef:  BEGIN
                                Branch(tree1,'tree1 = variable being subscripted');
                                Branch(tree2,'tree2 = subscript expressions');
                            END;
                pFieldRef:  BEGIN
                                Branch(tree1,'tree1 = variable being field-referenced');
                                Leaf(sym1,'sym1 = subfield''s symbol table entry');
                            END;
                pRealConst: BEGIN
                                TabIt(level+1);
                                WriteLn(outFile,'realValue = ',realValue);
                                Pause;
                            END;
                pIntConst:  BEGIN
                                TabIt(level+1);
                                WriteLn(outFile,'intValue = ',intValue);
                                Pause;
                            END;
                pReal2Int:  BEGIN
                                Branch(tree1,'tree1 = expression to make integer');
                            END;
                pInt2Real:  BEGIN
                                Branch(tree1,'tree1 = expression to make real');
                            END;
                pNeg:       BEGIN
                                Branch(tree1,'tree1 = expression to negate');
                            END;
                pAdd,pSub,
                pMult,pIDiv,
                pRDiv,
                pEq,pNeq,
                pLt,pGeq,
                pGt,pLeq:   BEGIN
                                Branch(tree1,'tree1 = left side expression');
                                Branch(tree2,'tree2 = right side expression');
                            END;
            END;
            IF next<>NIL THEN PrintPNodes(next,level);
        END;
    END;
END; { of PrintPNodes }



{============================================================================}
{=                                                                          =}
{=      DUMPPTREE                                                           =}
{=                                                                          =}
{=          Prints out all the nodes in a parse tree.                       =}
{=                                                                          =}
{=      Parameters                                                          =}
{=                                                                          =}
{=          TREE        The head of the parse tree to print                 =}
{=                                                                          =}
{============================================================================}

PROCEDURE DumpPTree(tree: PTree);

BEGIN
    PrintPNodes(tree,0);

    { If outputting to the screen, wait for a key or a click }

    IF screenOut THEN Wait;

    WriteLn(outFile);
END;



{============================================================================}
{=                                                                          =}
{=      ADDTREE                                                             =}
{=                                                                          =}
{=          Adds a new node to the end of a parse tree                      =}
{=                                                                          =}
{=      Parameters                                                          =}
{=                                                                          =}
{=          TREE1       The pointer to a list of parse trees                =}
{=          TREE2       The parse tree to tack on to the end                =}
{=                                                                          =}
{============================================================================}

PROCEDURE AddTree(VAR tree1: PTree; tree2: PTree);

VAR
    p,q:    PTree;

BEGIN
    { Find the last pointer in the list }

    p := tree1;
    q := NIL;
    WHILE p<>NIL DO BEGIN
        q := p;
        p := p^.next;
    END;

    { Set the pointer to point to the new subtree }

    IF q=NIL THEN tree1   := tree2
             ELSE q^.next := tree2;
END;

END.