Compiler and CFG question

[somebody already took it]

Pretend I have the following:
Context free grammars C1 and C2 for two programming languages.
A mapping M between some of the symbols of C1 and C2
An algorithm A that will use C1, C2 and M to convert a string S1 generated by C1 to a string S2 generated by C2. I haven't worked out the details of the algorithm, but I'm imagining something that would try to generate S2s making the minimal number of assumptions (i.e. S2 should have the minimal number of nodes in its parse tree). There are certain inferences that can be made with certainty, for example terminal to terminal mappings. Another more complex example would be if non-terminal X maps to non-terminal Y, and if all the symbols in the group X generated map to symbols in one of Y's groups, we can infer that Y generates that group.

My question: Can A be used as a compiler? If so, what can it compile?

Edit: Fixing symbol collision.

[asilentchime]

It sounds like you might be describing a synchronous context-free grammar? You might more generally want to look up syntax-directed translation schemas.

I'm not quite sure what you're asking when you want to know if A can be used as a compiler. If A can indeed be modeled as an SCFG, then obviously the input and output languages are both context-free. If you want to use it efficiently as a compiler, you'll usually want an SCFG of rank at most 2 (so that you can use a modified CKY, for example). But not all SCFGs can be transformed into a rank-2 grammar (unlike CFGs with Chomsky normal form) -- there are some reordering patterns that can't be handled. PM me for some citations if you want. Or tell me if I've totally misinterpreted your question.

[somebody already took it]

Thanks, I wasn't aware of SCFGs.
I have another CFG related question:
Is there a technical term for grammars with more than one symbol on the left hand side. So for example:
A->AA|B|C
BC->D
where if A generated BC adjacently, the symbols would be combined to produce D.

[troyp]

If it has multiple nonterminals on a LHS, then it's not a CFG at all. I guess you'd just call it a "non-context free grammar"?

[jareds]

Thanks, I wasn't aware of SCFGs.
I have another CFG related question:
Is there a technical term for grammars with more than one symbol on the left hand side. So for example:
A->AA|B|C
BC->D
where if A generated BC adjacently, the symbols would be combined to produce D.

Yes: unrestricted grammar

[somebody already took it]

Yes: unrestricted grammar

Thanks! I read the wikipeida article and discovered the charming programming language Thue.

I have yet another CFG question. This one's a bit more mathematical.
I had the realization that CFGs are essentially a class of directed hypergraphs and parse trees are in a sense a "walks" on them. Furthermore, it should be possible to create a 3 dimensional adjacency matrix that represents any CFG in Chomsky normal form.
So, what I'm wondering about is what kind of properties this mathematical formulation has that would be of interest in relation to the CFGs it represents. For example, adjacency matrices for standard digraphs can tell us a number of things. Their determinate can indicate if they are NOT isomorphic, and finding a permutation matrix between them can indicate they are. Their eigenvalues/vectors can be used to rank nodes. Another thing we are usually interested in for standard digraphs are minimum spanning trees and least cost paths/traversals. Do these have analogs for CFGs?
We might also be interested in whether a random walk on a graph returns to it's origin. What happens when the walk bifurcates?