Что это за грамматика? - PullRequest
       13

Что это за грамматика?

0 голосов
/ 12 августа 2011

Мне нужно проанализировать документ, содержащий группы пар переменная-значение, который сериализован в строку, например. как это:

4^26^VAR1^6^VALUE1^VAR2^4^VAL2^^1^14^VAR1^6^VALUE1^^

Вот различные элементы:

  1. Идентификаторы группы:

    4 26 ^ ^ VAR1 ^ 6 ^ VALUE1 ^ VAR2 ^ 4 ^ VAL2 ^^ 1 * 1 013 * ^ 14 ^ VAR1 ^ 6 ^ VALUE1 ^^

  2. Длина строкового представления каждой группы:

    * +1019 * 4 ^ 26 * * * тысяча двадцать-одна VAR1 ^ 6 ^ VALUE1 ^ VAR2 ^ 4 ^ VAL2 ^^ 1 ^ 14 ^ VAR1 ^ 6 ^ VALUE1 ^^
  3. Одна из групп:

    4 ^ 26 ^ VAR1 ^ 6 ^ VALUE1 ^ VAR2 ^ 4 ^ VAL2 ^^ 1 ^ 14 ^ VAR1 ^ 6 ^ VALUE1 ^^

  4. Переменные:

    4 ^ 26 ^ VAR1 ^ 6 ^ VALUE1 ^ VAR2 * * ^ тысячу сорок-один 4 ^ VAL2 ^^ 1 ^ 14 ^ VAR1 * * * тысяча сорок три 6 ^ VALUE1 ^^

  5. Длина строкового представления значений:

    4 ^ 26 ^ VAR1 ^ 6 * * * тысяча пятьдесят-одна VALUE1 ^ VAR2 ^ 4 ^ VAL2 ^^ 1 ^ 14 ^ VAR1 ^ * 1 054 * 6 * * * тысячу пятьдесят-пять VALUE1 ^^

  6. Сами значения:

    * * 4 тысяча шестьдесят один ^ 26 ^ VAR1 ^ 6 ^ * * VALUE1 тысячу шестьдесят-два ^ VAR2 ^ 4 ^ VAL2 * +1065 * ^^ 1 ^ 14 ^ VAR1 ^ 6 ^ * * VALUE1 тысяча шестьдесят шесть * +1067 * ^^

Переменные состоят только из буквенно-цифровых символов. В отношении значений не делается никаких предположений, т. Е. Они могут содержать любой символ, включая ^.

Есть ли название для этого вида грамматики? Есть ли библиотека разбора, которая может справиться с этим беспорядком?

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

Ответы [ 2 ]

1 голос
/ 12 августа 2011

Самый простой способ приблизиться к этому - заметить, что есть два вложенных уровня, которые работают одинаково. Шаблон очень прост:

id^length^content^

На внешнем уровне это создает набор групп. Внутри каждой группы content следует точно так же, только здесь id - это имя переменной, а content - это значение переменной.

Так что вам нужно написать эту логику только один раз, и вы можете использовать ее для анализа обоих уровней. Просто напишите функцию, которая разбивает строку на список пар id / content. Вызовите его один раз, чтобы получить группы, а затем выполните цикл, вызывая его снова для каждого content, чтобы получить переменные в этой группе.

Разбивая его на эти шаги, сначала нам нужен способ получить «токены» из строки. Эта функция возвращает объект с тремя методами, чтобы узнать, находимся ли мы в «конце файла», и захватить следующую разделенную или подсчитанную подстроку:

var tokens = function(str) {
    var pos = 0;
    return {
        eof: function() {
            return pos == str.length;
        },
        delimited: function(d) {
            var end = str.indexOf(d, pos);
            if (end == -1) {
                throw new Error('Expected delimiter');
            }
            var result = str.substr(pos, end - pos);
            pos = end + d.length;
            return result;
        },
        counted: function(c) {
            var result = str.substr(pos, c);
            pos += c;
            return result;
        }
    };
};

Теперь мы можем удобно написать повторно используемую функцию разбора:

var parse = function(str) {
    var parts = {};
    var t = tokens(str);
    while (!t.eof()) {
        var id = t.delimited('^');
        var len = t.delimited('^');
        var content = t.counted(parseInt(len, 10));
        var end = t.counted(1);
        if (end !== '^') {
            throw new Error('Expected ^ after counted string, instead found: ' + end);
        }
        parts[id] = content;
    }
    return parts;
};

Он создает объект, в котором ключами являются идентификаторы (или имена переменных). Я предполагаю, поскольку у них есть имена, что порядок не имеет значения.

Затем мы можем использовать это на обоих уровнях для создания функции, выполняющей всю работу:

var parseGroups = function(str) {
   var groups = parse(str);
   Object.keys(groups).forEach(function(id) {
     groups[id] = parse(groups[id]);
   });
   return groups;
}

Для вашего примера, он производит этот объект:

{
  '1': { 
    VAR1: 'VALUE1' 
  },
  '4': {
    VAR1: 'VALUE1',
    VAR2: 'VAL2'
  } 
}
0 голосов
/ 12 августа 2011

Я не думаю, что это простая задача - создать грамматику для этого.Но с другой стороны, простой прямой подход не так сложен.Вы знаете соответствующую длину строки для каждой критической строки.Таким образом, вы просто нарезаете свою строку по разным длинам ..

где вы видите проблемы?

...