0

问题：“大整数表示为（小）整数列表。”

假设有：

type reg = string;;   (* "$0" models register set to constant 0 *)
type label = string;; (* empty string models no label *)

type asmistr =
   AsmHalt
 | AsmNop
 | AsmAdd of reg * reg * reg
 | AsmAddi of reg * int * reg
 | AsmSub of reg * reg * reg
 | AsmMul of reg * reg * reg
 | AsmLoad of reg * reg * reg
 | AsmStore of reg * reg * reg
 | AsmJmp of label
 | AsmBne of reg * reg * label
 | AsmBeq of reg * reg * label
 | AsmSlt of reg * reg * reg
;;

type asmprog = AsmProg of (label * asmistr) list;;

type asmline = 
    AsmIstr of label * asmistr 
  | AsmComment of string 
  | AsmDebugReg of reg 
  | AsmDebugMem of int * int
;;

这组定义用于定义像汇编这样的语言，使用寄存器、指令和标签（用于跳转）

现在我需要实现一个从命令式语言（具有“while”“if”等指令）到 ASM 的编译器

我的老师建议的实现是使用一个列表，其中每个元素都是给定数字的数字（数字只能是整数），例如 11000 是 [1, 1, 0, 0, 0]

第一个差距是：考虑到通用的 O'Caml 程序，我该如何实现呢？假设我必须插入一个大整数，我可以使用什么逻辑来允许“计算”？因为最后一个ASM程序也可以做add、sub mul等可以包含大整数的指令，所以不知道怎么处理寄存器、大整数和指令

我需要的是如何实现大整数的一般方案，可能用 O'Caml 语言，以及如何考虑类似于汇编的语言（在本例中为 ASM）来实现这一点

提前感谢，如果不清楚，对不起我的英语，如果有人可以帮助我，如果需要，我会提供更多细节

4

2 回答 2

1

我对你的问题的理解如下：你想编译一个简单的命令式语言，它有无界整数来汇编，编译器将用 OCaml 编写。那正确吗？您的问题是“我应该如何编译无界整数的算术运算？”。

如果这确实是问题，一个很好的练习是首先在 OCaml 中实现那些大数操作（使用int; 的列表，注意每个元素不需要是0or 1，您可以使用任何更大的基数，其加法不会溢出您的本地 OCaml 整数，这将使操作更快），然后想知道如何将其移植到本地汇编程序。首先，您将如何编译列表？

于 2013-02-06T23:18:02.293 回答
0

首先，您应该了解数字有一个基础。通常人们使用十进制（以 10 为底），但程序员也使用十六进制（以 16 为底）和二进制（以 2 为底）。你的老师是对的（使用一个列表，其中每个元素都是给定数字的数字）；但可能没有提到这些数字可以是任何基数。为了性能/效率，您可能应该使用基数 256（其中每个数字是一个 8 位整数），或者可能使用基数 65536（其中每个数字是一个 16 位整数）、基数 2^32 或基数 2^64。选择取决于底层硬件预计能够处理的内容（例如，如果代码打算在 16 位 CPU 上运行，那么您将使用 base 65536）。

接下来要决定的是如何存储数字。通常，您需要一些东西来跟踪有多少位数字、一些标志和数字列表。对于标志，您需要一个标志来指示数字是正数还是负数，但您可能会使用更多标志来表示数字是否无穷大、数字是否有精度损失等。例如，“5/(- 6)" 可能导致“位数”为零的数字；设置了负数和精度标志。

一旦确定了这一点，您就想实现正数的加法。这主要只是添加带有进位的数字，其中结果可能（最多）比最大的源数字多一位。例如，如果您添加一个 2 位数字和一个 4 位数字，那么您将为 5 位结果分配内存，然后使用以下方式一次添加一个数字：

for(n = 0; n < result_digits; n++) {
    digit = source1[n] + source2[n] + carry;
        if(digit > DIGIT_MAX) {
            carry = 1;
            digit &= DIGIT_MASK;
        } else {
            carry = 0;
        }
        result[n] = digit;
    }
}

下一步是编写代码来处理从较大的正数中减去较小的正数。这只是从最重要的数字开始用进位从另一个数字中减去一个数字。一旦这个工作正常，您将扩展它以处理从较小的正数中减去较大的正数，这涉及事先交换数字并随后否定结果。例如，“3 - 10 = -( 10 - 3)”。

一旦正数的加法和减法开始工作，您就可以开始支持负数了。这主要是摆弄符号标志并选择是加还是减。例如，对于“8 + (-3) = 8 - 3”、“8 - (-3) = 8 + 3”、“-8 + 3 = 3 - 8”、“-8 + -3 = -( 8 + 3)”等。在所有情况下，它都可以重新排列并作为正数的加法或减法完成。

下一步是正数的乘法。这只是将每个数字相乘并添加前一个数字的溢出：

for(n = 0; n < result_digits; n++) {
    digit = source1[n] * source2[n] + temp;
    temp = digit >> DIGIT_BITS;
    digit &= DIGIT_MASK;
    result[n] = digit;
}

然后你会担心负数的乘法。在这里，您只需将源数设为正数并乘以正数，然后设置结果的符号。

于 2013-02-07T03:51:26.310 回答