What is a g-expression?

As far as we know, we're the only ones to talk about "g-expressions" -- it's a term we've used to more strongly establish the analogy between grap (graph-based lisp) and lisp, between graphs (used in graph) and lists (used in lisp). The lisp-based analog that we equate g-expressions with, are (as you might have guessed) s-expressions. You can read about s-expressions here:
  http://en.wikipedia.org/wiki/S-expression

In summary, s-expressions are essentially lists, usually nested, that represent an operation that can be performed. They have been used in things like Lisp and Scheme (their very foundation, in fact) as well as HTML-generation (e.g., the Divmod Nevow web framework).

A very simple example would be the operation of addition on two numbers:

  (+ 1 2)

As g-expressions evolved from the use of graphs, not lists, to represent operations, let's look at the graph-based form (that is an analog to the list-based form given above):

    +
   / \
 1 2

A common representation of the nodes in a graph is to provide a list of edges, where each edge represents the connection of one node to another. The graph above can be represented with the following list of edges:

  [(+ 1) (+ 2)]

And that is what we call a g-expression.

Note that in the code, we use Python syntax (as it is a Python project), so the g-expression you see will have the following form:

  [('+', 1), ('+', 2)]