Polish reverse assembly language with AT&T syntax

This program was originally written as a small laboratory work on the course of machine-oriented programming programming, but later there was an idea to introduce it to the community. Precisely because the algorithm is not implemented in assembly language with Intel syntax, but in assembly language with AT&T syntax.

This syntax was chosen simply because it’s fun and a bit non-standard compared to writing programs in “normal” assembler.

Algorithm


So, let's start with a description of the algorithm for converting an expression into reverse Polish notation.
We consider each character in turn:
  1. If this character is a number (or variable), then just put it in the output string.
  2. If the symbol is the operation sign (+, -, *, /), then we check the priority of this operation. The operations of multiplication and division have the highest priority (let's say it is 3). Addition and subtraction operations have a lower priority (equal to 2). The smallest priority (equal to 1) is the opening bracket.
    Having received one of these characters, we must check the stack:
    • a) If the stack is still empty, or the symbols that are in it (and only operation signs and the opening bracket can be in it) have a lower priority than the priority of the current symbol, then we put the current symbol on the stack.
    • b) If the character at the top of the stack has a priority greater than or equal to the priority of the current character, then we extract the characters from the stack into the output string until this condition is met; then go to point a)

  3. If the current character is an opening bracket, then put it on the stack.
  4. If the current character is a closing bracket, then we extract the characters from the stack into the output line until we meet the opening bracket in the stack (i.e., a character with a priority of 1), which should be simply destroyed. The closing bracket is also destroyed.
  5. If the entire input line is parsed, and there are still signs of operations on the stack, we extract them from the stack to the output line.

There was already a topic on the hub , in which the algorithm in detail dealt with examples of its work. Therefore, this post will not be considered in the framework of this post.

Program


So, let's start writing the program. In this implementation, the operation priorities are exactly the same as described above - the operations of multiplication and division have the highest priority equal to 3, the operations of addition and subtraction have a priority equal to 2, the closing bracket priority is equal to 1. The numbers have zero priority. Priority for numbers is introduced for a simpler and more flexible implementation of the algorithm. Also, for the closing bracket, the priority is 5. This is also done to facilitate the implementation of the algorithm. The following is a function that determines the priority of the character passed to it:
.text
.globl getPriotiry
#В %eax находится код символа для которого нужно получить приоритет
.type getPriority, @function
getPriority:
pushl %ebp
movl %esp, %ebp

movl 8(%esp), %eax

cmpl $42, %eax # *
je priority3
cmpl $47, %eax # /
je priority3
cmpl $43, %eax # +
je priority2
cmpl $45, %eax # -
je priority2
cmpl $40, %eax # (
je priority1
cmpl $41, %eax # )
je priority5

#в остальных случаях приоритет символа -- 0
movl $0, %eax
jmp exit
priority3: # * and /
movl $3, %eax
jmp exit
priority2: # + and -
movl $2, %eax
jmp exit
priority1: # (
movl $1, %eax
jmp exit
priority5: # )
movl $5, %eax
jmp exit
exit:
leave
ret
.size getPriority, .-getPriority

A very interesting point is the implementation of the stack. I decided not to complicate the implementation and understanding of the algorithm and therefore the stack is presented as an array of fixed length, where the first element stores the number of elements in the stack. So, below are the functions for working with the stack: put, take, check the stack for emptiness, get the size of the stack. Each function takes an address on the stack. The main loop of the algorithm is as follows:
#Положить элемент в стэк
.text
.globl stack_push
.type stack_push, @function
stack_push:
pushl %ebp
movl %esp, %ebp

#первый параметр -- адрес стека, второй -- что класть
movl 8(%ebp), %eax
cmp $50, %eax #небольшой костыль. если второй параметр -- адрес, то обрабатываем его соответствующим образом, иначе как просто число -- код символа
jg address
movl %eax, %edx
jmp number
address:
movzbl (%eax), %ebx
number:
movzbl 12(%ebp), %edx
movl %edx, (%eax, %ebx, 1)

#увеличиваем счетчик стека
movl 8(%ebp), %eax
addl $1, (%eax)

leave
ret
.size stack_push, .-stack_push
#-------------------------------------------------------------------
#Взять верхний элемент и вернуть его значение
.text
.globl stack_pop
.type stack_pop, @function
stack_pop:
pushl %ebp
movl %esp, %ebp

#уменьшить значение счетчика стека
movl 8(%ebp), %eax
subl $1, (%eax)
movzbl (%eax), %ebx

#взять верхний элемент
movzbl (%eax, %ebx, 1), %eax
# movzbl %edx, %eax

leave
ret
.size stack_pop, .-stack_pop
#-------------------------------------------------------------------
#Возвращает 0 если стек не пустой. Иначе 1
.text
.globl stack_isEmpty
.type stack_isEmpty, @function

stack_isEmpty:
pushl %ebp
mov %esp, %ebp

movl 8(%esp), %eax
movzbl (%eax), %eax
cmpl $1, %eax

movl $0, %eax
jg exit
movl $1, %eax

exit:
leave
ret
.size stack_isEmpty, .-stack_pop
#-------------------------------------------------------------------
# Возвращает размер стека
.text
.globl stack_size
.type stack_size, @function

stack_size:
pushl %ebp
movl %esp, %ebp

movl 8(%esp), %eax
movzbl (%eax), %eax
subl $1, %eax

leave
ret
.size stack_size, .-stack_size
#-------------------------------------------------------------------
# Возвращает просто значение верхнего элемента
.text
.globl stack_top
.type stack_top, @function

stack_top:
pushl %ebp
movl %esp, %ebp

movl 8(%esp), %eax
movzbl (%eax), %ebx
subl $1, %ebx
movzbl (%eax, %ebx, 1), %eax

leave
ret
.size stack_top, .-stack_size


  1. Take the next element of the string
  2. Get character priority
  3. Depending on the operation, perform the required action: push it onto the stack, push it into the resulting line, or push all operations from the stack to the opening bracket.

This part of the program is fairly straightforward and uninteresting, so it makes no sense to bring it.
The full program code as well as the makefile can be found here: dl.dropbox.com/u/1379084/pol.zip

Also popular now: