Morbig: A Static parser for POSIX shell

AI snapshot

**TL;DR** Morbig is an open-source static parser for a realistic subset of POSIX shell that builds concrete syntax trees without evaluating scripts, using speculative parsing and Menhir’s incremental LR(1) interface to handle parsing-dependent lexing. It parses large corpora such as 31,330 Debian maintainer scripts in 7.38s and agrees with Dash on 95% of 7,436,215 Software Heritage scripts, while excluding inherently dynamic constructs like `eval` and unrestricted `alias`. **Key findings** - Morbig is a static parser for a well-defined, realistic subset of POSIX shell; it constructs concrete syntax trees without evaluating constructs, except for limited `alias` handling. It is open-source under GPL3. - The implementation uses speculative parsing, parser state introspection, context-dependent lexical analysis, and longest-prefix parsing, relying on the purity and incrementality of Menhir-generated LR(1) parsers. It cut-and-pastes the POSIX grammar; the shell-specific OCaml code is about 1000 lines, versus approximately 5000 extra C lines in Bash, and the total Morbig source is 2622 lines. - On Debian GNU/Linux, there are 31,582 maintainer scripts, 31,330 of which are POSIX shell. Morbig parses those 31,330 scripts and serializes their CSTs in 7.38s, failing on only one script that uses a Bash-specific extension; average parse time is 0.2ms, maximum 70ms for a 1121-line `prerm` script. - On the Software Heritage archive of 7,436,215 scripts, Dash takes 400s and Morbig 3400s (19,000 vs. 2,200 scripts per second). Morbig and Dash agree on 95%; 350,259 scripts (4.7% of total) accepted by Dash and rejected by Morbig contain Bash-specific constructs in words, 23,464 (0.3%) are due to remaining bugs, and only 0.03% are accepted by Morbig and refused by Dash. **Methods** - Design: a modular syntactic analyzer separating prelexing (OCamllex) from parsing-dependent lexing and a Menhir incremental LR(1) parser; it uses speculative parsing, parser state introspection, context-dependent lexical analysis, and longest-prefix parsing to produce concrete syntax trees. - Data/sample: a hand-written testsuite of 177 tests; 31,582 Debian maintainer scripts (31,330 POSIX shell); and 7,436,215 scripts from the Software Heritage archive detected by `libmagic`, compared against Dash. - Analysis: parse scripts, compare accept/reject behavior with Dash, benchmark parsing time, and build applications including a shell parsing toolkit, a statistical analyzer, a C API, an AST (`Morsmall`), and a user-extensible linter. **Limitations** - Stated: Morbig cannot handle inherently dynamic constructs: the `eval` builtin, unrestricted use of `alias` (only use outside control structures is permitted), and premature termination of a script by `exit` with trailing garbage in the file. Static parsing is incompatible with aliases and `eval`, so support for these will always be limited. - Stated: validation is only partial. Counting accepted/rejected scripts does not show whether the syntax tree is correct; backslash interpretation in word literals cannot be validated without comparing trees with other POSIX shell implementations. The parser drops some layout, spaces, and comments, and the paper does not claim formal correctness or absence of bugs, calling the code immature. - Evident from the text: the parser targets a subset of POSIX shell rather than the full language, and alias expansion introduces desynchronization between token positions in the lexing buffer and their actual source positions, complicating precise error locations.