Design a parser for a hypothetical language

Q: Design a parser for a hypothetical language

This is a Coding & Algorithms interview question from OpenAI for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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

parse the grammar into an internal representation (terminals, nonterminals, productions, precedence/associativity); (
detect issues such as left recursion, ambiguity, unreachable or non-productive symbols; (
apply transformations (left-recursion elimination, left factoring) to enable efficient parsing; (
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; (
implement a lexer and parser that build an abstract syntax tree (AST) for input programs; (
provide error reporting and recovery with expected-token hints; (
support operator precedence and associativity declarations; (
analyze time and space complexity for grammar processing and parsing, and discuss trade-offs; (
optionally support incremental or streaming parsing. Provide pseudocode and explain your design choices.

Design a parser for a hypothetical language

Comments (0)