OCTools is a suite of tools which serve as a plug-in replacement for yacc and lex. The goal
is to provide a (roughly) source compatible tool which can convert yacc and lex
grammars into Objective C output for building parsers that run on MacOS and iOS.

The source kit can be found on GitHub.

Both tools can be compiled on the Macintosh using Xcode, and generate a command-line tool which can be run from the terminal or included into an Xcode project. (Both tools are built in C, so they should be portable to other platforms; however, I haven’t done the port so I’m not sure how successful porting would be.)

The goal of this project was to create Yacc and Lex analogs which generate re-entrant Objective C classes which implement the parsers, and for the Lex analog to use an Objective-C protocol definition for the input file, for maximum flexibility.

I’ve also included a PDF document which outlines how the LR(1) algorithm implemented in OCTools for the OCYacc parser generator works. Originally written as a guide to the code in OCYacc, I found myself including more and more details, until the paper turned into a 66 page review of LR grammar parsing, from LR(0) through SLR and LALR parsers to the LR(1) parser used by OCYacc.

The reason for the detail was because most of the documentation I found describing LR parsing techniques were hard to follow. I don’t know if my paper is any easier to follow, but I tried very hard to define concepts clearly as they were being used. This may make the paper a little redundant, but hopefully makes it easier to understand.

I would appreciate feedback.

The paper can be downloaded from here: Generating LR(1) and GLR grammars.

Note: While the paper intends to cover GLR grammars, at present that section is a placeholder. I’ve currently got the Tomita book “Efficient Parsing for Natural Language” which I need to review before I sketch a solution and flesh out the algorithm along with a detailed description in the same spirit as the rest of the paper. (I’ve read an overview of the algorithm, but sadly I have more questions than answers at this time.)

That paper, like the OCTools code, is free for download. Unlike the OCTools code, if you wish to redistribute the paper for commercial gain, please contact me for permission first.