Parsing: library functions, FSM, explode() or lex/yacc?
Asked Answered
T

3

6

When I have to parse text (e.g. config files or other rather simple/descriptive languages), there are several solutions that come to my mind:

  • using library functions, e.g. strtok(), sscanf()
  • a finite state machine which processes one char at a time, tokenizing and parsing
  • using the explode() function I once wrote out of pure boredom
  • using lex/yacc (read: flex/bison) to generate an appropriate parser

I don't like the "library functions" approach. It feels clumsy and awkward. explode(), while it doesn't take much new code, feels even more blown up. And flex/bison often seems like sheer overkill.

I usually implement a FSM, but at the same time I already feel sorry for the poor guy that may have to maintain my code at a later point.

Hence my question:

What is the best way to parse relatively simple text files?
Does it matter at all?
Is there a commonly agreed-upon approach?

Theorbo answered 17/4, 2011 at 22:3 Comment(1)
Why do you find flex/bison overkill ? They surely can easily be used to parse config files or simple languages. I usually parse my config files with home made C++ (or C when applicable) parsers, and I always regret it. Using a regex library could make you lean toward ad hoc parsing though. For config files, look at libconfig.Pauperism
G
6

I'm going to break the rules a bit and answer your questions out of order.

  • Is there a commonly agreed-upon approach?

Absolutely not. IMHO the solution you choose should depend on (to name a few) your text, your timeframe, your experience, even your personality. If the text is simple enough to make flex and bison overkill, maybe C is itself overkill. Is it more important to be fast, or robust? Does it need to be maintained, or can it start quick and dirty? Are you a passionate C user, or can you be enticed away with the right language features? &c., &c.

  • Does it matter at all?

Again, this is something only you can answer. If you're working closely with a team of people, with particular skills and abilities, and the parser is important and needs to be maintained, it sure does matter! If you're writing something "out of pure boredom," I would suggest that it doesn't matter at all, no. :-)

  • What is the best way to parse relatively simple text files?

Well, I don't know that you're going to like my answer. Maybe first read some of the other fine answers here.

No, really, go ahead. I'll wait.

Ah, you're back and relaxed. Let's ease into things, shall we?

Never write it in 'C' if you can do it in 'awk';
Never do it in 'awk' if 'sed' can handle it;
Never use 'sed' when 'tr' can do the job;
Never invoke 'tr' when 'cat' is sufficient;
Avoid using 'cat' whenever possible.
-- Taylor's Laws of Programming

If you're writing it in C, but C feels like the wrong tool...it really might be the wrong tool. awk or perl will likely do what you're trying to do without all the aggravation. You may even be able to do it with cut or something similar.

On the other hand, if you're writing it in C, you probably have a good reason to write it in C. Maybe your parser is a tiny part of a much larger system, which, for the sake of argument, is embedded, in a refrigerator, on the moon. Or maybe you loooove C. You may even hate awk and perl, heaven forfend.

If you don't hate awk and perl, you may want to embed them into your C program. This is doable, in principle--I've never done it myself. For awk, try libmawk. For perl, there are proably a few ways (TMTOWTDI). You can run perl separately using popen to start it, or you can actually embed a Perl interpreter into your C program--see man perlembed.

Anyhow, as I've said, "the best way to parse" entirely depends on you and your team, the problem space, and your approach to the issue. What I can offer is my opinion.

I'm going to assume that in your C-only solutions (library functions and FSM (considering your explode to essentially be a library function)) you've already done your best at isolating the relevant code, designing the code and files well, and so forth.

Even so, I'm going to recommend lex and yacc.

Library functions feel "clumsy and awkward." A state machine seems unmaintainable. But you say that lex and yacc feel like overkill.

I think you should approach your complaints differently. What you're really doing is specifying a FSM. However, you're also hiring someone to write and maintain it for you, thereby solving most of the maintainability problem. Overkill? Did I mention they'll work for free?

I suspect, but do not know, that the reason lex and yacc originally felt like overkill was that your config / simple files just felt too, well, simple. If I'm right (a big if), you may be able to do most of your work in the lexer. (It's even conceivable that you can do all of your work in the lexer, but I know nothing about your input.) If your input is not only simple but widespread, you may be able to find a lexer/parser combination freely available for what you need.

In short: if you can do this not in C, try something else. If you want C, use lex and yacc--they have a little overhead, but they're a very good solution.

Grantor answered 25/5, 2011 at 12:25 Comment(0)
A
0

If you can get it to work, I'd go with an FSM, but with a huge assist from Perl-compatible regular expressions. This library is easy to understand, and you ought to be able to trim back sufficient extraneous spaghetti to give your monster that aerodynamic flair to which all flying monsters aspire. That, and plenty of comments in well-structured spaghetti, ought to make your code-maintaining successor comfortable. (And, as I'm sure you know, that code-maintaining successor is you after six months, when you've moved on to something else and the details of this code have slipped your mind.)

Atmometer answered 18/4, 2011 at 8:27 Comment(1)
My FSMs usually resemble while(c = nextc()) switch(c) {...}. I don't consider them to be spaghetti monsters, merely... being large. That having said, I have never used RE in C and refuse to do so. :>Theorbo
N
0

My short answer is to use the right too for the problem. If you have configuration files use existing standards and formats e.g. ini Files and parse them using Boost program_options.

If you enter the world of "own" languages use lex/yacc, since they provide you with the required features, but you have to consider the cost of maintaining the grammar and language implementation.

As a result I would recommend to further narrow you problem scope to find the right tool.

Notify answered 27/5, 2011 at 10:54 Comment(1)
The trouble with Boost is that it is C++ code rather than C code and the question does ask about C.Leora

© 2022 - 2024 — McMap. All rights reserved.