Practice Problems
Test your skills with carefully curated grammars. Solve them using the Syntax Engine or the Semantic Translation Engine.
Basic Arithmetic
Easy
A standard grammar for arithmetic expressions mapping addition and multiplication.
E -> E + T | T T -> T * F | F F -> ( E ) | id
Concepts:
Left-RecursiveAmbiguous
The Dangling Else
Medium
The classic ambiguous grammar simulating conditional programming statements.
S -> i E t S | i E t S e S | a E -> b
Concepts:
AmbiguousShift/Reduce
Palindromes
Easy
A simple context-free grammar that generates odd-length palindromes.
S -> a S a | b S b | c
Concepts:
Context-FreeLL(1)
SDT: Desktop Calculator
Medium
Evaluate mathematical expressions dynamically using Syntax-Directed Translation actions.
E -> E + T { $1 + $3 }
E -> E - T { $1 - $3 }
E -> T { $1 }
T -> T * F { $1 * $3 }
T -> T / F { $1 / $3 }
T -> F { $1 }
F -> ( E ) { $2 }
F -> num { parseFloat($1) }Concepts:
SDTEvaluationLALR(1)
SDT: Binary to Decimal
Hard
Convert a binary fractional string into its decimal equivalent via synthesized attributes.
N -> L . L { $1 + $3 / Math.pow(2, $3.toString().length) }
N -> L { $1 }
L -> L B { $1 * 2 + $2 }
L -> B { $1 }
B -> 0 { 0 }
B -> 1 { 1 }Concepts:
SDTSynthesized Attributes
Strict Operator Precedence
Medium
A heavily nested unambiguous grammar forcing explicit operator precedence climbing.
Expr -> Expr || Term1 | Term1 Term1 -> Term1 && Term2 | Term2 Term2 -> Term2 == Term3 | Term3 Term3 -> Term3 + Term4 | Term3 - Term4 | Term4 Term4 -> Term4 * Factor | Term4 / Factor | Factor Factor -> ! Factor | ( Expr ) | id | num
Concepts:
UnambiguousPrecedenceDeep Recursion
Mini JSON Validator
Hard
A structurally complex grammar simulating the validation of JSON objects and arrays.
Value -> Object | Array | string | number | true | false | null
Object -> { Members } | { }
Members -> Pair , Members | Pair
Pair -> string : Value
Array -> [ Elements ] | [ ]
Elements -> Value , Elements | ValueConcepts:
Context-FreeData StructuresLL(1)
Epsilon Transitions
Hard
A grammar demonstrating the mathematical challenges of evaluating epsilon derivations causing reduce/reduce conflicts.
S -> A a A b | B b B a A -> ε B -> ε
Concepts:
EpsilonLALR(1)Conflicts
ICG: Arithmetic Expression
Easy
Generate three-address code for basic arithmetic expressions with named variables.
E -> E + T { $$ = $1 + $3 }
E -> T { $$ = $1 }
T -> T * F { $$ = $1 * $3 }
T -> F { $$ = $1 }
F -> ( E ) { $$ = $2 }
F -> id { $$ = $1 }Concepts:
ICGTACArithmetic
ICG: Nested Expression
Medium
Generate TAC for a complex nested expression with parentheses demonstrating temporary variable chains.
E -> E + T { $$ = $1 + $3 }
E -> E - T { $$ = $1 - $3 }
E -> T { $$ = $1 }
T -> T * F { $$ = $1 * $3 }
T -> T / F { $$ = $1 / $3 }
T -> F { $$ = $1 }
F -> ( E ) { $$ = $2 }
F -> id { $$ = $1 }Concepts:
ICGTACComplex