Парсер для регулярных выражений
Недавно я изучал основы, и в качестве практики я решил реализовать DFA в контексте C ++. Так что в основном это регулярные выражения. Это хорошо работает, когда я создаю дерево с нуля, но я не уверен, как обращаться с регулярными выражениями.
Я имею в виду, например, если у меня есть регулярное выражение (test)* Я должен преобразовать это в DFA. Проблема в том, что для этого мне нужно разобрать регулярное выражение. Это кажется замкнутым кругом (это еще хуже, потому что мне действительно нужен парсер с поддержкой скобок, регулярные выражения здесь не будут работать).
Так как с этим бороться? Я полностью понимаю, что у нас есть инструменты для этого (например, Flex & Зубр), но эти инструменты основаны на регулярных выражениях (ну, по крайней мере, токенизаторы). Так что же произошло в начале? Как написать парсер регулярных выражений с нуля? Любая ссылка на книгу / статью приветствуется.
Решение
Однажды я написал свою собственную версию Flex, которая генерировала набор классов вместо всей программы. Во-первых, мне пришлось анализировать регулярные выражения вручную, но когда я наконец написал его, я заменил механизм синтаксического анализа регулярного выражения на механизм, созданный самой программой.
Ручной анализ регулярного выражения на самом деле довольно прост. Во-первых, вы должны указать результат, которого хотите достичь. Например, в моем случае:
[abc]+test
Интерпретируется как:
[abc]@[abc]*@[t]@[e]@[s]@[t]
Которые на самом деле эквивалентны (@ — искусственно добавленный оператор конкатенации).
Затем вы должны создать набор правил, например.
'[' spotted:
- (optionally) expect '^' character;
- repeat:
- expect a non-special character;
- If it is not last character and is succeeded by '-', expect another character
- until `]` is spotted
- Return a character set
'(' spotted:
- Return a block-begin
')' spotted:
- Return a block-end
'*' spotted:
- Return a star-operator
'+' spotted:
- Return a plus-operator
'.' spotted:
- Return a whole character set
Any other char spotted:
- Return a character set consisting of this single character
Алгоритм, написанный таким образом, даст вам токенизатор — подпрограмму, которая разбивает элементы на логические токены. Затем вам придется обработать их в дерево выражений, и это может быть решено путем реализации Алгоритм обратной польской записи.
Вы можете проверить мой генератор парсера Вот, хотя он генерирует код Delphi. К сожалению, readme на польском языке, но внутри есть несколько примеров. Попробуйте, например:
Number=[0-9]+
Operator=[\+\-\*/]
А также
SpkParserGenerator -i myfile.regex -mc -sg
Кстати, вы можете сгенерировать парсер для себя, а затем просто перевести его с Delphi на C ++, на самом деле это довольно просто, даже если вы плохо знаете Delphi.
Это набор правил, которые я использовал для генерации парсера для генератора парсера:
SetRange=\{([0-9]*,[0-9]+)|([0-9]+,[0-9]*)|([0-9]+)\}
Star=\*
Plus=\+
QMark=\?
CharRange=\[\^?((\\.)|(\#[0-9]{3})|([^\\\#\]]))+\]
AnyChar=\.
EscapedChar=\\.
AsciiChar=\#[0-9]{3}
Char=[^\[\]\{\}\.\(\)\#\*\+\?\|\\]
OpenParenthesis=\(
CloseParenthesis=\)
Alternative=\|
Другие решения
Других решений пока нет …