9

I'm trying to find a better solution for making a parser to some of the famous file formats out there such as: EDIFACT and TRADACOMS.

If you aren't familiar with these standards then check out this example from Wikipedia:

See below for an example of an EDIFACT message used to answer to a product availability request:-

UNA:+.? '
UNB+IATB:1+6XPPC+LHPPC+940101:0950+1'
UNH+1+PAORES:93:1:IA'
MSG+1:45'
IFT+3+XYZCOMPANY AVAILABILITY'
ERC+A7V:1:AMD'
IFT+3+NO MORE FLIGHTS'
ODI'
TVL+240493:1000::1220+FRA+JFK+DL+400+C'
PDI++C:3+Y::3+F::1'
APD+714C:0:::6++++++6X'
TVL+240493:1740::2030+JFK+MIA+DL+081+C'
PDI++C:4'
APD+EM2:0:130::6+++++++DA'
UNT+13+1'
UNZ+1+1'

The UNA segment is optional. If present, it specifies the special characters that are to be used to interpret the remainder of the message. There are six characters following UNA in this order:

  • component data element separator (: in this sample)
  • data element separator (+ in this sample)
  • decimal notification (. in this sample)
  • release character (? in this sample)
  • reserved, must be a space
  • segment terminator (' in this sample)

As you can see it's just some data formatted in a special way waiting to be parsed (much like XML files).

Now my system is built on PHP and I was able to create parser using regular expressions for each segment, but the problem is not everybody implements the standard perfectly.

Some suppliers tend to ignore optional segments and fields entirely. Others may choose to send more data than others. That's why I was forced to create validators for segments and fields to test if the file was correct or not.

You can imagine the nightmare of regular expressions I'm having right now. In addition each supplier needs many modifications to the regular expressions that I tend to build a parser for each supplier.

Questions:

1- Is this the best practice for parsing files (using regular expressions)?

2- Is there a better solution for parsing files (maybe there are ready made solution out there)? Will it be able to show what segment is missing or if the file is corrupted?

3- If I have to build my parser anyway what design pattern or methodology should I use?

Notes:

I read somewhere about yacc and ANTLR, but I don't know if they match my needs or not!

Improve this question
1

6 Answers 6

Reset to default
18

What you need is a true parser. Regular expressions handle lexing, not parsing. That is, they identify tokens within your input stream. Parsing is the context of the tokens, I.E. who goes where and in what order.

The classic parsing tool is yacc/bison. The classic lexer is lex/flex. Since php allows for integrating C code, you can use flex and bison to build your parser, have php call it on the input file/stream, and then get your results.

It will be blazing fast, and far easier to work with once you understand the tools. I suggest reading Lex and Yacc 2nd Ed. from O'Reilly. For an example, I've set up a flex and bison project on github, with a makefile. It is cross compilable for windows if necessary.

It is complex, but as you found out, what you need done is complex. There is a great deal of "stuff" that must be done for a properly working parser, and flex and bison deal with the mechanical bits. Otherwise, you find yourself in the unenviable position of writing code at the same abstraction layer as assembly.

Improve this answer
8
  • 1
    +1 Great answer, especially considering that it comes with a sample parser.
    – Caleb
    May 7, 2012 at 13:08
  • @caleb thanks, I work with flex/bison a lot, but there are very few decent(read: complex) examples. This isn't the best parser ever, since there aren't many comments, so feel free to send in updates.
    – Spencer Rathbun
    May 7, 2012 at 13:11
  • @SpencerRathbun thanks very much for your detailed answer and example. I have no knowledge what so ever about any of the terminology you mentioned (yacc/bison, lex/flex,...etc.) as I my experience is mainly about web development. Is "Lex and Yacc 2nd Ed" sufficient for me to understand everything and build a good parser? or is there other topics and materials that I should cover first?
    – Songo
    May 7, 2012 at 13:23
  • @songo The book does cover all the relevant details and is quite short, clocking in at ~300 mid sized pages. It does not cover using c, or language design. Luckily, there are lots of c references available, such as K&R The C Programming Language and you don't need to design a language, just follow the standards you have referenced. Please note that reading cover to cover is recommended, since the authors will mention something once, and assume if you need it you will go back and reread. That way you don't miss anything.
    – Spencer Rathbun
    May 7, 2012 at 13:56
  • I don't think a standard lexer can handle dynamic separators, which the UNA line may specify. So at the least you'll need a lexer with runtime-customizable characters for the 5 separators.
    – Kevin
    May 7, 2012 at 14:18
3

ouch.. 'true' parser? state machines??

sorry but i've been converted from academic to hacker since I began my employment.. so I would say there are easier ways.. although maybe not as 'refined' academically :)

I will try to offer an alternative approach which some may or may not agree with but it CAN be very practical in a work environment.

I would;

loop every line
   X = pop the first 3 letters of line
   Y = rest of line
   case X = 'UNA':
       class init (Y)

from there i would use classes for the data types. splitting component and element separators and iterate over the returned arrays.

For me, this is code re-use, OO, low cohesion and highly modular.. and easy to debug and program. simpler is better.

to parse a file you don't need state machines or anything entirely complicated.. state machines are well suited to parse code, you'll be suprised at how powerfull the above pseduo code can be when used in an OO context.

ps. i've worked with very similar files before :)

More pseudo code posted here:

class 

UNA:

init(Y):
 remove ' from end
 components = Y.split(':') 
 for c in components
     .. etc..

 getComponents():
   logic..
   return

 getSomethingElse():
   logic..
   return

class UNZ:
   ...

Parser(lines):

Msg = new obj;

for line in lines
   X = pop the first 3 letters of line
   Y = rest of line
   case X = 'UNA':
      Msg.add(UNA(Y))

msg.isOK = true
return Msg

you could then use it like this..

msg = Main(File.getLines());
// could put in error checking
// if msg.isOK:
msg.UNA.getSomethingElse();

and say you have more than one segment.. use a queue to add them and get the first, second etc.. as you need. You are really just representing the msg into an obj and giving the object methods to call the data. you could take advantage of this by also creating custom methods.. for inheritance.. well that's a different question and i think you could easily apply it if you understand it

Improve this answer
7
  • 3
    I've done that before, and found it is insufficient for anything beyond one or two cases of recognize X token and do Y. There is no context, you cannot have multiple states, moving past a trivial number of cases bloats the code, and error handling is difficult. I find that I have needed these features in the real world in almost all cases. That leaves aside mistakes in it as the complexity grows. The hardest part is setting up a skeleton, and learning how the tool operates. Get past that and it's just as fast to whip up something.
    – Spencer Rathbun
    May 7, 2012 at 14:04
  • it is a message, what states do you need? it would seem that such a message, which is organised in a structure of composites and segments would fit this OO approach perfectly. error handling is done per class and done properly you can construct a parser that is very efficient and extensible. messages such as this lend themselves to classes and functions especially when multiple vendors send different flavours of the same format. An example would be a function in a UNA class which returned a particular value for a specific vendor.
    – Ross
    May 7, 2012 at 14:12
  • @Ross so basically you will have a "UNA class" for the segment "UNA" and inside it there will be a parse method for each vendor (parseUNAsegemntForVendor1(),parseUNAsegemntForVendor2(),parseUNAsegemntForVendor3(),...etc), right ?
    – Songo
    May 7, 2012 at 14:19
  • 2
    @Ross There are sections to the message, valid at different points during parsing. Those are the states I was talking about. The OO design is clever, and I'm not saying it won't work. I push flex and bison because like functional programming concepts, they fit better than other tools, but most people believe they are too complicated to bother learning.
    – Spencer Rathbun
    May 7, 2012 at 14:39
  • @Songo.. nope, you would parse independently of the vendor (unless you new who). the parse would be in the INIT of the class. You turn your message into a data object based on the same rules used to construct the message. If you needed to grab something from the message however.. and it is represented differently across your vendors then you would have the different functions yep.. But why do it like that? use a base class and have a separate class for each vendor, overriding only when necessary, much easier. take advantage of inheritance.
    – Ross
    May 7, 2012 at 14:39
1

Have you tried googling for "PHP EDIFACT"? This is one of the first results that popped up: http://code.google.com/p/edieasy/

While it may not be sufficient for your use case, you may be able to get some ideas from it. I don't like the code with its many nested for loops and conditions, but it may be a start.

Improve this answer
1
  • 1
    I checked many projects out there, but the problem was mainly in the different implementations of the vendors using the standard. I might force one vendor to send me a certain segment, but I may consider it optional for another vendor. That's why I probably gonna need to build my own customized parser anyway.
    – Songo
    May 8, 2012 at 9:20
1

Well since Yacc/Bison+Flex/Lex got mentioned, I might as well throw in one of the other major alternatives: parser combinators. These are popular in functional programming like with Haskell, but if you can interface to C code you can use them and, what do you know, somebody wrote one for PHP too. (I have no experience with that particular implementation, but if it works like most of them, it should be pretty nice.)

The general concept is that you start with a set of small, easy to define parsers, usually tokenizers. Like you'd have one parser function for each of the 6 data elements you mentioned. Then you use combinators (functions that combine functions) to make larger parsers that grab larger elements. Like an optional segment would be the optional combinator operating on the segment parser.

Not sure how well it works in PHP, but it's a fun way to write a parser and I very much enjoy using them in other languages.

Improve this answer
0
0

instead of fiddling with regexes make your own state machine

this will be more readable (and be able to have better comments) in non-trivial situations and will be easier to debug that the black box that is regex

Improve this answer
1
  • 5
    A quick note, this is what flex and bison do under the hood. Only they do it right.
    – Spencer Rathbun
    May 7, 2012 at 13:21
0

I don't know what you want to exactly do with this data afterwards and if it is not a sledgehammer for a nut, but i had good experiences with eli. You describe the lexical phrases and then concrete/abstract syntax and generate what you want to generate.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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