/**
\defgroup fcpptparse fcppt.parse
\ingroup fcpptmain
\brief Library for parsers

<b>Link to <code>fcppt_parse_interface</code>.</b>

<table id="toc">
<tr>
<td>

<ul>
	<li>\ref fcpptparse_introduction</li>
	<li>\ref fcpptparse_skipping</li>
	<li>\ref fcpptparse_recursive</li>
	<li>\ref fcpptparse_fatal_errors</li>
	<li>\ref fcpptparse_overview</li>
	<li>\ref fcpptparse_definition</li>
</ul>

</td>
</tr>
</table>

\section fcpptparse_introduction Introduction

A parser gets a string as input and if it belongs to a certain language it transforms this string into a specific output.
Parsers are built up from basic parsers and combinating parsers.
The most basic parsers are:
<ul>
<li>#fcppt::parse::epsilon, which recognizes the empty string and returns nothing.</li>
<li>#fcppt::parse::char_, which recognizes any single character and returns it.</li>
<li>#fcppt::parse::literal, which recognizes a specific single character and returns nothing.</li>
</ul>
From this, more complicated parsers can be built.
The combinating parsers are:
<ul>
<li>#fcppt::parse::alternative, which gets two parsers \em L and \em R. It first tries L and if that fails it tries R.
Its result type is a variant of L's and R's result types.</li>
<li>#fcppt::parse::repetition, which gets a single parser \em P and tries it until it fails.
Its result type is a vector of P's result type.</li>
<li>#fcppt::parse::sequence, which gets two parsers \em L and \em R. It first tries L and if that succeeds also R.
Its result type is a tuple of L's and R's result types.</li>
</ul>

Let us consider the following example.
We want to parse numbers of the form <code>{0, ..., 9}*</code>,
where we allow multiple leading zeroes for simplicity.
Each word that belongs to this language should produce a word over the alphabet <code>{0,...,9}</code>.
To encode this in C++, we start with an enum of the form
\snippet parse/main.cpp digit
Next, we create a function that given <code>char c</code> and <code>digit d</code>,
it produces a parser that returns <code>d</code> if and only if it gets <code>c</code> as input:
\snippet parse/main.cpp make_digit
We can use this function to create a parser that recognizes any digit:
\snippet parse/main.cpp parser_digit
Here, the <code>operator|</code> constructs a #fcppt::parse::alternative out of its two arguments.
The result type of <code>p09</code> is still <code>digit</code> because
<code>variant<digit, ..., digit></code> is simplified to <code>digit</code>.
To recognize an arbitrary string of digits, we define the following parser:
\snippet parse/main.cpp parser_digit_string
The <code>operator*</code> creates an #fcppt::parse::repetition out of its argument.
Its result type is <code>vector<digit></code>.
The #fcppt::parse::parse_string function takes a parser <code>P</code> and a string and returns an #fcppt::either::object of #fcppt::parse::parse_string_error and <code>P</code>'s result type.
We can then inspect this either by using #fcppt::either::match.
\snippet parse/main.cpp parser_example

\section fcpptparse_skipping Whitespace Skipping

A lot of languages are not whitespace-sensitive, which means that whitespaces can be added in a lot of places.
For example, in JSON, we can write <code>[1,2]</code> or <code>[1, 2]</code>, which both result in an array with elements 1 and 2.
Here, we use the notation of a \em Skipper to achieve this behaviour.
A skipper is simpler than a parser in the sense that it never produces results, it only consumes input.
Skippers are run in very specific places:
<ul>
<li>#fcppt::parse::phrase_parse (or the string or stream variant of this function) runs the skipper at the start.</li>
<li><code>fcppt::parse::sequence{l,r}</code> runs the skipper after running <code>l</code> and before running <code>r</code>.</li>
<li><code>fcppt::parse::repetition{p}</code> runs the skipper after each successful parse of <code>p</code>.</li>
</ul>
Whitespace skipping can be disabled using #fcppt::parse::lexeme.
Consider the following example:
We declare a parser that parses two unsigned ints in succession.
\snippet parse/skip.cpp parse_uint
Without whitespace skipping, this parser can never succeed, since the first uint parser will always consume as many digits as it can, leaving nothing for the second uint parser.
In the following example, the first uint parser reads <code>10</code>, stops at the space character, and then the second parser fails.
\snippet parse/skip.cpp parse_noskip
However, if we use whitespace skipping, then the first uint parser reads <code>10</code>, stops at the space character, then the sequence (<code>>></code>) parser runs the skipper,
which consumes the space character, and then the second uint parser reads <code>20</code>.
The skipper we use here consumes as many space characters as possible.
\snippet parse/skip.cpp parse_skip
Note that the implementation of #fcppt::parse::parse runs #fcppt::parse::phrase_parse internally, using the skipper #fcppt::parse::skipper::epsilon, which does nothing.

\section fcpptparse_recursive Recursive Parsers

Consider a language where we want to parse lists of the form <code>{E_1, ..., E_n}</code>,
where <code>E_1, ..., E_n</code> are of the form <code>name = L</code> (where we allow names to consist of the characters a, b and c) and <code>L</code> is again a list.
First, we need to create a C++ data type that represents such a list, which we declare as follows:
\snippet parse/grammar.cpp list_decl
We would like to create a parser for lists and a parser for entries.
The parser for lists needs the parser for entries in its definition and vice versa.
To deal with (mutually) recursive definitions, we do the following:
<ul>
<li>All parsers that mutually refer to each other must be elements of a class.
In the constructor of the class, they can then use each other as references.
This is similar to declaring nonterminals and their productions in a context-free grammar.
</li>
<li>The types of the parsers should not depend on their definitions, which would create an inifinitely large type.
Therefore, we have to hide their exact types using #fcppt::parse::base.
This in turn means that we have to commit to a specific character type and also a specific skipper type.
</li>
</ul>
In our example, we declare the class as follows:
\snippet parse/grammar.cpp grammar_decl
First, #fcppt::parse::grammar is a helper class that the actual grammars derive from.
It selects the result type produced by the start rule, the character type of the input and the skipper type that is being used.
Here, we use #fcppt::parse::skipper::epsilon, which implies that no skipping is done.
To actually implement the grammar, we have to define its constructor.
Here, we have to pass a reference to one of our parsers to the base class, which defines the start nonterminal of the grammar.
We also have to pass an implementation of the skipper type, which in this case simply is the epsilon skipper.
\snippet parse/grammar.cpp grammar_impl
To use the grammar for parsing, we call #fcppt::parse::grammar_parse_string.
This internally uses #fcppt::parse::phrase_parse_string, passing the start symbol and the skipper of the grammar.
\snippet parse/grammar.cpp parse

\section fcpptparse_fatal_errors Fatal Errors

The parser implementation makes use of so-called \em backtracking, which means that certain parsers are expected to fail,
and if they do, the input stream is set to a previous position and another parser is tried instead.
For example, the alternative parser <code>a | b</code> first tries <code>a</code> and then <code>b</code>.
Suppose that <code>a</code> fails on the current input.
Internally, the parser <code>a | b</code> first saves the current position <code>p</code>, runs <code>a</code> and after it fails,
resets the position to <code>p</code> and runs <code>b</code>.
However, depending on why <code>a</code> fails, we know that <code>b</code> cannot succeed.
Consider the following example:
\snippet parse/fatal.cpp parsers1
The parser <code>a</code> fails if the input is <code>{]</code>, but still the parser <code>b</code> is tried
even though it cannot succeed.
This is fine in most cases, but in some this may lead to excessive backtracking.
In addition, the parser <code>a | b</code> will produce an error message of the form
<blockquote>
&nbsp;&nbsp; At 1, J 1:2: Expected }, got ].<br>
or<br>
&nbsp;&nbsp; At 0, J 1:1: Expected [, got {.
</blockquote>
Since we know that <code>b</code> cannot succeed if <code>a</code> fails after reading <code>{</code>,
we can make the part after <code>{</code> fatal.
\snippet parse/fatal.cpp parsers2
Then the parser <code>a | b</code> does not try <code>b</code>
on input <code>{]</code>. Instead, it aborts immediately, and produces an error message of the form
<blockquote>
At 1, J 1:2: Expected }, got ].
</blockquote>
\warning Consider fatal errors as an optimization both to parsing and to error messages.
Be careful not to place fatal errors in the wrong place.
For example, if we made the whole parser <code>a</code> fatal, then the parser <code>b</code> would never be tried!
Using too many fatal errors can make parsers really hard to understand.

\section fcpptparse_overview Parser and Skipper Overview

\subsection fcpptparse_overview_parsers Parsers

The following tables gives a quick overview over all available parsers.
In the type column, we write that a parser P has type <code>(T_1,...,T_n) -> U</code>,
which means that if P is constructed from parsers that produce <code>T_1, ..., T_n</code>,
then P produces U.

<table>
<tr>
<th>
Parser
</th>
<th>
Type
</th>
<th>
Description
</th>
</tr>

<tr>
<td>
#fcppt::parse::alternative
</td>
<td>
<code>(L,R) -> fcppt::parse::alternative_result<L,R></code>
</td>
<td>
Returns the result of the first matching parser.
</td>
</tr>

<tr>
<td>
#fcppt::parse::as_struct
</td>
<td>
<code>fcppt::tuple::object<T_1,...,T_n> -> struct { T_1 t_1; ... ; T_n t_n }</code>
</td>
<td>
Converts a tuple to a struct.
</td>
</tr>

<tr>
<td>
#fcppt::parse::basic_char, #fcppt::parse::char_
</td>
<td>
<code>Char</code>
</td>
<td>
Parses any character.
</td>
</tr>

<tr>
<td>
#fcppt::parse::basic_char_set, #fcppt::parse::char_set
</td>
<td>
<code>Char</code>
</td>
<td>
Parses a set of characters.
</td>
</tr>

<tr>
<td>
#fcppt::parse::basic_literal, #fcppt::parse::literal
</td>
<td>
<code>fcppt::unit</code>
</td>
<td>
Parses a specific character.
</td>
</tr>

<tr>
<td>
#fcppt::parse::basic_string, #fcppt::parse::string
</td>
<td>
<code>fcppt::unit</code>
</td>
<td>
Parses a specific string.
</td>
</tr>

<tr>
<td>
#fcppt::parse::complement
</td>
<td>
<code>fcppt::unit -> fcppt::unit</code>
</td>
<td>
Complements a #fcppt::parse::basic_char_set parser.
</td>
</tr>

<tr>
<td>
#fcppt::parse::construct
</td>
<td>
<code>T -> U</code>
</td>
<td>
Constructs <code>U</code> from <code>T</code>.
</td>
</tr>

<tr>
<td>
#fcppt::parse::convert
</td>
<td>
<code>T -> U</code>
</td>
<td>
Converts <code>T</code> to <code>U</code> using a function.
</td>
</tr>

<tr>
<td>
#fcppt::parse::convert_const
</td>
<td>
<code>fcppt::unit -> U</code>
</td>
<td>
Converts to <code>U</code>.
</td>
</tr>

<tr>
<td>
#fcppt::parse::convert_if
</td>
<td>
<code>T -> U</code>
</td>
<td>
Converts <code>T</code> to <code>U</code> using a function. Can fail.
</td>
</tr>

<tr>
<td>
#fcppt::parse::epsilon
</td>
<td>
<code>fcppt::unit</code>
</td>
<td>
Parses the empty string.
</td>
</tr>

<tr>
<td>
#fcppt::parse::exclude
</td>
<td>
<code>(T,fcppt::unit) -> T</code>
</td>
<td>
Matches only if another parser fails.
</td>
</tr>

<tr>
<td>
#fcppt::parse::fail
</td>
<td>
<code>fcppt::unit</code>
</td>
<td>
Always fails.
</td>
</tr>

<tr>
<td>
#fcppt::parse::float_
</td>
<td>
<code>Float</code>
</td>
<td>
Parses floats.
</td>
</tr>

<tr>
<td>
#fcppt::parse::ignore
</td>
<td>
<code>T -> fcppt::unit</code>
</td>
<td>
Ignores a result.
</td>
</tr>

<tr>
<td>
#fcppt::parse::int_
</td>
<td>
<code>Signed Int</code>
</td>
<td>
Parses signed integers.
</td>
</tr>

<tr>
<td>
#fcppt::parse::lexeme
</td>
<td>
<code>T -> T</code>
</td>
<td>
Disables skipping.
</td>
</tr>

<tr>
<td>
#fcppt::parse::list
</td>
<td>
<code>(fcppt::unit, T, fcppt::unit, fcppt::unit) -> std::vector<T></code>
</td>
<td>
Parses a list of delimited values with opening and closing parentheses.
</td>
</tr>

<tr>
<td>
#fcppt::parse::named
</td>
<td>
<code>T -> T</code>
</td>
<td>
Gives a parser a name, improving error messages.
</td>
</tr>

<tr>
<td>
#fcppt::parse::not_
</td>
<td>
<code>fcppt::unit -> fcppt::unit</code>
</td>
<td>
Reverses a parser.
</td>
</tr>

<tr>
<td>
#fcppt::parse::optional
</td>
<td>
<code>T -> fcppt::optional::object<T></code>
</td>
<td>
Creates a parser that may fail.
</td>
</tr>

<tr>
<td>
#fcppt::parse::recursive
</td>
<td>
<code>T -> fcppt::recursive<T></code>
</td>
<td>
Wraps a type in #fcppt::recursive.
</td>
</tr>

<tr>
<td>
#fcppt::parse::repetition
</td>
<td>
<code>T -> fcppt::parse::repetition_result<T></code>
</td>
<td>
Repeats a parser as long as possible.
</td>
</tr>

<tr>
<td>
#fcppt::parse::repetition_plus
</td>
<td>
<code>T -> fcppt::parse::repetition_result<T></code>
</td>
<td>
Repeats a parser as long as possible.
Only accepts nonempty results.
</td>
</tr>

<tr>
<td>
#fcppt::parse::separator
</td>
<td>
<code>(T,fcppt::unit) -> std::vector<T></code>
</td>
<td>
Parses a list of delimited values.
</td>
</tr>

<tr>
<td>
#fcppt::parse::sequence
</td>
<td>
<code>(L,R) -> fcppt::parse::sequence_result<L,R></code>
</td>
<td>
Uses two parsers in succession.
</td>
</tr>

<tr>
<td>
#fcppt::parse::uint
</td>
<td>
<code>Unsigned Int</code>
</td>
<td>
Parses unsigned integers.
</td>
</tr>

</table>

\subsection fcpptparse_overview_skippers Skippers

The following table shows a list of available skippers.
<table>
<tr>
<th>
Skipper
</th>
<th>
Description
</th>
</tr>

<tr>
<td>
#fcppt::parse::skipper::basic_char_set, #fcppt::parse::skipper::char_set
</td>
<td>
Skips a set of characters.
</td>
</tr>

<tr>
<td>
#fcppt::parse::skipper::basic_literal, #fcppt::parse::skipper::literal
</td>
<td>
Skips a specific character.
</td>
</tr>

<tr>
<td>
#fcppt::parse::skipper::epsilon
</td>
<td>
Skips nothing.
</td>
</tr>

<tr>
<td>
#fcppt::parse::skipper::repetition
</td>
<td>
Repeats a skipper as long as possible.
</td>
</tr>

<tr>
<td>
#fcppt::parse::skipper::sequence
</td>
<td>
Runs two skippers in succession.
</td>
</tr>

</table>

\section fcpptparse_definition Parser definition

A parser is an object with the following properties:

<ul>
<li>
It inherits from #fcppt::parse::tag.
</li>
<li>
It has a typedef <code>result_type</code>.
</li>
<li>
It has a member function
\code
template<typename Ch, typename Skipper>
fcppt::parse::result<Ch, result_type>
parse(fcppt::reference<fcppt::parse::basic_stream<Ch>>, Skipper const &) const
\endcode
</li>
</ul>

A skipper is an object with the following properties:
<ul>
<li>
It inherits from #fcppt::parse::skipper::tag.
</li>
<li>
It has a member function
\code
template <typename Ch>
fcppt::parse::skipper::result<Ch>
skip(fcppt::reference<fcppt::parse::basic_stream<Ch>>) const;
\endcode
</li>
</ul>
*/

namespace fcppt
{
/// Library for parsers
namespace parse{}
}
