От нуля для реализации пользовательских парсеров JSON

JSON
От нуля для реализации пользовательских парсеров JSON

Введение

Zergling – это платформа для управления сайтами, разработанная нашей командой. Формат данных по умолчанию выглядит следующим образом:

{
    "page": "dsong|ufm", 
    "resource": "song", // 歌曲
    "resourceid": 1, // 资源 id
    "target": 111, // 不感兴趣
    "targetid": "button", 
    "reason": "", 
    "reason_type": "fixed" 
}

Пользовательский формат json, разница в следующем:

  1. Аннотированный
  2. струна через|разделитель, используемый как массив
  3. value является примитивным типом, а не объектом.

В самом процессе есть некоторые несоответствия:

  1. Использовать значение как комментарий, а не комментарий

должно быть

id: 1111, // 活动 url
  1. использовать/вместо этого сделайте разделитель массива|.

В дополнение к вышеуказанным типам ошибок существуют и другие типы ошибок. Поэтому я решил написать собственный анализатор json, чтобы стандартизировать проблему ввода. Он разделен на две части: лексический анализ и синтаксический анализ.

лексический анализ

Лексический анализ в основном делит исходный код на множество небольших подстрок в серии токенов.

Например, следующий оператор присваивания.

var language = "lox";

После лексического анализа выходные 5 токенов выглядят следующим образом.

Таким образом, ключ к лексическому анализу заключается в том, как разделить строку.

Сначала мы определяем структуру данных токена (Token.js)

class Token {
    constructor (type,value){
        this.type = type;
        this.value = value;
    }
}

Переопределение типов токенов (TokenType.js), ссылкаtoken type

const TokenType = {
    OpenBrace: "{", // 左括号
    CloseBrace: "}", // 右括号
    StringLiteral: "StringLiteral", // 字符串类型
    BitOr: "|",
    SingleSlash: "/",
    COLON: ":",
    QUOTE: '"',
    NUMBER: "NUMBER",
    COMMA: ",",
    NIL: "NIL", // 结束的字符
    EOF: "EOF", //end token
};

Проделав вышеуказанные приготовления, можно приступать к обработке символов.

Сначала определите класс Lexer (Lexer.js)

class Lexer {
  constructor (input) {
    this.input = input;// 输入
    this.pos = 0;// 指针
    this.currentChar = this.input [this.pos];
    this.tokens = []; // 返回的所有 token
  }
}

Лексическая обработка заключается в чтении строк одна за другой, а затем их сборке в токен. Начнем с простых символов, таких как{,=В начале, если мы встречаем символ, мы напрямую возвращаем соответствующий токен. Пробелы игнорируем.

// 获取所有的 token;
  lex () {
    while (this.currentChar && this.currentChar != TokenType.NIL) {// 如果当前不是结束的字符
      this.skipWhiteSpace ();
      let token = "";
      switch (this.currentChar) {
        case "{":
          this.consume ();
          token = new Token (TokenType.OpenBrace, TokenType.OpenBrace);
          break;
        case "}":
          this.consume ();
          token = new Token (TokenType.CloseBrace, TokenType.CloseBrace);
          break;
        case ":":
          this.consume ();
          token = new Token (TokenType.COLON, TokenType.COLON);
          break;
        case ",":
          this.consume ();
          token = new Token (TokenType.COMMA, TokenType.COMMA);
          break;
      }
      if (token) this.tokens.push (token);
    }

    this.tokens.push (new Token (TokenType.EOF, TokenType.EOF));
  }

this.skipWhiteSpaceВ основном для работы с пробелами, если текущий символ является пробелом, мы перемещаем указательpos++, чтобы судить о следующем символе, пока он не станет пустым символом.this.consumeЭта функция используется для перемещения указателя.

skipWhiteSpace () {
    while (!this.isEnd () && this.isSpace (this.currentChar)) {
      this.consume ();
    }
}

isSpace (char) {
  const re = /\s/gi;
  return re.test (char);
}

  /** 获取下一个字符 */
consume () {
  if (!this.isEnd ()) {
    this.pos++;
    this.currentChar = this.input [this.pos];
  } else {
    this.currentChar = TokenType.NIL;
  }
}

// 判断是否读完
isEnd () {
  return this.pos > this.input.length - 1;
}

Обработанные символы для возврата токена напрямую, для строки немного хлопотно. Например"page"Для этого нам нужно прочитать 4 символа вместе. Поэтому, когда мы сталкиваемся"При двойных кавычках мы вводим функцию getStringToken для обработки.

(Lexer.js->lex)

 case '"':
      token = this.getStringToken ();
      break;

дляgetStringToken. Мы здесь особенные, общей строки нет|этот разделитель, например"page". В нашем примере, как"dsong|ufm", вернусьdsong, |, ufm, три токена.

  getStringToken (){
      let buffer = "";
      while (this.isLetter (this.currentChar) || this.currentChar == TokenType.BitOr)
      {
        if (this.currentChar == TokenType.BitOr) {
          if (buffer)
              this.tokens.push (new Token (TokenType.StringLiteral, buffer));
          this.tokens.push (new Token (TokenType.BitOr, TokenType.BitOr));
          buffer = "";
        } 
      }
  }

Аналогично для комментария, когда мы нажимаем символ, который/, будем считать, что он комментарий//xxx. Он автоматически игнорируется для комментариев.

(Lexer.js->lex)

case "/":
        token = this.getCommentToken ();
        break;

  getCommentToken () {
    // 简单处理两个 /
    this.match (TokenType.SingleSlash);
    this.match (TokenType.SingleSlash);

    while (!this.isNewLine (this.currentChar) && !this.isEnd ()) {
      this.consume ();
    }
    return;
  }

  isNewLine (char) {
    const re = /\r?\n/;
    return re.test (char);
  }

Далее обрабатывается число, похожее на строку, например 111, три символа, мы трактуем его как число. Итак, мы оговариваем, что когда символ является числом, мы входим в обработкуgetNumberTokenдля обработки чисел.

(Lexer.js->лекс)

 default:
        if (this.isNumber (this.currentChar)) {
          token = this.getNumberToken ();
        } else {
          throw new Error (`${this.currentChar} is not a valid type`);
        }

Следующий процессgetNumberTokenфункция

getNumberToken () {
    let buffer = "";
    while (this.isNumber (this.currentChar)&&!this.isEnd ()) {
      buffer += this.currentChar;
      this.consume ();
    }
    if (buffer) {
      return new Token (TokenType.NUMBER, buffer);
    }
}

isNumber (char) {
    const re = /\d/g;
    return re.test (char);
}

На данный момент все мы получили все токены.

Разбор

Лексический анализ может решить проблему использования значения в качестве аннотации, такой как{id:"活动 id"}Этот способ письма, но не может справиться{id:"page || dsong"}Такого рода.因为按照我们的逻词法处理"page || dsong"вернусьpage,|,|,dsong4 жетона строк. Синтаксический анализ — это в основном проверка логики.

мы находим сначалаопределение синтаксиса json.

grammar JSON;

json
    : value
    ;


value
    : STRING
    | NUMBER
    | obj
    | 'true'
    | 'false'
    ;

obj 
    : "{" pair (,pair)* "}"
    ;

pair
    String: value

STRING
   : '"' (ESC | SAFECODEPOINT)* '"'
   ;

NUMBER
   : '-'? INT ('.' [0-9] +)? EXP?
   ;

Так как нам нужна поддержкаa|b|cПоэтому измените обработку String

value
    : STRING

изменить на

value
    : STRING (|STRING)*

Получив приведенное выше определение синтаксиса, пришло время подумать, как превратить его в код. Строка json грамматики — это просто определение, и ее можно игнорировать.

json
    : value
    ;


value
    : STRING
    | NUMBER
    | obj
    | 'true'
    | 'false'
    ;
NUMBER
   : '-'? INT ('.' [0-9] +)? EXP?
   ;

Здесь json может вывести значение, а значение может вывести число и «истину». Число может вывести другие, а «истина» — это базовый тип данных, который нельзя вывести.

Для вышеизложенного можно вывести другие, такие как json, значение, число, мы называем это нетерминалом, нетерминалом.

'true' Это называется терминатором.

Правую часть чисел и строк мы также рассматриваем как терминал, поскольку это лишь ограниченный диапазон символов.

Потому что, чтобы преобразовать приведенное выше определение грамматики в конкретный код, правила следующие:

  1. еслиnonterminal, то соответствующее преобразование в функцию
  2. terminal. сопоставьте текущий тип токена с типом терминала, затем переместите указатель к следующему
  3. если|. соответствуетifилиswitch
  4. если*или+.whileилиforцикл
  5. Если это вопросительный знак？. превращается вif

так что слеваvalue,Number,jsonи т. д. являются функциями, а правые, такие как{,trueОба сначала соответствуют текущему типу токена, а затем получают следующий токен.

Преобразуем синтаксис json в следующий.

Сначала определите Parser (Parser.js), вход — лексер.


class Parser {
  constructor (lexer) {
    this.lexer = lexer;
    this.currentToken = lexer.getNextToken ();
  }

}

Затем разберите первое правило, котороеjson:valueпреобразуются в функции.

(Paser.js)


  /**
    json: value
  */
  paseJSON () {
    this.parseValue ();
  }

Далее анализируется синтаксис значения, поскольку|является оператором выбора, и мы превращаем его в переключатель. Переходите к разным веткам в зависимости от того, является ли текущий тип токена объектом или числом, строкой.

(Parser.js->parseValue)

   /**
     * value
    : STRING (|STRING)*
    | NUMBER
    | obj
    | 'true'
    | 'false'
    ; */
  parseValue () {
    switch (this.currentToken.type) {
      case TokenType.OpenBrace:
        this.parseObject ();
        break;
      case TokenType.StringLiteral:
        this.parseString ();
        break;
      case TokenType.NUMBER:
        this.parseNumber ();
        break;
     case TokenType.TRUE:
        break;
     case TokenType.FLASE:
        break;
    }
  }

Согласно правилу 2, терминал, сопоставьте текущий тип токена, затем получите следующий токен. Поэтому, когда дело доходит доtrueа такжеvalue, оператор switch изменяется на следующий.

 case TokenType.TRUE:
      this.eat (TokenType.TRUE);
      break;
  case TokenType.FLASE:
      this.eat (TokenType.FALSE);
      break;

мы определяемeatФункция, сопоставьте текущий токен, а затем получите следующий, если он не соответствует, выдайте сообщение об ошибке напрямую.

/**match the current token and get the next */
  eat (tokenType) {
    if (this.currentToken.type == tokenType) {
      this.currentToken = this.lexer.getNextToken ();
    } else {
      throw new Error (
        `this.currentToken is ${JSON.stringify (
          this.currentToken
        )} doesn't match the input ${tokenType}`
      );
    }
  }

Следующий процессparseObject, его синтаксис"{" pair (,pair)* "}.

{терминал, непосредственноeat. pairпеременные, непосредственно в функции.

(,pair)*. Согласно правилу 4,*Перевести вwhileутверждение.

*Это обычный символ, который представляет ноль или более случаев, поэтому, когда это происходит, мы сначала оцениваем, соответствует ли запятая, а затем выполняемparsePairфункция.

код показывает, как показано ниже

    /**obj 
    : "{" pair (,pair)* "}"
    ; */
  parseObject () {
    this.eat (TokenType.OpenBrace);
    this.parsePair ()
    while (this.currentToken.type == TokenType.COMMA) {
      this.eat (TokenType.COMMA);
      this.parsePair ()
    }
    this.eat (TokenType.CloseBrace);
  }

После решения приведенного выше преобразования синтаксиса следующий код может быть преобразован в соответствии с приведенной выше обработкой.


  /** String: value */
  parsePair () {
  
    this.eat (TokenType.StringLiteral);
    this.eat (TokenType.COLON);
    this.parseValue ();
  }

    //STRING (|STRING)*
  parseString () {
    this.eat (TokenType.StringLiteral);
    while (this.currentToken.type == TokenType.BitOr) {
      this.eat (TokenType.BitOr);
      this.eat (TokenType.StringLiteral);
    }
  }

  parseNumber () {
    this.eat (TokenType.NUMBER);
  }

На этом наша работа завершена.

По двум вопросам, поднятым в начале.

первый, кто использовалvalueв качестве комментария вместоcomment. Это решается на этапе лексического разбора. Используйте регулярное выражение /w/ для оценки строки. И эта регулярка выдаст сообщение об ошибке, когда встретит китайский язык.

Второе использование/вместо этого сделайте разделитель массива|. Это решается на этапе разбора. при разбореvalue: STRING (|STRING)*При использовании этого правила, если за найденной строкой не следует разделитель |, будет сообщено об ошибке.

Вышеупомянутые два теста были рассмотрены, пожалуйста, проверьте полный код и тестовый пример.github

Эта статья была опубликована сКоманда внешнего интерфейса NetEase Cloud Music, Любое несанкционированное воспроизведение статьи запрещено. Мы набираем, если вы пытаетесь сменить работу, как и облачная музыка, тоПрисоединяйтесь к нам!

Категории