ARM ASSEMBLY LANGUAGE ARM ASSEMBLY LANGUAGE ARM ASSEMBLY LANGUAGE HOMEWORK 8 INT
ID: 3601307 • Letter: A
Question
ARM ASSEMBLY LANGUAGE
ARM ASSEMBLY LANGUAGE
ARM ASSEMBLY LANGUAGE
HOMEWORK 8
INTRODUCTION: In Reverse Polish(postfix) notation the operators follow their operands; for instance, to add three and four one would write "3 4 +" rather than "3 + 4". If there are multiple operations, the operator is given immediately after its second operand; so the expression written "3 4 + 5" in conventional infix notation would be written "3 4 5 +" in RPN: first subtract 4 from 3, then add 5 to that. An advantage of RPN is that it obviates the need for parentheses that are required by infix. While "3 4 + 5" can also be written "(3 4) + 5", that means something quite different from "3 (4 + 5)", and only the parentheses disambiguate the two meanings. In postfix, the latter would
be written "3 4 5 + ", which unambiguously means "3 (4 5 +) ".
Interpreters of Reverse Polish notation are stack-based; that is, operands are pushed onto a stack, and when an operation is performed, its operands are popped from a stack and its result pushed back on. Stacks, and therefore RPN, have the advantage of being easy to implement and very fast.
Please complete the implementation of the two functions given in the questions section below.
Test your functions using the main program given.
After you complete the homework rename the file “HW8_AssemblyFunctions.S” to “HW8_yourredID.S” and submit only this file on blackboard. Do not include main.c or add contents of main.c to this file.
QUESTION 1: Write a function to convert a given function from infix to postfix in assembly. The basic structure of the function is given in the attached assembly language file.
QUESTION 2: Write a function to convert a given function from postfix to infix in assembly language. The basic structure of the function is given in the attached assembly language file.
INTRODUCTION: In Reverse Polish(postfix) notation the operators follow their operands; for instance, to add three and four one would write "3 4 +" rather than "3 + 4". If there are multiple operations, the operator is given immediately after its second operand; so the expression written "3 4 + 5" in conventional infix notation would be written "3 4 5 +" in RPN: first subtract 4 from 3, then add 5 to that. An advantage of RPN is that it obviates the need for parentheses that are required by infix. While "3 4 + 5" can also be written "(3 4) + 5", that means something quite different from "3 (4 + 5)", and only the parentheses disambiguate the two meanings. In postfix, the latter would
be written "3 4 5 + ", which unambiguously means "3 (4 5 +) ".
Interpreters of Reverse Polish notation are stack-based; that is, operands are pushed onto a stack, and when an operation is performed, its operands are popped from a stack and its result pushed back on. Stacks, and therefore RPN, have the advantage of being easy to implement and very fast.
Explanation / Answer
globl _toPostfix 002 _toPostfix: 003 004 pushl %ebp 005 movl %esp,%ebp 006 movl 8(%ebp),%ebx /*move base address of infix stream into ebx*/ 007 movl 12(%ebp),%eax /*move base address of postfix stream into eax*/ 008 xorl %esi,%esi /* counter for infix stream */ 009 xorl %edi,%edi /* counter for postfix stream */ 010 xorl %ecx,%ecx /* counter for stack */ 011 012 loop: 013 cmpl $0x0,(%ebx,%esi,1)/* If infix index equal to NULL */ 014 je miniloop2 015 cmpl $0x2A, (%ebx,%esi,1)/* If infix index equal to '*' */ 016 je checkmultdiv 017 cmpl $0x2F, (%ebx,%esi,1) /* If infix index not equal to '/'*/ 018 jne addsubcheck 019 020 checkmultdiv: 021 cmpl $0x2A,4(%esp) /* If esp+4 (second-to-top stack value) equal to '*' */ 022 je removeone 023 cmpl $0x2F,4(%esp) /* If not equal to '/'*/ 024 jne pushtostack 025 026 removeone: 027 movl 4(%esp),%edx /* edx is temporary storage because we cannot copy from one memory address to another */ 028 movl %edx,(%eax,%edi,1) /* effectively copy esp+4 into postfix stream index */ 029 xorl %edx,%edx /*clears temporary storage edx*/ 030 popl %esp /* esp = esp+4 */ 031 decl %ecx /* decrement stack counter */ 032 incl %edi /*increment postfix counter */ 033 034 pushtostack: 035 pushl (%ebx,%esi,1) 036 incl %ecx 037 jmp incrementi 038 039 addsubcheck: 040 cmpl $0x2B,(%ebx,%esi,1) /* If equal to '+' */ 041 je removesome 042 cmpl $0x2D,(%ebx,%esi,1) /* If not equal to '-'*/ 043 jne openparencheck 044 045 removesome: 046 cmpl $0,%ecx /* If stack counter equal to 0 */ 047 je pushtostack 048 cmpl $0x28, 4(%esp)/* If equal to '(' */ 049 je pushtostack 050 movl 4(%esp),%edx 051 movl %edx,(%eax,%edi,1) 052 xor %edx,%edx 053 decl %ecx 054 incl %edi 055 jmp removesome 056 057 openparencheck: 058 cmpl $0x28,(%ebx,%esi,1) /* If not equal to '('*/ 059 jne closeparencheck 060 jmp pushtostack 061 062 closeparencheck: 063 cmpl $0x29, (%ebx,%esi,1) /* If not equal to ')'*/ 064 jne pushtopost 065 066 miniloop: 067 cmpl $0x28,4(%esp) /* If second highest value on stack equal to '(' */ 068 je decrements 069 movl 4(%esp),%edx 070 movl %edx,(%eax,%edi,1) 071 xor %edx,%edx 072 decl %ecx 073 incl %edi 074 jmp miniloop 075 076 decrements: 077 decl %ecx 078 jmp incrementi 079 080 pushtopost: 081 movl (%ebx,%esi,1),%edx 082 movl %edx,(%eax,%edi,1) 083 incl %edi 084 085 incrementi: 086 incl %esi 087 jmp loop 088 089 miniloop2: 090 cmp $0,%ecx /* If equal to 0 */ 091 je out 092 movl 4(%esp),%edx 093 movl %edx,(%eax,%edi,1) 094 xorl %edx,%edx 095 decl %ecx 096 incl %edi 097 098 out: 099 popl %ebp 100 ret 1.While there are input symbol left 2. Read the next symbol from input. 3. If the symbol is an operand Push it onto the stack. 4. Otherwise, the symbol is an operator. 5. If there are fewer than 2 values on the stack Show Error /* input not sufficient values in the expression */ 6. Else Pop the top 2 values from the stack. Put the operator, with the values as arguments and form a string. Encapsulate the resulted string with parenthesis. Push the resulted string back to stack. 7. If there is only one value in the stack That value in the stack is the desired infix string. 8. If there are more values in the stack Show Error /* The user input has too many values */