Developing a compiler for the Cool educational language in C # for .NET (Part 1)

result <- (new A)@D.func()

Writing Cool Grammar in ANTLRWorks

program ::= [[class; ]]+
class ::= class TYPE [inherits TYPE] { [[feature; ]]*}
feature ::= ID( [ formal [[, formal]]*] ) : TYPE { expr } | ID : TYPE [ <- expr ]
formal ::= ID : TYPE
expr ::=
ID <- expr
| expr[@TYPE].ID( [ expr [[, expr]]*] )
| ID( [ expr [[, expr]]*] )
| if expr then expr else expr fi
| while expr loop expr pool
| { [[expr; ]] +}
| let ID : TYPE [ <- expr ] [[, ID : TYPE [ <- expr ]]]* in expr
| case expr of [[ID : TYPE => expr; ]]+ esac
| new TYPE
| isvoid expr
| expr + expr
| expr ? expr
| expr ? expr
| expr / expr
| ~expr
| expr < expr
| expr <= expr
| expr = expr
| not expr
| (expr)
| ID
| integer
| string
| true
| false

• The existence of left recursion . Of course, ANTLRWorks, based on the recursive descent method, will immediately detect and produce this kind of error: [fatal] rule compilation_unit has non-LL (*) decision due to recursive rule invocations reachable from alts ... Resolve by left-factoring or using syntactic predicates or using backtrack = true option ... And, of course, ANTLR has the option backtrack = true, which allows you to overcome this limitation. But applying it, you have to come to terms with another node in the generated spacecraft for expression with left recursion. So all the same, it would be nice to get rid of it. In addition, as can be seen from this article , this option slows down the parser and the author recommends abandoning it whenever possible.
• But the main thing is that the priority of operators is not taken into account in this form of grammar . If left recursion affects only the parser efficiency, ignoring this problem will lead to incorrect code generation later (for example, 2 + 2 * 2 will be 8, not 6)

• .
• @
• ~
• isvoid
• * /
• + -
• <= <=
• not
• <-

expr:
  (ID ASSIGN^)* not;
not:
  (NOT^)* relation;
relation:
  addition ((LE^ | LT^ | GE^ | GT^ | EQUAL^) addition)*;
addition:
  multiplication ((PLUS^ | MINUS^) multiplication)*;
multiplication:
  isvoid ((MULT^ | DIV^) isvoid)*;
isvoid:
  (ISVOID^)* neg;
neg:
  (NEG^)* dot;
dot:
  term ((ATSIGN typeName)? DOT ID LPAREN invokeExprs? RPAREN)? ->
  ^(Term term ID? typeName? invokeExprs?);

{$channel = Hidden;};

COMMENT : '--' .* ('\n'|'\r') {$channel = Hidden;};

ANTLR Operators

1. ! - needed so that extra language tokens do not interfere with parsing. For example, brackets and other operators that are needed only for the parser (for example, the same endings of fi, esac syntax constructs). The operator is needed to ensure that the syntax tree is built from the token stream, and not the parse tree).
2. -> - is needed in order to convert the sequence of tokens standing on the left side into a sequence of tokens standing on the right side, which would be convenient to process when generating the code. Together with this operator, the ^ operator is also used.
3. ^ is used to create a new node in the generated syntax tree from the token marked with this operator and its descendants. There are two forms to this operator:
   • Postfix. For example, for such a rule:

     relation: addition ((LE^ | LT^ | GE^ | GT^ | EQUAL^) addition)*;

     a node is inserted into the syntax tree with one of the operators indicated in parentheses and children addition , which is to the left of the operator and addition , which is to the right of the operator.
   • Prefix. For example, for such a rule:

     CLASS typeName (INHERITS typeName)? LCURLY featureList RCURLY -> ^(Class typeName featureList typeName?)

     the parent node of the Class with the descendants of typeName featureList typeName is inserted into the syntax tree ?

1. * - Iteration.
2. + - Positive iteration.
3. ? - A left-handed token or a group of tokens can either be present or absent.

STRING: '"'
{ StringBuilder b = new StringBuilder(); }
( '"' '"' { b.Append('"');}
| c=~('"'|'\r'|'\n') { b.Append((char)c);}
)*
'"'
{ Text = b.ToString(); }
;

@lexer::header {#pragma warning disable 3021
using System;
using System.Text;
}
@parser::header {#pragma warning disable 3021
using System.Text;}

• CoolGrammar.tokens
• CoolGrammarLexer.cs
• CoolGrammarParser.cs

Using the generated lexer in C # code

var stream = new ANTLRStringStream(Source); // Source - исходный код.
lexer = new CoolGrammarLexer(stream, new RecognizerSharedState() { errorRecovery = true });
IToken token;
token = lexer.NextToken();
while (token.Type != CoolGrammarLexer.EOF)
{
  // Здесь обрабатываем каждый токен.
  // Имя токена: CoolTokens.Dictionary[token.Type] (Например для '(' это LPAREN,
  //  используется дополнительный заранее подготовленный словарь, сопоставляющий имя токена и его значение)
  // Текст токена: token.Text (Например для '(' это просто "(")
  // Номер линии токена в коде: token.Line
  // Позиция токена в коде от начала строки: token.Column
  token = lexer.NextToken(); // Читаем следующий токен, то тех пор, пока не дойдем до конца файла.
}
// Далее перегружаем поток токенов и устанавливаем позицию в коде в 0,
// чтобы использовать этот же поток токенов потом (читай в парсере).
lexer.Reset();

var Lines = File.ReadAllLines(fileName);
Dictionary = new Dictionary(Lines.Length);
foreach (var line in Lines)
{
  var parts = line.Split('=');
  if (!Dictionary.ContainsKey(int.Parse(parts[1])))
    Dictionary.Add(int.Parse(parts[1]), parts[0]);
}

Using the generated parser in C # code

var tokenStream = new CommonTokenStream(lexer); // как получить lexer, было описано ранее. 
parser = new CoolGrammarParser(tokenStream);
Tree = parser.program(); // Самый верхний узел, отвечающий за аксиому грамматики (т.е. program в нашем случае).

• treeNode.ChildCount - the number of children at the treeNode node
• treeNode.GetChild (i) - getting a child from the treeNode node i
• treeNode.Type - the token of this node. It is of type int and must be compared with constants declared in the lexer class. For example: treeNode.Type == CoolGrammarLexer.EQUAL (whether a given token is a '=' sign). I want to note that when traversing a tree, it is necessary to use the Type property, not Text, since adding numbers is faster than comparing strings. the likelihood of error is reduced, since all constants are automatically generated.
• treeNode.Line - token line number in code
• treeNode.CharPositionInLine - token position in the code from the beginning of the line

Conclusion

catch (NoViableAltException nvae) {
  DebugRecognitionException(nvae);
  throw;
}

Recommended reading

• Definite ANTLR Reference, Terence Parr, 2007.
• Compilers Principles, Technologies and Tools, 2008, Alfred W. Aho, Monica S. Lam, Ravi Seti, Jeffrey D. Ullman