# How to design a LL(1) grammar for basic regular expression?

I try to design a LL(1) grammar to parse the basic regular expression. Here's the origin grammar.（\| is the escape character, since | is a special character in grammar's pattern).

E -> E \| T | T
T -> TF | F
F -> P* | P
P -> (E) | i


To remove the left recursive, import new Variable

E -> TE'
E' -> \| TE' | ε
T -> FT'
T' -> FT' | ε
F -> P* | P
P -> (E) | i


now, for pattern F -> P* | P， import P'

P' -> * | ε
F -> PP'


However, the pattern T' -> FT' | ε has problem. Consider case (a|b):

E => TE'
=> FT' E'
=> PT' E'
=> (E)T' E'
=> (TE')T'E'
=> (FT'E')T'E'
=> (PT'E')T'E'
=> (iT'E')T'E'
=> (iFT'E')T'E'


Here, our human know that we should substitute the Variable T' with T' -> ε, but program will just call T' -> FT', which is wrong.

So, what's wrong with this grammar? And how should i rewrite it to make it suitable for the recursive descendent method.

## More

Now i've learn that there is a kind of grammar called "operator precedence grammar", its evaluation is similar to arithmetic expression's. It require that the pattern of the grammar cannot have the form of S -> ...AB...(A and B are non-terminal). Does it means that i just cannot directly use this method to parse the regular expression? https://stackoverflow.com/questions/53211961/how-to-deal-with-the-implicit-cat-operator-while-building-a-syntax-tree-for-re

• I responded to this question on SO. – rici Nov 12 '18 at 16:19