Addition and Other Operators
FrontEnd, Iteration 5

Not the Whole User Story

The user story you're shooting for is to be able to parse and interpret fully recursive arithmetic expressions. For this particular iteration, you'll worry about non-recursive expressions (in addition to the integers and strings you already handle).

So these are valid expressions:

(+ 1 2)
(* 8 9)
(- 6 3)
(/ 8 4)
(+ 'foo' 4)
(* 'foo' 4)
(< 'abc' 'xyz')
(= 'foo' 'foo')

These are not yet:

(+ 1 (* 2 3))
(* (/ 8 4) (+ 2 3))

Acceptance Tests

The problem should be with the left parenthesis and the operators. Nothing in the front end knows how to handle them.

Lexer or Parser

Recognize an integer or a string is a matter of matching up against patterns. An expression as a whole will have to be recognized by the parser. But what about the parentheses and the individual operator characters? There aren't exactly patterns here: you match a + or you don't.

ANTLR allows you to match these in the parser directly. Some grammar generators require you to use a token defined by the lexer, and ANTLR gives you this as an option. So we'll split the difference and do the recognition in both the lexer and parser.

The Lexer

So let's start with recognizing the operators in the lexer.

Here's an assertion for an operator token:

assertToken(HobbesParser.OPERATOR, "<", myTester.scanInput("<"));

HobbesParser.OPERATOR isn't defined.

You know the test is being triggered since you have the red bar.

OPERATOR itself should match any of the operators. The text of the token will keep track of which operator you've actually matched.

The Parser

As mentioned above, many grammar generators will require you to recognize the left and right parentheses in your lexer, but let's try this in parser.

An assertion:

assertTree(
  SchobbesParser.OPERATOR,
  "(<(1)(2))",
  myTester.scanInput("(< 1 2)").parseAs("program")
  );

The assertion says that the root of the tree will be an OPERATOR. The second argument to the assertion is the preorder traversal of the AST. That is, the operator < is at the root, and (1) and (2) are the subtrees.

You should be able to parse any operator and any integer or string arguments as an OPERATOR expression.

The commenting out and green bar is so that you can do some refactoring. The parser, as it exists right now, has a program rule to get things started. It handles the EOF. It's not a good idea to confuse a rule that handles EOF. (My opinion based on getting burned too many times.)

The only other parser rule is the atom rule. Integers and strings are atoms because they're at the lowest, basest level of any expression we might ever write in Schobbes. An operator expression is not an atom.

So we need to introduce another rule for general expressions. Right now, the only kind of expression you have is an atom. So that means it should be easy to add an expression rule now.

So, now that the grammar is ready for a new expression rule, let's analyze a possible expression. Let's consider (< 1 'foo') (while this doesn't interpret well (or at all), it will parse just fine).

The whitespace is tossed, so we expect the lexer to return these tokens: (, < (an OPERATOR), 1 (an INTEGER), 'foo' (a STRING), and ).

Is it important that it's a < in this expression? No! Any OPERATOR would be fine.

Is it important that it's 1 as the first argument? No! Is it important that it's an INTEGER? No! It's important (for now) that it's an atom.

Is it important that it's 'foo' as the second argument? No! Is it important that it's a STRING? No! It's important (for now) that it's an atom.

So an expression can be an OPERATOR followed by an atom followed by an atom.

All the rules you learned about lexer rules in ANTLR also apply to parsers. So if you want to match multiple things, just create a list of them (separated by whitespace).

sentence : NOUN VERB NOUN ;

So what about the punctuation? As mentioned at the beginning of this section of this iteration, some grammars will require you to match the parentheses in the lexer first, and you'd have to use tokens like LPAREN and RPAREN in the parser. Many ANTLR grammars follow this same tradition. But it looks a little bulky to me.

sentence : NOUN VERB NOUN PERIOD ;
PERIOD : '.' ;

sentence : NOUN VERB NOUN '.' ;

The failure should be over your preorder traversal of the AST. The problem is that the rule is matching the tokens from the lexer, but the parser isn't building the right AST.

All of your previous rules have had to return one token as the AST, including program since it ignores the EOF token! But with an operator expression, you need to bundle the operator and its arguments into the AST. Based on the preorder traversal, the operator should be at the root, and the two arguments as subtrees.

ANTLR provides a couple different ways to specify your AST. You'll use a rewrite rule. A rewrite rule looks like this: -> ^(root token subtrees). Each alternative for a rule can have its own rewrite. (Advanced hint: the atom alternative does not need a rewrite.)

ANTLR provides some incredible magic when writing the rewrite rule.

sentence
  : NOUN VERB NOUN '.'
    -> (VERB NOUN+)
  ;

The TIR Builder

The problem will be in the TIR builder.

An example assertion:

assertEquals(
  new OperatorETIR(
    new IntegerETIR(1), Operator.LESS_THAN, new IntegerETIR(2)
    ),
        myTester.scanInput("(< 1 2)")
          .parseAs("program")
          .treeParseAs("program")
        );

Keep in mind that strings have their single quotes stripped off by the TIR builder.

The solution here is to add another alternative to the expression rule of the TIR builder. But this begs a question: why isn't there a separate atom rule in the TIR builder?

In general, a tree parser can (and will, in my experience) have fewer rules than a parser. This is because the parser needs to be able to handle many different kinds of patterns, and some of these patterns are hard (or impossible) to detect all at the same time.

Check out the Hobbes parser sometime. The expression, term, and factor levels are necessary to get proper associativity and precedence in binary expressions. Contrast this with the Hobbes TIR builder which is much simpler.

A tree parser is based on the token types in the roots of ASTs—a very easy pattern! The hard work is already done. This results in fewer rules for the tree parser.

sentence returns [Sentence s]
  : ^(verb=VERB subject=NOUN object=NOUN)
    { s = new Sentence(subject.getText(), verb.getText(), object.getText()); }

sentence returns [Sentence s]
  : ^(verb=VERB subject=nounPhrase object=nounPhrase)
    { s = new Sentence(subject, verb.getText(), object); }

Recursively calling the expression rule for the two subtrees will take care of them. Converting the operator will take just a little work. Here's an assertion from the CITKit library:

assertEquals(
  OperatorETIR.Operator.MULTIPLY, 
  OperatorETIR.Operator.convertPunctuation("*")
  );

You give the text of an OPERATOR token to this static method, and you'll get the right Operator out. (Also take a look at the Hobbes TIR builder. It has a special case to handle (the equals operator), and it has a more interesting AST to deal with, but it does use this method.)