compiler-construction - 構文指向の変換スキームを使用して整数をローマ数字に変換しますか？

Question

Dragon Bookには、構文指向の変換スキームを使用して整数をローマ数字に変換する演習が含まれています。

これはどのように完了できますか？

Answer 1

次は、1xxx 形式の数値からローマ数字への構文指示変換を表す文法です。

数値 = 1000 桁 3 桁 2 桁 1 | nzdigit3 digit2 digit1 | nzdigit2 digit1 | nzdigit1

OneThousand -> 1 {print('M')}

数字3 -> 0 数字3 -> nz数字3

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

同様に、2 桁と 1 桁の数字の定義を書くと、変換が必要になります。

Answer 2

もう 1 つの方法は、1、5、10、50、100、500、1000 などのローマ数字を 2 次元配列に格納することです。例 (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 では、'.' は 2 つの文字列を連結します)

例：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'

次に、2 番目の列 (たとえば、右から 2 番目 = 10 の列) がある場合、それを使用してにマップします。

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

これは、初期出力の先頭に追加する必要があります。

文字がなくなるまで、次の列 (数百、数千) に対して繰り返します。

数値が「0」または負でないことを再確認してください。