Skip to content

Instantly share code, notes, and snippets.

@mujjingun
Last active April 29, 2020 14:50
Show Gist options
  • Save mujjingun/efcdc9d8e82bc44c67843a542d3917d9 to your computer and use it in GitHub Desktop.
Save mujjingun/efcdc9d8e82bc44c67843a542d3917d9 to your computer and use it in GitHub Desktop.
Undecidable C++ Grammar Example
#include <algorithm>
#include <type_traits>
template <int... Ints>
struct Row {
constexpr static bool empty = (sizeof...(Ints) == 0);
};
template <typename Upper, typename Lower>
struct Domino {
using upper = Upper;
using lower = Lower;
};
template <int... Ints, int... MoreInts>
auto concat(Row<Ints...>, Row<MoreInts...>) -> Row<Ints..., MoreInts...>;
template <typename Row1, typename Row2>
using Concat = decltype(concat(Row1{}, Row2{}));
template <typename Row1, typename Row2>
struct State {
using row1 = Row1;
using row2 = Row2;
using is_match = std::bool_constant<!Row1::empty && std::is_same_v<Row1, Row2>>;
};
template <typename... Elems>
struct Queue;
template <typename First, typename... Rest>
struct Queue<First, Rest...> {
using head = First;
using pop = Queue<Rest...>;
template <typename... Elems>
using push = Queue<First, Rest..., Elems...>;
constexpr static bool empty = false;
};
template <>
struct Queue<> {
template <typename... Elems>
using push = Queue<Elems...>;
constexpr static bool empty = true;
};
template <int... Upper, int... Lower>
constexpr auto partial_match(Row<Upper...>, Row<Lower...>)
{
int upper[]{0, Upper...};
int lower[]{0, Lower...};
auto size = std::min(sizeof...(Upper), sizeof...(Lower));
for (std::size_t i = 1; i <= size; ++i) {
if (upper[i] != lower[i]) {
return false;
}
}
return true;
}
template <typename Queue, typename... Dominos>
struct Match {
using Row1 = typename Queue::head::row1;
using Row2 = typename Queue::head::row2;
constexpr static bool value = std::disjunction_v<
typename Queue::head::is_match,
std::conjunction<
std::bool_constant<partial_match(Row1{}, Row2{})>,
Match<typename Queue::pop::template push<
State<Concat<Row1, typename Dominos::upper>, Concat<Row2, typename Dominos::lower>>...>,
Dominos...>>>;
};
template <typename... Dominos>
struct Match<Queue<>, Dominos...> {
constexpr static bool value = false;
};
template <typename... Dominos>
struct DominoList {
constexpr static bool match = Match<Queue<State<Row<>, Row<>>>, Dominos...>::value;
};
template <typename Dominos, typename = void>
struct ParseThis;
template <typename Dominos>
struct ParseThis<Dominos, typename std::enable_if_t<Dominos::match>> {
using typeOrValue = int;
};
template <typename Dominos>
struct ParseThis<Dominos, typename std::enable_if_t<!Dominos::match>> {
static constexpr int typeOrValue = 0;
};
// x is a function if a solution exists, a variable otherwise
int x(ParseThis<DominoList<
Domino<Row<'b', 'b', 'a'>, Row<'b', 'b'>>,
Domino<Row<'a', 'b'>, Row<'a', 'a'>>,
Domino<Row<'a'>, Row<'b', 'a', 'a'>>>>::typeOrValue);
int main()
{
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment