Context Free Grammars

Context-Free Grammars

The Grammar Lab acts as the centralized editor for Context-Free Grammars (CFGs). A CFG consists of a set of rules (productions) that describe how strings in a language are generated.

---

1. Syntax & Conventions

To ensure AutomataLab correctly parses your grammar into mathematical sets, follow these strict syntax rules:

Non-Terminals

• A non-terminal is any token that starts with an uppercase letter (e.g., E, Expr, T_prime).
• The left-hand side (LHS) of any production rule must be exactly one non-terminal.
• The first non-terminal defined in the editor is automatically assigned as the Start Symbol ($S$).

Terminals

• A terminal is any token that starts with a lowercase letter, number, or symbol (e.g., id, +, number, a).
• Tokens must be separated by whitespace. For example, id + id is parsed as three tokens (id, +, id), while id+id would be parsed as a single token.

The Epsilon Symbol ($\epsilon$)

To write an empty string/epsilon production, you can type:

• eps
• epsilon
• λ or lambda
• ε

AutomataLab's editor will immediately auto-format eps to the formal ε character for readability.

---

2. Production Rule Arrows

AutomataLab's parser is highly resilient and supports multiple popular syntax styles for drawing the production rule arrow. You can use any of the following to separate the LHS from the RHS:

1. -> (Standard text arrow)
2. ::= (BNF style)
3. → (Unicode arrow)
4. : (Colon format, often used in Yacc/Bison)

Note: The => arrow is intentionally disallowed here to reserve it for semantic step derivations in the syntax tree visualizer.

---

3. Grouped vs. Numbered Views

AutomataLab provides two ways to view and edit your grammar:

Grouped View

Use the pipe | character to group multiple RHS alternatives for the same non-terminal on a single line. This is the most readable format.

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

Numbered View

When transitioning to the Parser Studio for Shift-Reduce parsing (like LR or LALR), the algorithms require numbered production rules to explicitly dictate which rule was used to reduce the stack. AutomataLab can automatically toggle your grouped grammar into a flattened, numbered view:

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

See Also

• Mathematical Properties (FIRST, FOLLOW, Nullability)
• Grammar Transformations (CNF, GNF)