Как реализовать эффективный токенизатор с регулярным выражением, используя имена групп
Я пытаюсь написать токенизатор для анализа тела текста (входной строки) с помощью Regex. Я хочу разделить ввод на отдельные токены и сохранить их в List <Token>, где токен - это класс (C#), например
class Token {
string value;
string type; // "identifier", "string', "intliteral', ...
}
Я хочу использовать регулярное выражение, подобное приведенному ниже, для разделения входной строки:
public static Regex tokenPattern = new Regex (
@"
( (?<identifier>(?:\p{L}|_)\w*)
| (?<string>""[^""]*"")
| (?<intliteral>(?:-|\+)?\d+[^\.])
| (?<realliteral>(?:-|\+)?\d+(?:\.\d+)?)
| (?<comma>,)
| (?<lpar>\()
| (?<rpar>\))
| ...
| (?<undefined>[^\s]*?)
)
",
RegexOptions.ExplicitCapture |
RegexOptions.IgnorePatternWhitespace |
...
);
Моя проблема в том, что легко получить часть ценить каждого токена, но, похоже, нет простого способа получить часть тип, то есть имя группы. Я ожидал, что Regex Group будет иметь свойство Имя, содержащее «идентификатор» и т. д., Но, похоже, это не так.
Есть ли способ определить имя группы без перебора всех имен / номеров групп для каждого токена? (т.е. подход со сложностью O (n) вместо O (nm), n количество токенов во входной строке, m количество типов токенов)?
Да, вот в чем проблема. GroupCollection содержит все имена групп, а не только имена групп, которым принадлежит совпадение.
Написание лексеров нам, вероятно, не является основным ожидаемым вариантом использования библиотеки регулярных выражений. Существуют такие инструменты, как Flex, для создания эффективных лексеров, и я почти уверен, что вы сможете найти порт C#. Но я использовал ту же технику, что вы описываете здесь, для написания лексеров вопросов и ответов на JavaScript, и она отлично работает, хотя стоит сократить количество шаблонов до минимума. В JS вы можете создать лексический цикл с глобальным поиском и заменой, потому что вы можете использовать функцию в качестве замены arg. Я не знаю, делает ли это C#.
... но это все еще O (nm), потому что вызываемая функция должна проверять свои аргументы на соответствие фактически совпадающему.
Спасибо за Ваш ответ. Я собираюсь взглянуть на Flex. На самом деле TypeScript / JavaScript - мой целевой язык.
это было бы полезно знать раньше. Ваш вопрос заставляет думать, что C# - ваша цель; это другой язык с другой библиотекой регулярных выражений. Однако JS не помогает; у библиотеки регулярных выражений такая же проблема, как отмечалось в моем комментарии выше.
Как вы сказали, это не имело бы большого значения, я использовал C# для выполнения некоторых тестов и знал, что обе библиотеки регулярных выражений не предоставляют имена групп для совпадений. Еще раз спасибо - Джон
разница в том, что у меня где-то валяется (старый) JS-код, и я бы откопал его, если бы знал, что он актуален. Хотя это несколько версий js отстает от времени, так что, возможно, они не были бы настолько полезны
Взгляните на jison. Это может дать вам некоторые идеи.
Ответы 1
Это будет многоэтапная операция, и наличие одного регулярного выражения для выполнения такой операции не будет хорошим использованием времени процессора. Я рекомендую разделить этапы операции, такие как:
- Разберите каждое значение с помощью базового регулярного выражения в токен.
- Выполните конкретную операцию, чтобы определить, какой тип токена встречается, и установите соответствующее значение.
Вам, скорее всего, придется продолжать разбивать шаги после 2-го шага, чтобы добиться большей эффективности.
Я должен согласиться с мнением о том, что регулярное выражение не является инструментом для обработки языка токенов после идентификации отдельных токенов или внутри процесса токена для дополнительной идентификации атрибутов токенов.
Спасибо за ваш ответ, я знаю об этом двухэтапном подходе, и мой вопрос был именно в том, как его избежать. Это то, что я имею в виду под O (n), а не с O (nm).
Согласно эта документация,
Groupдействительно имеет свойствоName. Но я не знаю, действительно ли это помогает вам, поскольку уGroupCollection, похоже, есть все группы, совпадающие или нет.