Parser Design

August 6, 2026 · View on GitHub

Status

Implemented

Decision

Recursive descent parser with a context-aware lexer.

Input → Lexer → Tokens → Parser → AST

Token types, AST structures, and parser grammar live in crates/bashkit/src/parser/. They evolve as features are added.

Parser Rules (Simplified)

script        → command_list EOF
command_list  → pipeline (('&&' | '||' | ';' | '&') pipeline)*
pipeline      → command ('|' command)*
command       → simple_command | compound_command | function_def
time_command  → 'time' time_option* pipeline
simple_command → (assignment)* word (word | redirect)*
redirect      → ('>' | '>>' | '<' | '<<' | '<<<') word
               | NUMBER ('>' | '<') word

time is a reserved-word compound command, not a normal builtin. Its body is therefore a pipeline AST and can contain groups, functions, nested time, and redirections without converting shell syntax back into strings. Bashkit accepts Bash/POSIX -p plus -- and the practical GNU report flags -f/--format, -o/--output, -a/--append, and -v/--verbose on this grammar node.

Context-Aware Lexing

Handles bash's context-sensitivity:

  • $var in double quotes: expand; in single quotes: literal
  • Word splitting after expansion
  • Glob patterns (*, ?, [])
  • Brace expansion: {a,b,c} and {1..5} vs brace groups { cmd; }
  • Tilde expansion: ~ at start of word expands to $HOME

Arithmetic Expressions

$((expr)) supports: +, -, *, /, %, comparisons, logical &&/|| (short-circuit), bitwise operators, ternary ?:, variable references.

Error Recovery

Errors carry line/column, expected vs. found token, and parse context.

A nested parse must never silently vanish. parse_word is infallible (the interpreter also calls it for lazy parameter expansion), so a $(...) body that fails to parse still pushes its CommandSubstitution part — with empty commands — and stashes the inner error in Parser::deferred_error, which parse_script turns into a hard parse error. Both halves matter: the retained part keeps the word non-literal so surrounding literals cannot splice (a$(|)b must not become the command ab, which analysis would report to a host permission gate — see TM-ESC-032), and the deferred error rejects the script the way bash does. Process substitution keeps its part for the same reason, and hard-errors on budget failures (TM-DOS-021).

Alternatives Considered

  • PEG (pest, pom): rejected — bash grammar is context-sensitive, here-docs awkward, manual parser gives better errors.
  • Tree-sitter: rejected — incremental parsing overkill, large dep, harder to customize.

See also