PROJECT NOTES / COMP3888
Grammar Inference
Platform.
Our COMP3888 team implemented and compared grammar inference algorithms. We separated training from evaluation because asking the target language whether an input is valid does not tell us whether the learned grammar recognizes it correctly.
Separate inference from evaluation.
- 01
Train and save
Learn from positive samples and target-oracle queries, then save the grammar
- 02
Recognize independently
BRNGLR reads the saved grammar and decides membership for held-out inputs
- 03
Review the evaluation
Compare predictions with previously recorded test labels to produce metrics
01 / BACKGROUND
More than producing a grammar.
Our team developed a platform to implement and compare Arvada, TreeVada, Kedavra, Crucio and XVada, with a benchmark workflow supporting Arithmetic and Lisp. The algorithms learn grammars from positive training strings and target-language oracle feedback. Producing a grammar is only the starting point: we also need to examine its behavior on inputs that were not used for training.
The training oracle is the original target-language parser. It answers “Does this string belong to the target language?” and supplies membership-query feedback during learning; it does not represent the inferred grammar. Continuing to query that parser would not reveal whether the learned grammar accepts invalid inputs or misses valid ones. Evaluation therefore needs to read the inferred result independently and compare its predictions with existing held-out labels.
02 / MY CONTRIBUTION
Working on the connections.
Contributed to system architecture
I contributed to the platform’s architecture design, focusing on the boundaries between training, grammar artifacts and evaluation. The inference algorithm learns and exports a grammar; the evaluation module reads and tests that grammar rather than running inference again.
Refactored the evaluation workflow
I refactored evaluation into a separate stage, so training and evaluation never invoke each other. Training saves the grammar and training metadata; evaluation uses the saved grammar and held-out inputs to produce per-input predictions, metrics and evaluation metadata. This allows an existing grammar to be evaluated without retraining.
Integrated the BRNGLR recognizer
I integrated the native BRNGLR recognizer to evaluate inferred grammars. It answers “Does this string belong to the saved grammar?”, rather than replacing the training oracle’s target-language judgment. Evaluation compares its predictions on held-out positive and negative inputs with previously recorded target-language labels to calculate metrics such as precision, recall and F1.
03 / TECHNICAL DECISION
Make the saved grammar the boundary.
A key decision in the refactor was to make the saved grammar artifact the boundary between training and evaluation, instead of coupling evaluation to an algorithm’s internal state. Training exports a validated JSON grammar artifact that meets the BRNGLR contract. Reading it for evaluation requires neither selecting an inference algorithm nor calling the target-language oracle.
This makes “what was learned” and “how it is tested” separately inspectable, but requires the exported grammar to meet the recognizer’s supported contract. The current independent evaluation uses literal-terminal, character-level CFGs. Recognition timeouts or execution errors must be reported as evaluation failures, not disguised as negative membership predictions. Independent recognition provides test evidence for analysis, not proof that the grammar is equivalent to the target language.