Контекстная грамматика, описывающая регулярные выражения?

Question

Я пытаюсь написать движок регулярных выражений. Я хотел бы написать парсер рекурсивного спуска вручную. Как будет выглядеть не зависящая от контекста грамматика без левой рекурсии для языка регулярных выражений (а не языков, которые можно описать с помощью регулярных выражений)? Будет ли проще повторно выделить синтаксический сахар, то есть изменить a+ на aa*? Заранее спасибо!

Answer 1

Левая рекурсия:

Expression = Expression '|' Sequence
           | Sequence
           ;

Sequence = Sequence Repetition
         | <empty>
         ;

Правильная рекурсия:

Expression = Sequence '|' Expression
           | Sequence
           ;

Sequence = Repetition Sequence
         | <empty>
         ;

Неоднозначная форма:

Expression = Expression '|' Expression
           | Sequence
           ;

Sequence = Sequence Sequence
         | Repetition
         | <empty>
         ;

Answer 2

Вы можете посмотреть исходный код для Plan 9 grep . Файл grep.y содержит грамматику yacc (LALR (1), если я правильно помню) для регулярных выражений. Вы можете начать с грамматики yacc и переписать ее для анализа рекурсивного спуска.

Answer 3

Статья в Википедии о Left Recursion дает довольно хорошую информацию о том, как это осуществить.