• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 879
  • Last Modified:

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

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).
3 Solutions
>> 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 ?
ThoughtProcessAuthor Commented:
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".

ThoughtProcessAuthor Commented:
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.
Get your problem seen by more experts

Be seen. Boost your question’s priority for more expert views and faster solutions

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.
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:
>> 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.
ThoughtProcessAuthor Commented:
Thank you for your help, guys!  This is a great launching point for parsing these files.
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Introducing Cloud Class® training courses

Tech changes fast. You can learn faster. That’s why we’re bringing professional training courses to Experts Exchange. With a subscription, you can access all the Cloud Class® courses to expand your education, prep for certifications, and get top-notch instructions.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now