Search code examples
regexcompiler-constructionregular-languageautomata

Unable to fugure out the Regular Expression of the following

I've been working on Compiler Design lately and found Regular Expression quite tricky. So I am making a lexical analyzer for which I need lexical specification.

I'm unable to figure out the RE of identifiers (Rules defined below):

  • Maximum 4 characters
  • At least 1 Alphabet

What I have already tried:

(letter|digit){4} // I read that we can limit occurrence like this. But in this case, 11aa will also be accepted.

I think I can rewrite the above statement like this as well.

(letter|digit)(letter|digit)(letter|digit)(letter|digit)

Please correct me if I'm wrong and thanks in advance!

Solution

  • The tricky thing about this task is to make sure we have at least one letter. And that letter could be at any of four positions.

    (letter)(letter|digit){0,3} | (letter|digit)(letter)(letter|digit){0,2} | (letter|digit){2}(letter)(letter|digit){0,1} | (letter|digit){3}(letter)