I've written a simple interpreter with ANTLR for evaluating Roman numerals. Here's the contents of the grammar file (Roman.g4):
grammar Roman;
root : (oneThousand)* hundreds? tens? units?;
// --- I, II, III, IV, IX or V VI, VII, VIII
units : one ((one)* | five | ten) | five (one)*;
// --- X, XX, XXX, XL, XC or L, LX, LXX, LXXX
tens : ten ((ten)* | fifty | oneHundred) | fifty (ten)*;
// --- C, CC, CCC, CD, CM or D, DC, DCC, DCCC
hundreds : oneHundred ((oneHundred)* | fiveHundred | oneThousand) | fiveHundred (oneHundred)*;
// --- atomic definitions
one : 'I';
five : 'V';
ten : 'X';
fifty : 'L';
oneHundred : 'C';
fiveHundred : 'D';
oneThousand : 'M';
// --- skip over white spaces, tabs, newlines
WS : [ \t\r\n]+ -> skip ;
The target language I'm using is C# and my interpreter is implemented as a visitor. To compile the ANTLR parser/lexer, first create the directory Antlr
at the same level as the grammar file, then run antlr4 Roman.g4 -Dlanguage=CSharp_v4_0 -visitor -o Antlr
(or something equivalent if antlr4
isn't an alias). You should include the Antlr
directory and the generated files in your project.
Here's my visitor implementation:
public class RomanDecodeVisitor : AbstractParseTreeVisitor<int>, IRomanVisitor<int>
{
public int VisitRoot(RomanParser.RootContext context)
{
return RomanSum(from child in context.children select Visit(child));
}
public int VisitHundreds(RomanParser.HundredsContext context)
{
return RomanSum(from child in context.children select Visit(child));
}
public int VisitTens(RomanParser.TensContext context)
{
return RomanSum(from child in context.children select Visit(child));
}
public int VisitUnits(RomanParser.UnitsContext context)
{
return RomanSum(from child in context.children select Visit(child));
}
public int VisitOne(RomanParser.OneContext context)
{
return 1;
}
public int VisitFive(RomanParser.FiveContext context)
{
return 5;
}
public int VisitTen(RomanParser.TenContext context)
{
return 10;
}
public int VisitFifty(RomanParser.FiftyContext context)
{
return 50;
}
public int VisitOneHundred(RomanParser.OneHundredContext context)
{
return 100;
}
public int VisitFiveHundred(RomanParser.FiveHundredContext context)
{
return 500;
}
public int VisitOneThousand(RomanParser.OneThousandContext context)
{
return 1000;
}
private static int RomanSum(IEnumerable<int> nums)
{
// our zip might not capture the last number
// start the sum with this (e.g. zip for 'X' will be no elements)
int sum = nums.Last();
// look at each consecutive pair
// add/subtract based on less than/greater than
foreach (var pair in nums.Zip(nums.Skip(1), (smaller, larger) => new { smaller, larger }))
{
sum += (pair.smaller < pair.larger) ?
-pair.smaller : pair.smaller;
}
return sum;
}
}
I've also written some tests. In case you're wondering, I was having some issues with using nuget unit tests on my machine and basically just wrote a simple test class to do the same thing. These should suffice for now:
public class RomanDecodeTests
{
public void TestThousands()
{
BasicTest("MMMCMLXI", 3961);
BasicTest("MMMCMLXXIV", 3974);
BasicTest("MCMXC", 1990);
BasicTest("MMVIII", 2008);
BasicTest("MDCLXVI", 1666);
BasicTest("MCMLIV", 1954);
BasicTest("MCMLXXIV", 1974);
}
public void TestTens()
{
BasicTest("X", 10);
BasicTest("XX", 20);
BasicTest("XXX", 30);
BasicTest("XXXVI", 36);
BasicTest("XXXVIII", 38);
BasicTest("XXXIX", 39);
BasicTest("XLIV", 44);
}
public void TestUnits()
{
BasicTest("I", 1);
BasicTest("II", 2);
BasicTest("III", 3);
BasicTest("IV", 4);
BasicTest("V", 5);
BasicTest("VI", 6);
BasicTest("VII", 7);
BasicTest("VIII", 8);
BasicTest("IX", 9);
}
private static void BasicTest(string text, int expected)
{
// setup the lexer
var inputStream = new AntlrInputStream(text);
var lexer = new RomanLexer(inputStream);
// get the tree and and traverse
IParseTree tree = new RomanParser(new CommonTokenStream(lexer)).root();
int actual = tree.Accept(new RomanDecodeVisitor());
if (expected != actual)
throw new Exception(string.Format(
"failed to convert {0}: expected {1} got {2}", text, expected, actual));
}
}
Everything was simple enough where I didn't really think documentation would add any significant benefit (feel free to disagree).
I wasn't quite sure how validation should happen (e.g. with the exception of M
, no four numerals should appear contiguously). There's a great ANTLR Roman numeral interpreter out there that puts the validation in the grammar file (java is the target language). I don't really like this solution, because it's my understanding that the .g4 file should be portable and not language specific.
If possible, it would be great if someone could suggest where in my visitor to include validation (perhaps have a counter that checks the last numeral and adds/resets the counter depending on the current visited numeral). I actually tried a version of this, but found that my visit methods were getting called multiple times for a single numeral during the process and as a result messing up the count. Perhaps this has to do with the lazy queries getting reinvoked (I'm not sure).