Parsing and context-free grammars

"Oh, I'm building a scale model of the space needle out of lollipop sticks and chewing gum"

-- Millie, Ozy & Millie

This page is intended to provide a compilation of useful resources on parsers and context-free grammars. It exists because I'm presently writing a LL(k) parser, moocow, and because it's very hard to find good, clear, information on this on the 'net. (Yeesh, I wrote some of this stuff a long time ago)

Anyway, for one reason or another, what was moocow turned into ParseLib, a library that provides functions for generating various kinds of LR parse table from grammar descriptions. Parser generator tools such as YACC can be built on top of this (a demo application is ONNACC, which provides a YACC-like interface to parselib). ParseLib can also be used to generate parse tables on the fly - this can be useful for languages such as ASN.1 which can redefine themselves on the fly. ParseLib is also designed to provide functions suitable for the generation of different kinds of parse tables, although currently only a few LR-class parser tables are produced.

• LR parsing
  • SLR table generation
• LL parsing

Links

• Thomas Christopher has done some excellent work with LL(k) parsers
• Parsing Techniques - A Practical Guide - complete text of this book

Glossary

• BNF - Backus-Naur Form. A formal way of specifying language
• EBNF - Extended Backus-Naur Form. Backus-Naur form extended with Kleene closure and optional tokens. EBNF does not have any more expressive power than BNF, but can be more convienient to use.
• Non-terminal - a set of alternative productions that are given a token
• Production - a list of terminals and non-terminals. A parser tries to match its input to productions
• Terminal - a token returned by the lexer
• Token - a named entity