1<!--===- docs/ParserCombinators.md
2
3   Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4   See https://llvm.org/LICENSE.txt for license information.
5   SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
7-->
8
9## Concept
10The Fortran language recognizer here can be classified as an LL recursive
11descent parser.  It is composed from a *parser combinator* library that
12defines a few fundamental parsers and a few ways to compose them into more
13powerful parsers.
14
15For our purposes here, a *parser* is any object that attempts to recognize
16an instance of some syntax from an input stream.  It may succeed or fail.
17On success, it may return some semantic value to its caller.
18
19In C++ terms, a parser is any instance of a class that
201. has a `constexpr` default constructor,
211. defines a type named `resultType`, and
221. provides a function (`const` member or `static`) that accepts a reference to a
23`ParseState` as its argument and returns a `std::optional<resultType>` as a
24result, with the presence or absence of a value in the `std::optional<>`
25signifying success or failure, respectively.
26```
27std::optional<resultType> Parse(ParseState &) const;
28```
29The `resultType` of a parser is typically the class type of some particular
30node type in the parse tree.
31
32`ParseState` is a class that encapsulates a position in the source stream,
33collects messages, and holds a few state flags that determine tokenization
34(e.g., are we in a character literal?).  Instances of `ParseState` are
35independent and complete -- they are cheap to duplicate whenever necessary to
36implement backtracking.
37
38The `constexpr` default constructor of a parser is important.  The functions
39(below) that operate on instances of parsers are themselves all `constexpr`.
40This use of compile-time expressions allows the entirety of a recursive
41descent parser for a language to be constructed at compilation time through
42the use of templates.
43
44### Fundamental Predefined Parsers
45These objects and functions are (or return) the fundamental parsers:
46
47* `ok` is a trivial parser that always succeeds without advancing.
48* `pure(x)` returns a trivial parser that always succeeds without advancing,
49  returning some value `x`.
50* `pure<T>()` is `pure(T{})` but does not require that T be copy-constructible.
51* `fail<T>(msg)` denotes a trivial parser that always fails, emitting the
52  given message as a side effect.  The template parameter is the type of
53  the value that the parser never returns.
54* `nextCh` consumes the next character and returns its location,
55  and fails at EOF.
56* `"xyz"_ch` succeeds if the next character consumed matches any of those
57  in the string and returns its location.  Be advised that the source
58  will have been normalized to lower case (miniscule) letters outside
59  character and Hollerith literals and edit descriptors before parsing.
60
61### Combinators
62These functions and operators combine existing parsers to generate new parsers.
63They are `constexpr`, so they should be viewed as type-safe macros.
64
65* `!p` succeeds if p fails, and fails if p succeeds.
66* `p >> q` fails if p does, otherwise running q and returning its value when
67  it succeeds.
68* `p / q` fails if p does, otherwise running q and returning p's value
69  if q succeeds.
70* `p || q` succeeds if p does, otherwise running q.  The two parsers must
71  have the same type, and the value returned by the first succeeding parser
72  is the value of the combination.
73* `first(p1, p2, ...)` returns the value of the first parser that succeeds.
74  All of the parsers in the list must return the same type.
75  It is essentially the same as `p1 || p2 || ...` but has a slightly
76  faster implementation and may be easier to format in your code.
77* `lookAhead(p)` succeeds if p does, but doesn't modify any state.
78* `attempt(p)` succeeds if p does, safely preserving state on failure.
79* `many(p)` recognizes a greedy sequence of zero or more nonempty successes
80  of p, and returns `std::list<>` of their values.  It always succeeds.
81* `some(p)` recognized a greedy sequence of one or more successes of p.
82  It fails if p immediately fails.
83* `skipMany(p)` is the same as `many(p)`, but it discards the results.
84* `maybe(p)` tries to match p, returning an `std::optional<T>` value.
85  It always succeeds.
86* `defaulted(p)` matches p, and when p fails it returns a
87  default-constructed instance of p's resultType.  It always succeeds.
88* `nonemptySeparated(p, q)` repeatedly matches "p q p q p q ... p",
89  returning a `std::list<>` of only the values of the p's.  It fails if
90  p immediately fails.
91* `extension(p)` parses p if strict standard compliance is disabled,
92   or with a warning if nonstandard usage warnings are enabled.
93* `deprecated(p)` parses p if strict standard compliance is disabled,
94  with a warning if deprecated usage warnings are enabled.
95* `inContext(msg, p)` runs p within an error message context; any
96  message that `p` generates will be tagged with `msg` as its
97  context.  Contexts may nest.
98* `withMessage(msg, p)` succeeds if `p` does, and if it does not,
99  it discards the messages from `p` and fails with the specified message.
100* `recovery(p, q)` is equivalent to `p || q`, except that error messages
101  generated from the first parser are retained, and a flag is set in
102  the ParseState to remember that error recovery was necessary.
103* `localRecovery(msg, p, q)` is equivalent to
104  `recovery(withMessage(msg, p), q >> pure<A>())` where `A` is the
105  result type of 'p'.
106  It is useful for targeted error recovery situations within statements.
107
108Note that
109```
110a >> b >> c / d / e
111```
112matches a sequence of five parsers, but returns only the result that was
113obtained by matching `c`.
114
115### Applicatives
116The following *applicative* combinators combine parsers and modify or
117collect the values that they return.
118
119* `construct<T>(p1, p2, ...)` matches zero or more parsers in succession,
120  collecting their results and then passing them with move semantics to a
121  constructor for the type T if they all succeed.
122  If there is a single parser as the argument and it returns no usable
123  value but only success or failure (_e.g.,_ `"IF"_tok`), the default
124  nullary constructor of the type `T` is called.
125* `sourced(p)` matches p, and fills in its `source` data member with the
126  locations of the cooked character stream that it consumed
127* `applyFunction(f, p1, p2, ...)` matches one or more parsers in succession,
128  collecting their results and passing them as rvalue reference arguments to
129  some function, returning its result.
130* `applyLambda([](&&x){}, p1, p2, ...)` is the same thing, but for lambdas
131  and other function objects.
132* `applyMem(mf, p1, p2, ...)` is the same thing, but invokes a member
133  function of the result of the first parser for updates in place.
134
135### Token Parsers
136Last, we have these basic parsers on which the actual grammar of the Fortran
137is built.  All of the following parsers consume characters acquired from
138`nextCh`.
139
140* `space` always succeeds after consuming any spaces
141* `spaceCheck` always succeeds after consuming any spaces, and can emit
142  a warning if there was no space in free form code before a character
143  that could continue a name or keyword
144* `digit` matches one cooked decimal digit (0-9)
145* `letter` matches one cooked letter (A-Z)
146* `"..."_tok` match the content of the string, skipping spaces before and
147  after.  Internal spaces are optional matches.  The `_tok` suffix is
148  optional when the parser appears before the combinator `>>` or after
149  the combinator `/`.
150* `"..."_sptok` is a string match in which the spaces are required in
151   free form source.
152* `"..."_id` is a string match for a complete identifier (not a prefix of
153   a longer identifier or keyword).
154* `parenthesized(p)` is shorthand for `"(" >> p / ")"`.
155* `bracketed(p)` is shorthand for `"[" >> p / "]"`.
156* `nonEmptyList(p)` matches a comma-separated list of one or more
157  instances of p.
158* `nonEmptyList(errorMessage, p)` is equivalent to
159  `withMessage(errorMessage, nonemptyList(p))`, which allows one to supply
160  a meaningful error message in the event of an empty list.
161* `optionalList(p)` is the same thing, but can be empty, and always succeeds.
162
163### Debugging Parser
164Last, a string literal `"..."_debug` denotes a parser that emits the string to
165`llvm::errs` and succeeds.  It is useful for tracing while debugging a parser but should
166obviously not be committed for production code.
167