Rules inlining and graph algorithm

[yossigil]

The inliing cytcles problem should is a reduction to a familiar problem. Create a directed graph from a grammar like so: If there is a rule A-< B C, then symbol A depends on symbol B, and there is and an edge from A to B. Similarly, there is an edge from A to C. The problem is to find cycles in this graph. Or more generally, strongly connected components.

See this algorithm: https://en.wikipedia.org/wiki/Strongly_connected_component

[yossigil]

Problem solved? compute the strongly connected components. treat each component as a super node. These nodes make a Tree that includes all the nodes in the original graph..

Now you only inlined nodes that are visible in this tree. These are the essential nodes. All the rest are auxiliary.

[yossigil]

Check out this graph, and its strongly connected components.

(0,1,2,3) to be denoted A. (4,5,6) to be denoted B (7,8,9,10,11) to be denoted C (12,13,14,15) to be denoted D.

Now, nodes A, B, C, D make a directed tree.A with children B and C, and D child C. In the general case, it would be DAG not a tree. Consider this example with an edged between 12 and 4.

In grammars, the graph would always have a single root. In other graphs, there could be multiple sources.

you start with the super node of the start symbol, you inline everything iin this component into the start symbol. All other nodes in this component can be ignored for the purpose of inlining.

In the example, supposing that 0 is the start symbol, Continue the algorithm with other components, in say a DFS. Ignore all nodes that have no edges outgoing of the component.

to be continued

[yossigil]

You have to make the following decisions. Select one of 4 and 5 and do complete inlinig into it.Until you reach it back. Select one of 7 and 8 and do complete inlining into it.

Same for 12 and 14. Suppose you choose 7, then you eliminate 8, 9, 10, and 11, and express 7 in terms of 7, and 12 13, 14, and 15. But you do not have to do all of 7, 12, 13, and 14. Only one of them is enough. I recommend choosing between 12 and 14 since they are visible to 7 directly. but you can choose whichever one you want.

So, after computing the SCC of the grammar. You need to choose only one node from each such component. If the component is a singleton, and I suspect there would be many. If not choose one node from each component. I suggest only among the nodes that have incoming edges from other components.

[yossigil]

See also this live demo: https://www.cs.usfca.edu/~galles/visualization/ConnectedComponent.html