Research Bison library

[jacknugent1529]

We plan on researching the bison library (https://www.gnu.org/software/bison/) and examining its usefulness for the CLI++ or DSL features. We aim to create a pros and cons list and some sample code using this library.

Assignees: John and Jack team: CLI++/DSL

[john-hahn]

After reading through the Bison library documentation provided on their site, I came up with a few pros and cons.

Pros

• It has two parsing algorithms included: LR and GLR (Generalized LR). There is some grammar that LR is not able to determine which of two possible reductions apply, so the user can run GLR to solve the ambiguous grammar.

The following is an example of a case where GLR can be run while LR fails to run:

type subrange = (a) .. b;
type enum = (a);

In this case, both lines of code are seemingly identical until it encounters the '..' token. LR's one-token lookahead would not be able to determine what form '(a)' should be parsed. GLR, on the other hand, would split the case into two branches, testing out each possible case, and merging in the end with the intended result.

• Though not considered one of the modern options with an old-school design, Bison is well-maintained, stable, and free for public use.

Cons

• Bison only supports a grammar format of BNF, which makes grammar more complicated. This means that the code that is used to manipulate the results of parsing is inside the grammar. Compared to other parsing libraries that support EBNF (ANTLR supports this), Bison does not provide as much flexibility as modern parsing libraries do due to this limitation.

An example of the grammar they support would be:

sum : NUM '+' NUM        { $$ = std::stoi($1) + std::stoi($2);      }

As you can see, the manipulation is within the brackets for this rule as compared to an example of a rule from ANTLR:

sum : NUM PLUS NUM ;

• The parsing speed of GLR compared to that of ALL(), which is used by ANTLR, is slower. A research paper comparing the parsing speeds says, "In practice, we found GLL and GLR to be ̃135x slower than ALL() on a corpus of 12,920 Java 6 library source files (123M) and 6 orders of magnitude slower on a single 3.2M Java file, respectively."

Sources: https://www.gnu.org/software/bison/manual/bison.pdf https://www.antlr.org/papers/allstar-techreport.pdf

[jacknugent1529]

I looked into using bison to write parsers in C. Since bison is just a parser and does not include a lexer, I used flex to create a lexer. I followed an example for a basic calculator with 4 operations, and then expanded on the example to create a scientific calculator with additional functions and parentheses (replit).

Pros:

• Works with C
• Bison is a widely used standard library with comprehensive documentation that comes preinstalled on many operating systems.
• Due to the above, there are a good amount of resources and usage examples relating to bison.
• Bison is still actively maintained, meaning it should support all modern computers for the forseeable future.
• The lexers commonly used with bison including flex are also widely used and come installed on many systems.

Cons:

• A lexer must be written separately. This means there is an additional dependency which might need to be updated if the parser is changed.
• Although it is still maintained, there is no active development, and more modern libraries exist
• Gives unhelpful parsing error messages. This generally makes the code more difficult to maintain and debug.
• The code is not especially easy to read.
• Appears to use slower algorithm compared to antlr, although that shouldn't be much of an issue in this case
• Uses a slightly less flexible BNF format compared to EBNF which is common in more modern parses

Additional Notes: Bison is a parser generator, not a parser combinator. This is not necessarily an advantage or disadvantage, but allows for slightly less flexibility in return for greater speed.

[ecoble]

Issue Score: ✔️++

Comments: Great job on this really thorough research! In the future, it would be better to keep this kind of research documentation in a Wiki page for your team, so it is easier to reference in the future.