9
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ This is awesome. I'll be back tomorrow sometime. \$\endgroup\$ – RubberDuck Jan 24 '16 at 1:18
  • \$\begingroup\$ I've messed with this for far too long today. The problem is that we'd like four of something to be a syntax error and defined in the grammar, but that's extremely difficult in practice. The second problem is that Roman Numerals are not a context free language. i.e. We want to add in this case, but subtract in that case. I tried for hours to build a "proper" grammar for this and failed miserably. The core problem I ran across is that "IIII" is interpreted as a 3 and a 1. You may find success with Semantic Predicates, but I didn't understand it well enough. \$\endgroup\$ – RubberDuck Jan 24 '16 at 18:27
  • \$\begingroup\$ If you do manage to get a grammar that makes four of something a syntax error, then you want to create an error listener that throws an exception and attach it to the lexer. \$\endgroup\$ – RubberDuck Jan 24 '16 at 18:30
  • \$\begingroup\$ @RubberDuck Thanks a lot for taking a look. I'll look into those solutions. \$\endgroup\$ – rookie Jan 25 '16 at 0:30
  • 1
    \$\begingroup\$ @mdfst13 you could install AntlrWorks2. It's an IDE specifically for debugging/testing Antlr grammars. It gives a really nice visual representation of the AST that gets generated. Sadly, I don't know of any online tools (but now I'm tempted to build one...) \$\endgroup\$ – RubberDuck Jan 28 '16 at 10:37
7
\$\begingroup\$

I'm not sure this counts as a Code Review answer, but I wanted to at least share what I found out after nearly a day of fighting with this...


As I think you know, your grammar allows strings like "IIII" and "XXXX". This is definitively a bug, and a damn hard one to squish. Part of the problem is that Roman Numerals are not a context free language. (i.e. We want to add in this case, but subtract in that case.)

I think you were right about counting the tokens, but I took an approach of doing it in the lexer, which I'm not sure was a good idea. It might have been easier to do at the Parsing stage, but it seemed to make sense to me that this be a Syntax error. Anyway. Here's what I did.

I derived a subclass from the Antlr generated RomanLexer. This class counts the number of consecutive tokens and alerts any ErrorListeners that there was a SyntaxError.

public class DerivedRomanLexer : RomanLanguage.RomanLexer
{
    public DerivedRomanLexer(ICharStream input) 
        :base(input)
    { }

    private IToken _lastToken;
    private int _lastTokenCount;

    public override IToken NextToken()
    {
        var token = base.NextToken();

        if (_lastToken != null)
        {
            if (_lastToken.Type == token.Type)
            {
                _lastTokenCount++;
            }
            else
            {
                _lastTokenCount = 0;
            }

            if (_lastTokenCount > 2)
            {
                foreach (BaseErrorListener listener in this.ErrorListeners)
                {
                    listener.SyntaxError(this, token, token.Line, token.StartIndex, "Too many tokens. There can be a max of 3.", new RecognitionException(this, this._input));
                }
            }
        }

        _lastToken = token;
        return token;
    }
}

Obviously, we'll need to change your test class to use this customized Lexer instead.

        // setup the lexer
        var inputStream = new AntlrInputStream(text);

        //var lexer = new RomanLexer(inputStream);
        var lexer = new DerivedRomanLexer(inputStream);
        lexer.RemoveErrorListeners();
        lexer.AddErrorListener(new ThrowExceptionErrorListener());

        // get the tree and and traverse
        var tokenStream = new CommonTokenStream(lexer);

        IParseTree tree = new RomanParser(tokenStream).root();

        Console.WriteLine(tree.ToStringTree());

        int actual = tree.Accept(new RomanDecodeVisitor());

Now, you notice that ErrorListener there? It's there to force the Antlr to throw an exception if a SyntaxError happens. The implementation is right here.

class ThrowExceptionErrorListener : BaseErrorListener, IAntlrErrorListener<int>
{
    //BaseErrorListener implementation
    public override void SyntaxError(IRecognizer recognizer, IToken offendingSymbol, int line, int charPositionInLine, string msg, RecognitionException e)
    {
        throw new InvalidOperationException("Syntax Error: " + msg, e);
    }

    //IAntlrErrorListener<int> implementation
    public void SyntaxError(IRecognizer recognizer, int offendingSymbol, int line, int charPositionInLine, string msg, RecognitionException e)
    {
        throw new InvalidOperationException("Syntax Error: " + msg, e);
    }
}

As for an actual review then... I dislike that each visitor method is a copy/paste of each other visitor method. I'd go one step further and create this method overload.

private int RomanSum(Antlr4.Runtime.ParserRuleContext context)
{
    return RomanSum(from child in context.children select Visit(child));
}

But at this point, it becomes obvious that we're just walking the tree, which makes me wonder if it wouldn't be best to just implement a Listener and just walk the tree. Of course, if we use a Listener and a TreeWalker, then the custom Lexer code might as well go away and just have the Listener count the tokens as we walk.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.