实现一个自己的编程语言——起步

美团点评送外卖
美团点评送外卖   编辑于 2018-10-25 00:53
阅读量: 115

首先我们准备实现的编程语言长啥样

# 这是一个注释

println("Hello World!");

println(2 + 3 * 4);

# 使用lambda作为声明函数的关键字
fib = lambda (n) if n < 2 then n else fib(n - 1) + fib(n - 2);

println(fib(15));

print-range = lambda(a, b)             # 声明函数
                if a <= b then {  # 并且实现 if else 控制流
                  print(a);
                  if a + 1 <= b {
                    print(", ");
                    print-range(a + 1, b);
                  } else println("");        # 每个 println 会自动缀上 \n
                };
print-range(1, 5);

emmm 大概长成这个样子,因为if else 之类的分界要是用python 的缩进可能比较困难,so 还是用花括号吧声明函数的话 用缩进还是不错的比较好实现。

我们需要实现的模块

一个单文件解释型语言解释器的组成基本这四个模块就可以搞定了。

  1. File Scanner 的工作就是把文件读出来然后封装一些方法方便Token splitor 的token 分割
  2. Tokensplitor 的工作就是将字符流 转换成Token 流,并且进行词法分析,主要分析的是有没有使用 var if = 1 这种使用if 关键字引用一个变量
  3. AST 这里其实就是语法分析,将Token 流生成一颗AST 
  4. Executor 中其实包含了中间代码生成和指令执行器,主要就是用来运行程序的

Lambda 语言的教程

变量和常量

var a = 10
var b = "10"
var c = true
var x = 10 + 10 

const ac = 10
const xc = 10 + 10

以上就是全部定义变量的语法

控制流程 if else 

if true then 
   10 + 10 
else 
   10 + 2 

if 10 + 10 > 0 then 
   10 + 10
else 
   10 + 2 

if true then
   hello()
else
   return 

控制流程大概这个样子就好,不要else if 了 可能会对token处理比较复杂

循环控制

for let i in [1..10] then
   println("Helloworld")

for let (index,item) in [1..10]then
   println(index,item)

while true then
   println("LOOP")

   

各种循环啦

定义和调用函数

var func = lambda(arg1,arg2){
   if arg1 == arg2 then
      println("TRUE")
   else
      println("FALSE")
}


var func2 = lambda(arg1,arg2){
   func1(arg1,arg2)
   return null
}

var func3 = lambda(arg1,arg2){
   return arg1 + arg2
}

 

大概以上的语法足够写点东西了,写点排序查找还是很easy 的。

 

描述一下我们的语言

描述语言当然会有描述语言专用的工具,Backus–Naur Form 基本就是描述语言的一种语法。

Backus–Naur Form

STATEMENT_DEFINE ::= DEFINITIONS  

所有的语法都应该被组织成上面的形式。那么规则有以下几种

  1. 双引号 "" 内的字符串表示这些字符串的本身 
  2. 双引号之外的东西应该是一个STATEMENT_DEFINE 
  3. () 内的东西,被划分为一个分组集合,认为是一组文法集合
  4. <> 内的东西是必选项
  5. [] 内的东西是可选项,并且是或的关系
  6. {} 表示一个文法单位重复的次数
  7. | 表达的是一个或关系

下面给出一个Java的for 循环的定义

for(;;){//body}
for(int i = 0;i < 10;i++){//body}
for(;i<10;i++){//body}

上面三个for循环,应该符合同一个文法规则

VAR_ASSIGN ::= [TYPE]" " VARIABLE "=" VALUE ";"
EXPER_STATEMENT ::= VARIABLE OPERATOR (VARIABLE | EXPER_STATEMENT)";"
BLOCK_STATEMENT ::= "{" (EXPER_STATEMENT | VAR_ASSIGN|EMPTY){*} "}"

FOR_STATEEMENT ::= "for""("
   (VAR_ASSIGN|EXPER_STATEMENT";"|;)
   [EXPER_STATEMENT]";"
   [EXPER_STATEMENT]";"
")" BLOCK_STATEMENT

ok 我们写出这样的一个文法规则,当然并不是完整的总结了java的文法,但是还是可以很清楚的发现一个for 循环应该被怎么写,按照什么文法规则书写

Lambda 语言的文法

首先我们根据上面的语法写出全部的文法范式描述。

 

收藏 转发 评论