"Regular Pattern Analyzer (RPA)"

Regular Pattern Analyzer (RPA) is a top-down, recursive parser. The input grammar notation is Backus–Naur Form (BNF) and the produced output is a browsable Abstract Syntax Tree (AST). The grammar allows Regular Expressions, so the parser can also be used as RegEx or search engine. The regular expressions in the RPA library are NOT based on the automata theory and they are not the same as the traditional Unix regular expressions. If you need Unix compatible regular expressions, please check the REX library. The execution engine supports muti-threading and it can parse multiple input streams simultaneously.

Features

Support for recursive expressions is important for parsing computer languages, especially the Left-Recursion. The RPA parser is capable to handle both direct and indirect left and right recursive expressions. It uses iterative algorithm to handle Left-Recursion, because it is impossible to handle Left-Recursive expressions using recursion. Left-Recursive expressions produce left associativity and that is what you would want to use for parsing mathematical expressions. Math operations normally have left associativity. For example, consider the expression 7 − 4 + 2. The result could be either (7 − 4) + 2 = 5 or 7 − (4 + 2) = 1. The former result corresponds to the case when + and − are left-associative, the latter to when + and - are right-associative.

Design

RPA analyzes the BNF schema and builds a parsing tree. Then the parsing tree is compiled to byte code. The byte code is run in a virtual machine to parse the input stream and produce an Abstract Syntax Tree (AST). Once the schema is compiled to byte code, the code can be run in multiple VMs (threads), the parser naturally supports multi-threading.