Can the csv format be defined by a regex?

Question

A colleague and I have recently argued over whether a pure regex is capable of fully encapsulating the csv format, such that it is capable of parsing all files with any given escape char, quote char, and separator char.

The regex need not be capable of changing these chars after creation, but it must not fail on any other edge case.

I have argued that this is impossible for just a tokenizer. The only regex that might be able to do this is a very complex PCRE style that moves beyond just tokenizing.

I am looking for something along the lines of:

... the csv format is a context free grammar and as such, it is impossible to parse with regex alone ...

Or am I wrong? Is it possible to parse csv with just a POSIX regex?

For example, if both the escape char and the quote char are ", then these two lines are valid csv:

"""this is a test.""",""
"and he said,""What will be, will be."", to which I replied, ""Surely not!""","moving on to the next field here..."

Answer 1

Regex can parse any regular language, and cannot parse fancy things like recursive grammars. But CSV seems to be pretty regular, so parseable with a regex.

Let's work from definition: allowed are sequence, choice form alternatives (|), and repetition (Kleene star, the *).

• An unquoted value is regular: [^,]* # any char but comma
• A quoted value is regular: "([^\"]|\\\\|\\")*" # sequence of anything but quote " or escaped quote \" or escaped escape \\
  • Some forms may include escaping quotes with quotes, which adds a variant ("")*" to the expression above.
• An allowed value is regular: <unquoted-value>|<quoted-value>
• A single CSV line is regular: <value>(,<value>)*
• A sequence of lines separated by \n is also obviously regular.

I did not meticulously test each of these expressions, and never defined catch groups. I also glossed over some technicalities, like the variants of characters which can be used instead of ,, ", or line separators: these do not break the regularity, you just get several slightly different languages.

If you can spot a problem in this proof, please comment! :)

But despite this, practical parsing of CSV files by pure regular expressions my be problematic. You need to know which of the variants is being fed to the parser, and there's no standard for it. You can try several parsers against each line until one succeeds, or somehow divinate the format form comments. But this may require means other than regular expressions to do efficiently, or at all.

Answer 2

Simple answer - probably not.

The first problem is a lack of a standard. While one may describe their csv in a way that is strictly defined, one cannot expect to get strictly defined csv files. "Be conservative in what you do, be liberal in what you accept from others" -Jon Postal

Assuming that one does have a standardesque that is acceptable, there is the question of escape characters and if these need to be balanced.

A string in many csv formats is defined as string value 1,string value 2. However, if that string contains a comma it is now "string, value 1",string value 2. If it contains a quote it becomes "string, ""value 1""",string value 2.

At this point I believe it is impossible. The problem being you need to determine how many quotes you have read and if a comma is inside or outside of the double quoted mode of the value. Balancing parentheses is an impossible regex problem. Some extended regular expression engines (PCRE) can deal with it, but it isn't a regular expression then.

You might find http://stackoverflow.com/questions/8629763/csv-parsing-with-a-context-free-grammar useful.

---

Amended:

I have been looking at formats for escape characters and haven't found any that need arbitrary counting - so that is probably not the issue.

However, there are issues of what is the escape character and record delimiter (to start with). http://www.csvreader.com/csv_format.php is a good read on the different formats in the wild.

• The rules for the quoted string (if it is a single quoted string or a double quoted string) differ. ** 'This, is a value' vs "This, is a value"
• The rules for escape characters ** "This ""is a value""" vs"This \"is a value\""`
• The handling of embedded record delimiter ({rd}) ** (raw embeded) "This {rd}is a value" vs (escaped) "This \{rd}is a value" vs (translated)"This {0x1C}is a value"

The key thing here is that it is possible to have a string that will always have multiple valid interpretations.

The related question (for edge cases) "is it possible to have a invalid string that is accepted?"

I still strongly doubt that there is a regular expression that can match every valid CSV that is created by some application and reject every csv that cannot be parsed.

Answer 3

First define the grammar for your CSV (are the field delimiters escaped or encoded somehow if they appear in text?) and then it can be determined if it is parsable with regex. Grammar first: parser second: http://www.boyet.com/articles/csvparser.html It should be noted that this method uses a tokenizer - but I can't constuct a POSIX regex that would match all edge cases. If your usage of CSV formats is non-regular and context free ... then your answer is in your question. Good overview here: http://nikic.github.com/2012/06/15/The-true-power-of-regular-expressions.html

Answer 4

While I'm not a regex guru, I'm pretty comfortable stating that if there is a set of rules to parse the file then regex can do it. It might well be fugly and unmaintainable, but regex can be written to parse just about anything.

By definition, a CSV file (comma separated values) must have some sort of separator between values. Traditionally that's a comma but others can be used. Even if you use a quote mark for your separator along with quoted strings, it could still be parsed. Note that I'm relying upon the base assumption of there being rules to parse the file.

If it can't be parsed by any means, then no, regex isn't a silver bullet.