Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Грамматика языка регулярных выражений

Автор: dantistus 20.12.2007, 02:30

Доброй ночи smile

Мне нужно записать грамматику языка регулярных выражений в БНФ. В нете не нашел, с гуглом никогда не дружил :( Попробовал изобразить сам - подскажите, правильно ли получилось?

RE ::= single_match | anchor | concat | or | qunatified | (RE)
concat ::= RE single_match | RE anchor
quantified ::= single_mantch quant | (RE) quant
or ::= RE "|" RE
single_match ::= все, что "совпадает" с одним символом (a, \x2a, [abc], ., \d, \S - все это дает совпадение с одним символом)
anchor ::= якоря (^, $, \b, \B)
quant ::= квантификаторы (*, +, ?, *?, +?, ??, {n}, {n,m})

Вроде как-то так smile

Буду благодарен за помощь smile

Еще, если в инете есть эта грамматика - дайте, пожалуйста, ссылочку smile

Заранее спасибо.

Автор: PPS05 21.12.2007, 21:58

На русском:

http://ru.wikipedia.org/wiki/Форма_Бэкуса_—_Наура

На английском:

http://cui.unige.ch/db-research/Enseignement/analyseinfo/AboutBNF.html

BNF and EBNF: What are they and how do they work?
http://www.garshol.priv.no/download/text/bnf.html

Extended Backus–Naur form
http://en.wikipedia.org/wiki/Extended_Backus–Naur_form

Extended BNF — A generic base standard
http://www.cl.cam.ac.uk/~mgk25/iso-14977-paper.pdf

Автор: Mayk 21.12.2007, 22:39

Цитата(dantistus @ 20.12.2007, 06:30

)

Еще, если в инете есть эта грамматика - дайте, пожалуйста, ссылочку

http://www.opengroup.org/onlinepubs/007908799/xbd/re.html можно найти грамматику в формате yacc'а. переделать в BNF достаточно легко.

Автор: dantistus 22.12.2007, 00:26

PPS05, спасибо, но я не о том спрашивал smile

Мне нужно не определение БНФ, а запись грамматики языка регулярных выражений в БНФ.

Mayk, спасибо, буду разбираться smile

Самое смешное заключается в том, что я эту статью находил, но не дочитал до конца и закрыл smile