# Fuchsia Shell Parser

Provides a basic parser for the shell grammar.

The parser is built on combinators, which means the parser is built out of other parsers.

A parser in the source appears as a function taking a single argument of type ParseResultStream and
returning a value of type ParseResultStream. The argument is the result of parsing a prefix before
the current parse. As an example, consider the grammar:

  S <- A B

Assuming we had parser functions for A and B, named A() and B() respectively, we could implement S
as follows:

  ParseResultStream S(ParseResultStream prefixes) {
    return B(A(prefixes));
  }

(There's some subtleties here, such that this rule wouldn't be implemented this way in practice, but
it gets a point across).

ParseResultStream is a stream of ParseResult objects. If parsing goes normally, the first
ParseResult yielded by the stream is the only one of interest. If parsing has failed, each
successive ParseResult yielded by the stream will contain a different attempt at error recovery.
Successful parses will also yield error recovery attempts if polled further, as a parse that seemed
okay may turn out to be wrong after parsing further. As an example, consider a grammar that parses
nested parentheses encountering the string '('. We might parse the opening parenthesis successfully,
then try to parse the closing parenthesis. When we discover it's missing, we might decide that the
opening parenthesis should not actually have parsed successfully.

ParseResultStream also contains a flag indicating whether the last parser succeeded. This is useful
in avoiding error recovery in some cases, as polling the stream will always attempt to construct a
recovered parse, whereas we sometimes only want to know the parse failed but don't need a recovery.

ParseResult itself contains three pieces of information: the "tail" of the parse, representing the
un-parsed data remaining after the parse, various information comprising an "error score", which
indicates how much error recovery was necessary to make the parse succeed, and a stack, which
contains the AST nodes we have produced.

To understand the stack, consider our A B example above. After successfully parsing S, the stack
might contain two nodes:

Node("A") Node("B")

The ParseResult's "node" accessor would yield Node("B"), as it yields the top of the stack. We can
call Reduce() on a ParseResult to collapse the stack into a single node, so if we called Reduce("S")
on our result, we would end up with one node on the stack:

Node("S", children = { Node(A) Node(B) })

Reduce() will consume the entire stack by default. This is inconvenient for more complicated
parsers. To make S safe, we would insert a "marker node" to indicate the point in the stack where
Reduce() should stop consuming.

ParseResultStream has methods to automatically push a marker node to each result it yields, or
reduce every result it yields, so a better implementation of S would be:

  ParseResultStream S(ParseResultStream prefixes) {
    return B(A(prefixes.Mark())).Reduce("S");
  }

The only issue with this is that it doesn't necessarily set the "ok" flag on ParseResultStream
correctly. Because the "ok" flag is set to the success of the last parser, this would return "ok" if
B returned "ok". But from a caller's perspective, the parse should only succeed if neither A nor B
required error correction, so we need to adjust our handling of the flag:

  ParseResultStream S(ParseResultStream prefixes) {
    auto a_result = A(prefixes.Mark());
    bool a_ok = a_result.ok();
    auto b_result = B(std::move(a_result)).Reduce("S");

    if (ok) {
    	return b_result;
    } else {
    	return b_result.Fail();
    }
  }

This pattern is somewhat unwieldy, so we implement several combinator functions to produce it
automatically. The NT ("NonTerminal") combinator takes a parser as input and automatically places a
Mark() before it and a Reduce after it, while the Seq combinator runs two parsers in sequence and
handles the ok flag correctly. With these tools, our S implementation becomes:

  ParseResultStream S(ParseResultStream prefixes) {
    return NT("S", Seq(A, B));
  }

## Error handling in a nutshell

Error handling relies on one invariant: ParseResultStream yields results in order of increasing
amount of error correction (measured as Levenshtein distance to the nearest correctly-parsing
string). That means that a correct parse will always come first, and that if there is no correct
parse, the parse requiring the least error correction will come first.

For the simple base parsers which parse single tokens, this is baked into the implementation. The
provided combinators guarantee this property by induction (i.e. if the input parsers have this
property, the combinator will produce a parser with this property).