9

The Dragon Book includes an exercise on converting integers to roman numerals using a syntax-directed translation scheme.

How can this be completed?

Trojan
  • 2,256
  • 28
  • 40
Daniel Magliola
  • 30,898
  • 61
  • 164
  • 243
  • 2
    looks like a homework question, smells like a homework question... ;-) – Steven A. Lowe Nov 06 '08 at 03:41
  • 1
    Yep, I know... I wish I could prove I'm not cheating. It IS actually a homework question, for CS students... Just, not for me, I'm just reading the book on my own, and have no teacher (or knowledgeable enough friend) to go ask. – Daniel Magliola Nov 06 '08 at 12:08

3 Answers3

4

Next is grammar to represent syntax directed translation from number in format 1xxx into roman numerals.

number = OneThousand digit3 digit2 digit1 | nzdigit3 digit2 digit1 | nzdigit2 digit1 | nzdigit1

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

digit3 -> 0 digit3 -> nzdigit3

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')

In similar manner write definition for digits in 2 and 1 position and you will have needed translation.

Yola
  • 18,496
  • 11
  • 65
  • 106
3

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 ..

Lukman
  • 18,462
  • 6
  • 56
  • 66
2

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.

Oddthinking
  • 24,359
  • 19
  • 83
  • 121
  • This means that making a context-free grammar that would then allow me to convert using a sytanx-directed translation scheme, I need to create 10 rules for each "column". (so, about 34 rules to be able to get to 3999) Am I correct? – Daniel Magliola Nov 06 '08 at 12:04
  • I actually thought about something like this, I was kind of expecting there to be a more elegant method... Is there? – Daniel Magliola Nov 06 '08 at 12:04
  • Yes, that means 10 rules per column. I guess you could write a single function that works for each of the columns, and takes the letters as parameters... So, for 219, you would output f(2,'C', 'D', 'M') + f(1. 'X', 'L', 'C') + f(9, 'I', 'V', 'X') Doesn't 'feel' context-free though. – Oddthinking Nov 06 '08 at 15:16
  • 1
    This is wrong answer, because no grammar here. No function at all must be present. Translation must give the result during tree traversal and its not possible do determine how deep in the tree you are. – Yola Oct 22 '11 at 15:51