# Parsing shell commands **URL:** \ **Category:** Learning\ **Tags:** menhir, parsing\ **Created:** [August 20, 2019, 6:37pm UTC](https://discuss.ocaml.org/t/parsing-shell-commands/4274 "2019-08-20T18:37:37Z")\ **Posts on this page:** 10\ **Page:** 1
**Author:** ![AjayMT](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/ajaymt/32/1732_2.png) [@AjayMT](https://discuss.ocaml.org/u/AjayMT)\ **Post date:** [August 20, 2019, 6:37pm UTC](https://discuss.ocaml.org/t/parsing-shell-commands/4274/1 "2019-08-20T18:37:37Z")
Hey everyone, As a first project, I’m trying to write a simple shell in OCaml. I want to be able to parse commands that look like this: ```auto ENV_VAR=value ENV_VAR=value command arg1 arg2 ``` I’ve written a menhir/ocamlyacc grammar that parses commands and arguments just fine, but fails when they are preceded by environment variables. Here is the relevant parser code: ```auto %{ type expr = Empty | Expr of (string * string) list * string * string list %} %token WORD %token KEY %token EQ %token EOL %start main %type <(expr, string) result> main %% main: expr EOL { Ok $1 } | error EOL { Error "Parse error" } ; expr: { Empty } | WORD { Expr ([], $1, []) } | WORD args { Expr ([], $1, $2) } | env WORD { Expr ($1, $2, []) } | env WORD args { Expr ($1, $2, $3) } ; // ...arg parsing... env: var { [$1] } | env var { $2 :: $1 } ; var: KEY EQ WORD { ($1, $2) } ; ``` Here is the relevant lexer rule: ```auto { open Parser exception Eof exception SyntaxError } let char = [^ '\\' ' ' '\t' '\n' '|' '='] let alpha = ['a'-'z' 'A'-'Z'] let keyChar = ['a'-'z' 'A'-'Z' '0'-'9' '_'] rule token = parse | [' ' '\t'] { token lexbuf } | '\n' { EOL } | '=' { EQ } | char+ as w { WORD (w) } | alpha keyChar* as w { KEY (w) } | eof { raise Eof } | _ { raise SyntaxError } ``` Adding a separator between environment variables and the rest of the expression didn’t seem to solve the problem, so my understanding is that the parser (or perhaps the lexer, in this case) cannot distinguish between `KEY`s and `WORD`s in certain cases. Is there a better way to approach this problem? Any advice or insight is appreciated. ---
**Author:** ![Chet\_Murthy](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/chet_murthy/32/1501_2.png) [@Chet\_Murthy](https://discuss.ocaml.org/u/Chet_Murthy)\ **Post date:** [August 20, 2019, 8:22pm UTC](https://discuss.ocaml.org/t/parsing-shell-commands/4274/2 "2019-08-20T20:22:38Z")
There are a lot of shells out there in the wild, and most of 'em OSS. I’d go dig up a few, say, bash, csh, zsh, ash, and have a quick look at how they parse. Which formalisms they use (LALR? LL? hand-coded recursive descent (hope not!)) and maybe even I could steal some code, if they use LALR. At least, that’s how I’d start. ETA: it won’t help with the “how do I design the AST & evaluator” but it might help with parsing and lexing. ---
**Author:** ![octachron](https://avatars.discourse-cdn.com/v4/letter/o/49beb7/32.png) [@octachron](https://discuss.ocaml.org/u/octachron)\ **Post date:** [August 20, 2019, 9:30pm UTC](https://discuss.ocaml.org/t/parsing-shell-commands/4274/3 "2019-08-20T21:30:00Z")
There is at least one problem in the lexer: the `char+` rule in the parser is a superset of the `alpha KeyChar*` rule, thus `KEY` tokens are never produced. ---
**Author:** ![XVilka](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/xvilka/32/5334_2.png) [@XVilka](https://discuss.ocaml.org/u/XVilka)\ **Post date:** [August 21, 2019, 7:00am UTC](https://discuss.ocaml.org/t/parsing-shell-commands/4274/4 "2019-08-21T07:00:54Z")
There is also a grammar-based parser in [Cicada](https://github.com/mitnk/cicada) - Rust-written POSIX shell. It might be helpful for your project to check its internals too. ---
**Author:** ![Armael](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/armael/32/1223_2.png) [@Armael](https://discuss.ocaml.org/u/Armael)\ **Post date:** [August 21, 2019, 8:20am UTC](https://discuss.ocaml.org/t/parsing-shell-commands/4274/5 "2019-08-21T08:20:28Z")
This is a bit off-topic since @AjayMT is probably not aiming for a fully posix-compatible shell, but I should mention the [CoLiS project](https://www.irif.fr/~treinen/colis/) (currently ongoing) that focuses on building tools for static analysis of shell scripts (install scripts from debian packages being the main target). One achievement of the project is [Morbig](https://github.com/colis-anr/morbig), a “trustworthy shell parser” implemented in OCaml, which parses posix shell statically and has been validated against the specification. They manage to use a menhir-generated parser to do the bulk of the work, and then use menhir’s incremental API to instrument the parser in order to handle the unorthodox parts of the specification. The companion paper is quite a fun read: [https://niols.fr/materials/papers/sle18.pdf](https://niols.fr/materials/papers/sle18.pdf) @Chet_Murthy you’d be surprised… To quote the paper above: > The parser of Dash 0.5.7 is made of 1569 hand-crafted lines of C code. This parser is hard to understand because it is implemented by low-level mechanisms that are difficult to relate to the high-level specification of the POSIX standard: for example, lexing functions are implemented by means of gotos and complex character-level manipulations; the parsing state is encoded using activation and deactivation of bit fields in one global variable; some speculative parsing is done by allowing the parser to read the input tokens several times, etc. In fact, POSIX shell is very challenging to parse _statically_ because lexing may depend on parsing, or even the evaluation (!) in full generality (because of `alias`)… The difficulties are well described in the paper. ---
**Author:** ![XVilka](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/xvilka/32/5334_2.png) [@XVilka](https://discuss.ocaml.org/u/XVilka)\ **Post date:** [August 21, 2019, 8:29am UTC](https://discuss.ocaml.org/t/parsing-shell-commands/4274/6 "2019-08-21T08:29:39Z")
There is also the [ShellCheck](https://github.com/koalaman/shellcheck/) for static analysis of the shell scripts. Production-ready tool, but in Haskell. ---
**Author:** ![Chet\_Murthy](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/chet_murthy/32/1501_2.png) [@Chet\_Murthy](https://discuss.ocaml.org/u/Chet_Murthy)\ **Post date:** [August 21, 2019, 5:34pm UTC](https://discuss.ocaml.org/t/parsing-shell-commands/4274/7 "2019-08-21T17:34:01Z")
Interesting. I wonder if Dash has a claim to fame of being really low-overhead? I know that back in the day, the Yacc authors (or maybe somebody else) showed that they could could achieve some speedup by (in FP terms) partially-evaluating the stack automaton and actions, with the tables – resulting in a massive goto-nest. One presumes that the same thing is true of lexing. In any case, it seems that bash itself uses a Yacc grammar. I’m not at a real machine, so can’t check what its lexer is written in/with. ---
**Author:** ![perry](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/perry/32/518_2.png) [@perry](https://discuss.ocaml.org/u/perry)\ **Post date:** [August 21, 2019, 8:54pm UTC](https://discuss.ocaml.org/t/parsing-shell-commands/4274/8 "2019-08-21T20:54:56Z")
> [@Chet\_Murthy](#): > > I wonder if Dash has a claim to fame of being really low-overhead? The reason people use ash/dash for scripts instead of bash is dramatically better execution time. I suspect, though, that parsing overhead is a small part of that. ---
**Author:** ![Chet\_Murthy](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/chet_murthy/32/1501_2.png) [@Chet\_Murthy](https://discuss.ocaml.org/u/Chet_Murthy)\ **Post date:** [August 22, 2019, 12:21am UTC](https://discuss.ocaml.org/t/parsing-shell-commands/4274/9 "2019-08-22T00:21:20Z")
Agreed. And I find no … “breakdown” of the reasons for which dash is faster than bash. Which … as an engineer, I find “interesting”, but hey, I get it: software -is-. Ah, well. FWIW, it’s clear that dash is wildly faster than bash. Wildly. ---
**Author:** ![perry](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/perry/32/518_2.png) [@perry](https://discuss.ocaml.org/u/perry)\ **Post date:** [August 22, 2019, 12:42am UTC](https://discuss.ocaml.org/t/parsing-shell-commands/4274/10 "2019-08-22T00:42:23Z")
Dash is just a modified version of ash, FYI. It wasn’t intended as such to be a faster shell; it was written to be an unencumbered reimplementation of the Bourne shell in an era where few such things existed. It’s used as /bin/sh on the various BSDs. Debian forked it and modified it.