-2

I code a new shell in C, that could be done in several ways: Flex/bison, finite state machine, abstract syntax tree or just a tokenizer in C. Now I've written a for-loop that changes the condition of the increment and I wonder if that is the same as a FSM? First I did it as a finite state machine but that code was very basic. Now I work on doing it with loops or recursion, hopefully I can make 2 methods that are mutually recursive in building up a pipeline, or that the for loop can handle all cases by dynamically building up an array an increasing the arguments. I still didn't settle on a reasonable MAX_PIPELINE_LENGTH but that could also be dynamic. Now the part of the code that I'm writing about looks as follows and tokenizes input from the shell e.g. the parameter const char * cmd is a string that could be something like echo 'foobar blarg'|grep foo|awk '{print $1}'|wc but it can only parse the command up to 4 pipelines this far.

I'm wondering if it is even possible to solve the problem with a for loop that implements a FSM or an AST with a for loop and the way that I try to do it or do I need I new strategy where I "think about recursion" from the beginning rather that hoping to make the function recursive later? I already have code to check if a char is between quotations.

Niklas Rosencrantz
  • 8,008
  • 17
  • 56
  • 95

1 Answers1

1

I think that between compound lists (which involve parenthesized expressions) and various operators (like |, && and ||, ...) the shell grammar is fundamentally recursive in nature, so yes, you should consider recursion up front.

There are many ways to parse language, but for this grammar, any way you do it your parser needs to handle recursive expressions on input, and your parser output needs to be be a some kind of recursive construct.

See here.

That doesn't necessarily mean you have to use a recursive algorithm to do the parsing, however, if you don't you'll most certainly need one or more growable stack's to store intermediate parsing state, which kind of rules out a simple state machine.

Erik Eidt
  • 33,282
  • 5
  • 57
  • 91
  • The recursion I've come up with is 1. Check if command contains the pipeline delimiter and call a function that is recursive for every substring, save the substring and make recursion until the substring doesn't contain a delimiter, and I will end up with a delimited list that a can execute: `{echo} {'foo bar'} {|} {awk} {'{print$1}'} {>} {output.txt}` and the state machine can depend on the current delimiter (', ", |, <...) – Niklas Rosencrantz Apr 27 '16 at 02:43