Как реализовать простую машину стека? - PullRequest
Новая
       20

Как реализовать простую машину стека?

0 голосов
/ 29 ноября 2018

Я прочитал несколько статей об этом и примерно понял, что чаще всего используется.Наиболее простым и распространенным методом, по-видимому, является обратная польская запись, которая заключается в следующем.Чтобы вычислить выражение, первые два операнда помещаются в стек, читается инструкция, подобно операции, такой как сложение, оператор обрабатывает два самых верхних элемента стека, два верхних элемента выталкиваются, и в результате получаетсятолкнул на стек.Однако, похоже, это работает только с примерами, которые я видел, но не в других случаях.Вот несколько примеров:

Выражение: 

(11 * 22 + 33 * 44) / 121

помечено как следующие инструкции: 

push 11
push 22
mult
push 33
push 44
mult
add
push 121
div

Я понимаю это.Аналогичным образом приведен еще один пример из другой статьи:

Выражение: 

(12 + 45) * 98

содержит инструкции: 

push 98
push 12  
push 45  
+    
*

Я тоже это понимаю.Но предположим, что в первом примере мы хотели изменить деление следующим образом: 

 Instead of:
    (11 * 22 + 33 * 44) / 121

    have:
    121 / (11 * 22 + 33 * 44)

Теперь вместо того, чтобы нажимать 121 прямо в конце, кажется, что его нужно подтолкнуть прямо в начале и посмотреть что-товот так: 

push 121
push 11
push 22
mult
push 33
push 44
mult
add
div

Как видите, 121 - это первое нажатие, а не второе последнее в исходном примере.Однако, поскольку остальные части заключены в квадратные скобки, их следует оценить в первую очередь, как вы справитесь с этим?

У меня также есть такая же проблема с другими примерами, которые я нашел.Как правильно упорядочить значения и операции?Вам нужно смотреть в будущее?Или есть простой способ просто пройтись по выражению и создать инструкции?Из того, что я прочитал, кажется, что это самый простой способ оценки выражений, и они, по-видимому, подразумевают, что написание инструкций действительно просто, как будто вы можете просто просмотреть выражение и создать для него правильную нотацию обратной полировки.У меня проблемы с пониманием того, как правильно упорядочить значения и инструкции.

1 Ответ

0 голосов
/ 29 ноября 2018

Как мы обсуждали в комментариях, порядок оценки не имеет ничего общего с приоритетом оператора.Например, в Java подвыражения оцениваются слева направо.В C порядок оценки не указан.Скорее, он имеет концепцию точек последовательности , которая в основном гласит: «Все, что вам нужно сделать, просто убедитесь, что это происходит до этой точки с запятой».

Так что ваша обратная польская запись можетпросто создавайте слева направо без необходимости переупорядочивать скобки.Если вы вообще не знаете, как создать RPN, возьмите книгу по анализу или компиляторам.Книга Дракона открывается подробным примером перевода выражения в RPN.

Теперь есть один случай, когда порядок оценки имеет значение.В большинстве языков && и || короткое замыкание, поэтому в некоторых случаях мы должны избегать оценки RHS.Это может быть выполнено с помощью инструкции перехода.

Например, если у нас есть 1 > 2 && 2 < 3, мы можем выдать следующие инструкции: 

push 1
push 2
>
jmp_f lbl0  ; jump if false to label lbl0
push 2
push 3
<
&&
label lbl0

(Конечно, ваша виртуальная машина может иметь не всеэти инструкции, но это только пример того, как условно вычислять выражения)

...