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.


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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.