How can I convert from integers to roman numerals using a syntax-directed translation scheme?

Question

I'm reading the dragon book (just starting for now), and I found this exercise which I can absolutely not solve. I understand the concept, but building a context-free grammar for this looks like way out of my league.

NOTE: I'm not taking a Compiler class in College and trying to cheat. I'm just reading the dragon book and this exercise caught my attention (and I have no idea even how to start solving it)

Plus, I have no teacher to go ask...

Any clues/pointers?

BTW, If you have any idea on how I can prove that I'm not cheating in college, I'll gladly do it. I'm just trying to learn on my own here.

Thanks

Answer 1

I would consider parsing from right-to-left.

First, I would map the units column:

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

Then, if there was a second column (e.g. second from the right = tens column), I would use that to map to

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

That would need to be prepended to the initial output.

Repeat for next columns (hundreds, thousands) until you run out of letters.

Double-check the number isn't '0' or negative.

Answer 2

Another way is to store in two-dimensional array the roman numerals for 1, 5, 10, 50, 100, 500, 1000 and so on. Example (in PHP array):

$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" ),
);

Then take each digit from right-to-left and apply the following translation. Set a variable $level = 0 and increase its value by 1 after every digit processed:

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]

(in PHP a '.' concats two strings)

Example: 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"

So the translated number is "MCMXLV"

Sorry this might not fully answer your question but I hope it helps in any way ..