Grammar Lab Guide

Grammar Lab Guide

The Grammar Lab is AutomataLab's dedicated environment for defining, analyzing, and transforming Context-Free Grammars (CFGs). It provides real-time mathematical diagnostics, derivation tree exploration, and automatic conversions.

---

1. Defining a Grammar

You can define your grammar in the Grammar Editor Panel on the left. AutomataLab supports two modes of editing:

Grouped Productions View

This is the standard view where multiple right-hand sides for the same non-terminal are separated by the pipe character (|).

E -> E + T | T
T -> T * F | F
F -> ( E ) | id

Numbered (Flat) Productions View

This view separates every alternative into its own numbered rule. This format is essential when you later move to the Parser Studio, as algorithms like LR parsing refer to specific numbered production rules for reductions.

1: E -> E + T
2: E -> T
3: T -> T * F
4: T -> F
5: F -> ( E )
6: F -> id

Syntax & Arrow Conventions

The Grammar Lab's parser is highly flexible. It natively supports multiple "arrow" operators for production rules:

• -> (Standard text arrow)
• ::= (BNF-style)
• → (Unicode arrow)
• : (Colon style)

Important Constraints:

• The left-hand side (LHS) must be a single non-terminal (starting with a capital letter).
• To represent the empty string (epsilon), use the symbol ε or type eps. AutomataLab will automatically format eps to ε.
• Terminals and non-terminals are split by whitespace. E.g., id is a single terminal, while i d represents two separate terminals.
• Note: the => arrow was intentionally removed to reserve it for semantic derivations.

---

2. Real-Time Diagnostics

As you type, AutomataLab continuously analyzes your grammar and displays the results in the middle panel.

Nullable Symbols

The lab identifies all non-terminals that can ultimately derive the empty string ($\epsilon$).

FIRST & FOLLOW Sets

AutomataLab automatically computes the FIRST and FOLLOW sets for every symbol in your grammar.

• FIRST($X$): The set of terminals that begin strings derived from $X$.
• FOLLOW($X$): The set of terminals that can appear immediately to the right of $X$ in some sentential form.

These sets are mathematically crucial for predictive parsing and are utilized by the LL(1) algorithm in the Parser Studio.

Grammar Properties Matrix

The diagnostics panel evaluates your grammar against several formal properties:

• Left Recursive: Detects direct or indirect left recursion (fatal for LL parsers).
• Left Factored: Checks if multiple rules share common prefixes.
• Cycle Free: Detects infinite derivation loops like A -> B and B -> A.
• Epsilon Free: Checks if the grammar produces $\epsilon$ rules.

---

3. Ambiguity & Derivation Testing

Ambiguity Detection

A grammar is ambiguous if a single string has more than one valid leftmost derivation (or multiple parse trees). You can enter a test string in the Derivation Input Bar. AutomataLab will attempt to generate a derivation tree. If it discovers multiple unique trees for the same input, it will flag the grammar as Ambiguous and display the conflicting derivation paths side-by-side to help you identify the flaw.

Generating Parse Trees

When a valid string is entered, the Syntax Tree Panel will render the hierarchical derivation tree, allowing you to visually trace how the non-terminals expanded into your input tokens.

---

4. Grammar Transformations

AutomataLab provides automated algorithms to transform your CFG into specific normal forms. These are accessible via the Tools menu above the diagnostics panel.

Chomsky Normal Form (CNF)

Transforms the grammar such that every production is of the form: $A \rightarrow BC$ or $A \rightarrow a$ (where $A, B, C$ are non-terminals, and $a$ is a terminal). This conversion step is required before running the CYK Algorithm in the Parser Studio.

Greibach Normal Form (GNF)

(Advanced Feature) Transforms the grammar such that every right-hand side begins with exactly one terminal symbol, optionally followed by any number of non-terminals.

---

Next Steps

Once your grammar is polished and unambiguous, switch over to the Parser Studio to automatically generate Parse Tables and simulate token processing!