Парсер Bencode с использованием стека - PullRequest
Новая
       91

Парсер Bencode с использованием стека

0 голосов
/ 05 мая 2020

Я пытаюсь использовать стековый подход для анализа закодированной строки. Эта ссылка описывает кодирование: https://www.bittorrent.org/beps/bep_0003.html

Мой псевдокод не может обработать случай, когда есть вложенные списки, например, [1, [2]] и [[1, 2]] вернут [[1 ,2]] , даже если кодировка явно отличается, "li1eli2eee" против "lli1ei2eee".

Вот мой псевдокод 

input: string
output: map/list/integer/string in a bencoded data structure
first, tokenize the string into valid tokens
Valid tokens "d, l, [words], [numbers], e, s (virtual token)"
Strings are tokenized as 4:spam becomes "s spam e" with s being a virtual token
Eg. li1el4:spamee becomes [l i 1 e i 22 e l s spam e i 2 e e e]
Parsing:
make two stacks:
stack1
stack2
for token in tokens:

    if stack is empty
        return error

    if the token isn’t an “e”
        push token onto stack1

    while the stack isn’t empty:
        elem = pop off the stack
        if elem is “i”
            elem2 = pop elem off stack2 and check if it can be converted to an int
            if not
                return error
            push elem2 onto stack2 again
        elif elem is “d”
            make a new dict
            while stack2 isn’t empty:
                key = pop off stack2
                if stack2 is empty:
                    return error (because then we have an odd key value encoding)
                value = pop off stack2
                dict[key] = value
            push dict onto stack2
        elif elem is “l”
            make a new list
            while stack2 isn’t empty:
                append pop off stack2 to l
            push l onto stack2
        elif elem is “s”
            dont need to do anything :P
        else
            push elem onto stack2

if stack2 isn’t empty:
    ret = pop the lone element off stack2
if stack2 isn’t empty:
    return error

return ret

1 Ответ

0 голосов
/ 06 мая 2020

Я не совсем следую spe c или псевдокоду, но кажется довольно простым реализовать подмножество «Bencoding» для обработки двух показанных вами строк (списков и целых чисел). Все остальное относительно тривиально (dicts в большей или меньшей степени такие же, как списки, а строки и другие нерекурсивно определенные типы данных в основном такие же, как ints), насколько я могу судить.

Мой алгоритм таков. следующим образом:

  • Создайте стек и поместите в него пустой массив.
  • Для каждого индекса в закодированной строке:
    • Если текущий символ i, проанализируйте целое число и перемотайте индекс вперед до e, которое закрывает целое число. Добавить целое число в массив наверху стека.
    • Если текущий символ l, pu sh новый arr в стек.
    • Если текущий символ e, вставьте стек и sh извлеченный массив в массив под ним (т. Е. Новый верх).
  • Верните единственный элемент в стеке.

Вот это JS: 

const tinyBencodeDecode = s => {
  const stack = [[]];

  for (let i = 0; i < s.length; i++) {
    if (s[i] === "i") {
      for (var j = ++i; s[j] !== "e"; j++);

      stack[stack.length-1].push(+s.slice(i, j));
      i = j;
    }
    else if (s[i] === "l") {
      stack.push([]);
    }
    else if (s[i] === "e") {
      stack[stack.length-2].push(stack.pop());
    }
  }

  return stack[0];
};

[
  "i1ei2e",     // => [1, 2]
  "lli1ei2eee", // => [[1, 2]]
  "li1eli2eee", // => [[1, [2]]]

  // [44, [1, [23, 561, [], 1, [78]]], 4]
  "i44eli1eli23ei561elei1eli78eeeei4e",
].forEach(e => console.log(JSON.stringify(tinyBencodeDecode(e))));

Обработка ошибок не выполняется и предполагается, что все правильно сформировано, но обработка ошибок не влияет на основной алгоритм; это просто вопрос добавления кучи условных выражений для проверки индекса, стека и строки в процессе работы.

Вот (правда, ленивый) пример того, как вы могли бы поддерживать 4 типа данных. Опять же, обработка ошибок опускается. Идея в основном та же, что и выше, за исключением того, что нужно больше суетиться, чтобы определить, создаем ли мы словарь или список. Поскольку null не кажется действительным ключом для spe c, я использую его в качестве заполнителя для объединения токенов значений с соответствующими им ключами.

В обоих случаях будут внесены незначительные изменения. необходимо сделать, если окажется, что в bencoding есть только один элемент root (список или словарь). В этом случае s = "i42ei43e" будет недопустимым на верхнем уровне, и мы начнем с пустого стека. 

const back = (a, n=1) => a[a.length-n];

const append = (stack, data) => {
  if (Array.isArray(back(stack))) {
    back(stack).push(data);
  }
  else {
    const emptyKey = Object.entries(back(stack))
                           .find(([k, v]) => v === null);

    if (emptyKey) {
      back(stack)[emptyKey[0]] = data;
    }
    else {
      back(stack)[data] = null;
    }
  }
};

const bencodeDecode = s => {
  const stack = [[]];

  for (let i = 0; i < s.length; i++) {
    if (s[i] === "i") {
      for (var j = ++i; s[j] !== "e"; j++);

      append(stack, +s.slice(i, j));
      i = j;
    }
    else if (/\d/.test(s[i])) {
      for (var j = i; s[j] !== ":"; j++);
      
      const num = +s.slice(i, j++);
      append(stack, s.slice(j, j + num));
      i = j + num - 1;
    }
    else if (s[i] === "l") {
      stack.push([]);
    }
    else if (s[i] === "d") {
      stack.push({});
    }
    else if (s[i] === "e") {
      append(stack, stack.pop());
    }
  }

  return stack[0];
};

[
  "i1ei2e",     // => [1, 2]
  "lli1ei2eee", // => [[1, 2]]
  "li1eli2eee", // => [[1, [2]]]
  "li1e4:spamli2eee", // => [[1, "spam", [2]]]

  // [[1, "spam", {"cow": "moo", "spam": {"eggs": [6, "rice"]}}, [2]]]
  "li1e4:spamd3:cow3:moo4:spamd4:eggsli6e4:riceeeeli2eee",

  // [44, [1, [23, 561, [], 1, [78]]], 4]
  "i44eli1eli23ei561elei1eli78eeeei4e",
].forEach(e => console.log(JSON.stringify(bencodeDecode(e))));
...