Covh

V1

2022/01/18阅读:71主题:橙心

如何实现自己的计算机语言

antlr4

Antlr是指可以根据输入自动生成语法树并可视化的显示出来的开源语法分析器。ANTLR—Another Tool for Language Recognition,其前身是PCCTS,它为包括Java,C++,C#在内的语言提供了一个通过语法描述来自动构造自定义语言的识别器(recognizer),编译器(parser)和解释器(translator)的框架。

Antlr 是一个强大的跨语言语法解析器,可以用来读取、处理、执行或翻译结构化文本或二进制文件

antlr运行流程

  1. 词法分析(接收文本,源代码,输出token流,同时生成符号表)
  2. 语法分析(接收token stream并且生成语法树)
  3. 语义分析(讲语法树转换成能被cpu执行的中间代码)
  4. 解释器解释(调⽤宿主语⾔,或虚拟机直接执⾏代码)

安装antlr

打开官网anttr4

如果是macOS的话,执行以下代码

cd /usr/local/lib
$ sudo curl -O https://www.antlr.org/download/antlr-4.9.2-complete.jar
export CLASSPATH=".:/usr/local/lib/antlr-4.9.2-complete.jar:$CLASSPATH"
alias antlr4='java -jar /usr/local/lib/antlr-4.9.2-complete.jar'
alias grun='java org.antlr.v4.gui.TestRig'

如果是windows用户的话

  1. 下载antlr4 这里是下载地址
  2. 将 antlr-4.9.2-complete.jar 加入环境变量中

安装好之后可以通过antlr4 的命令来验证是否安装完毕

初始化TS项目

这里我们用typescript来编写antlr4的项目

  1. 创建一个新目录,我们暂且称呼该语言为A语言,并且初始化npm
mkdir ALang 
cd ALang  
npm init -y

  1. 安装antlr4ts,用于解析g4语法文件,antlr4ts-cli作为包管理器
yarn add antlr4ts
yarn add -D antlr4ts-cli
  1. 新建语法文件目录,这里我讲语法文件放入一个新目录
ALang>src>antlr>ALang.g4
  1. 设置package.json启动脚本,脚本的含义是用antlr4ts的访问者模式来解析ALang.g4文件
"scripts": {
  "antlr4ts""antlr4ts -visitor src/antlr/ALang.g4"
}
  1. 新建入口文件app.ts
touch app.ts
  1. 解析g4文件,会在src/antlr目录下生成相关ts文件
npm run antlr4ts

初始化的任务就结束了,接下来开始写相关代码了

语法文件

grammar Alang;
prog:   stat+ ;

// -------------给每个备选分支打标签

stat:   expr NEWLINE                # printExpr
    |   ID '=' expr NEWLINE         # assign
    |   NEWLINE                     # blank
    ;

expr:   expr MUL expr               # Multiplication
    |   expr ADD expr               # Addition
    |   expr DIV expr               # Division
    |   expr SUB expr               # Subtraction
    |   INT                         # int
    |   ID                          # id
    |   BooleanLiteral              # BooleanExpr
    |   '(' expr ')'                # parens
    ;

// -------------给运算符号设置名字,也形成词法符号

MUL :   '*' ;
DIV :   '/' ;
ADD :   '+' ;
SUB :   '-' ;
BooleanLiteral:                 'true'
              |                 'false';
// -------------剩下的是和之前一样的词法符号

ID  :   [\u4e00-\u9fa5_a-zA-Z]+ ;      // 标识符:一个到多个英文字母
INT :   [0-9]+ ;         // 整形值:一个到多个数字
NEWLINE:'\r''\n' ;     // 换行符
WS  :   [ \t]+ -> skip ; // 跳过空格和tab

  1. grammar Alang(是用来声明当前的语言名叫Alang)
  2. prog: stat+ (程序入口是prog,所以app.ts中会执行prog方法)
  3. stat和expr都是用来声明语法,规定了该语言是如何编写的
  4. 文件底部的是词法文件,是对词汇的描述,比如MUL代表的是“*”乘号,在anglr解析之后会生成对应的符号表

入口文件

这里需要按照antlr的执行顺序,依次对代码进行操作: 分别是:

  1. 词法分析(接收文本,源代码,输出token流,同时生成符号表)
  2. 语法分析(接收token stream并且生成语法树)
  3. 语义分析(讲语法树转换成能被cpu执行的中间代码)
  4. 解释器解释(调⽤宿主语⾔,或虚拟机直接执⾏代码)

完整代码如下

import {
    ANTLRInputStream, BufferedTokenStream, CharStream, CommonTokenStream
from "antlr4ts";
import { ALangLexer } from "./antlr/ALangLexer";
import { ALangParser } from "./antlr/ALangParser";
//将文本转换为token,并生成符号表
let inputStream: CharStream = new ANTLRInputStream("a=1+2\nb=a*2+1\nc=a*3+2*b\n");
// 词法分析
let lexer: ALangLexer = new ALangLexer(inputStream);
// 生成token流
let tokenStream: BufferedTokenStream = new CommonTokenStream(lexer);
//接收token并且生成语法树
let parser = new ALangParser(tokenStream);
//执行解析器
let tree = parser.prog();

实现访问者具体方法

antlr工具生成的可以使用的代码中,我们已经使用了两个文件,第一个是ALangLexer,第二个是ALangParser,还有两个我们没有使用到,分别是ALangListener和ALangVisitor

这里我们使用ALangVisitor,采用的访问者模式,更适合当前对树形结构的遍历

打开ALangVisitor文件我们可以看到它的源代码

// Generated from src/antlr/ALang.g4 by ANTLR 4.9.0-SNAPSHOT


import { ParseTreeVisitor } from "antlr4ts/tree/ParseTreeVisitor";

import { PrintExprContext } from "./ALangParser";
import { AssignContext } from "./ALangParser";
import { BlankContext } from "./ALangParser";
import { MultiplicationContext } from "./ALangParser";
import { AdditionContext } from "./ALangParser";
import { DivisionContext } from "./ALangParser";
import { SubtractionContext } from "./ALangParser";
import { IntContext } from "./ALangParser";
import { IdContext } from "./ALangParser";
import { BooleanExprContext } from "./ALangParser";
import { ParensContext } from "./ALangParser";
import { ProgContext } from "./ALangParser";
import { StatContext } from "./ALangParser";
import { ExprContext } from "./ALangParser";


export interface ALangVisitor<Result> extends ParseTreeVisitor<Result> {

 visitPrintExpr?: (ctx: PrintExprContext) => Result;
 visitAssign?: (ctx: AssignContext) => Result;
 visitBlank?: (ctx: BlankContext) => Result;
 visitMultiplication?: (ctx: MultiplicationContext) => Result;
 visitAddition?: (ctx: AdditionContext) => Result;
 visitDivision?: (ctx: DivisionContext) => Result;
 visitSubtraction?: (ctx: SubtractionContext) => Result;
 visitInt?: (ctx: IntContext) => Result;
 visitId?: (ctx: IdContext) => Result;
 visitBooleanExpr?: (ctx: BooleanExprContext) => Result;
 visitParens?: (ctx: ParensContext) => Result;
 visitProg?: (ctx: ProgContext) => Result;
 visitStat?: (ctx: StatContext) => Result;
 visitExpr?: (ctx: ExprContext) => Result;
}


源代码是一堆需要实现的接口类,所以我们需要对这些方法进行实现。新建一个ALangBaseVisitor.ts文件,实现上述接口类

import { AbstractParseTreeVisitor } from "antlr4ts/tree";
import { ALangVisitor } from "./antlr/ALangVisitor";
export default class ALangBaseVisitor
  extends AbstractParseTreeVisitor<number>
  implements ALangVisitor<number>{
    protected defaultResult(): number {
        throw new Error("Method not implemented.");
    }
  }
  1. visitPrintExpr方法,这里需要讲表达式进行递归调用,拿到最终的值,并且打印出文本
visitPrintExpr(ctx: PrintExprContext) {
  const value: number = this.visit(ctx.expr());
  const exprString: string = ctx.expr().text;
  console.log(exprString+":"+value.toString());
  return value;
}

2.visitAssign 赋值语句

  1. 需要拿到待赋值的变量名出
  2. 拿到药赋值的值
  3. 将计算之后的值存储在内存中,以便后续计算使用
  4. 计算结束之后需要清空内存
visitAssign(ctx: AssignContext) {
    const id: string = ctx.ID().text;
    const value: number = this.visit(ctx.expr());
    this.memory[id]=value;
    return value;
}
  1. visitMultiplication 乘法表达式,需要注意的就是乘法表达式两侧都是表达式,需要对两侧的表达式进行递归执行visitAddition,visitDivision,visitSubtraction都是同理
visitMultiplication(ctx: MultiplicationContext){
      const left: number = this.visit(ctx.expr(0));
      const right: number = this.visit(ctx.expr(1));
      return left*right;
};
  1. visitInt 在语法声明文件中,单独写一个数字也会默认为表达式语句,我将它原封不动返回
visitInt (ctx: IntContext){
    return parseInt(ctx.INT().text);
};
  1. visitId 访问到Id的时候,实际上是对Id的取值,这里就需要从缓存中读取Id的值,并且返回,如果没有读取到,则返回0
visitId (ctx: IdContext){
  const id: string = ctx.ID().text;
  if(this.memory[id]!=null){
      return this.memory[id]
  }
  return 0;
};
  1. visitParens 括号表达式,只需要对括号内对语句进行递归之行即可
visitParens(ctx: ParensContext){
    return this.visit(ctx.expr());
};

到此为止,访问者已经创建完毕,接下来我们在入口文件中使用该访问者,即可访问到之前生成的语法树的内容,并且执行访问者中的代码,就可以得到结果了

app.ts

import {
    ANTLRInputStream, BufferedTokenStream, CharStream, CommonTokenStream
} from "antlr4ts";
import ALangBaseVisitor from "./ALangBaseVisitor";
import { ALangLexer } from "./antlr/ALangLexer";
import { ALangParser } from "./antlr/ALangParser";



let inputStream: CharStream = new ANTLRInputStream("a=1+2\nb=a*2+1\nc=a*3+2*b\n");
let lexer: ALangLexer = new ALangLexer(inputStream);
let tokenStream: BufferedTokenStream = new CommonTokenStream(lexer);
let parser = new ALangParser(tokenStream);
let tree = parser.prog();

const exprBaseVisitor: ALangBaseVisitor = new ALangBaseVisitor();
const result: number = exprBaseVisitor.visit(tree);
console.log("计算结果是:",result);

和预期结果一致!

该demo是一个很小的antlr语言解析例子,采用了访问者模式对生成的语法树进行递归访问,做到了对语法树很小的入侵性。

源代码:

java版本: https://github.com/chesongsong/h-lang typescript版本: https://github.com/chesongsong/h-lang-ts

分类:

前端

标签:

JavaScript

作者介绍

Covh
V1