Об авторе Техническая команда zqlu Ant Financial Data Experience
Введение
Во фронтенд-разработке обычно упоминаются такие функции, как анализ грамматики, потому что бэкэнд отвечает за предоставление интерфейсов и фронтенд-вызовов. Так может ли фронтенд самостоятельно доделать функции, связанные с парсингом, и запустить его в браузере? Ответ положительный, в этой статье будет описан упрощенный язык под названиемExprязык, а ввод осуществляется в браузереExprКод выполняет такие функции, как проверка ошибок, выполнение и перевод.
2. Упрощенный язык выражений
Во-первых, давайте представим нашуExprязык,ExprВ этой статье рассматривается упрощенный язык, подобный C. Фрагмент кода выглядит следующим образом:
a = 2;
b = 3
c = a * (b + 2);
d = a / (c - 1);
a; // 应该输出2
b; // 应该输出3
c;
d;
Поведение первых 4 строк — это знакомые выражения присваивания, а последние 4 строки — операторы печати, то есть значения каждой переменной печатаются по очереди.Конечно, здесь также включены знакомые комментарии.
Вопрос в том, можем ли мы независимо анализировать код грамматики Expr на внешнем интерфейсе, а также интерпретировать и выполнять их? Если в фрагменте кода есть ошибка, можем ли мы дать точное сообщение об ошибке? Есть более интересные вопросы, наш язык Expr принимает инфиксные выражения, можем ли мы перевести входной код в код префиксного выражения? Можем ли мы выполнить форматирование кода во входном фрагменте кода? Можем ли мы перевести код Expr в исходный код на других языках?
Первый взгляд на последнийDemo, мы можем ввести код языка Expr в поле кода демо-страницы, нажать кнопку выполнить, и вы сможете увидеть результат после выполнения:
Эти функции используют ANTLR v4 для завершения синтаксического анализа грамматики в браузере и, наконец, реализуют такие функции, как проверка, интерпретация и выполнение грамматики.
3. Первое знакомство с ANTLR v4
Введение в ANTLR
Antlr4 — это еще один инструмент для распознавания языков, еще один инструмент для распознавания языков.
Парсер, созданный Antlr4, включает в себя лексический анализатор и анализатор синтаксиса Да, это лексический анализ и анализ синтаксиса в курсе «Принципы компиляции». Писал несколько лет, неужели фронтенд забыли?Нам нужно только знать, что лексический анализатор — это программа, которая преобразует входную последовательность символов кода в последовательность токенов, а парсер — это программа, которая преобразует последовательность токенов в синтаксическое дерево. К счастью, определение грамматики сформулировано в соответствии со спецификацией Antlr4, и Antlr4 может генерировать исходный код парсера для нас, причем не только исходный код Java, но и генерировать исходный код JavaScript и TypeScript, удобный для нашего интерфейса. Да, в этой статье мы собираемся использовать версию парсера TypeScript, сгенерированную Antlr4, для анализа кода нашего языка Expr.
Установка и использование ANTLR v4
Для установки и использования Antlr4 вы можете обратиться к GithubGetting Started with ANTLR v4, здесь не представлено. Короче говоря, использование ANTLR v4 обычно делится на три этапа:
- Напишите файл определения грамматики языка, который необходимо проанализировать в соответствии с ANTLR v4. Определение грамматики ANTLR v4 для основного языка можно найти на складе.antlr/grammars-v4Найдено в , обычно используйте g4 в качестве суффикса файла определения грамматики.
- Запустите инструмент ANTLR, чтобы сгенерировать исходный код синтаксического анализатора для указанного целевого языка.
- Используйте сгенерированный парсер для завершения разбора кода и т. д.
В-четвертых, грамматическое определение языка Expr
Согласно приведенному выше введению, для интерпретации и выполнения нашего языка Expr первым шагом является определение файла определения грамматики Expr.g4 языка Expr в соответствии со спецификацией ANTLR v4. Вот краткое введение в идею определения грамматики ANTLR v4, Для более подробного ознакомления, пожалуйста, обратитесь к книге «Полное руководство по ANTLR 4» автора ANTLR.
грамматические правила
Файл определения грамматики ANTLR v4 использует операторы объявления грамматики и ряд грамматических правил грамматики.Общая структура выглядит следующим образом:
grammar Name; # 申明名为Name的语法
# 一次定义语法规则
rule1
rule2
...
ruleN
Структура каждого грамматического правила выглядит следующим образом:
ruleName: alternative1 | alternative2 | alternative3 ;
Это правило грамматики объявляет правило с именемruleNameправила, которые|Имя таблицы — ветвь, то есть правило может соответствовать любой из трех ветвей.
Наконец, грамматические правила ANTLR v4 делятся на лексические (Lexer) правила и грамматические правила (Parser): лексические правила определяют, как преобразовывать последовательности кодовых строк в последовательности токенов, а правила грамматики определяют, как преобразовывать последовательности токенов в синтаксические деревья. Как правило, имена правил лексических правил обозначаются прописной буквой, а имена правил грамматики — строчными буквами.
Синтаксис выражения
Для нашей грамматики Expr определенная грамматика Expr.g4 выглядит следующим образом:
grammar Expr;
prog
: stat+ ;
stat
: exprStat
| assignStat
;
exprStat
: expr SEMI
;
assignStat
: ID EQ expr SEMI
;
expr
: expr op = (MUL | DIV ) expr # MulDivExpr
| expr op = ( ADD | SUB ) expr # AddSubExpr
| INT # IntExpr
| ID # IdExpr
| LPAREN expr RPAREN # ParenExpr
;
MUL : '*' ;
DIV : '/' ;
ADD : '+' ;
SUB : '-' ;
LPAREN : '(' ;
RPAREN : ')' ;
ID : LETTER (LETTER | DIGIT)* ;
INT : [0-9]+ ;
EQ : '=' ;
SEMI : ';' ;
COMMENT : '//' ~[\r\n]* '\r'? '\n'? -> channel(HIDDEN);
WS : [ \r\n\t]+ -> channel(HIDDEN);
fragment
LETTER : [a-zA-Z] ;
fragment
DIGIT : [0-9] ;
Можно видеть, что определение грамматики использует метод построения сверху вниз, и наш код Expr основан на правилахprogКак правило,progпо нескольким операторамstatсостав; в то время как предложениеstatможет быть оператором выраженияexprStateЗаявление о живом назначенииassignState; в свою очередь, до последнего уровня выражений правил грамматикиexpr, выражение может быть операцией сложения, вычитания, умножения и деления, состоящей из выражений, или целым числомINT,ПеременнаяID,УведомлениеexprВ правилах используются рекурсивные выражения, т.е.exprУпоминается в определении правилаexpr, что также является особенностью ANTLR v4. Наконец, определенные здесь лексические правила включают правила сложения, вычитания, умножения и деления, круглых скобок, переменных, целых чисел, присваиваний, комментариев и пробелов; обратите внимание на комментарии (COMMENT) и пустой (WS) правила определеныchannel(HIDDEN), что означает, что при синтаксическом анализе необходимо игнорировать комментарии и пробелы.
иметь грамматическое определениеExpr.ge, мы можем сгенерировать исходный код нужного нам парсера.Здесь мы используем antlr4ts и добавляем скрипт в package.json:
"scripts": {
"antlr4ts": "antlr4ts -visitor Expr.g4 -o src/parser"
},
"dependencies": {
"antlr4ts": "^0.4.1-alpha.0"
}
"devDependencies": {
"antlr4ts-cli": "^0.4.0-alpha.4",
"typescript": "^2.5.3",
},
воплощать в жизньnpm run antlr4ts, ты сможешьsrc/parserКаталог видит исходный код TypeScript сгенерированного парсера Expr.
5. Интерпретатор языка Expr
С синтаксическим анализатором языка Expr мы можем использовать синтаксический анализатор для реализации нашего интерпретатора языка Expr.Конкретная цель, которую необходимо достичь, состоит в том, чтобы ввести код языка Expr и, наконец, распечатать результат выполнения.
Код и синтаксические деревья
Как использовать ANTLR для интерпретации кода Expr, который выполняет ввод, давайте сначала посмотрим на следующий входной код, что такое последовательность токенов и синтаксическое дерево, сгенерированное ANTLR?
a = 1;
b = a + 1;
b;
Последовательность токенов, полученная с помощью лексического анализа, показана на рисунке ниже, который разбит на 22 токена.Каждый токен содержит порядковый номер токена, текст токена и тип токена, например, токен, серийный номер которого равен 0, текст — «a», а тип — «ID», что соответствует нашемуExpr.g4лексические правилаID.
Структура синтаксического дерева показана на рисунке ниже, а узлы в дереве соответствуютExpr.g4Правила грамматики или лексические правила, определенные в , следует отметить, что все листовые узлы в дереве грамматики соответствуют лексическим правилам или символьным константам, что мы и разрабатываем.Expr.g4Такой же подход к проектированию сверху вниз.
Видно, что следующий узелprogУзел правила, его дочерние узлы - это три оператораstatузел, где первые два дочерних узла являются операторами присваиванияassignStatузел, последний дочерний узел является узлом оператора выраженияstatExpr. Согласно определению в первой части, для этого кода нам нужно идентифицировать оператор выражения в коде и напечатать значение выражения. В частности, в этом примере в этом входном коде используется только один оператор выражения, а выражение в нем является переменной b. Чтобы напечатать значение b, нам нужно интерпретировать первые два оператора для вычисления значения b (данные здесь Не забывайте, что ссылка на переменную должна идти после определения переменной). Следовательно, общая идея состоит в том, что нам нужно интерпретировать каждое утверждение по порядку и помнить переменные и их значения, которые появляются в процессе интерпретации утверждения.В процессе интерпретации последующих утверждений, если встречается ссылка на переменную, нам нужно найти значение переменной .
Используйте посетителя для доступа к дереву синтаксиса
Чтобы реализовать описанный выше процесс интерпретации, нам нужно пройти через синтаксическое дерево, проанализированное синтаксическим анализатором. ANTLR предоставляет два механизма для доступа к сгенерированному синтаксическому дереву: прослушиватель и посетитель. При использовании режима прослушивателя для доступа к синтаксическому дереву внутренний ANTLRParserTreeWalkerВ процессе обхода узлов синтаксического дерева при встрече с разными узлами будут вызываться разные методы предоставленного слушателя, при использовании режима «Посетитель» посетителю необходимо указать самому, что при обращении к определенному типу узла, исходный код синтаксического анализатора, сгенерированный ANTLR. Содержит базовый класс/интерфейс посетителя по умолчанию.ExprVisitor.ts, в процессе использования нужно только реализовать метод посещения интересующей ноды, например, нам нужно получить доступ кexprStatNode, нужно только реализовать следующий интерфейс:
export interface ExprVisitor<Result> extends ParseTreeVisitor<Result> {
...
/**
* Visit a parse tree produced by `ExprParser.exprStat`.
* @param ctx the parse tree
* @return the visitor result
*/
visitExprStat?: (ctx: ExprStatContext) => Result;
...
}
После знакомства с использованием Visitor для доступа к узлам синтаксического дерева давайте реализуем Visitor, требуемый интерпретатором Expr:ExprEvalVisitor.
Как упоминалось выше, в процессе доступа к синтаксическому дереву нам необходимо записать встречающиеся переменные и их значения, а также конечный результат печати.Мы используем внутренние переменные Visitor для сохранения этих промежуточных значений:
class ExprEvalVisitor extends AbstractParseTreeVisitor<number>
implements ExprVisitor<number> {
// 保存执行输出结果
private buffers: string[] = [];
// 保存变量
private memory: { [id: string]: number } = {};
}
Какие узлы синтаксического дерева нам нужно посетить? Во-первых, для окончательного результата оператор выраженияexprStateДоступ является наиболее важным, мы обращаемся к выражению в операторе выражения, чтобы получить значение выражения, и печатаем значение в результате выполнения. Поскольку оператор выражения состоит из выражения и точки с запятой, нам нужно продолжать обращаться к выражению, чтобы получить значение этого оператора, а точку с запятой игнорировать:
class ExprEvalVisitor extends AbstractParseTreeVisitor<number>
implements ExprVisitor<number> {
// 保存执行输出结果
private buffers: string[] = [];
// 保存变量
private memory: { [id: string]: number } = {};
// 访问表达式语句
visitExprStat(ctx: ExprStatContext) {
const val = this.visit(ctx.expr());
this.buffers.push(`${val}`);
return val;
}
}
Приведенное выше рекурсивно обращается к узлу выражения в операторе выражения.Какой метод доступа используется на этапе выражения? Возвращаясь к нашему определению грамматики Expr.g4, выражение состоит из ветвей 5. Для разных ветвей методы обработки разные, поэтому мы используем разные методы доступа для разных ветвей. Мы добавили разные аннотации после разных ветвей.В парсере, сгенерированном этими аннотациями, их можно использовать для различения разных типов узлов.В сгенерированном Посетителе можно увидеть разные интерфейсы:
export interface ExprVisitor<Result> extends ParseTreeVisitor<Result> {
...
/**
* Visit a parse tree produced by the `MulDivExpr`
* labeled alternative in `ExprParser.expr`.
* @param ctx the parse tree
* @return the visitor result
*/
visitMulDivExpr?: (ctx: MulDivExprContext) => Result;
/**
* Visit a parse tree produced by the `IdExpr`
* labeled alternative in `ExprParser.expr`.
* @param ctx the parse tree
* @return the visitor result
*/
visitIdExpr?: (ctx: IdExprContext) => Result;
/**
* Visit a parse tree produced by the `IntExpr`
* labeled alternative in `ExprParser.expr`.
* @param ctx the parse tree
* @return the visitor result
*/
visitIntExpr?: (ctx: IntExprContext) => Result;
/**
* Visit a parse tree produced by the `ParenExpr`
* labeled alternative in `ExprParser.expr`.
* @param ctx the parse tree
* @return the visitor result
*/
visitParenExpr?: (ctx: ParenExprContext) => Result;
/**
* Visit a parse tree produced by the `AddSubExpr`
* labeled alternative in `ExprParser.expr`.
* @param ctx the parse tree
* @return the visitor result
*/
visitAddSubExpr?: (ctx: AddSubExprContext) => Result;
...
}
Итак, в нашемExprEvalVisitor, мы получаем доступ к разным ветвям выражений, реализуя разные интерфейсы, дляAddSubExprBranch, метод доступа реализован следующим образом:
visitAddSubExpr(ctx: AddSubExprContext) {
const left = this.visit(ctx.expr(0));
const right = this.visit(ctx.expr(1));
const op = ctx._op;
if (op.type === ExprParser.ADD) {
return left + right;
}
return left - right;
}
дляMulDivExpr, способ доступа тот же. дляIntExprветвь, так как ее дети имеют толькоINTnode, нам нужно только разобрать в нем целые числа:
visitIntExpr(ctx: IntExprContext) {
return parseInt(ctx.INT().text, 10);
}
дляIdExprВетка, чьи дочерние элементы имеют только переменныеID, в это время нам нужно найти эту переменную в нашей сохраненной переменной и вынуть ее значение:
visitIdExpr(ctx: IdExprContext) {
const id = ctx.ID().text;
if (this.memory[id] !== undefined) {
return this.memory[id];
}
return 0;
}
для последней веткиParenExpr, его метод доступа очень прост, просто нужно получить доступ к выражению в скобках:
visitParenExpr(ctx: ParenExprContext) {
return this.visit(ctx.expr());
}
На этом этапе вы можете обнаружить, что вышеуказанные методы доступа складываются.У нас есть только процесс чтения переменных из памяти, но не процесс записи переменных из памяти, который требует от нас доступа к выражениям присваивания.assignExprУзел: для выражений присваивания вам необходимо указать имя переменной слева от знака равенства и выражение справа от знака равенства и, наконец, сохранить имя переменной и значение выражения справа в памяти:
visitAssignStat(ctx: AssignStatContext) {
const id = ctx.ID().text;
const val = this.visit(ctx.expr());
this.memory[id] = val;
return val;
}
Интерпретация и выполнение языка Expr
Пока наш гостьExprEvalVisitorОн готов, нам нужно только использовать посетителя для доступа к проанализированному синтаксическому дереву для указанного входного кода, а затем мы можем реализовать интерпретацию и выполнение кода Expr:
// Expr代码解释执行函数
// 输入code
// 返回执行结果
function execute(code: string): string {
const input = new ANTLRInputStream(code);
const lexer = new ExprLexer(input);
const tokens = new CommonTokenStream(lexer);
const parser = new ExprParser(tokens);
const visitor = new ExprEvalVisitor();
const prog = parser.prog();
visitor.visit(prog);
return visitor.print();
}
Шесть, транслятор выражений префикса кода Expr
В предыдущем введении мы интерпретировали и выполняли код Expr через ANTLR. В сочетании с введением ANTLR: ANTLR используется для чтения, обработки, выполнения и перевода структурированного текста. Итак, можем ли мы использовать ANTLR для перевода входного кода Expr? В языке Expr выражения являются нашими обычными инфиксными выражениями, можем ли мы перевести их в префиксные выражения? Помните, как преобразовывать инфиксные выражения в префиксные выражения, используя pop и push в курсе структуры данных? Не помните, мы также можем просто переключиться на конвертацию с помощью парсера, сгенерированного ANTLR.
Например, для следующего кода Expr:
a = 2;
b = 3;
c = a * (b + 2);
c;
Результат после нашего преобразования следующий: мы делаем преобразование для выражения отсоединения, но не делаем преобразование для выражения присваивания, то есть выражения, встречающиеся в коде, будут преобразованы в:
a = 2;
b = 3;
c = * a + b 2;
c;
Посетитель перевода префикса
Опять же, здесь мы используем режим посетителя для доступа к дереву синтаксиса, на этот раз мы напрямую посещаем корневой узел.progи возвращает переведенный код:
class ExprTranVisitor extends AbstractParseTreeVisitor<string>
implements ExprVisitor<string> {
defaultResult() {
return '';
}
visitProg(ctx: ProgContext) {
let val = '';
for (let i = 0; i < ctx.childCount; i++) {
val += this.visit(ctx.stat(i));
}
return val;
}
...
}
Здесь мы предполагаем, что наш посетитель находится в заявлении посетителя.stat, переведенный код был возвращен, поэтомуvisitProgПросто соедините переведенный код каждого оператора. Для операторов, как упоминалось ранее, мы не переводим операторы, поэтому доступ к их посещению также очень прост: для операторов-выражений напечатайте переведенное выражение напрямую и добавьте точку с запятой; для операторов присваивания просто подождите. знак можно перевести:
visitExprStat(ctx: ExprStatContext) {
const val = this.visit(ctx.expr())；
return `${val};\n`;
}
visitAssignStat(ctx: AssignStatContext) {
const id = ctx.ID().text;
const val = this.visit(ctx.expr());
return `${id} = ${val};\n`;
}
Давайте посмотрим, как переводить различные выражения. дляAddSubExprа такжеMulDivExprПеревод — это логика всего транслятора, то есть к нему добавляется оператор:
visitAddSubExpr(ctx: AddSubExprContext) {
const left = this.visit(ctx.expr(0));
const right = this.visit(ctx.expr(1));
const op = ctx._op;
if (op.type === ExprParser.ADD) {
return `+ ${left} ${right}`;
}
return `- ${left} ${right}`;
}
visitMulDivExpr(ctx: MulDivExprContext) {
const left = this.visit(ctx.expr(0));
const right = this.visit(ctx.expr(1));
const op = ctx._op;
if (op.type === ExprParser.MUL) {
return `* ${left} ${right}`;
}
return `/ ${left} ${right}`;
}
Поскольку скобки в префиксных выражениях не нужны,ParenExprЧтобы получить доступ, просто поместите скобки:
visitParenExpr(ctx: ParenExprContext) {
const val = this.visit(ctx.expr());
return val;
}
Для других узлов больше никакой обработки не требуется, просто верните отмеченный текст, соответствующий узлу:
visitIdExpr(ctx: IdExprContext) {
const parent = ctx.parent;
const id = ctx.ID().text;
return id;
}
visitIntExpr(ctx: IntExprContext) {
const parent = ctx.parent;
const val = ctx.INT().text;
return val;
}
Выполнить перевод префикса кода
На данный момент Посетитель для нашего перевода префикса кода готов.Точно так же процесс выполнения также очень прост.Для входного кода разберите и сгенерируйте синтаксическое дерево,используйтеExprTranVisitorриторический вопросprogКорневой узел, вы можете вернуть переведенный код:
function execute(code: string): string {
const input = new ANTLRInputStream(code);
const lexer = new ExprLexer(input);
const tokens = new CommonTokenStream(lexer);
const parser = new ExprParser(tokens);
const visitor = new ExprTranVisitor();
const prog = parser.prog();
const result = visitor.visit(prog);
return result;
}
Для входного кода:
A * B + C / D ;
A * (B + C) / D ;
A * (B + C / D) ;
(5 - 6) * 7 ;
Результат выполнения:
+ * A B / C D;
/ * A + B C D;
* A + B / C D;
* - 5 6 7;
7. Резюме
Я полагаю, что с помощью приведенного выше исполнителя языка Expr вы увидели, что с помощью ANTLR v4 разработчики внешнего интерфейса также могут выполнять множество операций, связанных с синтаксическим анализом, в сегменте браузера.
Если вы хотите узнать, как мы используем ANTLR для разбора сложного кода SQL, выполнения проверки синтаксиса кода SQL и как использовать ANTLR для форматирования сценариев SQL, вы можете подписаться на эту колонку или отправить свое резюме по адресу tao.qit#### alibaba-inc.com '.replace('####', '@'), приглашаем людей с высокими идеалами присоединиться~
Оригинальный адрес:GitHub.com/proto team/no…