Однозначная грамматика для регулярных выражений - PullRequest
Новая
       5

Однозначная грамматика для регулярных выражений

0 голосов
/ 18 июля 2011

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

-= Regex Grammar (EBNF) =-
    <start> -> <expr> '\n'

    <expr>  -> <expr> { '|' <term> }         // Union
             | <expr> { <expr> }             // Concatenation
             | <expr> '*'                    // Closure
             | <term>

    <term>  -> '(' <expr> ')' | <char>       // Grouping
             | <char>

    <char>  -> a|b|c| ... |z

Несколько рекомендаций:
1. Приоритетность: В указанном порядке(сверху вниз) Закрытие, Конкатенация, Объединение
2. Ассоциативность: Закрытие является правоассоциативным;Конкатенация / объединение являются левоассоциативными
3. Должны ли поддерживать группировку с парэнсами

Мой вопрос: соответствует ли приведенная выше грамматика?Я уверен, но я не на 100% и надеялся, что несколько опытных глаз могут указать на некоторые проблемы / ошибки.

TIA Noob

1 Ответ

1 голос
/ 18 июля 2011 
<start>
<expr>
<expr><expr>
<expr><expr><expr>
<term><term><term>
'abc'

Это неоднозначно, потому что на третьем шаге вы можете расширить либо первый <expr>, либо последний. Вы должны быть в состоянии обойти это, удалив 

<expr> -> <expr> { <expr> }

и создать 

<term> -> <term> <expr>

вместо.

Вы повторяетесь здесь 

<term>  -> '(' <expr> ')' | <char>       // Grouping
         | <char>

(у вас есть <char> два раза, вы хотели иметь это '(' <expr> ')' '|' <char> в первом правиле?) Думаю, было бы яснее удалить 

<term> -> '(' <expr> ')'

и создайте 

<expr> -> '(' <expr> ')'

вместо.

Затем вам также нужно добавить кавычки вокруг символов в <char>.

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

...