template_parser

parser.hpp

//          Copyright plasma-effect 2017.
// Distributed under the Boost Software License, Version 1.0.
//    (See at http://www.boost.org/LICENSE_1_0.txt)

#pragma once
#include<vector>
#include<optional>
#include<variant>
#include<memory>
#include<string>
#include<string_view>
#include<functional>
#include<map>
#include<set>
#include<iostream>

namespace template_parser
{
	template<class Expr, class Recur>struct parsing_result;
	template<class Expr, class Recur>struct parser_inside;

	template<class Derived>struct parser_base;
	template<class Expr, class Recur>struct parser_base<parser_inside<Expr, Recur>>
	{
		typedef parsing_result<Expr, Recur> result_t;
		std::string_view const view;
		parser_base(parser_base const&) = delete;
		parser_base(parser_base&&) = delete;
		parser_base() = delete;
		parser_base& operator=(parser_base const&) = delete;
		parser_base& operator=(parser_base&&) = delete;


		parser_base(std::string_view v) :view(v)
		{

		}
		std::optional<result_t> parse(std::size_t index, bool phrase, std::set<char> const& space)
		{
			auto start = index;
			if (phrase)
			{
				for (; index < view.size(); ++index)
				{
					if (!space.count(view[index]))
					{
						break;
					}
				}
			}
			auto ret = static_cast<parser_inside<Expr, Recur>&>(*this).parse(view, index, phrase, space);
			if (ret)
			{
				ret->view = view.substr(start, ret->view.size() + index - start);
			}
			return ret;
		}
	};
	template<class Expr>struct parser;
	
	namespace type
	{
		struct string
		{
			std::string_view view;
		};
		struct range
		{
			char min;
			char max;
		};
		template<class Expr>struct repeat
		{
			Expr expr;
			std::size_t min;
			std::size_t max;
		};
		template<class Expr>struct ignore
		{
			Expr expr;
		};
		template<class Expr>struct cat
		{
			Expr expr;
			std::function<void(std::string_view, std::size_t)> message;
		};
		template<class Previous, class Current>struct sequence
		{
			Previous previous;
			Current current;
		};
		template<class Expr>struct optional
		{
			Expr expr;
		};
		template<class Previous, class Current>struct select
		{
			Previous previous;
			Current current;
		};
		template<class Prev0, class Prev1, class Current>struct select<select<Prev0, Prev1>, Current>
		{
			select<Prev0, Prev1> previous;
			Current current;
		};
		struct recursive
		{

		};
		template<class Derived, class Expr>struct value_instance
		{
			Expr expr;
			bool phrase_parse;
			value_instance(Expr e, bool phrase) :expr(e), phrase_parse(phrase)
			{

			}
			value_instance(const value_instance&) = default;
		};
		template<class Derived>struct value
		{
			bool phrase_parse = false;
			template<class Expr>auto operator()(Expr e)const
			{
				return value_instance<Derived, Expr>(e, phrase_parse);
			}
		};
		template<class Derived, class Expr>struct closed_value_instance
		{
			Expr expr;
			bool phrase_parse;
			closed_value_instance(Expr e, bool phrase) :expr(e), phrase_parse(phrase)
			{

			}
			closed_value_instance(const closed_value_instance&) = default;
		};
		template<class Derived>struct closed_value
		{
			bool phrase_parse = false;
			template<class Expr>auto operator()(Expr e)const
			{
				return closed_value_instance<Derived, Expr>(e, phrase_parse);
			}
		};

		template<class Previous, class Current>auto operator<<(Previous prev, Current curr)
			->sequence<Previous, Current>
		{
			return sequence<Previous, Current>{prev, curr};
		}
		template<class Previous, class Current>auto operator/(Previous prev, Current curr)
		{
			return select<Previous, Current>{prev, curr};
		}
		template<class Expr, class Func>auto operator%(Expr expr, Func func)
		{
			return type::cat<Expr>{expr, func};
		}
		template<class Expr>auto operator+(Expr expr)
		{
			return repeat<Expr>{expr, 1, std::numeric_limits<std::size_t>::max()};
		}
		template<class Expr>auto operator*(Expr expr)
		{
			return repeat<Expr>{expr, 0, std::numeric_limits<std::size_t>::max()};
		}
	}
	namespace detail
	{
		template<class T>void reset(parser<T>& p);
	}
	template<class Expr>auto parse(std::string_view view, Expr expr)
	{
		parser<Expr> p{ view ,expr };
		return static_cast<parser_base<parser_inside<Expr, Expr>>&>(p).parse(0, false, std::set<char>{' ', '\n', '\t'});
	}

	template<class Recur>struct parsing_result<type::string, Recur>
	{
		std::string_view view;
		std::string_view str;
	};
	template<class Recur>struct parser_inside<type::string, Recur> :parser_base<parser_inside<type::string, Recur>>
	{
		type::string string;
		typedef parsing_result<type::string, Recur> result_t;
		std::optional<result_t> parse(std::string_view view, std::size_t index, bool, std::set<char>const&)
		{
			if (string.view.size() + index <= view.size())
			{
				for (std::size_t i{}; i < string.view.size(); ++i)
				{
					if (view[i + index] != string.view[i])
					{
						goto end;
					}
				}
				return std::make_optional(result_t{ string.view,view.substr(index,string.view.size()) });
			}
		end:
			return std::nullopt;
		}
		parser_inside(std::string_view view, type::string expr, std::reference_wrapper<parser<Recur>>) :
			parser_base<parser_inside<type::string, Recur>>(view),
			string(expr)
		{

		}
	};
	
	template<class Recur>struct parsing_result<type::range, Recur>
	{
		std::string_view view;
		char c;
	};
	template<class Recur>struct parser_inside<type::range, Recur> :parser_base<parser_inside<type::range, Recur>>
	{
		type::range range;
		typedef parsing_result<type::range, Recur> result_t;
		std::optional<result_t> parse(std::string_view view, std::size_t index, bool, std::set<char>const&)
		{
			if (index != view.size() && view[index] >= range.min&&view[index] <= range.max)
			{
				return result_t{ view.substr(index,1),view[index] };
			}
			return std::nullopt;
		}
		parser_inside(std::string_view view, type::range expr, std::reference_wrapper<parser<Recur>>) :
			parser_base<parser_inside<type::range, Recur>>(view),
			range(expr)
		{

		}
	};
	
	template<class Expr, class Recur>struct parsing_result<type::repeat<Expr>, Recur>
	{
		std::string_view view;
		std::vector<parsing_result<Expr, Recur>> value;
	};
	template<class Expr, class Recur>struct parser_inside<type::repeat<Expr>, Recur> :parser_base<parser_inside<type::repeat<Expr>, Recur>>
	{
		std::size_t min;
		std::size_t max;
		parser_inside<Expr, Recur> inside;
		typedef parsing_result<type::repeat<Expr> , Recur> result_t;
		std::optional<result_t> parse(std::string_view view, std::size_t index, bool phrase, std::set<char>const& space)
		{
			std::vector<parsing_result<Expr, Recur>> vec;
			auto start = index;
			while (auto ret = static_cast<parser_base<parser_inside<Expr, Recur>>&>(inside).parse(index, phrase, space))
			{
				index += ret->view.size();
				vec.emplace_back(*ret);
				if (vec.size() == max)
				{
					break;
				}
			}
			if (vec.size() < min)
			{
				return std::nullopt;
			}
			return result_t{ view.substr(start,index - start),std::move(vec) };
		}

		parser_inside(std::string_view view,type::repeat<Expr> expr,std::reference_wrapper<parser<Recur>> recur):
			parser_base<parser_inside<type::repeat<Expr>, Recur>>(view),
			min(expr.min),
			max(expr.max),
			inside(view, expr.expr, recur)
		{

		}
	};
	
	template<class Expr, class Recur>struct parsing_result<type::ignore<Expr>, Recur>
	{
		std::string_view view;
	};
	template<class Expr, class Recur>struct parser_inside<type::ignore<Expr>, Recur> :parser_base<parser_inside<type::ignore<Expr>, Recur>>
	{
		parser_inside<Expr, Recur> inside;
		typedef parsing_result<type::ignore<Expr>, Recur> result_t;
		std::optional<result_t> parse(std::string_view, std::size_t index, bool phrase, std::set<char>const& space)
		{
			if (auto ret = static_cast<parser_base<parser_inside<Expr, Recur>>&>(inside).parse(index, phrase, space))
			{
				return result_t{ ret->view };
			}
			return std::nullopt;
		}
		parser_inside(std::string_view view,type::ignore<Expr> expr,std::reference_wrapper<parser<Recur>> recur):
			parser_base<parser_inside<type::ignore<Expr>, Recur>>(view),
			inside(view, expr.expr, recur)
		{

		}
	};
	
	template<class Expr, class Recur>struct parsing_result<type::cat<Expr>, Recur> :parsing_result<Expr, Recur>
	{
		parsing_result(parsing_result<Expr, Recur> arg) :parsing_result<Expr, Recur>{ arg }
		{

		}
	};
	template<class Expr, class Recur>struct parser_inside<type::cat<Expr>, Recur> :parser_base<parser_inside<type::cat<Expr>, Recur>>
	{
		std::function<void(std::string_view, std::size_t)> message;
		parser_inside<Expr, Recur> inside;
		std::reference_wrapper<parser<Recur>> rec;
		typedef parsing_result<type::cat<Expr>, Recur> result_t;
		std::optional<result_t> parse(std::string_view view, std::size_t index, bool phrase, std::set<char>const& space)
		{
			detail::reset(rec.get());
			if (auto ret = static_cast<parser_base<parser_inside<Expr, Recur>>&>(inside).parse(index, phrase, space))
			{
				return *ret;
			}
			message(view, index);
			throw std::invalid_argument("parse error!!");
		}
		parser_inside(std::string_view view, type::cat<Expr> expr, std::reference_wrapper<parser<Recur>> recur) :
			parser_base<parser_inside<type::cat<Expr>, Recur>>(view),
			message(expr.message),
			inside(view, expr.expr, recur),
			rec(recur)
		{

		}
	};
	
	template<class Previous, class Current, class Recur>struct parsing_result<type::sequence<Previous, Current>, Recur>
	{
		std::string_view view;
		std::tuple<
			parsing_result<Previous, Recur>,
			parsing_result<Current, Recur>> result;
	};
	template<class Previous, class Current, class Recur>struct parser_inside<type::sequence<Previous, Current>, Recur> :parser_base<parser_inside<type::sequence<Previous, Current>, Recur>>
	{
		parser_inside<Previous, Recur> previous;
		parser_inside<Current, Recur> current;
		typedef parsing_result<type::sequence<Previous, Current>, Recur> result_t;

		std::optional<result_t> parse(std::string_view view, std::size_t index, bool phrase, std::set<char>const& space)
		{
			auto start = index;
			if (auto p = static_cast<parser_base<parser_inside<Previous, Recur>>&>(previous).parse(index, phrase, space))
			{
				index += p->view.size();
				if (auto c = static_cast<parser_base<parser_inside<Current, Recur>>&>(current).parse(index, phrase, space))
				{
					return result_t{ view.substr(start,index - start + c->view.size()), std::make_tuple(*p,*c) };
				}
			}
			return std::nullopt;
		}
		parser_inside(std::string_view view, type::sequence<Previous, Current> expr, std::reference_wrapper<parser<Recur>> recur) :
			parser_base<parser_inside<type::sequence<Previous, Current>, Recur>>(view),
			previous(view, expr.previous, recur),
			current(view, expr.current, recur)
		{

		}
	};
	
	template<class Prev0, class Prev1, class Current, class Recur>struct parsing_result<type::sequence<type::sequence<Prev0, Prev1>, Current>, Recur>
	{
		std::string_view view;
		decltype(std::tuple_cat(
			std::declval<parsing_result<type::sequence<Prev0,Prev1>,Recur>>().result,
			std::declval<std::tuple<parsing_result<Current, Recur>>>())) result;
	};
	template<class Prev0, class Prev1, class Current, class Recur>struct parser_inside<type::sequence<type::sequence<Prev0, Prev1>, Current>, Recur> :parser_base<parser_inside<type::sequence<type::sequence<Prev0, Prev1>, Current>, Recur>>
	{
		typedef type::sequence<Prev0, Prev1> Previous;
		parser_inside<Previous, Recur> previous;
		parser_inside<Current, Recur> current;
		typedef parsing_result<type::sequence<Previous, Current>, Recur> result_t;
		std::optional<result_t> parse(std::string_view view, std::size_t index, bool phrase, std::set<char>const& space)
		{
			auto start = index;
			if (auto p = static_cast<parser_base<parser_inside<Previous, Recur>>&>(previous).parse(index, phrase, space))
			{
				index += p->view.size();
				if (auto c = static_cast<parser_base<parser_inside<Current, Recur>>&>(current).parse(index, phrase, space))
				{
					return result_t{ view.substr(start,index - start + c->view.size()), std::tuple_cat(p->result,std::make_tuple(*c)) };
				}
			}
			return std::nullopt;
		}
		parser_inside(std::string_view view, type::sequence<type::sequence<Prev0, Prev1>, Current> expr, std::reference_wrapper<parser<Recur>> recur) :
			parser_base<parser_inside<type::sequence<type::sequence<Prev0, Prev1>, Current>, Recur>>(view),
			previous(view, expr.previous, recur),
			current(view, expr.current, recur)
		{

		}
	};
	
	template<class Expr, class Recur>struct parsing_result<type::optional<Expr>, Recur>:std::optional<parsing_result<Expr, Recur>>
	{
		std::string_view view;
		parsing_result(std::string_view v, std::optional<parsing_result<Expr, Recur>> opt) :
			std::optional<parsing_result<Expr, Recur>>(opt),
			view(v)
		{

		}

	};
	template<class Expr, class Recur>struct parser_inside<type::optional<Expr>, Recur> : parser_base<parser_inside<type::optional<Expr>, Recur>>
	{
		parser_inside<Expr, Recur> inside;
		typedef parsing_result<type::optional<Expr>, Recur> result_t;
		std::optional<result_t> parse(std::string_view view, std::size_t index, bool phrase, std::set<char>const& space)
		{
			if (auto ret = static_cast<parser_base<parser_inside<Expr, Recur>>&>(inside).parse(index, phrase, space))
			{
				return result_t(ret->view, ret);
			}
			else
			{
				return result_t(view.substr(index, 0), std::nullopt);
			}
		}

		parser_inside(std::string_view view, type::optional<Expr> expr, std::reference_wrapper<parser<Recur>> recur) :
			parser_base<parser_inside<type::optional<Expr>, Recur>>(view),
			inside(view, expr.expr, recur)
		{

		}
	};
	
	template<class Previous, class Current, class Recur>struct parsing_result<type::select<Previous, Current>, Recur>
	{
		static constexpr int size = 2;
		std::string_view view;
		std::variant<
			std::pair<std::integral_constant<int, 0>, parsing_result<Previous,Recur>>,
			std::pair<std::integral_constant<int, 1>, parsing_result<Current, Recur>>> value;
		parsing_result(parsing_result<Previous, Recur> p, std::integral_constant<int, 0> v) :
			view(p.view), value(std::make_pair(v, p))
		{

		}
		parsing_result(parsing_result<Current, Recur> p, std::integral_constant<int, 1> v) :
			view(p.view), value(std::make_pair(v, p))
		{

		}

		std::optional<parsing_result<Previous, Recur>> get(std::integral_constant<int, 0>)const
		{
			if (value.index() == 0)
			{
				return std::get<0>(value).second;
			}
			else
			{
				return std::nullopt;
			}
		}
		std::optional<parsing_result<Current, Recur>> get(std::integral_constant<int, 1>)const
		{
			if (value.index() == 1)
			{
				return std::get<1>(value).second;
			}
			else
			{
				return std::nullopt;
			}
		}
		template<int I>auto get()const
		{
			return get(std::integral_constant<int, I>());
		}
	};
	template<class Previous, class Current, class Recur>struct parser_inside<type::select<Previous, Current>, Recur> :parser_base<parser_inside<type::select<Previous, Current>, Recur>>
	{
		parser_inside<Previous, Recur> previous;
		parser_inside<Current, Recur> current;
		typedef parsing_result<type::select<Previous, Current>, Recur> result_t;
		std::optional<result_t> parse(std::string_view, std::size_t index, bool phrase, std::set<char>const& space)
		{
			if (auto p = static_cast<parser_base<parser_inside<Previous, Recur>>&>(previous).parse(index, phrase, space))
			{
				return result_t(*p, std::integral_constant<int, 0>());
			}
			else if (auto c = static_cast<parser_base<parser_inside<Current, Recur>>&>(current).parse(index, phrase, space))
			{
				return result_t(*c, std::integral_constant<int, 1>());
			}
			return std::nullopt;
		}
		parser_inside(std::string_view view, type::select<Previous, Current> expr, std::reference_wrapper<parser<Recur>> recur) :
			parser_base<parser_inside<type::select<Previous, Current>, Recur>>(view),
			previous(view, expr.previous, recur),
			current(view, expr.current, recur)
		{

		}
	};
	
	template<class Prev0, class Prev1, class Current, class Recur>struct parsing_result<type::select<type::select<Prev0, Prev1>, Current>, Recur>
	{
		typedef type::select<Prev0, Prev1> Previous;
		static constexpr auto size = parsing_result<Previous, Recur>::size + 1;
		std::string_view view;
		std::variant<
			parsing_result<Previous, Recur>,
			parsing_result<Current, Recur>> value;
		parsing_result(parsing_result<Previous, Recur> p, ...) :view(p.view), value(p)
		{

		}
		parsing_result(parsing_result<Current, Recur> p, ...) :view(p.view), value(p)
		{

		}

		template<int I>auto get(std::integral_constant<int, I> v, std::enable_if_t<(I < size - 1)>* = nullptr)const
			->decltype(std::get<0>(value).get(v))
		{
			if (value.index() == 0)
			{
				return std::get<0>(value).get(v);
			}
			else
			{
				return std::nullopt;
			}
		}
		std::optional<parsing_result<Current, Recur>> get(std::integral_constant<int, size - 1>)const
		{
			if (value.index() == 1)
			{
				return std::get<1>(value);
			}
			else
			{
				return std::nullopt;
			}
		}
		template<int I>auto get()const
		{
			return get(std::integral_constant<int, I>());
		}
	};
	template<class Prev0,class Prev1, class Current, class Recur>struct parser_inside<type::select<type::select<Prev0,Prev1>, Current>, Recur> :parser_base<parser_inside<type::select<type::select<Prev0, Prev1>, Current>, Recur>>
	{
		parser_inside<type::select<Prev0, Prev1>, Recur> previous;
		parser_inside<Current, Recur> current;
		typedef parsing_result<type::select<type::select<Prev0, Prev1>, Current>, Recur> result_t;
		std::optional<result_t> parse(std::string_view, std::size_t index, bool phrase, std::set<char>const& space)
		{
			if (auto p = static_cast<parser_base<parser_inside<type::select<Prev0, Prev1>, Recur>>&>(previous).parse(index, phrase, space))
			{
				return result_t(*p, std::integral_constant<int, 0>());
			}
			else if (auto c = static_cast<parser_base<parser_inside<Current, Recur>>&>(current).parse(index, phrase, space))
			{
				return result_t(*c, std::integral_constant<int, 1>());
			}
			return std::nullopt;
		}
		parser_inside(std::string_view view, type::select<type::select<Prev0, Prev1>, Current> expr, std::reference_wrapper<parser<Recur>> recur) :
			parser_base<parser_inside<type::select<type::select<Prev0, Prev1>, Current>, Recur>>(view),
			previous(view, expr.previous, recur),
			current(view, expr.current, recur)
		{

		}
	};

	template<class Recur>struct parsing_result<type::recursive, Recur>
	{
		std::string_view view;
		std::shared_ptr<parsing_result<Recur, Recur>> value;
		parsing_result(std::shared_ptr<parsing_result<Recur, Recur>> arg) :
			view(arg->view),
			value(std::move(arg))
		{
		}
		auto const& operator*()const
		{
			return *value;
		}
	};
	template<class Recur>struct parser_inside<type::recursive, Recur> :parser_base<parser_inside<type::recursive, Recur>>
	{
		std::reference_wrapper<parser<Recur>> rec;
		typedef parsing_result<type::recursive, Recur> result_t;
		std::optional<result_t> parse(std::string_view, std::size_t index, bool, std::set<char>const& space)
		{
			if (auto ret = rec.get().parse(index, false, space))
			{
				return result_t{ std::make_shared<parsing_result<Recur,Recur>>(*ret) };
			}
			return std::nullopt;
		}
		parser_inside(std::string_view view, type::recursive, std::reference_wrapper<parser<Recur>> recur) :
			parser_base<parser_inside<type::recursive, Recur>>(view),
			rec(recur)
		{

		}
	};

	template<class Derived, class Expr, class Recur>struct parsing_result<type::value_instance<Derived, Expr>, Recur> :parsing_result<Expr, Recur>
	{
		Derived derived;
		parsing_result(parsing_result<Expr, Recur> res) :
			parsing_result<Expr, Recur>(res),
			derived()
		{

		}
	};
	template<class Derived, class Expr, class Recur>struct parsing_result<type::closed_value_instance<Derived, Expr>, Recur> :parsing_result<Expr, Expr>
	{
		Derived derived;
		parsing_result(parsing_result<Expr, Expr> res) :
			parsing_result<Expr, Expr>(res),
			derived()
		{

		}
	};
	template<class Derived, class Expr, class Recur>struct parser_inside<type::value_instance<Derived, Expr>, Recur> :parser_base<parser_inside<type::value_instance<Derived, Expr>, Recur>>
	{
		parser_inside<Expr, Recur> inside;
		bool phrase_parse;
		typedef parsing_result<type::value_instance<Derived, Expr>, Recur> result_t;
		std::optional<result_t> parse(std::string_view, std::size_t index, bool, std::set<char>const& space)
		{
			if (auto ret = static_cast<parser_base<parser_inside<Expr, Recur>>&>(inside).parse(index, phrase_parse, space))
			{
				return result_t(*ret);
			}
			return std::nullopt;
		}
		parser_inside(std::string_view view, type::value_instance<Derived, Expr> val, std::reference_wrapper<parser<Recur>> recur) :
			parser_base<parser_inside<type::value_instance<Derived, Expr>, Recur>>(view),
			inside(view, val.expr, recur),
			phrase_parse(val.phrase_parse)
		{

		}
	};
	template<class Derived, class Expr, class Recur>struct parser_inside<type::closed_value_instance<Derived, Expr>, Recur> :parser_base<parser_inside<type::closed_value_instance<Derived, Expr>, Recur>>
	{
		parser<Expr> inside;
		bool phrase_parse;
		typedef parsing_result<type::closed_value_instance<Derived, Expr>, Recur> result_t;
		std::optional<result_t> parse(std::string_view, std::size_t index, bool, std::set<char>const& space)
		{
			if (auto ret = inside.parse(index, phrase_parse, space))
			{
				return result_t(*ret);
			}
			return std::nullopt;
		}
		parser_inside(std::string_view view, type::closed_value_instance<Derived, Expr> val, std::reference_wrapper<parser<Recur>>) :
			parser_base<parser_inside<type::closed_value_instance<Derived, Expr>, Recur>>(view),
			inside(view, val.expr),
			phrase_parse(val.phrase_parse)
		{

		}
	};

	template<class Expr>struct parser :parser_inside<Expr, Expr>
	{
		std::map<std::size_t, std::optional<parsing_result<Expr, Expr>>> memo;
		parser(std::string_view view, Expr expr) :parser_inside<Expr, Expr>(view, expr, std::ref(*this)), memo{}
		{

		}
		std::optional<parsing_result<Expr, Expr>> parse(std::size_t index, bool phrase, std::set<char>const& space)
		{
			if (memo.count(index))
			{
				return memo[index];
			}
			return memo.emplace(index, static_cast<parser_base<parser_inside<Expr, Expr>>&>(*this).parse(index, phrase, space)).first->second;
		}
		void reset()
		{
			memo.clear();
		}
	};

	type::range range(char min, char max)
	{
		return type::range{ min,max };
	}
	type::string operator""_v(char const* str, std::size_t)
	{
		return type::string{ str };
	}
	template<class Expr>auto optional(Expr expr)
	{
		return type::optional<Expr>{expr};
	}
	template<class Expr>auto ignore(Expr expr)
	{
		return type::ignore<Expr>{expr};
	}
	constexpr type::recursive recursive = {};
	template<class T, class U>using result_inside = parsing_result<std::remove_const_t<std::remove_reference_t<T>>, std::remove_const_t<std::remove_reference_t<U>>>;
	namespace detail
	{
		template<class T>void reset(parser<T>& p)
		{
			p.reset();
		}
	}
}

test.cpp

// Copyright plasma-effect 2017
// Distributed under the MIT license
// see at https://opensource.org/licenses/mit-license.php

#include"parser.hpp"
#include<iostream>
#include<sstream>

[[noreturn]]void error(std::string_view view, std::size_t i)
{
	std::stringstream ss;
	ss << "expression error:" << std::endl;
	ss << view << std::endl;
	for (std::size_t x{}; x < i; ++x)
	{
		ss << " ";
	}
	ss << "^";
	throw std::invalid_argument(ss.str());
}

using namespace template_parser;
struct value_t {};
constexpr type::value<value_t> vali;
const auto value = vali(ignore(+range('0', '9')));

struct atomic_t {};
constexpr type::value<atomic_t> atom{ true };
const auto atomic = atom(value / ("("_v << recursive << ")"_v));

struct mul_t {};
constexpr type::value<mul_t> muli{ true };
const auto mul = muli(atomic << *("*"_v << (atomic%error)));

struct expr_t {};
constexpr type::value<expr_t> expri{ true };
const auto expr = expri(mul << *("+"_v << (mul%error)));

template<class T>using inside_t = result_inside<T, decltype(expr)>;

void space(int v)
{
	for (int i{}; i < v; ++i)
	{
		std::cout << "  ";
	}
}

void print(inside_t<decltype(value)> const& result, int rec);
void print(inside_t<decltype(atomic)> const& result, int rec);
void print(inside_t<decltype(mul)> const& result, int rec);
void print(inside_t<decltype(expr)> const& result, int rec);

void print(inside_t<decltype(expr)>const& result, int rec)
{
	auto const& vec = std::get<1>(result.result).value;
	if (vec.size() != 0)
	{
		space(rec);
		std::cout << result.view << std::endl;
		space(rec + 1);
		std::cout << "+" << std::endl;
		print(std::get<0>(result.result), rec + 1);
		for (auto const& v : vec)
		{
			print(std::get<1>(v.result), rec + 1);
		}
	}
	else
	{
		print(std::get<0>(result.result), rec);
	}
}
void print(inside_t<decltype(mul)>const& result, int rec)
{
	auto const& vec = std::get<1>(result.result).value;
	if (vec.size() != 0)
	{
		space(rec);
		std::cout << result.view << std::endl;
		space(rec + 1);
		std::cout << "*" << std::endl;
		print(std::get<0>(result.result), rec + 1);
		for (auto const& v : vec)
		{
			print(std::get<1>(v.result), rec + 1);
		}
	}
	else
	{
		print(std::get<0>(result.result), rec);
	}
}
void print(inside_t<decltype(atomic)> const& result, int rec)
{
	if (auto ret = result.get<0>())
	{
		print(*ret, rec);
	}
	else if (auto ret = result.get<1>())
	{
		print(*std::get<1>(ret->result), rec);
	}
}
void print(inside_t<decltype(value)> const& result, int rec)
{
	space(rec);
	std::cout << result.view << std::endl;
}

int main()
{
	std::string str;

	while (std::getline(std::cin, str))
	{
		if (str == "")
		{
			break;
		}
		try
		{
			if (auto ret = parse(str, expr))
			{
				print(*ret, 0);
			}
			else
			{
				std::cout << "NG" << std::endl;
			}
			
		}
		catch (std::exception exp)
		{
			std::cout << exp.what() << std::endl;
		}
	}
}