Module Kernel.Sentence_generationSource

Generating parse sentences from transitions

This module provides functionality to generate concrete parse examples (sentences) from sequences of LR states or LR transitions. It's used for generating counterexamples and debug information.

Core algorithm:

• The algorithm works backwards from the desired parsing outcome to find a valid sequence of transitions that would produce that outcome.

• to_transitions converts a sequence of LR states to a sequence of transitions that connect those states.

• to_cells maps transitions to reduction graph cells, using dynamic programming to find the minimum-cost path through the reduction graph.

• expand_cells recursively expands cells back to the original terminal symbols that would trigger the reductions.

Key data structures:

• Cells: Represent positions in the reduction graph, encoded as a compact triple (node, pre_class, post_class) for efficient storage and lookup. (Pre_class and post_class constrain the lookahead symbols that can precede and follow)

• The algorithm uses dynamic programming to find minimum-cost paths through the reduction graph.

Implementation details:

• to_cells uses a sophisticated dynamic programming approach where at each transition, it considers:
• All post_classes of the current node
• For each, all pre_classes that can reach it with finite cost Then it keeps only the minimal cost paths

• expand_cells handles two cases:
• L tr: A transition node - either shift (return the terminal) or goto (recursively solve the subproblem with minimum cost)
• R (l, r): An inner node - decompose into left and right subproblems, finding solutions that minimize total cost

• The Break exception is used to short-circuit when a minimal-cost solution is found during the exploration of all possible decompositions.

• Nullable reductions need some special care. If a nullable reduction is possible and the lookahead classes allow it, the algorithm takes that path instead of the non-nullable one.