OSParsers

The OSParsers component of the OS library contains reentrant parsers that read OSiL and OSrL strings and build, respectively, in-memory OSInstance and OSResult objects.

The OSiL parser is invoked through an OSiLReader object as illustrated below. Assume osil is a string with the problem instance.

OSiLReader *osilreader = NULL;
OSInstance *osinstance = NULL;
osilreader = new OSiLReader();
osinstance = osilreader->readOSiL( &osil);

The readOSiL method has a single argument which is a pointer to a string. The readOSiL method then calls an underlying method yygetOSInstance that parses the OSiL string. The major components of the OSiL schema recognized by the parser are.

<instanceHeader>
<variables>
<objectives>
<constraints>
<linearConstraintCoefficients>
<quadraticCoefficients>
<nonlinearExpressions>

There are other components in the OSiL schema, but they are not yet implemented. In most large-scale applications the <variables>, <objectives>, <constraints>, and <linearConstraintCoefficients> will comprise the bulk of the instance memory. Because of this, we have ``hard-coded'' the OSiL parser to read these specific elements very efficiently. The parsing of the <quadraticCoefficients> and <nonlinearExpressions> is done using code generated by flex and bison. In the OSParsers the file parseosil.l is used by flex to generate parseosil.cpp and the file parseosil.y is used by bison to generate parseosil.tab.cpp. In parseosil.l we use the reentrant option and in parseosil.y we use the pure-parser option to generate reentrant parsers. The parseosil.y file contains both our ``hard-coded'' parser and the grammar rules for the <quadraticCoefficients>!

and <nonlinearExpressions> sections. We are currently using GNU Bison version 3.2 and flex 2.5.33.

The typical OS user will have no need to edit either parseosil.l or parseosil.y and therefore will not have to worry about running either flex or bison to generate the parsers. The generated parser code from flex and bison is distributed with the project and works on all of the platforms listed in Table 1. If the user does edit either parseosil.l or parseosil.y then parseosil.cpp and parseosil.tab.cpp need to be regenerated with flex and bison. If these programs are present, in the OS directory execute

make  run_parsers

The files parseosrl.l and parseosrl.y are used by flex and bison to generate the code parseosrl.cpp and parseosrl.tab.cpp for parsing strings in OSrL format. The comments made above about the OSiL parser apply to the OSrL parser. The OSrL parser, like the OSiL parser, is invoked using an OSrL reading object. This is illustrated below (osrl is a string in OSrL format).

OSrLReader *osrlreader = NULL;
osrlreader = new OSrLReader();
OSResult *osresult = NULL;
osresult = osrlreader->readOSrL( osrl);

There is also a lexer parseosss.l for tokenizing the command line for the OSSolverService executable described in Section 10.

We hope to have a parser for OSoL in a future version of the project.