/* The AST is an n-ary tree whose nodes and leaves are a polymorphic set of records. However rather than a complex data structure involving structs and unions, the actual storage of the AST is done in a single flat array of ints. It is up to the programmer to correlate virtual record fields with offsets into the subarrays which denote each AST cell. There were originally two fixed fields in every AST cell: [0] was the type code (eg AST_Mul) and [1] is a count of the number of integers that follow. Much later during development, when the data structure was already well established, I had to add a new field to almost all records, so I did this by having the AST cell creation functions add a new field *before* the [0]th item. So TYPEINFO(x) is held in AST[(x)-1]. At some later point I may correct this, but it was expedient and avoided the need to renumber every reference to an object in the AST array. */ /* I had a BFO this afternoon... sometimes in the ast-building code I want to pass a lot of info back up to a parent node, but it's not structured info that readily fills an ast object. BFO: create a generic ast object of variable length just for passing data around. (Done. It's called AST_Dummy) */ /* There is a table below (op[]) which holds information about each of the AST types. Each row is indexed by the AST type itself, so it has to be kept in synch with the chain of #defines immediately preceding it. The table could be split up into multiple simple arrays of atoms, rather than one array of structs, which would have made bootstrapping much easier, however from previous experience, keeping all of these parallel arrays in synch was so laborious that the saved effort was worth the cost of having to implement structs in the first iteration of the bootstrapped compiler. */ struct operation { int AST_Code; // switch code. Note, >= AST_BASE which is currently 1000. int Children; // Expected number of children. AST[ap+1] is the actual number, if they // differ. (For instance if we decided to code a*b*c as (AST_Times, 3, a, b, c) // rather than as two binary nodes) char *Diag_Name; // The AST_ name as a string for diags char *C_Name; // for use as label when drawing AST as a tree char *Stack_Name; // This is a mild hack for table-driven code generation. Use this opcode // (with no args, for now) as the generated code if present. // Otherwise go through the code-generation switch as normal. int Display_Children; // used in two places - primary use is now to determine what is a safe // branch to walk with a generic tree-walker (I.e. if allowed, the chilod // is a proper AST_ item; if not it may be a string or something else // secondary use is in automatic display of the AST as a tree - do not // display the child unless it is enabled here. // Least significant bit corresponds to rightmost child, so be careful. }; // would be an enum if we supported it. Maybe after bootstrapping. #define AST_BASE 1000 #define AST_Add 1000 #define AST_Sub 1001 #define AST_Mul 1002 #define AST_Div 1003 #define AST_Mod 1004 #define AST_AddAss 1005 #define AST_SubAss 1006 #define AST_MulAss 1007 #define AST_DivAss 1008 #define AST_ModAss 1009 #define AST_Post_Inc 1010 #define AST_Pre_Inc 1011 #define AST_Post_Dec 1012 #define AST_Pre_Dec 1013 #define AST_Idx 1014 #define AST_Member 1015 #define AST_Ptr 1016 #define AST_Call 1017 #define AST_Cond 1018 #define AST_Type 1019 #define AST_Return 1020 #define AST_ReturnResult 1021 #define AST_LE 1022 #define AST_GT 1023 #define AST_LT 1024 #define AST_GE 1025 #define AST_EQ 1026 #define AST_NE 1027 #define AST_IFTHENELSE 1028 #define AST_IFTHEN 1029 #define AST_UNeg 1030 #define AST_UPos 1031 #define AST_UBitNot 1032 #define AST_UBoolNot 1033 #define AST_BoolAnd 1034 #define AST_BoolOr 1035 #define AST_ShortcutBoolAnd 1036 #define AST_ShortcutBoolOr 1037 #define AST_BitAnd 1038 #define AST_BitOr 1039 #define AST_BitAndAss 1040 #define AST_BitOrAss 1041 #define AST_BitXor 1042 #define AST_BitXorAss 1043 #define AST_BitLsh 1044 #define AST_BitRsh 1045 #define AST_BitLshAss 1046 #define AST_BitRshAss 1047 #define AST_Const 1048 #define AST_Var 1049 #define AST_AssignTo 1050 #define AST_Declare 1051 #define AST_DefProc 1052 #define AST_DefParam 1053 #define AST_ReceiveParam 1054 #define AST_UseParam 1055 #define AST_AddressOf 1056 #define AST_IndirectThrough 1057 #define AST_SizeOf 1058 #define AST_TypeOf 1059 #define AST_C_ForLoop 1060 #define AST_C_While 1061 #define AST_C_DoWhile 1062 #define AST_C_Break 1063 #define AST_C_Continue 1064 #define AST_Cast 1065 #define AST_Label 1066 #define AST_Case 1067 #define AST_DefaultCase 1068 #define AST_Goto 1069 #define AST_Switch 1070 #define AST_Sourceline 1071 #define AST_LINENO 1072 #define AST_REDIRECT 1073 #define AST_SEQ 1074 #define AST_CommaSEQ 1075 #define AST_LINEAR_BLOB 1076 #define AST_TYPE_ArrayOf 1077 // child index lower upper #define AST_TYPE_Struct 1078 // structtypename childlinks structsize #define AST_TYPE_PointerTo 1079 // child #define AST_TYPE_Atom 1080 // NAME bytes signed #define AST_TYPE_StructMember 1081 // next_member this_element #define AST_SHOWTREE 1082 #define AST_TAG 1083 // only operand is integer index into 'c' array #define AST_Scope 1084 // // Scope is not part of the AST tree. Scopes are created and deleted // on the fly, as you walk the AST, generating code etc. // A scope is merely a pointer to the current enclosing block, // and locating a declaration within that block is a simple // linear walk of the code within that block - stopping at the // 'current position' so as not to pick up declarations that // have not yet taken effect. // When walking parent blocks, do not enter sub-compound statements. #define AST_Dummy 1085 #define AST_TOP AST_Dummy // if you added any above, remember to also add to the table below // CURRENTLY THESE *MUST* BE IN THE SAME ORDER AS THE DEFINES ABOVE! // Unless noted otherwise, assume each cell is a simple 2-operand node. /* There is a *small* attempt at table-driving a code generator here, in the cases where an AST node maps directly to an operation, and its arguments (child nodes) can be recursively evaluated in left to right order. This should give the student a taste of what can be done using a table-driven code generator, however it is not taken any further as that is not the primary method to be used in this exercise. Including the stack-based opcodes here does slightly mix the separation between levels that we have been trying to acheive, but that's a fair lesson in itself as a fully clean separation is not always the best strategy. (For example, where do you convert array indexing operations into multiplies and adds? Do it too early and your front-end has to have knowlege of all the target architectures; do it too late and your back-end cannot take advantage of the generic arithmetic optimisations performed on the AST...) */ struct operation op[AST_TOP-AST_BASE+2] = { {AST_Add, 2, "AST_Add", "+", "ADD", 3}, {AST_Sub, 2, "AST_Sub", "-", "SUB", 3}, {AST_Mul, 2, "AST_Mul", "*", "MUL", 3}, {AST_Div, 2, "AST_Div", "/", "DIV", 3}, // Do we need a separate IDIV or will the type mechanism sort it out? {AST_Mod, 2, "AST_Mod", "%", "MOD", 3}, {AST_AddAss, 2, "AST_AddAss", "+=", "ADDI", 3}, {AST_SubAss, 2, "AST_SubAss", "-=", "SUBI", 3}, {AST_MulAss, 2, "AST_MulAss", "*=", "MULI", 3}, {AST_DivAss, 2, "AST_DivAss", "/=", "DIVI", 3}, {AST_ModAss, 2, "AST_ModAss", "%=", "MODI", 3}, {AST_Post_Inc, 1, "AST_Post_Inc", "()++", "", 1}, // TO DO {AST_Pre_Inc, 1, "AST_Pre_Inc", "++()", "", 1}, // TO DO {AST_Post_Dec, 1, "AST_Post_Dec", "()--", "", 1}, // TO DO {AST_Pre_Dec, 1 ,"AST_Pre_Dec", "--()", "", 1}, // TO DO {AST_Idx, 2, "AST_Idx", "[]", "INDEX 4", 3}, // May be subsumed in arithmetic ops before reaching code generator {AST_Member, 2, "AST_Member", ".", "ADDI", 3}, // May be subsumed in arithmetic ops before reaching code generator {AST_Ptr, 2, "AST_Ptr", "->", "ADD", 3}, // May be subsumed in arithmetic ops before reaching code generator {AST_Call, 3, "AST_Call", "()", "", 3<<1}, // "name", UseParam chain, ptr to proc definition {AST_Cond, 3, "AST_Cond", "( ? : )", "", 7}, {AST_Type, 1, "AST_Type", "simple type", "", 1}, // integer representing "int" etc {AST_Return, 1, "AST_Return", "return", "RET 0", 0}, {AST_ReturnResult, 2, "AST_ReturnResult", "return ...", "RET 1", 2}, {AST_LE, 2, "AST_LE", "<=", "CMPLE", 3}, {AST_GT, 2, "AST_GT", ">", "CMPGT", 3}, {AST_LT, 2, "AST_LT", "<", "CMPLT", 3}, {AST_GE, 2, "AST_GE", ">=", "CMPGE", 3}, {AST_EQ, 2, "AST_EQ", "==", "CMPEQ", 3}, {AST_NE, 2, "AST_NE", "!=", "CMPNE", 3}, {AST_IFTHENELSE, 3, "AST_IFTHENELSE", "if () ... else ...", "", 7}, {AST_IFTHEN, 2, "AST_IFTHEN", "if () ...", "", 3}, {AST_UNeg, 1, "AST_UNeg", "-()", "NEG", 1}, {AST_UPos, 1, "AST_UPos", "+()", "NOOP", 1}, {AST_UBitNot, 1, "AST_UBitNot", "~()", "NOT", 1}, {AST_UBoolNot, 1, "AST_UBoolNot", "!()", "BNOT", 1}, {AST_BoolAnd, 2, "AST_BoolAnd", "&&", "BAND", 3}, {AST_BoolOr, 2, "AST_BoolOr", "||", "BOR", 3}, {AST_ShortcutBoolAnd, 2, "AST_ShortcutBoolAnd", "&&", "", 3}, {AST_ShortcutBoolOr, 2, "AST_ShortcutBoolOr", "||", "", 3}, {AST_BitAnd, 2, "AST_BitAnd", "&", "AND", 3}, {AST_BitOr, 2, "AST_BitOr", "|", "OR", 3}, {AST_BitAndAss, 2, "AST_BitAndAss", "&=", "ANDI", 3}, {AST_BitOrAss, 2, "AST_BitOrAss", "|=", "ORI", 3}, {AST_BitXor, 2, "AST_BitXor", "^", "XOR", 3}, {AST_BitXorAss, 2, "AST_BitXorAss", "^=", "XORI", 3}, {AST_BitLsh, 2, "AST_BitLsh", "<<", "LSH", 3}, {AST_BitRsh, 2, "AST_BitRsh", ">>", "RSH", 3}, {AST_BitLshAss, 2, "AST_BitLshAss", "<<=", "LSHI", 3}, {AST_BitRshAss, 2, "AST_BitRshAss", ">>=", "RSHI", 3}, {AST_Const, 2, "AST_Const", "Const", "", 0},// 1st points to C[] item (whence can be found type), 2nd holds bin val for ints // rightchild so far undefined for strings. // - less than useful in summary diags. // proper print finds the argument. {AST_Var, 2, "AST_Var", "Var", "", 0}, // Var was from an earlier design before adding the current // type mechanism. It may soon be dropped. // 1st param is tag, // 2nd param is 'value of' (0) vs 'address of' (1). // Will need to also add a type param later {AST_AssignTo, 2, "AST_AssignTo", "=", "POPI", 3}, {AST_Declare, 3, "AST_Declare", "Decl", "", 7}, // name, type, init assignment {AST_DefProc, 4, "AST_DefProc", "DefProc", "", 15}, // DefProc: ast_type, id, params, body // recently changed defparam and receiveparam from mask=1 to mask=3 - watch for consequences... // and now from 3 to 7... {AST_DefParam, 3, "AST_DefParam", "DefParam", "", 7}, // param name (ident), param type, link to next DefParam {AST_ReceiveParam, 3, "AST_ReceiveParam", "ReceiveParam", "", 7}, // param name (ident), param type, link to next ReceiveParam {AST_UseParam, 2, "AST_UseParam", "Param", "", 3}, {AST_AddressOf, 1, "AST_AddressOf", "&", "", 1}, // may later modify this to add a const offset {AST_IndirectThrough, 1, "AST_IndirectThrough", "*", "PUSHI", 1}, {AST_SizeOf, 2, "AST_SizeOf", "sizeof", "", 0}, // object, class of object (lvalue, expr, type) {AST_TypeOf, 1, "AST_TypeOf", "typeof", "", 1}, // object (assumed always lvalue?) // 1st three extra fields in for loop are label IDs: exit_label, continue_label, branch_back_label // the continue label may not be the same as the branch back label, for do {} while loops which test // at the end. {AST_C_ForLoop, 4+4, "AST_C_ForLoop", "for (;;) ...", "", 15<<4}, {AST_C_While, 2+3, "AST_C_While", "while () ...", "", 3<<3}, {AST_C_DoWhile, 2+3, "AST_C_DoWhile", "do ... while ();", "", 3<<3}, {AST_C_Break, 1, "AST_C_Break", "break", "", 0}, {AST_C_Continue, 1, "AST_C_Continue", "continue", "", 0}, {AST_Cast, 2, "AST_Cast", "()...", "", 2}, {AST_Label, 2, "AST_Label", "lab:", "", 2}, {AST_Case, 3, "AST_Case", "case :", "", 2<<1}, // leftchild = , // rightchild = link to next case // last = internal number for label {AST_DefaultCase, 2, "AST_DefaultCase", "default:", "", 0}, // leftchild = link to next case // rightchild = internal number for label {AST_Goto, 1, "AST_Goto", "goto ...", "", 1}, {AST_Switch, 5, "AST_Switch", "switch (...)", "", 3<<3}, // leftchild = switch value, rightchild = compound statement // 1st extra field is for target of "break" statement, // partly TO DO: 2nd extra field is link to chain of case statements, // partly TO DO: 3rd extra field is default case {AST_Sourceline, 1, "AST_Sourceline", "src", "", 1}, {AST_LINENO, 1, "AST_LINENO", "Line #", "", 1}, {AST_REDIRECT, 1, "AST_REDIRECT", "REDIR", "", 1}, {AST_SEQ, 2, "AST_SEQ", ";", "", 3}, {AST_CommaSEQ, 2, "AST_CommaSEQ", ",", "", 3}, {AST_LINEAR_BLOB, 1, "AST_LINEAR_BLOB", "BLOB", "", 0}, {AST_TYPE_ArrayOf, 5, "AST_TYPE_ArrayOf", "[]", "", 3<<3}, // child index lower upper elsize {AST_TYPE_Struct, 3, "AST_TYPE_Struct", "{}", "", 2}, // StructName StructMemberList structsize {AST_TYPE_PointerTo, 1, "AST_TYPE_PointerTo", "->", "", 1}, // child {AST_TYPE_Atom, 2, "AST_TYPE_Atom", "atom", "", 0}, // signed bytesize {AST_TYPE_StructMember, 4, "AST_TYPE_StructMember", "stmemb", ".", 7<<1}, // next_member tag this_element_type offset #ifdef NEVER {AST_Typed_Object, 3, "AST_Typed_Object", "Obj", "", 5}, // This was intended for intermediate objects with the AST - // but it may go the way of the AST_Var type as well... // 1st param is tag, // 2nd param is 'value of' (0) vs 'address of' (1). // 3rd param is tree of AST_TYPE_* #endif {AST_SHOWTREE, 1, "AST_SHOWTREE", "tree", "tree", 1}, // Internal debugging hack {AST_TAG, 1, "AST_TAG", "tag", "tag", 0}, // All variables are treated as generic tags while building the AST. // They turn into proper variables once the AST is decorated with type information {AST_Scope, 3, "AST_Scope", "scope", "{ { } }", 2<<1}, // following code, parent AST_Scope, type (as in BLOCK_PROCFN) // can't recurse on parent block - infinite recursion // Scope is effectively a '{' ... '}' wrapper. we only care // to distinguish global scope, procdural scope, and syntactically // nested blocks, for the purpose of code generation. Other info // is present but probably won't be used. (eg if/while/do blocks) // TODO: add line number to scope, for diags {AST_Dummy, 10, "AST_Dummy", "dummy", "dummy", 0}, // only used within grammar.c to pass partial results back up the tree {-1, 0, "ERROR IN op[] ARRAY!"} };