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' -> ε, 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.
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