Реализация парсера для escape-последовательностей - PullRequest
Новая
       16

Реализация парсера для escape-последовательностей

4 голосов
/ 19 декабря 2008

Я хочу проанализировать пользовательский формат строки, сохраняющий состояние графов объектов. Это сценарий ASP.NET, и я хотел что-то простое в использовании на клиенте (JavaScript) и сервере (C #).

У меня есть формат что-то вроде 

{Name1|Value1|Value2|...|ValueN}{Name2|Value1|...}{...}{NameN|...}

В этом формате у меня есть 3 разделителя, {, } и |. Кроме того, поскольку эти символы возможны в имени / значениях, я определил escape-последовательность с использованием очень распространенного \, так что \{, \} и \| все интерпретируются как обычные версии самих себя и, конечно, \\ - это обратный слеш. Все довольно стандартно.

Первоначально я пытался использовать регулярное выражение, чтобы попытаться разобрать строковое представление объекта с чем-то вроде этого (?<!\\)\{(.*?)(?<!\\)\}. Помните, что \, { и } все зарезервированы в регулярных выражениях. Это, конечно, сможет правильно разобрать что-то вроде {category|foo\}|bar\{}. Однако я понял, что он потерпит неудачу с чем-то вроде {category|foo|bar\\}.

Мне потребовалась всего минута или около того, чтобы попробовать это (?<!(?<!\\)\\)\{(.*?)(?<!(?<!\\)\\)\} и понять, что такой подход невозможен, учитывая, что вам понадобится бесконечное количество отрицательных взглядов, чтобы справиться с потенциальным бесконечным числом escape-последовательностей. Конечно, маловероятно, что у меня когда-либо будет больше одного или двух уровней, поэтому я, вероятно, смогу жестко закодировать его. Тем не менее, я чувствую, что это достаточно распространенная проблема, которая должна иметь четко определенное решение.

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

Так что мой вопрос заключается в том, каков самый простой, эффективный и элегантный способ декодирования входного буфера, подобного этому, с возможными escape-последовательностями?

Ответы [ 2 ]

6 голосов
/ 19 декабря 2008 
(?<!\\)(?:\\\\)*\{(.*?(?<!\\)(?:\\\\)*)\}

(?<!\\) предотвратит любые \ до этой точки.

(?:\\\\)* разрешит любое количество сбежавших \.

\{ соответствует открывающей скобке.

( начинает группу захвата.

.*? соответствует содержанию, включая любые |.

(?<!\\) предотвратит любые \ до этой точки.

(?:\\\\)* разрешит любое количество сбежавших \.

) завершает захват группы.

\} соответствует закрывающей скобке.

1 голос
/ 09 марта 2009

Этот вид синтаксического анализатора довольно легко сделать с минимальным отслеживанием состояния. Ниже заняло у меня несколько минут, это довольно уродливо, и даже делает небольшую проверку ошибок. :)

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

struct RECORD
{
    public string[] Entries;
}
struct FILE
{
    public RECORD[] Records;
}

static FILE parseFile(string input)
{
    List<RECORD> records = new List<RECORD>();
    List<string> entries = new List<string>();
    bool escaped = false;
    bool inRecord = false;
    StringBuilder sb = new StringBuilder();
    foreach (char c in input)
    {
        switch (c)
        {
            case '|':
                if (escaped)
                {
                    sb.Append('|');
                    escaped = false;
                }
                else if (inRecord)
                {
                    entries.Add(sb.ToString());
                    sb = new StringBuilder();
                }
                else
                    throw new Exception("Invalid sequence");
                break;
            case '{':
                if (escaped)
                {
                    sb.Append('{');
                    escaped = false;
                }
                else if (inRecord)
                    throw new Exception("Invalid sequence");
                else
                {
                    inRecord = true;
                    sb = new StringBuilder();
                }
                break;
            case '}':
                if (escaped)
                {
                    sb.Append('}');
                    escaped = false;
                }
                else if (inRecord)
                {
                    inRecord = false;
                    entries.Add(sb.ToString());
                    sb = new StringBuilder();
                    records.Add(new RECORD(){Entries = entries.ToArray()});
                    entries.Clear();
                }
                else
                    throw new Exception("Invalid sequence");
                break;
            case '\\':
                if (escaped)
                {
                    sb.Append('\\');
                    escaped = false;
                }
                else if (!inRecord)
                    throw new Exception("Invalid sequence");
                else
                    escaped = true;
                break;
            default:
                if (escaped)
                    throw new Exception("Unrecognized escape sequence");
                else
                    sb.Append(c);
                break;
        }
    }
    if (inRecord)
        throw new Exception("Invalid sequence");
    return new FILE() { Records = records.ToArray() };
}
...