compiler-construction - 使用语法导向的翻译方案将整数转换为罗马数字？

Question

Dragon Book 包括一个使用语法指导的翻译方案将整数转换为罗马数字的练习。

这怎么能完成？

Answer 1

接下来是表示从 1xxx 格式的数字到罗马数字的语法定向翻译的语法。

数字 = 千位 3 位 2 位 1 | nzdigit3 digit2 digit1 | nzdigit2 digit1 | nzdigit1

一千 -> 1 {print('M')}

digit3 -> 0 digit3 -> nzdigit3

nzdigit3 -> 1 打印('C') nzdigit3 -> 2 打印('CC') nzdigit3 -> 3 打印('CCC') nzdigit3 -> 4 打印('CCCC') nzdigit3 -> 5 打印('D') nzdigit3 -> 6 打印('DC') nzdigit3 -> 7 打印('DCC') nzdigit3 -> 8 打印('DCCC') nzdigit3 -> 9 打印('DCCCc')

以类似的方式为 2 和 1 位置的数字编写定义，您将需要翻译。

Answer 2

另一种方法是将 1、5、10、50、100、500、1000 等罗马数字存储在二维数组中。示例（在 PHP 数组中）：

$roman = array(
  [0] = array( 1=>"I", 5=>"V", 10=>"X" ),
  [1] = array( 1=>"X", 5=>"L", 10=>"C" ),
  [2] = array( 1=>"C", 5=>"D", 10=>"M" ),
  [3] = array( 1=>"M", 5=>"^V", 10=>"^X" ),
);

然后从右到左取每个数字并应用以下翻译。设置变量 $level = 0 并在处理完每个数字后将其值增加 1：

1 => $roman[$level][1]
2 => $roman[$level][1].$roman[$level][1]
3 => $roman[$level][1].$roman[$level][1].$roman[$level][1]
4 => $roman[$level][1].$roman[$level][5]
5 => $roman[$level][5]
6 => $roman[$level][5].$roman[$level][1]
7 => $roman[$level][5].$roman[$level][1].$roman[$level][1]
8 => $roman[$level][5].$roman[$level][1].$roman[$level][1].$roman[$level][1]
9 => $roman[$level][1].$roman[$level][10]

（在 PHP 中，一个 '.' 连接两个字符串）

示例：1945 年

5 => $roman[0][5] = "V"
4 => $roman[1][1].$roman[1][5] = "XL"
9 => $roman[2][1].$roman[2][10] = "CM"
1 => $roman[3][1] = "M"

所以翻译后的数字是“MCMXLV”

抱歉，这可能无法完全回答您的问题，但我希望它对您有所帮助..

Answer 3

我会考虑从右到左解析。

首先，我将映射单位列：

0 -> ''
1 -> 'I'
2 -> 'II'
3 -> 'III'
4 -> 'IV'
...
9 -> 'IX'

然后，如果有第二列（例如，从右边数第二列 = 十列），我会用它来映射到

0 -> ''
1 -> 'X'
2 -> 'XX'
...
9 -> 'XC'

这需要预先添加到初始输出中。

重复下一列（数百、数千），直到用完字母。

仔细检查数字不是“0”或负数。