2
$\begingroup$

I have started to learn automata theory and languages. I am new to regular expressions.

As a use case in real world, I would like to construct a regular expression to accept a c-style string: enclosed by double quotes, allows escape sequences (\" to escape a double quote, \ escape a backslash, \n escape a new line...) and allows all characters in between, and pretty much everything that the standard identifies as a string literal.

I don't have a specific language that the regex is to be used in, for I'm not going to use this in a program. I just want to know the theory behind constructing the regex, one step at a time. For example, Initially, how to account for the enclosing quotes ? then how to allow arbitrary sequences of characters between the quotes ? and then how to account for escaping ?

I don't have a regex tester. I just need the construction idea.

Strings that are to be accepted are, for example,

"hello world!"
"hi!\n"
"000022lkjads\t{"
"\0Hello World"

The following would be rejected

"hello 

for there is no enclosing double quotes

"Hello World"" 

for it does not escape the quote

$\endgroup$
  • $\begingroup$ Construct a DFA/NFA instead. Regular expressions are not the perfect representation for every purpose. $\endgroup$ – Yuval Filmus Sep 9 '18 at 2:01
2
$\begingroup$

Here is a regular expression for the set of all strings of the following form:

  • They start and end with ".
  • Every " in the middle must be escaped using a backslash.
  • Every backslash must be followed by a letter from $A$.
  • All other letters are from $B$; in particular, " is not in $B$.

For simplicity, I identify $A$ and $B$ with the regular expressions $\sum_{\sigma \in A} \sigma$ and $\sum_{\tau \in B} \tau$.

Here is the regular expression: $$ \text"(B+\backslash A)^*\text" $$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.