使用Python构建一种简单但高级的JSONIC语言
#javascript #python #json #算法

Blog on LinkedIn

先决条件

  • 此博客的源代码
  • Python支持

本指南的布局

  • 动机
  • 简介
  • 字符流
  • 前缀检查(PEEK,Current,Advance)
  • 递归下降
  • 错误处理
  • 跳过白空间
  • 进口
  • 从后端到前端
  • 对象范围
  • 标志
  • 方法链接
  • 解释空对象
  • Scoping
  • 表达
  • 结束方法链接
  • 结论
  • 参考

此博客的源代码:

Source Code

我们使用的小公用事业库:

utility library

Python支持

在此博客中,我们使用python v3.8.x,但您可以使用v3.5或更高版本。请注意,自3.5自3.5以来的类型注释得到了支持。

对于任何有兴趣构建自己语言的第一个原型的开发人员来说,此博客都是一个很好的开端。高级Python技能当然是最佳的。

动机

在Voxgig工作时,我对我们为模型驱动的应用程序使用的提示语言原型如何在幕后工作了。只是它的基础。但是,即使基本知识在我眼中似乎也很复杂。因此,我想让它看起来简单,并提高我对语言的理解。这在许多方面为我创造了奇迹。从为什么我们可以写

foo:bar:zoo: 1

为什么JavaScript在:
上引发错误

console.log('hi!')
(10 + 10) * 1


/*
 * Uncaught TypeError: console.log(...) is not a function
     at <anonymous>:3:1
*/

介绍

作为开发人员,我们一直喜欢尝试建立和自定义自己的工具包 - 无论是出于好奇还是出于必要。

此博客将为您提供一些有关如何构建自己的基本语言的准则和基本知识,在我们的情况下是一种JSONIC语言,并根据您的需求进行自定义。 jsonic语言是一种类似JSON的语言,具有有趣但有用的语法功能,例如表达式,范围,调用函数等。

阅读此博客后,您不仅了解如何构建高级JSonic语言的基础知识,而且还会使用简单的算法来实现这一目标,这将提高生产力并降低混乱!

我们语言的原型在Python中,但我们尝试尽可能抽象,以便您可以选择您选择的语言来构建自己的这种语言版本。当然,诸如垃圾收集器之类的东西是内置的,所以我们不会掩盖,如果您想使用c。

之类的语言

字符流

为了直接削减追逐,我们将忽略CharStream类的实现,并证明其功能。您的源代码实际上是您的朋友,CharStream类非常简单,是我们项目的核心。

char_stream = CharStream("welcome!")
char_stream.peek() == 'w' # True
char_stream.advance() 
char_stream.peek() == 'e' # True

对于前缀检查,我们使用 peek()当前 charstream 类的方法,然后用 Advance消费字符( )将一个角色向前移动并返回当前一个字符。
将其与python内置 iter

stream = iter("welcome")

next(stream) == 'w'

next(stream) == 'e' # it is 'e' now - there isn't really a way to check the current char but not advance

前缀检查

如果字符流窥视某个字符,我们可以轻松地确定该令牌的类型,然后用它滚动直到循环完成,然后对其进行评估。

我们将一口气应用扫描,解析和评估 - 也就是说,我们不会生成Lexer和AST。相反,我们直接跳到解释我们的对象。

开始:

def interpret_obj(char_stream: CharStream, advance: bool, ...):
  if advance:
    char_stream.advance()
  skip_space(char_stream)
  if char_stream.peek().isdigit():
    value = ''
    while char_stream.peek().isdigit():
      value += char_stream.advance()
    skip_space(char_stream)
    return int(value, 10) # base 10
...
      Snippet 1

在这里,bool Advance 参数将是一个帮助,因为每次我们匹配某个角色时,我们可能会忘记消耗它 - 因此我们将其通过真实,如有必要,false。<<<<<<<<<<<<< /p>

我们回到此逻辑上以整理标识符并引入标志。

def scan_id(char_stream: CharStream, advance: bool):
  if advance:
    char_stream.advance()
  value = ''
  if not char_stream.peek().isalpha():
    raise SyntaxError("Expected an identifier to start with an alpha")
  while char_stream.peek().isalpha() or char_stream.peek().isdigit():
    value += char_stream.advance()
  return value

def interpret_obj(char_stream: CharStream, advance: bool, scope: dict, flags: utils.Map):
  ...
  elif char_stream.peek().isalpha() and flags.temFlag:
    identifier = scan_id(char_stream, False)
    skip_space(char_stream) # clear up the following white space
    if flags.isKey:
      return identifier
    if identifier not in scope.keys():
      raise NameError(identifier + " not defined!")
    return scope[identifier]
  ...
      Snippet 2

更多, utils.map 与典型 dict 相似,只是仅使用 obj ['key1'] <仅访问其值/strong>,但使用 obj.key1 obj ['key1'] ,更像是javascript。

setAttr getAttribute strong> dict 在标志部分上的标志上更多。

递归下降

我们的小语言只会使用一种主要算法,并且仍然足够好,可以支持高级语法功能,例如:范围,方法链,表达式和调用函数。

在本系列中,我们优先考虑典型 json 数据,即: null 数字 string ,< strong>对象和 array

但是,本指南仅向您展示如何支持数字,因为它更容易完全理解它,并且您可以使用相同的方法来扫描其他类型。它们将很容易适合其余的代码 - 您只需要编写一些条件即可识别这些类型。

例如,数组以字符 [而开始,并以] 结尾,而字符串则以“。”。

不要流汗!这是一个博客系列,所以还有更多。

错误处理

检测语法错误很重要。处理它们的方法是抛出异常!

抛出这种算法的例外是理想的选择,因为无论深度如何

跳过白色空间

要跳过空白,我们只是窥视''或'\ n'然后前进到下一个角色。

def skip_space(char_stream: CharStream):
  while not char_stream.is_over() and (char_stream.peek() == ' ' or char_stream.peek() == '\n'):
    char_stream.advance() # consume the white space
      Snippet 3

进口

在此博客中,我们使用: sys utils parser

import sys # built-in python sys module
import utils # this-project-specific set of utilities – see examples: https://github.com/BeAllAround/py_utils
from parser import CharStream # library that will help us with scanning/lexical analysis
      Snippet 4

我们建议您尽可能多地编写自己的后端库。它使您的语言开放到更大的功能,例如合并嵌套对象,例如: {a:1,{b:2}} 等。

从后端到前端

对我们来说,前端将扫描和解析文本,以便我们可以使用后端模块进行评估:
前端 扫描和解析
后端 评估
前端 +后端 解释

Python本身是该语言的后端引擎,用于其内置错误处理系统和 dict 的引擎盖下的方法, str 列表例如 添加 eq getItem < /strong>等。但是我们将退后一步,专注于不内置的模块。

扫描和解析时,我们必须考虑评估。那是公用事业根据我们想做的事情发挥作用的时候。

一个很好的例子是合并对象的深度扩展功能。

merge({foo: {a: 1}}, {foo: {b:2}}) => {foo: {a: 1, b: 2}}

考虑到这一点,我们需要一个函数才能合并两个对象,如上面的示例中的对象。

utils.deep_update(obj1, obj2)

对象范围

我们语言的目的是解释对象。现在我们知道如何应用前缀检查,我们都将开始启动!

如果我们尝试解释:“ {1:1}”

def interpret_obj(char_stream: CharStream, advance: bool, scope: dict, flags: utils.Map):
  if advance:
    char_stream.advance();
  ...
  elif char_stream.peek() == '{':
    obj = {}
    while True:
      key = interpret_obj(char_stream, True, scope, utils.Map({'temFlag': True, 'isKey': True,}) ) # key == 1
      skip_space(char_stream)
      if char_stream.peek() == ':':
        value = interpret_obj(char_stream, True, obj, utils.Map({'temFlag': True, 'isKey': False,}) )
        utils.deep_update(obj, { key: value }) # obj now equals to "{1: 1}" – see docs: https://github.com/BeAllAround/py_utils
        if char_stream.peek() == '}':
          char_stream.advance() # eat '}'
          skip_space(char_stream)
          return obj
        elif char_stream.peek() == ',':
          continue
        else:
          raise SyntaxError("Unexpected char " + char_stream.current)
      else:
        raise SyntaxError("Unexpected char " + char_stream.current)
  else:
    raise SyntaxError("Unexpected char " + char_stream.current)
      Snippet 5

标志

启用和注册功能,我们可以简单地使用utils.map的实例,其中包含供我们使用的标志。

我们可以将布尔人传递给我们的功能,但这很难维护。

比较以下两个片段:

def interpret_obj(char_stream: CharStream, ..., flags: utils.Map):
  ...
    value = interpret_obj(char_stream, ..., utils.Map({'temFlag': True, 
                                                   'isKey': False,}) )
  ...
      Snippet 6
def interpret_obj(char_stream: CharStream, ..., temFlag = False, isKey = False):
  ...
    value = interpret_obj(char_stream, ..., True, False)
  ...
      Snippet 7

您可以看到,前者可显着提高可读性,并在您拾取新功能时简化添加新标志。

仍然,这种方法不错,需要一些重构,我们可以在本系列的下一个卷中查看。

方法链

对于方法链接,如果我们的现有条件都不匹配,我们将需要另一个无限环路。

value_ptr 只是一个元素的数组,它试图模仿python或其他脚本语言的指针,而这些语言确实没有相等的。

它将帮助我们实现以下各个方面:

a = 1
def modify_a(a):
  a = 2
modify_a(a)
> a # still 1 but we need it to be 2
      Snippet 8

,但至少它模仿了这方面的指针:

a = [ 1 ]
def modify_a(value_ptr):
  value_ptr[0] = 2
modify(a)
> a[0] # our main value is now 2
      Snippet 9
def chain_obj(char_stream: CharStream, value_ptr: list, scope: dict):
  while True:
    if callable(value_ptr[0]) and char_stream.peek() == '(':
      args = [] # a place to store the evaluated arguments

      # evaluating "func()"
      cs = CharStream(char_stream.source, char_stream.c)
      char_stream.advance()
      skip_space(char_stream) # evaluate "func(  )"
      if char_stream.peek() == ')':
        char_stream.advance() # eat ')'
    skip_space(char_stream)
    value_ptr[0] = value_ptr[0]() # evaluate the function with no arguments passed
    continue
      else:
        char_stream.set_cs(cs) # reset the char stream to last matched '('
      while True:
        args.append(parse_obj(char_stream, True, scope, utils.Map({'temFlag': True, 'isKey': False,}) )
    if char_stream.peek() == ',':
      continue
    elif char_stream.peek() == ')':
      char_stream.advance() # eat ')'
      skip_space(char_stream)
      value_ptr[0] = value_ptr[0](*args) # evaluate the function with x number of arguments passed
      break
    else:
      raise SyntaxError("Unexpected char while evaluating a function: " + char_stream.current)

    elif type(value_ptr[0]) == dict and char_stream.peek() == '.':
      identifier = scan_id(char_stream, True)
      skip_space(char_stream)
      value_ptr[0] = value_ptr[0][identifier]
      continue

    else:
      break
      Snippet 10

此代码实现 obj.a.b obj.a()。b func(1,2),“ func()()() - 调用功能”,反之亦然,具体取决于您想做的事情。
由于我们的语言不支持函数定义,因此我们需要传递Python函数。毕竟,这将派上用场,因为您可以添加任何python代码并从语言代码本身中使用它。
正式地,我们提供一些“上下文”

例如:

def json_export():
  scope =  {'func': lambda x,y: x+y,} # our language can call functions
  default_flags = utils.Map({})
  utils.export_json( interpret_obj(CharStream('{' + input() + '}'), False, scope, default_flags) )
  # Note that 'utils.export_json' is a custom alternative to 'json.dump' from Python Standard Library
  # more details on that here: https://docs.python.org/3/library/json.html
      Snippet 11

在打印我们的最终对象时,有一个有趣的细节要指出。也就是说,Python实际上使用 sys.stdout.write(obj。到控制台。

在此片段中,我们使用了 utils.export_json 仅使用 print 使用单引号来编码Python字符串。 “ a” 将是'a' - 不是标准 json

生成重复使用的JSON数据:

Generating JSON

要进一步自定义我们的格式,您可以编码自己的 object_to_string 函数:

def object_to_string(obj: dict):
  # handle obj
  return str(...)

# Afterwards, you can add it up like this:
print(object_to_string(interpret_obj(CharStream('{' + input() + '}'), False, scope, default_flags)))
      Snippet 12

要更好地了解如何使用一组简单的规则格式化对象,请查看源代码的 utils.export_json 的实现。

为了启用方法链接,我们将将代码的一部分从 simpet 5 转换为:

...
  if char_stream.peek() == ':':
    value = interpret_obj(char_stream, True, scope, utils.Map({ 'isKey': False, 'temFlag': True, }) )
    value_ptr = [ value ]
    chain_main(char_stream, value_ptr, scope)
    value = value_ptr[0]
    utils.deep_update(obj, { key: value }) 
...
      Snippet 13

,否则我们可以将其包装在单个功能中以进行可重复使用。

def interpret_obj_and_chain(char_stream: CharStream, advance: bool, scope: dict, flags: utils.Map):
  value = interpret_obj(char_stream, advance, scope, flags)
  value_ptr = [ value ]
  chain_obj(char_stream, value_ptr, scope)
  return value_ptr[0] # return the final value
      Snippet 14

现在,摘要5 的一部分转化为

...
if char_stream.peek() == ':':
  value = interpret_obj_and_chain(char_stream, True, scope, utils.Map({'temFlag': True, 'isKey': False,}) )
  utils.deep_update(obj, { key: value })
...
      Snippet 15

解释空对象

我们尚未设定一种特殊情况。也就是说,解释 {}

让我们将一块摘要5 变成

def interpret_obj(char_stream: CharStream, advance: bool, scope: dict, flags: utils.Map):
  ...
  elif char_stream.peek() == '{':
    obj = {}
    # interpreting "{}"
    cs = CharStream(char_stream.source, char_stream.c)
    char_stream.advance()
    skip_space(char_stream) # with this, we can interpret "{  }"
    if char_stream.peek() == '}':
      char_stream.advance() # eat '}'
      skip_space(char_stream)
      return obj
    else:
      char_stream.set_cs(cs) # trace the char_stream back to last matched '{' and proceed
  ...
      Snippet 16

范围

范围最重要的是,您可以使用 sippet 11 中详细介绍的预定义上下文。

要确保我们不将上下文变为上下文,我们将将其副本纳入 obj_scope ,从那时起,将其用作词典来获取项目。<<<<<<<<<< /p>

让我们的摘要5 进一步。

def interpret_obj(char_stream: CharStream, advance: bool, scope: dict, flags: utils.Map):
  ...
  elif char_stream.peek() == '{':
    obj = {}
    obj_scope = {}
    ...
    utils.deep_update(obj_scope, scope)
    ...
      if char_stream.peek() == ':':
        value = interpret_obj_and_chain(char_stream, True, obj_scope, utils.Map({ 'temFlag': True, 'isKey': False, }) )
        utils.deep_update(obj_scope, { key: value })
        utils.deep_update(obj, { key: value })
      ...
    ...
  ...
      Snippet 17

表达

首先,将其视为桌面计算器!我们首先必须处理基本的算术操作:乘法,除法,加法和减法。

考虑:(3 + 3) *(3 * 3)

为了实现这一目标,我们需要优先考虑乘法和除法而不是加法和减法。 expr 围绕术语 术语 围绕 prim

在计算机科学中,该术语是操作员预言解析器或仅优先。

def expr(char_stream: CharStream, advance: bool, scope: dict, flags: utils.Map):
  left = term(char_stream, advance, scope, flags)
  while True:
    if char_stream.peek() == '+':
      left += term(char_stream, True, scope, flags)
    elif char_stream.peek() == '-':
      left -= term(char_stream, True, scope, flags)
    else:
      return left

def term(char_stream: CharStream, advance: bool, scope: dict, flags: utils.Map):
  left = prim(char_stream, advance, scope, flags)
  while True:
    if char_stream.peek() == '*':
      left *= prim(char_stream, True, scope, flags)
    elif char_stream.peek() == '/':
      left /= prim(char_stream, True, scope, flags)
    else:
      return left

def prim(char_stream: CharStream, advance: bool, scope: dict, flags: utils.Map):
  if advance:
    char_stream.advance()
  skip_space(char_stream)
  if char_stream.peek() == '(': # enable ((2 * 2) + 1)  
    value = expr(char_stream, True, scope, flags)
    if char_stream.peek() != ')':
      raise SyntaxError("Missing ')'")
    char_stream.advance() # eat ')'
    skip_space(char_stream)
    return value 
  return interpret_obj_and_chain(char_stream, False, scope, flags) # use the complete variant of interpret_obj with method chaining

      Snippet 18

可以使用AST或解析树来说明我们的功能。

视觉上,我们有:

Abstract Syntax Tree/Parse Tree

用这个新功能替换 replact drivent_obj_and_chain
返回摘要5

def interpret_obj(char_stream: CharStream, advance: bool, scope: dict, flags: utils.Map):
  ...
  elif char_stream.peek() == '{':
    ...
      if char_stream.peek() == ':':
        value = expr(char_stream, True, obj_scope, utils.Map({ 'temFlag': True, 'isKey': False, }) )
        ...
    ...
  ...
      Snippet 19

此外,也不要忘记呼叫 expr 也来自 chain_obj ,尤其是在获得函数参数时,尤其不是 drivent_obj

例如,解释 {f:func(1+1,2*2)} 将需要:

args.append( expr(char_stream, True, scope, utils.Map({'temFlag': True, 'isKey': False,}) )

结束方法链接

现在,如果我们写 {c:{b:1,d:{a:21}},d1:(c.d.a)*2+1} - 正确的结果。但是,如果我们试图写((C.D).A)而不是(C.D.A)该怎么办。好吧,很容易实施!如果您将步骤追溯到 prim - 您会找到与括号匹配并撞到头上的零件!这就是我们需要处理的代码块!

def prim(char_stream: CharStream, advance: bool, scope: dict, flags: utils.Map):
  ...
  if char_stream.peek() == '(': # enable ((2 * 2) + 1)  
    value = expr(char_stream, True, scope, flags)
    value_ptr = [ value ]
    if char_stream.peek() != ')':
      raise SyntaxError("Missing ')'")
    char_stream.advance() # eat ')'
    skip_space(char_stream)
    chain_obj(char_stream, value_ptr, scope) # just enable method-chaining
    value = value_ptr[0] # the final value
    return value
  ...
      Snippet 20

接下来,继续尝试(c.d).a

由于我们的递归逻辑,如果有额外的字符,我们也必须忘记检查是否会产生错误 - 例如: {}},(),())和类似。

在这种情况下,我们有:

def interpret_object(stream: CharStream, scope: dict): 
    default_flags = utils.Map({})
    obj = interpret_obj(stream, False, scope, default_flags)
    if not stream.is_over():
        raise SyntaxError('unmatched ' + stream.current)
    return obj

def main():
    text = CharStream(r'''{}''')
    # text = Char_stream(r'''{}}''') # we now get "SyntaxError('unmatched }')"
    scope = { 'func': lambda x,y: x+y, 'func1': lambda: print('hi!'), }

    obj = interpret_object(text, scope)
    utils.export_json(obj)
      Snippet 21




结论

了解编程语言的工作方式通过向您介绍自然语言处理,模式匹配,评估,编译器,口译员等,从而为计算机科学界开辟了许多机会。

它可以帮助您描绘您在尝试仅运行几行代码的Enter键之前如何处理所编写的每个表达式 - 它可以激发您将您在显微镜下使用的编程语言放置第一次。

有足够的构造空间来改进我们的代码。方法之一是倾向于OOP,这正是下一个卷大约一个步骤!

我们祝您使用语言的原型好运,并期待与您分享更高级的指导。

在评论中让我们知道任何错别字和您的收获。

参考