REPOSITORY CODING · MEDIUM
Propagate FOLLOW through nullable suffixes
For S -> A B with nullable B, FOLLOW(A) must include FOLLOW(S), even when FIRST(B) is nonempty. Iterate propagation to a fixed point.
Grammar analysisLL(1) grammar workbench
Work through a real codebase.
Choose an environment, investigate the existing implementation and use the tests to check your change. Sign in to open a workspace; execution and Ono usage follow your plan’s allowances.
Task requirements and environments
Java · 55 minute session
- Analyze a bounded context-free grammar: 1..8 nonterminals, 1..6 alternatives per nonterminal, at most 30 productions and eight symbols per production. An empty right-hand-side array denotes epsilon. Terminals are unique printable ASCII tokens of length 1..16; nonterminals match [A-Z][A-Za-z0-9_]{0,15}, are disjoint from terminals and start must be defined.
- Reject undefined production symbols, reserved $ input tokens and tokens outside the terminal set. Up to 64 input tokens are accepted. Reject direct or indirect left recursion, including left edges revealed by nullable prefixes, even in unreachable productions.
- Compute nullable nonterminals and FIRST/FOLLOW sets to fixed points; FIRST excludes epsilon and FOLLOW includes $ for the start. Propagate FIRST through nullable sequences and FOLLOW through nullable suffixes. Return all sets in lexical order.
- Build an LL(1) prediction table from FIRST and nullable FOLLOW entries, preserving every competing local production index. Return deterministic conflicts sorted by nonterminal and token, with zero-based alternative indices. A conflicted grammar is analyzed but accepted is false.
- Predictive parsing pushes the selected production in reverse order and requires complete token consumption. Return {nullable,first,follow,conflicts,accepted} inside an ok result, or a stable validation error. Native Java and Spring Boot hosts share these domain modules.
Spring Boot · 55 minute session
- Analyze a bounded context-free grammar: 1..8 nonterminals, 1..6 alternatives per nonterminal, at most 30 productions and eight symbols per production. An empty right-hand-side array denotes epsilon. Terminals are unique printable ASCII tokens of length 1..16; nonterminals match [A-Z][A-Za-z0-9_]{0,15}, are disjoint from terminals and start must be defined.
- Reject undefined production symbols, reserved $ input tokens and tokens outside the terminal set. Up to 64 input tokens are accepted. Reject direct or indirect left recursion, including left edges revealed by nullable prefixes, even in unreachable productions.
- Compute nullable nonterminals and FIRST/FOLLOW sets to fixed points; FIRST excludes epsilon and FOLLOW includes $ for the start. Propagate FIRST through nullable sequences and FOLLOW through nullable suffixes. Return all sets in lexical order.
- Build an LL(1) prediction table from FIRST and nullable FOLLOW entries, preserving every competing local production index. Return deterministic conflicts sorted by nonterminal and token, with zero-based alternative indices. A conflicted grammar is analyzed but accepted is false.
- Predictive parsing pushes the selected production in reverse order and requires complete token consumption. Return {nullable,first,follow,conflicts,accepted} inside an ok result, or a stable validation error. Native Java and Spring Boot hosts share these domain modules.