Parsing declarations

6/10/15

Using the help of many online sources, including the Spirit manual, StackOverflow, and other forums and discussion lists, I have achieved success with regards to declarative statements in a Bertini Classic parser for Bertini2. What remains is to link the declarations to the definitions.

Some symbols, such as variables and the path variable do not depend on anything, and it would be an error to define them. These symbols are driven by the continuator as a path is tracked, so their value may be set, but they are never really defined.

In contrast, functions, constants (constant functions), parameters, and implicitly given subfunctions all must be defined. There is no way to know what $f_1$ is supposed to be unless the user tells Bertini. So, for each of these symbols, I must detect when they are on the left hand side of an = sign, and parse the right hand side as a function. Furthermore, each of the symbols must be associated with the correct location in the tree. That is, there is only one $x$, only one subfunction $s$, only one pathvariable $t$, and every time we find them, we must point to the correct location from the operator node.

To achieve this, I will try to build a master list of symbols (using qi::symbols<>). The key in the qi::symbols will be the name of the symbol. The value will hopefully be the location in memory of the symbol.

At this point, we are building a singly-linked tree. For simple operations at the beginning stages of the program, this will be sufficient. However, a singly linked-tree can only be forwardly differentiated using automatic differentiation method, which is known to be slow for functions of many variables. In contrast, backward differentiation is quick for such functions, but requires a doubly-linked tree. I believe that I can properly construct the backwards linkage at a later time without too much effort, so I am willing to pay any performance price by simply using forward differentiation for the time being.

Looking forward, after parsing, we must solve the problems of
• differentiation
• degree calculation
• verification of membership in the ring of polynomials,
• homogenization
• and probably a few others.

I am excited to be able to start tracking paths using the new machinery soon! I really hope that we made sound design choices early in the process, and that we won't have to refactor too many things in the future, ha.
Combining Spirit Qi Grammars

6/8/15

I am learning about how you combine grammars in Boost.Spirit Qi. As per this SO post, you simply create your base grammars as usual (ha, as if there's really anything usual about working with these at first), then create instances of them with in the grammar which needs the subgrammars.

So, in Bertini2, we have already defined two grammars:
  • one for parsing comma-separated lists of variable names (or really, any other type of name which is separated by commas),
  • one for parsing expression trees, which may or may not be polynomial.

Then, in a grammar which should parse both kinds of things (e.g. a system parser, which is what I am writing right now), you just make instances of the two grammars, and use them as you would rules. So cool.

Also, I found the reference for qi::symbols parsing: here on Boost.org.