I have a file specification in BNF format.  How do I implement a parser that can read those files?

Posted on 2010-09-01
Last Modified: 2013-11-18
I have a specification for a proprietary text-based file format.  The spec contains about 10 pages worth of BNF logic to describe the formatting rules for these files.  I would like to implement a program that can read files in this format.  My understanding is that I'll need some kind of tool set (like lex and yacc) to parse and validate the file, and then read the contents of the file to allocate and populate objects in my program.

There are commercial implementations of this spec, but the vendors that I have found charge *annual* licensing fees in the tens of thousands of dollars.  To my knowledge, the organization that devised the spec charges no such royalty fees--it sounds like the cost is just an issue of the vendors' business models, and the fact that we're a niche industry.

When we look at what we need to do with the files vs. how much the 3rd party licenses cost, the build vs. buy equation makes it seem much more practical to roll our own implementation.

Getting back to the BNF issue, I *vaguely* remember dealing with this in my compilers class in college, but that was several years ago, and I haven't used that stuff since that class.  Should I look into a tool set like lex and yacc?  Or are there other options available?  I'm open to a variety of options (C++, .NET, etc).
Question by:ThoughtProcess
LVL 53

Accepted Solution

Infinity08 earned 84 total points
ID: 33578452
>> My understanding is that I'll need some kind of tool set (like lex and yacc) to parse and validate the file

lex/yacc (or one of their variants) would be my first choice.

If the BNF specification is clean, there should not be too much issues generating a parser for it using those tools.

Do you have any specific questions about them ?

Author Comment

ID: 33578597
As far as specific questions go, I'd like to build an in-memory representation of the data.

Here's a dumbed-down look at how the file is formatted:

[optional whitespace]
attribute 1
attribute 2
/BEGIN [child element]
/END [child element]
/END Foo

I plan to define a set of classes to match the possible elements.  Here's an example class that could work for the above file fragment:

class Foo : public Bar
      virutal ~Foo();

      ContainerClass<Attribute> attributeList;
      ContainerClass<Bar> children;

I need a way to allocate and populate a series of objects to match the data in the file.  Then I'd like to perform some checks on the resulting data.

I imagine that yacc/lex have the logic to determine if a file is well-formeed, but do they have a callback mechanism that can call constructors when certain patterns are matched?  

I guess I'm unsure of how I can make the jump from "knowing that the file is well-formed" to "populating data from the file into a set of objects".


Author Comment

ID: 33578683
Not-quite-ninja edit:

I did more reading on lex and yacc, and I think this fits the bill almost exactly.  Sorry for the previous "RTFM" comment.
Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

LVL 11

Assisted Solution

cup earned 83 total points
ID: 33581180
There are several ways to parse BNF - if you want speed, use recrsive descent but you need to make sure you do not have any left recursive definitions.   If you want good error messages, use LALR - lex/yacc/bison.  Lex/yacc/bison is OK if you keep to using it as a tool and don't try to debug the generated code.  Note that lex and yacc/bison are separate tools with their own distinct syntax rules.

Assisted Solution

jhp333 earned 83 total points
ID: 33581626
I recently used Flex/Bison, 15 years after I took compiler theory class. It was not too difficult to catch up, but it surely took some time especially when I wanted more accurate error messages. I used only C, not C++, as those tools looked more native to C, and built a syntax tree with C structure.

Looking at your example, I got an impression that its grammar is so simple (no operator precedence etc.) that it might be easily converted to XML using only lex. Yacc is far more complicated than lex.

It seems you're working on a Windows platform. Then you can find your tools from these links:
LVL 53

Expert Comment

ID: 33584389
>> I imagine that yacc/lex have the logic to determine if a file is well-formeed,

They provide you the tools to implement this kind of check. You'll still have to add the logic yourself though. In the most basic way, you can show an error message whenever an unexpected token is encountered.

>> but do they have a callback mechanism that can call constructors when certain patterns are matched?  

Yes. Whenever a rule is matched, yacc allows you to execute arbitrary code. So, it's just a matter of specifying the right rules, and adding the right code to the rules.

>> /BEGIN Foo
>> [optional whitespace]
>> attribute 1
>> attribute 2
>> /BEGIN [child element]
>> ...
>> /END [child element]
>> /END Foo

That doesn't look too complicated, so it shouldn't be too difficult to parse it.

Author Closing Comment

ID: 33694439
Thank you for your help, guys!  This is a great launching point for parsing these files.

Featured Post

Find Ransomware Secrets With All-Source Analysis

Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

Join & Write a Comment

Navigation is an important part of web design from a usability perspective. But it is often a pain when it comes to a developer’s perspective. By navigation, it often means menuing. This is less theory and more practical of how to get a specific gro…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

758 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

22 Experts available now in Live!

Get 1:1 Help Now