Как я писал в своем последнем посте , я недавно начал работать над новым языком программирования под названием Турин. Работающий компилятор для начальной версии языка доступен на GitHub . В настоящее время я улучшаю язык и работаю над плагинами Maven и IntelliJ . Здесь и в следующих постах я рассмотрю различные компоненты компилятора и связанные с ним инструменты.
Структура компилятора
Компилятор должен сделать несколько вещей:
- Получить исходный код и сгенерировать абстрактное синтаксическое дерево (AST)
- Переведите AST на разные этапы, чтобы упростить обработку. В основном мы хотим перейти от представления, очень близкого к синтаксису, к представлению, которое легче обрабатывать. Например, мы могли бы «десугаризовать» язык, представляя несколько (очевидно) различных конструкций как варианты одной и той же конструкции. Пример? Компилятор Java переводит конкатенации строк в вызовы StringBuffer.append
- Выполните семантические проверки. Например, мы хотим проверить, все ли выражения используют допустимые типы (мы не хотим суммировать символы, верно?)
- Создать байт-код
Первый шаг требует создания двух компонентов: лексера и парсера. Лексер работает с текстом и создает последовательности токенов, в то время как анализатор формирует токены в конструкции (объявление типа, оператор, выражение и т. Д.), Создающие AST. Для написания лексера и парсера я использовал ANTLR.
В оставшейся части этого поста мы рассмотрим лексер. Парсер и другие компоненты компилятора будут рассмотрены в следующих публикациях.
Зачем использовать ANTLR?
ANTLR — очень зрелый инструмент для написания лексеров и парсеров. Он может генерировать код для нескольких языков и имеет приличную производительность. Он хорошо поддерживается, и я был уверен, что в нем есть все, что мне нужно, чтобы справиться со всеми угловыми случаями, которые я мог встретить. В дополнение к этому, ANTLR 4 позволяет писать простые грамматики, потому что он решает левое рекурсивное определение для вас. Таким образом, вам не нужно писать много промежуточных типов узлов для указания правил приоритета для ваших выражений. Подробнее об этом мы рассмотрим в парсере.
ANTLR используется Xtext (который я много использовал), и у меня есть ANTLR при создании инфраструктуры для разработки на основе моделей для платформы .NET (своего рода EMF для .NET). Так что я знаю ANTLR и доверяю ему, и у меня нет причин искать альтернативы.
Текущая грамматика лексера
Это текущая версия грамматики лексера.
|
001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
lexer grammar TurinLexer;@header {}@lexer::members { public static final int WHITESPACE = 1; public static final int COMMENTS = 2;}// It is suggested to define the token types reused in different mode.// See mode in-interpolation belowtokens { VALUE_ID, TYPE_ID, INT, LPAREN, RPAREN, COMMA, RELOP, AND_KW, OR_KW, NOT_KW }// Of course keywords has to be defined before the rules for identifiersNAMESPACE_KW : 'namespace';PROGRAM_KW : 'program';PROPERTY_KW : 'property';TYPE_KW : 'type';VAL_KW : 'val';HAS_KW : 'has';ABSTRACT_KW : 'abstract';SHARED_KW : 'shared';IMPORT_KW : 'import';AS_KW : 'as';VOID_KW : 'Void';RETURN_KW : 'return';FALSE_KW : 'false';TRUE_KW : 'true';IF_KW : 'if';ELIF_KW : 'elif';ELSE_KW : 'else';// For definitions reused in mode in-interpolation we define and refer to fragmentsAND_KW : F_AND;OR_KW : F_OR;NOT_KW : F_NOT;LPAREN : '(';RPAREN : ')';LBRACKET : '{';RBRACKET : '}';LSQUARE : '[';RSQUARE : ']';COMMA : ',';POINT : '.';COLON : ':';// We use just one token type to reduce the number of states (and not crash Antlr...)EQUAL : '==' -> type(RELOP);DIFFERENT : '!=' -> type(RELOP);LESSEQ : '<=' -> type(RELOP);LESS : '<' -> type(RELOP);MOREEQ : '>=' -> type(RELOP);MORE : '>' -> type(RELOP);// ASSIGNMENT has to comes after EQUALASSIGNMENT : '=';// Mathematical operators cannot be merged in one token type because// they have different precedencesASTERISK : '*';SLASH : '/';PLUS : '+';MINUS : '-';PRIMITIVE_TYPE : F_PRIMITIVE_TYPE;BASIC_TYPE : F_BASIC_TYPE;VALUE_ID : F_VALUE_ID;// Only for typesTYPE_ID : F_TYPE_ID;INT : F_INT;// Let's switch to another mode hereSTRING_START : '"' -> pushMode(IN_STRING);WS : (' ' | '\t')+ -> channel(WHITESPACE);NL : '\r'? '\n';COMMENT : '/*' .*? '*/' -> channel(COMMENTS);LINE_COMMENT : '//' ~[\r\n]* -> channel(COMMENTS);mode IN_STRING;STRING_STOP : '"' -> popMode;STRING_CONTENT : (~["\\#]|ESCAPE_SEQUENCE|SHARP)+;INTERPOLATION_START : '#{' -> pushMode(IN_INTERPOLATION);mode IN_INTERPOLATION;INTERPOLATION_END : '}' -> popMode;I_PRIMITIVE_TYPE : F_PRIMITIVE_TYPE -> type(PRIMITIVE_TYPE);I_BASIC_TYPE : F_BASIC_TYPE -> type(BASIC_TYPE);I_FALSE_KW : 'false' -> type(FALSE_KW);I_TRUE_KW : 'true' -> type(TRUE_KW);I_AND_KW : F_AND -> type(AND_KW);I_OR_KW : F_OR -> type(OR_KW);I_NOT_KW : F_NOT -> type(NOT_KW);I_IF_KW : 'if' -> type(IF_KW);I_ELSE_KW : 'else' -> type(ELSE_KW);I_VALUE_ID : F_VALUE_ID -> type(VALUE_ID);I_TYPE_ID : F_TYPE_ID -> type(TYPE_ID);I_INT : F_INT -> type(INT);I_COMMA : ',' -> type(COMMA);I_LPAREN : '(' -> type(LPAREN);I_RPAREN : ')' -> type(RPAREN);I_LSQUARE : '[' -> type(LSQUARE);I_RSQUARE : ']' -> type(RSQUARE);I_ASTERISK : '*' -> type(ASTERISK);I_SLASH : '/' -> type(SLASH);I_PLUS : '+' -> type(PLUS);I_MINUS : '-' -> type(MINUS);I_POINT : '.' -> type(POINT);I_EQUAL : '==' -> type(RELOP);I_DIFFERENT : '!=' -> type(RELOP);I_LESSEQ : '<=' -> type(RELOP);I_LESS : '<' -> type(RELOP);I_MOREEQ : '>=' -> type(RELOP);I_MORE : '>' -> type(RELOP);I_STRING_START : '"' -> type(STRING_START), pushMode(IN_STRING);I_WS : (' ' | '\t')+ -> type(WS), channel(WHITESPACE);fragment F_AND : 'and';fragment F_OR : 'or';fragment F_NOT : 'not';fragment F_VALUE_ID : ('_')*'a'..'z' ('A'..'Z' | 'a'..'z' | '0'..'9' | '_')*;// Only for typesfragment F_TYPE_ID : ('_')*'A'..'Z' ('A'..'Z' | 'a'..'z' | '0'..'9' | '_')*;fragment F_INT : '0'|(('1'..'9')('0'..'9')*);fragment F_PRIMITIVE_TYPE : 'Byte'|'Int'|'Long'|'Boolean'|'Char'|'Float'|'Double'|'Short';fragment F_BASIC_TYPE : 'UInt';fragment ESCAPE_SEQUENCE : '\\r'|'\\n'|'\\t'|'\\"'|'\\\\';fragment SHARP : '#'{ _input.LA(1)!='{' }?; |
Несколько вариантов, которые я сделал:
- Есть два разных типа идентификатора: VALUE_ID и TYPE_ID. Это позволяет иметь меньшую неопределенность в грамматике, потому что значения и типы могут быть легко различимы. В Java вместо этого, когда встречается (foo), мы не знаем, является ли оно выражением (ссылкой на значение, представленное foo между круглыми скобками) или приведением к типу foo. Нам нужно посмотреть на то, что следует, чтобы понять это. На мой взгляд, это довольно глупо, потому что на практике все используют заглавные идентификаторы только для типов, но поскольку это не обеспечивается языком, компилятор не может воспользоваться этим
- Символы новой строки актуальны в Турине, поэтому у нас есть для них токены, в основном мы хотим, чтобы операторы заканчивались символами новой строки, но мы принимаем необязательные символы новой строки после запятых
- пробелы (но новые строки) и комментарии записываются в их собственных каналах, так что мы можем игнорировать их в грамматике синтаксического анализатора, но мы можем извлекать их при необходимости. Например, они нужны нам для подсветки синтаксиса и вообще для плагина IntelliJ, потому что он требует определения токенов для каждого отдельного символа в исходном файле без пробелов
- самая сложная часть — это синтаксический анализ строковых интерполяций в стиле Ruby, таких как «меня зовут # {user.name}». Мы используем режимы: когда мы встречаем начало строки («), мы переключаемся в режим лексера IN_STRING. Находясь в режиме IN_STRING, если мы встречаем начало интерполированного значения (# {), мы переходим в режим лексера IN_INTERPOLATION. В режиме IN_INTERPOLATION нам нужно принять большинство токенов, используемых в выражениях (а это, к сожалению, означает много дублирования в нашей лексерской грамматике).
- Мне пришлось свернуть реляционные операторы в один тип токена, чтобы число состояний сгенерированного лексера не было слишком большим. Это означает, что мне придется просмотреть текст токенов RELOP, чтобы выяснить, какую операцию необходимо выполнить. Ничего страшного, но вы должны знать, как решить подобные проблемы.
Тестирование лексера
Я написал несколько тестов специально для лексера. В частности, я протестировал наиболее важную часть: ту, что касается интерполяции строк.
Пример нескольких тестов:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
@Test public void parseStringWithEmptyInterpolation() throws IOException { String code = "\"Hel#{}lo!\""; verify(code, TurinLexer.STRING_START, TurinLexer.STRING_CONTENT, TurinLexer.INTERPOLATION_START, TurinLexer.INTERPOLATION_END, TurinLexer.STRING_CONTENT, TurinLexer.STRING_STOP); } @Test public void parseStringWithInterpolationContainingID() throws IOException { String code = "\"Hel#{foo}lo!\""; verify(code, TurinLexer.STRING_START, TurinLexer.STRING_CONTENT, TurinLexer.INTERPOLATION_START, TurinLexer.VALUE_ID, TurinLexer.INTERPOLATION_END, TurinLexer.STRING_CONTENT, TurinLexer.STRING_STOP); } @Test public void parseStringWithSharpSymbol() throws IOException { String code = "\"Hel#lo!\""; verify(code, TurinLexer.STRING_START, TurinLexer.STRING_CONTENT, TurinLexer.STRING_STOP); } @Test public void parseMethodDefinitionWithExpressionBody() throws IOException { String code = "Void toString() = \"foo\""; verify(code, TurinLexer.VOID_KW, TurinLexer.VALUE_ID, TurinLexer.LPAREN, TurinLexer.RPAREN, TurinLexer.ASSIGNMENT, TurinLexer.STRING_START, TurinLexer.STRING_CONTENT, TurinLexer.STRING_STOP); } |
Как видите, я просто проверяю токен на строке и проверяю, что он выдает правильный список токенов. Легко и прямо в точку.
Выводы
Мой опыт использования ANTLR для этого языка не был идеальным: есть проблемы и ограничения. Необходимость сворачивать несколько операторов в один тип токена нехорошо. Повторять несколько определений токенов для разных режимов лексера плохо. Однако ANTLR оказался полезным инструментом на практике: он делает все, что ему нужно, и для каждой проблемы есть приемлемое решение. Решение может быть не идеальным, может быть не элегантным, как хотелось бы, но оно есть. Так что я могу использовать его и перейти к более интересным частям компилятора.