Documentation-Two-Pass-Assembler.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Documentation\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Project 1 - Two Pass Assembler\n",
    "\n",
    "### Course: CSE112 Computer Organization <br> \n",
    "\n",
    "Project Members: <br>\n",
    "1. Bhavya Chopra - 2018333  <br>\n",
    "2. Sonali Singhal - 2018317"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Input file should be put in the folder Sample_Inputs. The type of file should be .txt for example \"sampl and when asked for"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Assumptions\n",
    "### Opcode and Operands\n",
    "1. CLA and STP take no operands/arguments\n",
    "2. LAC, SAC, INP, DSP take 1 operand which is an address\n",
    "3. ADD, SUB, MUL, DIV take 1 operand which can be a literal or an address \n",
    "4. BRZ, BRN, BRP take 1 operand which should be a valid label\n",
    "5. If DIV is called, the quotient and remainder get stored in Variables R1 and R2 which can be used in the code later. If DIV is called again, then the value in R1 and R2 will get overwritten.\n",
    "6. SAC and INP can take undefined address as an argument. Rest of the opcodes cannot. (If no valid value is present in an address, it is treated as an undefined address)\n",
    "\n",
    "### General\n",
    "1. Clear accumulator (CLA) resets the accumulator. No address or value is present in the accumulator.\n",
    "2. Execution stops after the end statement. The code written after the end statement is not executed.\n",
    "3. START loads the instructions from the specified address. If no address is specified, instruction set is loaded normally.\n",
    "4. Label name **cannot** be an opcode name and cannot have a Macro name anywhere in it. <br> For example if ADDTWO is a macro, then: \"SUB\", \"ADD\", \"ADDTWOXYZ\" are invalid label names. While this can be handled, it is not considered to be a good programming practice.\n",
    "5. Comments can be added with the help of  **; or /**.\n",
    "6. Literals/Constants can be specified between single quotes \"''\". Example `ADD '3'`\n",
    "6. Variable names and label names can be alpha-numeric. However, the same variable cannot be used as a label name and vice versa.\n",
    "7. Literals can be of any value, contiguous memory spaces are allotted accordingly.\n",
    "8. If the size of the literal uses more than 1 memory space, then only the first is written in the machine code. Exact memory mapping can be seen from the LiteralTable.\n",
    "9. The maximum memory size is 256 words, which can be stored using 8 bit addresses. If the program size is greater than this, the assembler will throw an error and terminate.\n",
    "10. Total instruction length is 12 bit: 8 bit instruction address + 4 bit opcode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Macros\n",
    "1. Macros can be handled.\n",
    "2. Macro is defined at the top of the file before being called.\n",
    "3. Macro calls cannot be made inside other macro definitions.\n",
    "4. There can be more than one macro\n",
    "5. Macros can have labels."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Design"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. Data Table\n",
    "**Contains all the (numeric) addresses defined in the code**\n",
    "1. **Value:** Integer address value\n",
    "2. **Defined/Undefined:** Defined if the address is taking in a value using INP. Eg INP 157, else undefined\n",
    "Example: <br>\n",
    "```\n",
    "INP 157\n",
    "LAC 157\n",
    "DIV 157\n",
    "```\n",
    "\n",
    "|Value|Defined/Undefined|\n",
    "|-----|-----------------|\n",
    "|157  |Defined          |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Label Table\n",
    "**Contains all the Labels defined in the main code and the modified labels created after expanding macro calls.**\n",
    "1. **Label name:** Name of the label as defined in the code\n",
    "2. **Virtual Address:** Virtual address allotted to the label during the first pass\n",
    "3. **Code:** refers to the name of the macro or Main code\n",
    "4. **Physical Address:** Physical address allotted to the label during the second pass\n",
    "\n",
    "Example: <br>\n",
    "```\n",
    "ADDTWO MACRO A,B,C\n",
    "L1: LAC A\n",
    "ADD B\n",
    "SAC C\n",
    "MEND\n",
    "L1: INP 157\n",
    "LAC 157\n",
    "ADDTWO 157 '4' 90\n",
    "``` \n",
    "\n",
    "|Name     |Virtual Address  |Code     |Physical Address|\n",
    "|---------|-----------------|---------|----------------|\n",
    "|L1       |00000000     |Main     |00000010    |\n",
    "|ADDTWOL11|00000010     |ADDTWO   |00000100    |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Symbol Table\n",
    "**Contains all the variables defined in the main code**\n",
    "1. **Name:** Variable name defined in the main code\n",
    "2. **Physical Address:** Physical address allotted to the variable during the second pass\n",
    "\n",
    "Example: <br>\n",
    "```\n",
    "INP A\n",
    "SAC B\n",
    "```\n",
    "\n",
    "|Name |Physical Address |\n",
    "|-----|-----------------|\n",
    "|A    |01001010     |\n",
    "|B    |01001110     |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. Literal Table \n",
    "**Contains all the constants defined in the code**\n",
    "1. **Name:** String value of the constant eg ‘1’\n",
    "2. **Value:** Integer value of the literal\n",
    "3. **Size:** Word size of the literal considering 2s complement for storing data\n",
    "4. **Physical address:** Physical address allotted to the Literal during the second pass\n",
    "\n",
    "Example: <br>\n",
    "```\n",
    "ADD '128'\n",
    "SUB '-20'\n",
    "```\n",
    "\n",
    "|Name     |Value    |Size     |Physical Address           |\n",
    "|---------|---------|---------|---------------------------|\n",
    "|'128'  |128    |2        |[00000010,00000011] |\n",
    "|'-20'    |-20      |1        |00000100               |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5. Macro Table\n",
    "**Contains all the macros and their definitions**\n",
    "1. **Name:** Name of the macro\n",
    "2. **Macro Parameters:** Parameters used with the macro. Eg ADDTWO MACRO A,B,C -> parameters=A,B,C\n",
    "3. **Instruction Table:** Instructions present in the macro without modifications\n",
    "4. **Labels:** Labels defined in the macro without modifications\n",
    "\n",
    "Example: <br>\n",
    "```\n",
    "ADDTWO MACRO A,B,C\n",
    "L1: LAC A\n",
    "ADD B\n",
    "L2: SAC C\n",
    "MEND\n",
    "```\n",
    "|Name     |Macro Parameters |Labels     |Instruction Table               |\n",
    "|---------|-----------------|-----------|--------------------------------|\n",
    "|ADDTWO   |A,B,C            |L1,L2      |[[L1:,LAC,A],<br>[ADD,B],<br>[L2:,SAC,C]|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6. Instruction Table\n",
    "**Contains all the instructions and expanded Macro calls**\n",
    "1. **Virtual Address:** Generates a new virtual address for every instruction\n",
    "2. **Instruction:** the complete instruction\n",
    "When a macro call is encountered, the instructions present in the macro table for the respective macro definition is substituted in the this instruction table\n",
    "\n",
    "Example: <br>\n",
    "```\n",
    "ADDTWO MACRO A,B,C\n",
    "L1: LAC A\n",
    "ADD B\n",
    "SAC C\n",
    "BRP L1\n",
    "MEND\n",
    "L1: INP 157\n",
    "LAC 157\n",
    "ADDTWO 157 '4' 90\n",
    "``` \n",
    "\n",
    "|Virtual Address |Instruction                             |\n",
    "|----------------|----------------------------------------|\n",
    "|00000000    |[L1:,INP,157]                           |\n",
    "|00000001    |[LAC,157]                               |\n",
    "|00000010    |[ADDTWOL11,LAC,157]                     |\n",
    "|00000011    |[ADD,'4']                               |\n",
    "|00000100    |[SAC,90]                                |\n",
    "|00000101    |[BRP,ADDTWOL11]                         |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Error Reporting and handling"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Errors handled in first pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. **Invalid Label name**\n",
    "\n",
    "There are two conditions for a label name to be invalid. Label cannot have a macro name in it and it cannot be an opcode name. This error occus if such a label is detected. Examples: `ADD: SUB 123` or `ADDTWOLR: SUB 123` (assuming a macro named ADDTWO is defined in the code)\n",
    "\n",
    "![error: invalid label name](./Assets/images/error1.png)\n",
    "\n",
    "![error: invalid label name](./Assets/images/error2.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. **Multiple label definitions**\n",
    "\n",
    "This error occurs when a label is defined/declared multiple times. Label declaration includes statements such as `L1: ADD 589`\n",
    "\n",
    "![error: multiple label definitions](./Assets/images/error3.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. **Defined label names cannot be used as variable names and vice versa**\n",
    "\n",
    "Since both label names and variable names can be alpha-numeric, it is possible for `ADD L4` and `BRN L4` can both be valid. To avoid this, an error is thrown if the label is declared as a variable before or vice versa.\n",
    "![error: invalid Label and Variable names](./Assets/images/error4.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. **Address supplied is out of bounds**\n",
    "\n",
    "Since the maximum size of the memory is 8 bit, user cannot access memory cells greater than 256. This error is thrown if the user tries to access addresses greater than 256 such as `SAC 12392`\n",
    "\n",
    "![error: Address out of bounds](./Assets/images/errorMem.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "5. **Incorrect number of operands supplied for an opcode** \n",
    "\n",
    "This error will be throws in the parameters/arguments supplied to the argument is greater than or less than the number of arguments required by the opcode. For example `CLA 88` or `DIV`\n",
    "\n",
    "![error: Incorrect number of operands](./Assets/images/error6.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "6. **Invalid opcode name/Macro name**\n",
    "\n",
    "This error is thrown if the opcode supplied is not a macro call and neither is it a part of the available opcodes i.e. ['CLA',LAC','SAC','ADD','SUB','BRZ','BRN','BRP','INP','DSP','MUL','DIV','STP']\n",
    "For example `WHDK 123`\n",
    "\n",
    "![error: Invalid Opcode/Macro name](./Assets/images/error7.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "7. **END of program not found**\n",
    "\n",
    "This error is throw if the assembly directive `END` is not found anywhere in the code.\n",
    "\n",
    "![error: END not found](./Assets/images/error8.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "8. **Multiple macro definitions**\n",
    "\n",
    "This error occurs when a macro is defined/declared multiple times. Macro declaration includes statements such as `ADDTWO MACRO ABC`\n",
    "\n",
    "![error: multiple Macro definitions](./Assets/images/error9.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "9. **Incorrect number of parameters supplied in a macro** \n",
    "\n",
    "This error occurs if the parameters supplied during the macro call does not match the number of parameters supplied during macro definition. For example: (consider the ADDTWO macro declared above) `ADDTWO 157 158` or `ADDTWO '5' '6' 192 102`\n",
    "\n",
    "![error: Incorrect number of parameters for Macro](./Assets/images/error10.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "10. **Unidentified symbol used in a macro**\n",
    "\n",
    "This error occurs if a symbol(variable) is used in a macro which is not a one of the parameters supplied. For example: (consider the ADDTWO macro declared above `ADDTWO MACRO A,B,C` and Macro call `ADDTWO 157, D,E`), `ADD F` will throw this error. \n",
    "![error: Undefined symbol used in Macro](./Assets/images/error11.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "11. **MEND/ENDM for macro not found**\n",
    "\n",
    "This error is thrown if the assembly directive `ENDM` or `MEND` to specify the end of a MACRO is not found anywhere in the code.\n",
    "![error: MEND/ENDM for Macro not found](./Assets/images/error12.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Errors handled in second pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. **Not enough space for complete program**\n",
    "\n",
    "This error is rare and will be thrown if the memory spaces occupied by the direct addresses, literals, symbols and instructions exceeds the total available memory or if there is no contiguous space available to fit all the instructions.\n",
    "\n",
    "![error: not enough space for complete program](./Assets/images/pass2error1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. **Opcode can only have address/variable as operand**\n",
    "\n",
    "Operands supplied for LAC, DSP, INP should be an address/variable only. No constants or labels allowed. For example, consider: `INP '110'` or `DSP L1` (provided, L1 is a defined label).\n",
    "![error: Opcode can only have address/variable as operand](./Assets/images/pass2error2.png)\n",
    "![error: Opcode can only have address/variable as operand](./Assets/images/pass2error2_2.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. **Opcode can only have a valid label as operand**\n",
    "\n",
    "Operands supplied for BRN, BRZ, BRP should have a defined and valid label. This error is thrown if the operand is anything but a defined label. For example, `BRZ 120` or `BRN L5` (provided, L5 is not a defined label).\n",
    "![error: Opcode can only have a valid label as operand](./Assets/images/pass2error3_1.png)\n",
    "![error: Opcode can only have a valid label as operand](./Assets/images/pass2error3_2.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. **Opcode can only have address or variable or constant as operand**\n",
    "\n",
    "Operands supplied for ADD, MUL, SUB and DIV should be a defined address or a constant (not undefined address). For example, `ADD X` will throw an error if the variable `X` is undefined.\n",
    "![error: Opcode can only have address or variable or constant as operand](./Assets/images/pass2error4.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Methods and working of code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### First Pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Open input file to read the file instruction by instruction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Refine the instruction by checking for empty lines, comments, and assembler directives, while separating instructions into opcodes and corresponding operands.\n",
    "\n",
    "```python\n",
    "def refine(instruction):  \n",
    "\t'''\n",
    "\tInput: Instruction\n",
    "\n",
    "\tOperation: Removes comments, splits instruction into opcode and operands.\n",
    "    '''\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. Checking for presence of macro definitions, and generating the macro table if Macro definition is found.\n",
    "\n",
    "```python\n",
    "def checkMacro(instruction):    \n",
    "\t'''\n",
    "\tInput: Instruction\n",
    "\n",
    "\tOperation: Checking for beginning and ending of Macro definition.\n",
    "\t'''\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. Assigning virtual addresses to each instruction, while checking for the presence of label declarations, adding operands to literal table/ symbol table/ data table, and handling Macro calls from the main code.\n",
    "\n",
    "```python\n",
    "def getLabel(instruction):    \n",
    "\t'''\n",
    "\tInput: Instruction from instruction table\n",
    "\n",
    "\tReturns: True if label definition is found, else, returns False.\n",
    "\t'''\n",
    "```\n",
    "<br>\n",
    "\n",
    "```python\n",
    "def addLabel(label, address,code,instruction): \n",
    "\t'''\n",
    "\tInput: label name, label declaration address, part of program to which the label belongs (macro body/main).\n",
    "\n",
    "\tOperation: Adds detected label to the label table\n",
    "\n",
    "\tThrows exception if detected label is invalid:\n",
    "\t\tAlready used as variable, \n",
    "\tor, contains the name of a macro,\n",
    "\tor, has been defined more than once,\n",
    "\tor, has the same name as a valid opcode.\n",
    "\t'''\n",
    "```\n",
    "<br>\n",
    "\n",
    "```python\n",
    "def addData(parameters,opcode):      \n",
    "\t'''\n",
    "\tInput: Opcode and operands following the opcode for given instruction.\n",
    "\n",
    "\tOperation: Adds operands to the dataTable/ symbolTable.\n",
    "\n",
    "\tThrows : Memory Address out of bounds error.\n",
    "\t'''\n",
    "```\n",
    "\n",
    "<br>\n",
    "\n",
    "```python\n",
    "def getLiteral(token): \n",
    "\t'''\n",
    "\tInput: Operand for given instruction.\n",
    "\n",
    "\tReturns: Literal if found, else, returns False.\n",
    "\t'''\n",
    "```\n",
    "<br>\n",
    "\n",
    "```python\n",
    "def addLiteral(literal): \n",
    "\t'''\n",
    "\tInput: Detected Literal.\n",
    "\n",
    "\tOperation: Adds newly detected literal to literal table.\n",
    "\t'''\n",
    "```\n",
    "\n",
    "<br>\n",
    "\n",
    "```python\n",
    "def handleMacroCalls(name,parameters,num_ins):   \n",
    "\t'''\n",
    "\tInput: Macro name, macro parameters and number of instructions.\n",
    "\n",
    "\tOperation: Maps actual and formal parameters and expands the macro call in the instruction table.\n",
    "\t'''\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Second Pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Calculate offset for instructions in instruction table.\n",
    "\n",
    "```python\n",
    "def getOffset(num_ins):\n",
    "\t'''\n",
    "\tInput: Number of instructions present in instruction table.\n",
    "\n",
    "\tReturns: Offset/Starting address for instruction table, to be stored in a contiguous memory space.\n",
    "\n",
    "\tThrows \"Not enough space\" exception if instruction table size is larger than available memory, or if a contiguous memory space cannot be found.\n",
    "\t'''\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Add calculated offset to map instruction and label virtual addresses to their physical addresses.\n",
    "```python\n",
    "def addOffset(offset):\n",
    "\t'''\n",
    "\tInput: Offset calculated for binding of instructions and labels.\n",
    "\n",
    "\tOperation: Maps the instructions and labels in Instruction Table and Label Table to\n",
    "\tphysical addresses by adding offset.\n",
    "\t'''\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. Find location for literal and variable pool and assign physical addresses and memory spaces to literals according to their size, and to variables.\n",
    "\n",
    "```python\n",
    "def getLiteralPool(offset,num_ins):\n",
    "\t'''\n",
    "\tInput: offset for Instruction table and total number of instructions.\n",
    "\n",
    "\tReturns: Offset/Starting address for literal pool, to be stored in a contiguous memory space.\n",
    "\n",
    "\tThrows \"Not enough space\" exception if literal pool is larger than available memory, or if a contiguous memory space cannot be found.\n",
    "\t'''\n",
    "```\n",
    "<br>\n",
    "\n",
    "```python\n",
    "def getSymbolPool(offset,literalPoolAdd,nextAdd,num_ins):\n",
    "\t'''\n",
    "\tInput: offset for Instruction table, literal pool starting and ending addresses, total number of instructions.\n",
    "\n",
    "\tReturns: Offset/Starting address for variables in symbol table, to be stored in a contiguous memory space.\n",
    "\n",
    "\tThrows \"Not enough space\" exception if variable pool is larger than available memory, or if a contiguous memory space cannot be found.\n",
    "\t'''\n",
    "```\n",
    "<br>\n",
    "\n",
    "```python\n",
    "def assignLiteralPool(startAdd):\n",
    "\t'''\n",
    "\tInput: Starting address for literal pool\n",
    "\n",
    "\tOperation: Assigns physical addresses for literals for binding.\n",
    "\t'''\n",
    "```\n",
    "<br>\n",
    "\n",
    "```python\n",
    "def assignSymbolPool(startAdd):\n",
    "\t'''\n",
    "\tInput: Starting address for variable pool\n",
    "\n",
    "\tOperation: Assigns physical addresses for variables for binding.\n",
    "\t'''\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. Remove label declarations from instructions in instruction table.\n",
    "\n",
    "```python\n",
    "def removeLabelDefinitions():\n",
    "\t'''\n",
    "\tOperation: Removes label declarations from the instruction table for conversion to machine language.\n",
    "\t'''\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "5. Traverse the instruction table to check if operand(s) corresponding to instruction opcodes are valid undeclared/declared addresses/variables, or literals, or labels.\n",
    "\n",
    "```python\n",
    "def checkOperands():\n",
    "\t'''\n",
    "\tOperation: Checks validity of operands corresponding to opcodes.\n",
    "\tADD, MUL, LAC, SUB: Only have defined variables/addresses or literals.\n",
    "\tDSP: Only has defined variable/address.\n",
    "\tBRN, BRP, BRZ: Only have defined label.\n",
    "\tSAC, INP: Only have defined/undefined variables/addresses\n",
    "\tDIV: Only has first operand as defined variable/address or literal.\n",
    "\t'''\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "6. Traverse the instruction table instruction by instruction to:<br>\n",
    "Convert assembly opcodes to corresponding machine language opcodes.<br>\n",
    "Convert operands present in literal table/symbol table/data table/label table to their assigned physical addresses.<br> \n",
    "\n",
    "```python\n",
    "def convertOpcodes():\n",
    "\t'''\n",
    "\tOperation: Convert opcodes in instruction table to machine language.\n",
    "\t'''\n",
    "```\n",
    "<br>\n",
    "\n",
    "```python\n",
    "def convertOperands():\n",
    "\t'''\n",
    "\tOperation: Convert operands to the physical adresses they are bound to.\n",
    "\t'''\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "7. Write the generated machine code to a text file.\n",
    "```python\n",
    "def writeToFile():\n",
    "\t'''\n",
    "\tOperation: Write generated machine code to text file named:\n",
    "\t<sample_file>_output.txt\n",
    "\tSplits machine code into blocks of four bits for readability.\n",
    "\t'''\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sample Input and Output "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Assembly code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider the assembly program below:\n",
    "```\n",
    "GREATER MACRO X,Y,RES ;store the greater in X and Y in res\n",
    "LAC X\n",
    "SAC RES\n",
    "SUB Y\n",
    "BRP L1\n",
    "LAC Y\n",
    "SAC RES\n",
    "L1: MEND\n",
    "\n",
    "START 50\n",
    "INP 197\n",
    "SAC A\n",
    "INP 199\n",
    "SAC B\n",
    "L1: GREATER A B C\n",
    "DSP C\n",
    "ADD A\n",
    "SAC A\n",
    "BRN L1\n",
    "ADD '150'\n",
    "END\n",
    "```  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### First Pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If the first pass ends ends successfully, following message is displayed: <br>\n",
    "`######## SUCCESS: First pass ended successfully ########`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the first pass all the tables are populated with symbols, labels, addresses, instructions and macros. The macros are also expanded.\n",
    "\n",
    "\n",
    "When a macro call is encountered, the instructions are appended from the macro Instruction table to the main instruction table. If any label is present in the macro, it is substituted with a unique label of the form (macro_name+Label_name+call_count) where call count is the number of times the macro has been called in the main code. Therefore label L1 in macro GREATER becomes \"GREATERL11\" for its first call. \n",
    "This helps to support multiple call to the macros and to avoid conflict if a similar label name has been defined in the main code (example 'L1' in this case)\n",
    "\n",
    "This is how the tables look after the first pass."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Instruction table:\n",
    "```\n",
    "['00000000', ['INP', '197']]\n",
    "['00000001', ['SAC', 'A']]\n",
    "['00000010', ['INP', '199']]\n",
    "['00000011', ['SAC', 'B']]\n",
    "['00000100', ['LAC', 'A']]\n",
    "['00000101', ['SAC', 'C']]\n",
    "['00000110', ['SUB', 'B']]\n",
    "['00000111', ['BRP', 'GREATERL11']]\n",
    "['00001000', ['LAC', 'B']]\n",
    "['00001001', ['SAC', 'C']]\n",
    "['00001010', ['DSP', 'C']]\n",
    "['00001011', ['ADD', 'A']]\n",
    "['00001100', ['SAC', 'A']]\n",
    "['00001101', ['BRN', 'L1']]\n",
    "['00001110', ['ADD', \"'150'\"]]\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Macro Table:\n",
    "```\n",
    "GREATER\n",
    "Parameters: ['X', 'Y', 'RES'] , Labels: ['L1']\n",
    "Instruction Table:\n",
    "['LAC', 'X']\n",
    "['SAC', 'RES']\n",
    "['SUB', 'Y']\n",
    "['BRP', 'L1']\n",
    "['LAC', 'Y']\n",
    "['SAC', 'RES']\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Label Table\n",
    "```\n",
    "L1\n",
    "V.Add: 00000010 , P.Add: None , Code: Main\n",
    "GREATERL11\n",
    "V.Add: 00001000 , P.Add: None , Code: GREATER\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Symbol Table\n",
    "```\n",
    "A\n",
    "P.Add: None , Status: defined\n",
    "B\n",
    "P.Add: None , Status: defined\n",
    "C\n",
    "P.Add: None , Status: defined\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Data Table\n",
    "```\n",
    "{197: 'defined', 199: 'defined'}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Second pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then the second pass takes place in which all the instructions, symbols and literals are bound to physical addresses and the final machine code is generated.\n",
    "\n",
    "If the second pass ends successfully, the following message is generated on the terminal:<br>\n",
    "`######## SUCCESS: Second pass ended successfully ########`\n",
    "This is how the tables look after the second pass. The tables show the physical memory mapping of symbols. \n",
    "(The \"None\" in physical address attribute in each table is replaced by respective physical address that the symbol is bound to)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Instruction Table\n",
    "```\n",
    "```\n",
    "\n",
    "Label Table\n",
    "```\n",
    "```\n",
    "\n",
    "Symbol Table\n",
    "```\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Machine code\n",
    "The machine code is generated and appended in a file.\n",
    "The instruction is padded with 0s so that all instructions are of same length.\n",
    "Final machine code generated is as follows."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "00110010 1000 11000101\n",
    "\n",
    "00110011 0010 01000010\n",
    "\n",
    "00110100 1000 11000111\n",
    "\n",
    "00110101 0010 01000011\n",
    "\n",
    "00110110 0001 01000010\n",
    "\n",
    "00110111 0010 01000100\n",
    "\n",
    "00111000 0100 01000011\n",
    "\n",
    "00111001 0111 00111100\n",
    "\n",
    "00111010 0001 01000011\n",
    "\n",
    "00111011 0010 01000100\n",
    "\n",
    "00111100 1001 01000100\n",
    "\n",
    "00111101 0011 01000010\n",
    "\n",
    "00111110 0010 01000010\n",
    "\n",
    "00111111 0110 00110110\n",
    "\n",
    "01000000 0011 01000000\n",
    "```"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}