Парсер для регулярных выражений

Недавно я изучал основы и на практике решил реализовать DFA в контексте C ++. Так что в основном это регулярные выражения. Это хорошо работает, когда я строю дерево с нуля, однако я не знаю, как обращаться с регулярными выражениями.

Я имею в виду, что если у меня есть регулярное выражение, например (test)*, я должен преобразовать его в DFA. Проблема в том, что для этого мне нужно проанализировать регулярное выражение. Это кажется замкнутым кругом (это еще хуже, потому что мне действительно нужен синтаксический анализатор с учетом скобок, регулярные выражения здесь не работают).

Итак, как с этим бороться? Я полностью понимаю, что сейчас у нас есть инструменты для этого (например, Flex & Bison), но эти инструменты основаны на регулярных выражениях (ну, по крайней мере, есть токенизаторы). Так что же произошло вначале? Как написать парсер регулярных выражений с нуля? Любая ссылка на книгу / статью приветствуется.


c++ parsing regex dfa
person freakish    schedule 18.03.2014    source источник
comment
До появления генераторов парсеров люди программировали его вручную. Точно так же, как они писали ассемблерный код до того, как появились компиляторы языков высокого уровня.   -  person Barmar    schedule 18.03.2014
comment
@Barmar Я понимаю это. Однако я не уверен, как написать парсер без регулярных выражений? Возможно, я просто слишком усложняю, я просто пытаюсь чему-то научиться.   -  person freakish    schedule 18.03.2014
comment
Вы можете попробовать написать синтаксический анализатор в духе ускорения - я сомневаюсь, что вам понадобится использовать регулярные выражения ....   -  person Tony Delroy    schedule 18.03.2014
comment
Вы пишете много if или switch утверждений.   -  person Barmar    schedule 18.03.2014
comment
Если вам никогда не приходилось писать синтаксический анализатор языка без использования механизма регулярных выражений для обработки ваших DFA, считайте, что вам повезло (и я очень разочарован качеством любого языка алгоритмов и курса проектирования компилятора, который вы прошли). Вы действительно не жили, пока не запрограммировали токенизатор, чтобы он соответствовал уже созданной вами DFA вручную. Это свой особенный мир.   -  person WhozCraig    schedule 18.03.2014
comment
@WhozCraig Я никогда не говорил, что пишу синтаксический анализатор языка. Также я не проходил никаких курсов программирования (я чисто самоучка). Я постараюсь написать его с большим количеством операторов if и switch, как это предлагает Бармар. :)   -  person freakish    schedule 18.03.2014
comment
@TonyD Cue мой простой Парсер регулярных выражений, написанный с помощью Boost Spirit? :)   -  person sehe    schedule 18.03.2014
comment
@sehe вы животное, сэр. (а если кто в это не верит, посмотрите его аватар =)   -  person WhozCraig    schedule 18.03.2014
comment
@WhozCraig, вы когда-нибудь слышали о парсинге без лексического анализа? Токенизаторы - это прошлый век.   -  person SK-logic    schedule 18.03.2014
comment
Я бы рекомендовал взглянуть на en.wikipedia.org/wiki/Parsing_expression_grammar и en.wikipedia.org/wiki/Parser_combinators - за пределами узкой книги драконов есть огромный мир способ мышления.   -  person SK-logic    schedule 18.03.2014

Ответы (1)


arrow_upward
3
arrow_downward

Однажды я написал свою собственную версию 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=\|
person Spook    schedule 18.03.2014
comment
Я нет, думаю, мне сначала придется перевернуть польскую нотацию: D - person MSalters; 18.03.2014