Katkat
Back

Design a parser for a hypothetical language

OpenAISoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates competency in compiler and language design, covering grammar analysis, parsing algorithms (LL/LR/GLR/Earley/PEG), lexer and parser implementation, AST construction, error reporting and recovery, operator precedence and associativity, and analysis of time/space trade-offs.

You are given a set of syntax rules for a hypothetical programming language written in BNF/EBNF. Design data structures and algorithms that: (

  1. parse the grammar into an internal representation (terminals, nonterminals, productions, precedence/associativity); (
  2. detect issues such as left recursion, ambiguity, unreachable or non-productive symbols; (
  3. apply transformations (left-recursion elimination, left factoring) to enable efficient parsing; (
  4. compute FIRST/FOLLOW sets and determine whether the grammar is LL ( 1); if not LL ( 1), justify choosing LR ( 1), GLR, Earley, or PEG parsing and outline construction; (
  5. implement a lexer and parser that build an abstract syntax tree (AST) for input programs; (
  6. provide error reporting and recovery with expected-token hints; (
  7. support operator precedence and associativity declarations; (
  8. analyze time and space complexity for grammar processing and parsing, and discuss trade-offs; (
  9. optionally support incremental or streaming parsing. Provide pseudocode and explain your design choices.