Skip to main content
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
Source Link

Practically speaking, what are examples of languages or grammars that regex can always parse successfully?

A short answer is: Probably nothing that you call a language.

In theoretical computer science (TCS), a language simply means a set of words. But in most cases, what people call a “language” outside TCS has some recursive structure. “Recursive structure” is ambiguous here, but intuitively regular expressions cannot parse them because regular expressions even cannot parse balanced parentheses.

Many compilers use regular expressions for lexical analysis before parsing. For example, you can decide whether a certain string is a valid identifier in C++ or not by using a regular expression. This is possible because the language consisting of valid identifiers in C++ is a regular language. But the set of valid C++ identifiers is usually not called a language outside TCS.

Disclaimers:

  1. Some people distinguish “regular expression” and “regex.”Some people distinguish “regular expression” and “regex.” In this answer, I am talking about regular expressions, not regexes, if we use this convention.

  2. Actual C++ compilers do not probably use a regular expression for valid identifiers because excluding keywords makes the regular expression unmanageable. They use a different technique to cope with this, but that is not the main point here.

Practically speaking, what are examples of languages or grammars that regex can always parse successfully?

A short answer is: Probably nothing that you call a language.

In theoretical computer science (TCS), a language simply means a set of words. But in most cases, what people call a “language” outside TCS has some recursive structure. “Recursive structure” is ambiguous here, but intuitively regular expressions cannot parse them because regular expressions even cannot parse balanced parentheses.

Many compilers use regular expressions for lexical analysis before parsing. For example, you can decide whether a certain string is a valid identifier in C++ or not by using a regular expression. This is possible because the language consisting of valid identifiers in C++ is a regular language. But the set of valid C++ identifiers is usually not called a language outside TCS.

Disclaimers:

  1. Some people distinguish “regular expression” and “regex.” In this answer, I am talking about regular expressions, not regexes, if we use this convention.

  2. Actual C++ compilers do not probably use a regular expression for valid identifiers because excluding keywords makes the regular expression unmanageable. They use a different technique to cope with this, but that is not the main point here.

Practically speaking, what are examples of languages or grammars that regex can always parse successfully?

A short answer is: Probably nothing that you call a language.

In theoretical computer science (TCS), a language simply means a set of words. But in most cases, what people call a “language” outside TCS has some recursive structure. “Recursive structure” is ambiguous here, but intuitively regular expressions cannot parse them because regular expressions even cannot parse balanced parentheses.

Many compilers use regular expressions for lexical analysis before parsing. For example, you can decide whether a certain string is a valid identifier in C++ or not by using a regular expression. This is possible because the language consisting of valid identifiers in C++ is a regular language. But the set of valid C++ identifiers is usually not called a language outside TCS.

Disclaimers:

  1. Some people distinguish “regular expression” and “regex.” In this answer, I am talking about regular expressions, not regexes, if we use this convention.

  2. Actual C++ compilers do not probably use a regular expression for valid identifiers because excluding keywords makes the regular expression unmanageable. They use a different technique to cope with this, but that is not the main point here.

Source Link
Tsuyoshi Ito
  • 16.6k
  • 2
  • 56
  • 106

Practically speaking, what are examples of languages or grammars that regex can always parse successfully?

A short answer is: Probably nothing that you call a language.

In theoretical computer science (TCS), a language simply means a set of words. But in most cases, what people call a “language” outside TCS has some recursive structure. “Recursive structure” is ambiguous here, but intuitively regular expressions cannot parse them because regular expressions even cannot parse balanced parentheses.

Many compilers use regular expressions for lexical analysis before parsing. For example, you can decide whether a certain string is a valid identifier in C++ or not by using a regular expression. This is possible because the language consisting of valid identifiers in C++ is a regular language. But the set of valid C++ identifiers is usually not called a language outside TCS.

Disclaimers:

  1. Some people distinguish “regular expression” and “regex.” In this answer, I am talking about regular expressions, not regexes, if we use this convention.

  2. Actual C++ compilers do not probably use a regular expression for valid identifiers because excluding keywords makes the regular expression unmanageable. They use a different technique to cope with this, but that is not the main point here.