如何打造自己的計(jì)算機(jī)語言

antlr4

Antlr是指可以根據(jù)輸入自動(dòng)生成語法樹并可視化的顯示出來的開源語法分析器。ANTLR—Another Tool for Language Recognition，其前身是PCCTS，它為包括Java，C++，C#在內(nèi)的語言提供了一個(gè)通過語法描述來自動(dòng)構(gòu)造自定義語言的識(shí)別器（recognizer），編譯器（parser）和解釋器（translator）的框架。

Antlr 是一個(gè)強(qiáng)大的跨語言語法解析器，可以用來讀取、處理、執(zhí)行或翻譯結(jié)構(gòu)化文本或二進(jìn)制文件

antlr運(yùn)行流程

  1. 詞法分析(接收文本，源代碼，輸出token流，同時(shí)生成符號(hào)表)
  2. 語法分析（接收token stream并且生成語法樹）
  3. 語義分析（講語法樹轉(zhuǎn)換成能被cpu執(zhí)行的中間代碼）
  4. 解釋器解釋（調(diào)?宿主語?，或虛擬機(jī)直接執(zhí)?代碼）

安裝antlr

打開官網(wǎng)anttr4

如果是macOS的話,執(zhí)行以下代碼

$ 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 加入環(huán)境變量中

安裝好之后可以通過antlr4 的命令來驗(yàn)證是否安裝完畢

初始化TS項(xiàng)目

這里我們用typescript來編寫antlr4的項(xiàng)目

  1. 創(chuàng)建一個(gè)新目錄,我們暫且稱呼該語言為A語言，并且初始化npm
mkdir ALang 
cd ALang  
npm init -y
  1. 安裝antlr4ts，用于解析g4語法文件,antlr4ts-cli作為包管理器
yarn add antlr4ts
yarn add -D antlr4ts-cli
  1. 新建語法文件目錄，這里我講語法文件放入一個(gè)新目錄
ALang>src>antlr>ALang.g4
  1. 設(shè)置package.json啟動(dòng)腳本，腳本的含義是用antlr4ts的訪問者模式來解析ALang.g4文件
"scripts": {
  "antlr4ts": "antlr4ts -visitor src/antlr/ALang.g4"
}
  1. 新建入口文件app.ts
touch app.ts
  1. 解析g4文件，會(huì)在src/antlr目錄下生成相關(guān)ts文件
npm run antlr4ts
image

初始化的任務(wù)就結(jié)束了，接下來開始寫相關(guān)代碼了

語法文件

grammar Alang;
prog:   stat+ ;

// -------------給每個(gè)備選分支打標(biāo)簽

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
    ;

// -------------給運(yùn)算符號(hào)設(shè)置名字，也形成詞法符號(hào)

MUL :   '*' ;
DIV :   '/' ;
ADD :   '+' ;
SUB :   '-' ;
BooleanLiteral:                 'true'
              |                 'false';
// -------------剩下的是和之前一樣的詞法符號(hào)

ID  :   [\u4e00-\u9fa5_a-zA-Z]+ ;      // 標(biāo)識(shí)符：一個(gè)到多個(gè)英文字母
INT :   [0-9]+ ;         // 整形值：一個(gè)到多個(gè)數(shù)字
NEWLINE:'\r'? '\n' ;     // 換行符
WS  :   [ \t]+ -> skip ; // 跳過空格和tab
  1. grammar Alang(是用來聲明當(dāng)前的語言名叫Alang)
  2. prog: stat+ (程序入口是prog，所以app.ts中會(huì)執(zhí)行prog方法）
  3. stat和expr都是用來聲明語法，規(guī)定了該語言是如何編寫的
  4. 文件底部的是詞法文件，是對(duì)詞匯的描述，比如MUL代表的是“*”乘號(hào)，在anglr解析之后會(huì)生成對(duì)應(yīng)的符號(hào)表

入口文件

這里需要按照antlr的執(zhí)行順序，依次對(duì)代碼進(jìn)行操作：
分別是：

  1. 詞法分析(接收文本，源代碼，輸出token流，同時(shí)生成符號(hào)表)
  2. 語法分析（接收token stream并且生成語法樹）
  3. 語義分析（講語法樹轉(zhuǎn)換成能被cpu執(zhí)行的中間代碼）
  4. 解釋器解釋（調(diào)?宿主語?，或虛擬機(jī)直接執(zhí)?代碼）

完整代碼如下

import {
    ANTLRInputStream, BufferedTokenStream, CharStream, CommonTokenStream
} from "antlr4ts";
import { ALangLexer } from "./antlr/ALangLexer";
import { ALangParser } from "./antlr/ALangParser";
//將文本轉(zhuǎn)換為token，并生成符號(hào)表
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);
//執(zhí)行解析器
let tree = parser.prog();

實(shí)現(xiàn)訪問者具體方法

antlr工具生成的可以使用的代碼中，我們已經(jīng)使用了兩個(gè)文件，第一個(gè)是ALangLexer，第二個(gè)是ALangParser，還有兩個(gè)我們沒有使用到，分別是ALangListener和ALangVisitor

這里我們使用ALangVisitor，采用的訪問者模式，更適合當(dāng)前對(duì)樹形結(jié)構(gòu)的遍歷

打開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;
}

源代碼是一堆需要實(shí)現(xiàn)的接口類，所以我們需要對(duì)這些方法進(jìn)行實(shí)現(xiàn)。新建一個(gè)ALangBaseVisitor.ts文件,實(shí)現(xiàn)上述接口類

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方法,這里需要講表達(dá)式進(jìn)行遞歸調(diào)用，拿到最終的值，并且打印出文本
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. 將計(jì)算之后的值存儲(chǔ)在內(nèi)存中，以便后續(xù)計(jì)算使用
  4. 計(jì)算結(jié)束之后需要清空內(nèi)存
visitAssign(ctx: AssignContext) {
    const id: string = ctx.ID().text;
    const value: number = this.visit(ctx.expr());
    this.memory[id]=value;
    return value;
}
  1. visitMultiplication 乘法表達(dá)式，需要注意的就是乘法表達(dá)式兩側(cè)都是表達(dá)式，需要對(duì)兩側(cè)的表達(dá)式進(jìn)行遞歸執(zhí)行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 在語法聲明文件中，單獨(dú)寫一個(gè)數(shù)字也會(huì)默認(rèn)為表達(dá)式語句，我將它原封不動(dòng)返回
visitInt (ctx: IntContext){
    return parseInt(ctx.INT().text);
};
  1. visitId 訪問到Id的時(shí)候，實(shí)際上是對(duì)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 括號(hào)表達(dá)式，只需要對(duì)括號(hào)內(nèi)對(duì)語句進(jìn)行遞歸之行即可
visitParens(ctx: ParensContext){
    return this.visit(ctx.expr());
};

到此為止，訪問者已經(jīng)創(chuàng)建完畢，接下來我們?cè)谌肟谖募惺褂迷撛L問者，即可訪問到之前生成的語法樹的內(nèi)容，并且執(zhí)行訪問者中的代碼，就可以得到結(jié)果了

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("計(jì)算結(jié)果是：",result);
image

和預(yù)期結(jié)果一致！

該demo是一個(gè)很小的antlr語言解析例子，采用了訪問者模式對(duì)生成的語法樹進(jìn)行遞歸訪問，做到了對(duì)語法樹很小的入侵性。

源代碼：

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

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

關(guān)于我

微信：cjs764901388

公眾號(hào)：xstxoo

我的公眾號(hào)：小松同學(xué)哦

可以關(guān)注我，一起學(xué)習(xí)前端知識(shí)，喜歡把生活中用到技術(shù)的地方記錄下來

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容