Angly parser

I’ve implemented a parser for template expressions.  This will enable EDSLs in the realm of C++ angle brackets.

For example, yesterday I created a new syntax for specifying graph metadata:

struct A {}; struct B {}; struct C {}; struct D {}; struct E {}; struct F {}; struct G {};
struct t {}; struct u {}; struct v {}; struct w {}; struct x {}; struct y {}; struct z {};

/*
  A - t > B - v > D - x > F
    - u > C - w > E - y > F
                    - z > G
*/
typedef graph<node<A, edge<t, B>, edge<u, C> >,
              node<B, edge<v, D> >,
              node<C, edge<w, E> >,
              node<D, edge<x, F> >,
              node<E, edge<y, F>, edge<z, G> > > adjacencies;
typedef typename tmparser::run_dfa<graph_dfa, graph_nodes, adjacencies>::type graph_data;
typedef typename mpl_graph::adjacency_list_graph<graph_data> parsed_graph;

This allows the most concise possible description of graph metadata.  It allows the format to be validated.  And since the keywords used in these expressions are not metafunctions but just tokens to be matched, they can have different meaning in different grammars and contexts.

The matching is done by a DFA with a stack, implemented on MPL.Graph.  At each level of the expression, the DFA follows transitions matching items in the current list.  A transition can recurse into the deeper level of the expression, in which case a new stack frame is created with new data and a new start state.  The transition is labeled with semantic actions for before and after recursing.

Next up: a language for specifying these DFA’s nicely.  Right now it’s kind of messy:

template<typename ...>
struct graph {};
template<typename ...>
struct node {};
template<typename ...>
struct edge {};
//bogus
template<typename ...>
struct foo {};

// parser for metadata text of adjacency_list format
// graph< node< node_tag, edge< edge_tag, target_node_tag >, ...> >
// this an example of a graph language parser, not realistic
// define types for states
struct graph_nodes : tmparser::dfa_state<mpl::true_, mpl::vector<> > {};
struct node_name : tmparser::dfa_state<> {};
struct node_edges : tmparser::dfa_state<mpl::true_> {};
struct edge_name : tmparser::dfa_state<> {};
struct edge_target : tmparser::dfa_state<> {};
struct edge_done : tmparser::dfa_state<mpl::true_> {};
// types for transitions
struct graph_node : 
  tmparser::dfa_transition<tmparser::match_token<node<> >, 
                           node_name, 
                           mpl::push_back<mpl::_1, mpl::_2> > {}; 
struct node_name_trans : 
  tmparser::dfa_transition<mpl::always<mpl::true_>, 
                           void, 
                           mpl::pair<mpl::_2, mpl::vector<> > > {};
struct node_edge : 
  tmparser::dfa_transition<tmparser::match_token<edge<> >, 
                           edge_name, 
                           mpl::pair<mpl::first<mpl::_1>, mpl::push_back<mpl::second<mpl::_1>, mpl::_2> > > {}; 
struct edge_name_trans : 
  tmparser::dfa_transition<mpl::always<mpl::true_>, 
                           void, 
                           mpl::_2> {};
struct edge_target_trans : 
  tmparser::dfa_transition<mpl::always<mpl::true_>, 
                           void, 
                           mpl::pair<mpl::_1, mpl::_2> > {};

typedef mpl_graph::adjacency_list_graph<
  mpl::vector<mpl::pair<graph_nodes, 
                        mpl::vector<mpl::pair<graph_node, graph_nodes> > >,
              mpl::pair<node_name, 
                        mpl::vector<mpl::pair<node_name_trans, node_edges> > >,
              mpl::pair<node_edges, 
                        mpl::vector<mpl::pair<node_edge, node_edges> > >,
              mpl::pair<edge_name,
                        mpl::vector<mpl::pair<edge_name_trans, edge_target> > >,
              mpl::pair<edge_target,
                        mpl::vector<mpl::pair<edge_target_trans, edge_done> > >
              > > graph_dfa;

Leave a Comment