librdesc

Introduction

librdesc is a standard C99-based, right-recursive, table-driven parsing library. Unlike traditional parsing engines usually rely heavily on the machine's call stack, librdesc implements its own backtracing algorithm over Concrete Sytax Tree (CST) and token stack.

Key Features

• Table-Driven Parsing: Parser logic is generic and can be controlled at runtime without recompiling via the struct rdesc_cfg table.
• Pump Mechanism: Parsing is driven by rdesc_pump(), a state machine that allows for token by token feeding.
• Backtracing Without Call-Stack: Since backtracing is performed via CST, the call stack does not grow. Tokens are be stored in a heap-allocated stack to try non-terminal variants.

API Overview

1. Parser (rdesc.h): The engine that consumes the CFG and Input. It maintains a cursor (cur) and a root node (root).
2. CFG (cfg.h): Defines the rules, tokens, and non-terminals. This is usually static constant data populated via macros.
3. Stack (stack.h): Stores consumed tokens to facilitate backtracking. If a rule fails, the parser pops tokens back to retry an alternative variant.
4. BNF DSL (bnf_dsl.h): A set of macros to facilitate definning Context free grammars.

Quick Start Guide

To use librdesc, you typically follow these steps:

1. Define tokens and non-terminals. Create enums for your language symbols.
2. Define your grammar. You may use bnf_dsl.h macros to create the rules table.
3. Initialize:

   struct rdesc_cfg cfg;
   rdesc_cfg_init(&cfg, ...); // Load your rules
    
   struct rdesc parser;
   rdesc_init(&parser, &cfg);

4. Pump Tokens: Feed tokens into the loop until a tree is ready.

   rdesc_start(&parser, NT_STMT);  // Set your start symbol.
    
   enum rdesc_result res;
   struct rdesc_node *cst;
   while ((res = rdesc_pump(&parser, &cst, next_token())) == RDESC_CONTINUE) {
        // Acquire next_token from your lexer
   }
    
   if (res == RDESC_READY) {
        // Process the `cst`
   } else if (res == RDESC_NOMATCH) {
        // Handle syntax error
   }

Examples

• boolean_algebra.h : A Boolean Algebra grammar demonstrating backtracking and ambiguity handling.
• bc.h : A Basic Calculator implementation demonstrating operator precedence and expressions.

Building

See librdesc for building instructions.