| 1 | # re2c/Lemon Parser for Netdata Expression Evaluator |
| 2 | |
| 3 | This directory contains a parser implementation for Netdata's expression evaluator using re2c for lexical analysis and Lemon for syntax parsing. |
| 4 | |
| 5 | ## Overview |
| 6 | |
| 7 | The re2c/Lemon-based parser is designed to be more efficient and maintainable compared to the handwritten recursive descent parser in the parent directory. It achieves full compatibility with the original parser while providing better performance, especially for complex expressions with nested operations. |
| 8 | |
| 9 | ## Components |
| 10 | |
| 11 | - **lexer.re** - The re2c-based lexical analyzer source file |
| 12 | - **lexer.c** - The generated lexer code (generated from lexer.re) |
| 13 | - **parser.y** - The Lemon-based grammar definition |
| 14 | - **parser.c** - The generated parser code (generated from parser.y) |
| 15 | - **parser.h** - The generated parser header |
| 16 | - **parser_internal.h** - Internal definitions shared between the lexer and parser |
| 17 | - **parser_wrapper.c** - Integration wrapper for the Netdata build system |
| 18 | - **Makefile** - Build instructions for regenerating the parser |
| 19 | |
| 20 | ## Technology Stack |
| 21 | |
| 22 | ### re2c |
| 23 | |
| 24 | [re2c](https://re2c.org/) is a lexer generator that translates regular expressions into deterministic finite automata (DFA) and produces efficient C code. The lexer implemented in `lexer.re` tokenizes the input string according to the expression language grammar, handling: |
| 25 | |
| 26 | - Special literals (nan, inf) |
| 27 | - Numbers |
| 28 | - Variable names |
| 29 | - Operators |
| 30 | - Function names |
| 31 | - Whitespace |
| 32 | |
| 33 | ### Lemon |
| 34 | |
| 35 | [Lemon](https://www.sqlite.org/lemon.html) is a parser generator similar to YACC/Bison but with a different parsing technique and better thread safety. The grammar in `parser.y` defines the expression language syntax, operator precedence, and associativity rules. |
| 36 | |
| 37 | ## Integration |
| 38 | |
| 39 | This parser implementation can be selected by defining `USE_RE2C_LEMON_PARSER` in `eval-internal.h`. When enabled, the function `parse_expression_with_re2c_lemon()` is used instead of the original recursive descent parser. |
| 40 | |
| 41 | ## Key Features |
| 42 | |
| 43 | 1. **Parser Generator Approach**: Using specialized tools (re2c and Lemon) for lexical analysis and parsing rather than handwritten code. |
| 44 | |
| 45 | 2. **Full Compatibility**: Maintains 100% compatibility with the original parser, ensuring all test cases pass with identical results. |
| 46 | |
| 47 | 3. **Proper Operator Precedence**: Handles operator precedence correctly, especially for complex cases like nested ternary operators. |
| 48 | |
| 49 | 4. **Flexible Variable Names**: Supports the same variable naming rules as the original parser, including braced variables with spaces. |
| 50 | |
| 51 | 5. **Special Literal Handling**: Properly processes special literals like NaN and Infinity in various capitalizations. |
| 52 | |
| 53 | 6. **Case-Insensitive Keywords**: Handles logical operators (AND, OR, NOT) case-insensitively, just like the original parser. |
| 54 | |
| 55 | 7. **Reduced Memory Leaks**: Carefully manages memory allocations to prevent leaks, especially in error conditions. |
| 56 | |
| 57 | ## Rebuilding the Parser |
| 58 | |
| 59 | If you need to modify the lexer or parser definitions, you can rebuild the generated files using: |
| 60 | |
| 61 | ```bash |
| 62 | make -C src/libnetdata/eval/re2c_lemon |
| 63 | ``` |
| 64 | |
| 65 | This requires re2c and lemon to be installed on your system. |
| 66 | |
| 67 | ## Technical Details |
| 68 | |
| 69 | ### Parser Notes |
| 70 | |
| 71 | - The parser builds an abstract syntax tree (AST) using the `EVAL_NODE` structure. |
| 72 | - Operator precedence is carefully defined to match C-like languages. |
| 73 | - The ternary operator (`?:`) is properly implemented as right-associative. |
| 74 | - Error handling includes meaningful error messages and reporting of error locations. |
| 75 | |
| 76 | ### Lexer Notes |
| 77 | |
| 78 | - The re2c lexer is implemented as a scanner that tokenizes the input string one token at a time. |
| 79 | - It handles variable names with both simple syntax (`$var`) and braced syntax (`${complex var}`). |
| 80 | - Special care is taken for case-insensitive handling of keywords and special literals. |
| 81 | - The lexer automatically skips whitespace and handles end-of-input conditions. |
| 82 | |
| 83 | ### Memory Management |
| 84 | |
| 85 | - Uses Netdata's memory allocation patterns (`mallocz`, `freez`, etc.). |
| 86 | - Carefully tracks and frees memory in error conditions. |
| 87 | - Ensures proper cleanup on parse failure. |