O'Reilly logo

Building Parsers with Java™ by Steven John Metsker

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

8.3. A Regular Expression Grammar

A modestly ambitious regular expression language allows the user to express sequences, alternations, and repetitions of characters. The following grammar is based on rules given in Introduction to Automata Theory, Languages and Computation [Hopcroft and Ullman]. The rules recognize conventional operator precedence, and they avoid the problem of left recursion.

expression    = term ('|' term)*; 
term          = factor factor*;
factor        = phrase | (phrase '*');
phrase        = letterOrDigit | '(' expression ')';
letterOrDigit = Letter | Digit;

Note that there is a major difference between the meaning of a vertical bar by itself and a vertical bar in single quotes. There is also a major difference between an asterisk and an asterisk ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required