Как стать автором
Обновить

Обратная польская запись на языке ассемблера с синтаксисом AT&T

Время на прочтение 4 мин
Количество просмотров 6.3K
Данная программа изначально была написана как небольшая лабораторная работа по курсу машинно-ориентированного программирования программирования, но в последствии появилась мысль представить её сообществу. Именно потому что алгоритм реализован не на языке ассемблера с синтаксисом Intel, а на языке ассемблера с синтаксисом AT&T.

Данный синтаксис выбран просто потому что прикольно и немного нестандартно по сравнению с написанием программ на «обычном» ассемблере.

Алгоритм


Итак, начнем с описания алгоритма преобразования выражения в обратную польскую запись.
Рассматриваем поочередно каждый символ:
  1. Если этот символ — число (или переменная), то просто помещаем его в выходную строку.
  2. Если символ — знак операции (+, -, *, / ), то проверяем приоритет данной операции. Операции умножения и деления имеют наивысший приоритет (допустим он равен 3). Операции сложения и вычитания имеют меньший приоритет (равен 2). Наименьший приоритет (равен 1) имеет открывающая скобка.
    Получив один из этих символов, мы должны проверить стек:
    • a) Если стек все еще пуст, или находящиеся в нем символы (а находится в нем могут только знаки операций и открывающая скобка) имеют меньший приоритет, чем приоритет текущего символа, то помещаем текущий символ в стек.
    • b)Если символ, находящийся на вершине стека имеет приоритет, больший или равный приоритету текущего символа, то извлекаем символы из стека в выходную строку до тех пор, пока выполняется это условие; затем переходим к пункту а)

  3. Если текущий символ — открывающая скобка, то помещаем ее в стек.
  4. Если текущий символ — закрывающая скобка, то извлекаем символы из стека в выходную строку до тех пор, пока не встретим в стеке открывающую скобку (т.е. символ с приоритетом, равным 1), которую следует просто уничтожить. Закрывающая скобка также уничтожается.
  5. Если вся входная строка разобрана, а в стеке еще остаются знаки операций, извлекаем их из стека в выходную строку.

На хабре уже был топик, в котором подробно разбирался алгоритм с примерами его работы. Поэтому в рамках данного поста это рассмотрено не будет.

Программа


Итак, приступим к написанию программы. В данной реализации приоритеты операций точно такие же как и описано выше — операции умножения и деления имеют высший приоритет равный 3, операции сложения и вычитания имеют приоритет равный 2, закрывающая скобка приоритет равный 1. Цифры имеют нулевой приоритет. Приоритет для цифры введен для более простой и гибкой реализации алгоритма. Так же для закрывающей скобки приоритет равен 5. Это тоже сделано для облегчения реализации алгоритма. Ниже приведена функция, определяющая приоритет переданного ей символа:
.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

Весьма интересным моментом является реализация стека. Я решил не усложнять реализацию и понимание работы алгоритма и поэтому стек представлен в виде массива фиксированной длины, где первый элемент хранит количество элементов в стеке. Итак, ниже приведены функции для работы со стеком: положить, взять, проверка стека на пустоту, получение размера стека. Каждая функция принимает адрес на стек.
#Положить элемент в стэк
.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. Взять очередной элемент строки
  2. Получить приоритет символа
  3. В зависимости от операции выполнить требуемое действие: занести в стек, занести в результирующую строку или вытолкнуть из стека все операции до открывающей скобки.

Эта часть программы достаточно прямолинейна и неинтересна, поэтому приводить ее не имеет никакого смысла.
Полный код программы а так же мейкфайл можно найти здесь: dl.dropbox.com/u/1379084/pol.zip
Теги:
Хабы:
+2
Комментарии 5
Комментарии Комментарии 5

Публикации

Истории

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн