Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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..."
share|improve this question
    
it's not a CSV as there's no nesting anywhere (IIRC) –  ratchet freak Sep 27 '12 at 16:41
1  
but what are the edge cases ? maybe there is more in CSV, than i ever thought ? –  c69 Sep 27 '12 at 16:44
1  
@c69 How about escape and quote char are both ". Then the following is valid: """this is a test.""","" –  Spencer Rathbun Sep 27 '12 at 17:00
    
Did you try regexp from here? –  dasblinkenlight Sep 27 '12 at 17:09
1  
You do need to watch out for edge cases, but a regex should be able to tokenize csv as you have described it. The regex does not need to count up an arbitrary number of quotes -- it only needs to count to 3, which regular expressions can do. As others have mentioned, you should try to write down a well-defined representation of what you expect a csv token to be... –  comingstorm Sep 27 '12 at 17:53

5 Answers 5

up vote 6 down vote accepted

Nice in theory, terrible in practice

By CSV I'm going to assume you mean the convention as described in RFC 4180.

While matching basic CSV data is trivial:

"data", "more data"

Note: BTW, it's a lot more efficient to use a .split('/n').split('"') function for very simple and well-structured data like this. Regular Expressions work as a NDFSM (Non-Deterministic Finite State Machine) that wastes a lot of time backtracking once you start adding edge cases like escape chars.

For example here's the most comprehensive regular expression matching string I've found:

re_valid = r"""
# Validate a CSV string having single, double or un-quoted values.
^                                   # Anchor to start of string.
\s*                                 # Allow whitespace before value.
(?:                                 # Group for value alternatives.
  '[^'\\]*(?:\\[\S\s][^'\\]*)*'     # Either Single quoted string,
| "[^"\\]*(?:\\[\S\s][^"\\]*)*"     # or Double quoted string,
| [^,'"\s\\]*(?:\s+[^,'"\s\\]+)*    # or Non-comma, non-quote stuff.
)                                   # End group of value alternatives.
\s*                                 # Allow whitespace after value.
(?:                                 # Zero or more additional values
  ,                                 # Values separated by a comma.
  \s*                               # Allow whitespace before value.
  (?:                               # Group for value alternatives.
    '[^'\\]*(?:\\[\S\s][^'\\]*)*'   # Either Single quoted string,
  | "[^"\\]*(?:\\[\S\s][^"\\]*)*"   # or Double quoted string,
  | [^,'"\s\\]*(?:\s+[^,'"\s\\]+)*  # or Non-comma, non-quote stuff.
  )                                 # End group of value alternatives.
  \s*                               # Allow whitespace after value.
)*                                  # Zero or more additional values
$                                   # Anchor to end of string.
"""

It reasonably handles single and double quoted values, but not newlines in values, escaped quotes, etc.

Source: Stack Overflow - How can I parse a string with JavaScript

It's becomes a nightmare once the common edge-cases are introduced like...

"such as ""escaped""","data"
"values that contain /n newline chars",""
"escaped, commas, like",",these"
"un-delimited data like", this
"","empty values"
"empty trailing values",        // <- this is completely valid
                                // <- trailing newline, may or may not be included

The newline-as-value edge case alone is enough to break 99.9999% of the RegEx based parsers found in the wild. The only 'reasonable' alternative is to use RegEx matching for basic control/non-control character (ie terminal vs non-terminal) tokenization paired with a state machine used for higher level analysis.

Source: Experience otherwise known as extensive pain and suffering.

I am the author of jquery-CSV, the only javascript based, fully RFC-compliant, CSV parser in the world. I have spent months tackling this problem, speaking with many intelligent people, and trying a ton if different implementations including 3 full rewrites of the core parser engine.

tl;dr - Moral of the story, PCRE alone sucks for parsing anything but the most simple and strict regular (Ie Type-III) grammars. Albeit, it's useful for tokenizing terminal and non-terminal strings.

share|improve this answer
    
Yup, that's been my experience as well. Any attempt to fully encapsulate more than a very simple CSV pattern runs into these things, and then you ram up against both the efficiency problems and complexity problems of a massive regex. Have you looked at the node-csv library? It seems to validate this theory as well. Every non trivial implementation uses a parser internally. –  Spencer Rathbun Oct 22 '13 at 12:22
    
@SpencerRathbun Yep. I'm sure I've taken a look at the node-csv source before. It appears to use a typical character tokenization state machine for processing. The jquery-csv parser works on the same fundamental concept except I use regex for terminal/non-terminal tokenization. Instead of evaluating and concatenating on a char-by-char basis, regex is able to match multiple non-terminal characters at a time and return them as a group (ie string). This minimizes unnecessary concatenation and 'should' increase efficiency. –  Evan Plaice Oct 22 '13 at 18:31

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.

share|improve this answer
    
Sure, it can still be parsed, but a regex is a tokenizer, not a parser. That is the question, can csv be handled just by a tokenizer and not a parser a la ANTLR or BISON. –  Spencer Rathbun Sep 27 '12 at 17:20
1  
@SpencerRathbun - given that I've done that with some reasonably simple csv files, I think the answer is yes. I used regex to extract out the values I needed from a particular csv file. Apologies if I'm missing the nuances of the terms that your question may be relying upon. –  GlenH7 Sep 27 '12 at 17:24
2  
-1: You cannot parse "just about anything" defined by "a set of rules" with a regex. See Chomsky hierarchy. Nested and matching parenthesis are the standard example, e.g. (), (()), ((())), (((()))) and so on - that is the number of opening parenthesis has to match the number of closing parenthesis. –  scarfridge Sep 28 '12 at 10:47

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

share|improve this answer

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.

share|improve this answer
1  
Quotes inside quotes need not be balanced. Instead, there must be an even number of quotes before an embedded quote, which is obviously regular: ("")*". If the quotes inside the value are off balance, it's already not our business. –  9000 Sep 27 '12 at 17:39
    
This is my position, having run into these horrible excuses for "data transfer" in the past. The only thing that properly handled them was a parser, pure regex broke every few weeks. –  Spencer Rathbun Sep 27 '12 at 18:23

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 may 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.

share|improve this answer
4  
Absolutely a +1 for the practical point. There is something that I'm sure, somewhere deep is an example of a (contrived) value that would break the quoted value version I just don't know what it is. The 'fun' with multiple parsers would be "these two work, but give different answers" –  MichaelT Sep 27 '12 at 17:55
1  
You will obviously need different regexes for backslash-escaped-quotes vs. doubled-quote-escaped-quotes. A regex for the former type of csv field should be something like [^,"]*|"(\\(\\|")|[^\\"])*", and the latter should be something like [^,"]*|"(""|[^"])*". (Beware, as I have not tested either of these!) –  comingstorm Sep 27 '12 at 18:10
    
Hunting for something that might be a standard, there is a case that is missed - a value with a record delimiter enclosed. This also makes the practical parsing even more fun when there are multiple different ways to handle that –  MichaelT Sep 27 '12 at 18:11
    
Nice answer, but if I run perl -pi -e 's/"([^\"]|\\\\|\\")*"/yay/' and pipe in "I have here an item,\" that is a test\"" then the result is `yay that is a test\"". Methinks your regex is flawed. –  Spencer Rathbun Sep 27 '12 at 18:22
    
@SpencerRathbun: when I have more time I'll actually test the regexes and probably even paste some proof-of-concept code that passes tests. Sorry, work day is going on. –  9000 Sep 27 '12 at 18:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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