Take the 2-minute tour ×

I've came across a question transform this text with sed [sed only] and it got me wondering what class of problems is solvable by stream editors or programs/computational models with similar constraints.

For E.g Regular expressions can solve problems that require fixed/const amount of memory (Can solve all problems that have a Deterministic Finite state automa)

My question is what are the computational limits/constraints of sed in particular and any stream editor in general and what class/classes of problems can be solved by it? (after mapping it some text alphabet set if need be)

share|improve this question

migrated from stackoverflow.com Mar 17 '13 at 12:27

This question came from our site for professional and enthusiast programmers.

A couple of years ago, there was a paper titled Extending Finite Automata to Efficiently Match Perl-Compatible Regular Expressions. Note that while a PCRE is more powerful than a DFA, it is not as powerful as a push down automata. The class of problems solvable by a PCRE is not yet well defined (other than "more than this, but less than that"). –  MichaelT Mar 17 '13 at 16:19
add comment

2 Answers

First of all, I would say that "can be done (or solvable)" != "best choice"

Let's see some examples:

  • You mentioned regex. Regex can detect prime numbers. Would you use regex for it?

  • text processing with some math calculation, can be done by sed too. however, if awk is available, would you go with sed?

  • also something like, parsing a text with a certain pattern, when 3rd match, do A, 6th match, do B, xth match do Y. this can be done by sed as well by playing with hold space. but think about it how straightforward if you use awk to solve it.

  • think about writing a normal for(i=1;i<100;i++) loop with sed

gnu sed supports passing matched part to external programs to do further processing then get result back. (like system() or getline in awk) So you could imagine what kind of problems sed can do if your sed is backup-ed with bc, sed, nl, seq, join, cut, sort, paste, grep even cp, mv, rm, find... and awk

The best choice for same problem could be different to different people. say a problem, sed is the best choice from your point of view. However he is not good at sed, but knows awk well, he thought awk is best choice. She knows python well.. and I am an expert of MS-Excel....

my 2cents.

share|improve this answer
Kent I understand your concerns, using sed for almost anything other than stream editing, i.e substitute;match;print etc, is probably not the most feasible of pursuits. My question was more of what is possible with sed, not what is feasible. After reading the FAQ, I understand this is not the best platform for such a question. I thank you for bringing out the full scope of what is practically(albeit a quite difficult) possible with sed. –  ffledgling Mar 17 '13 at 8:07
Kent also, in the question that I linked to, it is not about whether "solvable by sed implies best way to solve it is sed", infact quite the opposite, if the problem is not solvable , by sed (or the computational model you are working in) it certainly can't be best way to solve it. Ofcourse you solved the problem using gnu-sed, but not all similar problems may be solvable by gnu-sed (and certainly not pure sed). I hope this explains the intent behind this question. –  ffledgling Mar 17 '13 at 8:23
add comment

I use sed primarily in a *nix environment where the problem to be solved is a straightforward data transformation problem. For example, adding or removing columns from .csv data or modifying an existing date in a field. Also, sed is warranted where writing another piece of software written in Python, Perl, Clojure, awk, or your favorite language does not support the overhead of another module's maintenance.

I have not used sed's advanced features, like swapping registers, and probably will not, because going beyond a simple data transformation would warrant the overhead of a more fully fledged program.

share|improve this answer
I think I might not have been clear enough in explaining the question. This question wants to understand the scope (class of) all problems solvable with sed, for example Turing complete languages can solve problems in the class of P and some of the NP problems in exponential time. –  ffledgling Mar 17 '13 at 20:13
add comment

Your Answer


