この構文が選ばれたのは、「通常の」アセンブラーでプログラムを作成するのに比べて、面白くて少し非標準だからです。
アルゴリズム
それでは、式を逆ポーランド記法に変換するアルゴリズムの説明から始めましょう。
各文字を順番に検討します。
- この文字が数字（または変数）である場合は、出力文字列に入力してください。
- 記号が操作の記号（+、-、*、/）である場合、この操作の優先順位を確認します。 乗算と除算の演算の優先順位が最も高くなります（3としましょう）。 加算および減算の優先順位は低くなります（2に等しい）。 最小の優先順位（1に等しい）は、開始ブラケットです。
これらの文字のいずれかを受け取ったら、スタックを確認する必要があります。
- a）スタックがまだ空であるか、スタックに含まれるシンボル（および操作記号と開始ブラケットのみがその中にある）が現在のシンボルの優先度よりも低い優先度を持っている場合、現在のシンボルをスタックに配置します。
- b）スタックの一番上にある文字の優先度が現在の文字の優先度以上である場合、この条件が満たされるまでスタックから出力文字列に文字を抽出します。 次に、ポイントに移動しますa）
- 現在の文字が左角かっこである場合は、スタックに配置します。
- 現在の文字が右角かっこである場合、スタックの左角かっこ（つまり、優先順位が1の文字）に遭遇するまでスタックから出力行に文字を抽出します。 閉じ括弧も破壊されます。
- 入力行全体が解析され、スタック上に操作の兆候が残っている場合、スタックから出力行にそれらを抽出します。
ハブには 、アルゴリズムが詳細に理解されるトピックとその作業例がすでにありました。 したがって、この投稿はこの投稿の枠組みでは考慮されません。
プログラム
それでは、プログラムの作成を始めましょう。 この実装では、演算の優先順位は上記とまったく同じです。乗算と除算の演算の優先順位は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
非常に興味深い点は、スタックの実装です。 アルゴリズムの実装と理解を複雑にしないことにしました。したがって、スタックは固定長の配列として表示されます。最初の要素にはスタック内の要素の数が格納されます。 そのため、スタックを操作するための関数を以下に示します。put、take、空のスタックのチェック、スタックのサイズの取得。 各関数は、スタック上のアドレスを取得します。
#
.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
アルゴリズムのメインサイクルは次のとおりです。
- 文字列の次の要素を取得します
- キャラクターの優先度を取得する
- 操作に応じて、必要なアクションを実行します。スタックにプッシュする、結果の行にプッシュする、またはスタックからすべての操作を開始ブラケットにプッシュします。
プログラムのこの部分はかなり単純で面白くないので、持っていく意味はありません。
完全なプログラムコードとメイクファイルは、 dl.dropbox.com / u / 1379084 / pol.zipにあります。