This page needs a newer browser to run its tools. You can still read everything here.

OCaml Module 14

Parsing and interpreters interview questions

Interview questions on parsing and interpreters: short warm-ups, then what each harder question tests, the first step of a good answer and its follow-ups.

9 questions: 3 warm-ups and 6 with model answers · Levels: Fresher to staff

Warm-up questions

Short questions with short answers, each answered in full.

Fresher to mid

What does the lexer decide, and what does it leave to the parser?

Answered in the lesson Lexing and parsing with ocamllex and Menhir
Mid

Would you start a new grammar with Menhir or with ocamlyacc?

Answered in the lesson Lexing and parsing with ocamllex and Menhir
Fresher to mid

What does a closure hold that the text of a function does not?

Answered in the lesson Writing an interpreter and a type checker

Questions with model answers

What each question tests, the first step of a good answer and the follow-ups to expect.

Mid to senior

You add the comparisons < and = to a calculator grammar whose +, -, * and / already have precedence lines. Menhir now warns that 7 states have shift/reduce conflicts, yet the build succeeds. What do you change, and how do you make sure the grammar groups formulas the way you intend?
What it tests

Reading conflict warnings as groupings nobody chose, ranking new operators with the right associativity, deciding what a chain of comparisons means, and keeping conflicts out of the build for good.

First step

Measure before changing anything: run 1 + 2 < 4 and 1 < 2 < 3 through the parser and read parser.conflicts for the states where LT or EQ is the next token. A comparison should take whole sums as its operands, so it belongs on the loosest precedence line, and you still have to decide whether a chain of comparisons is allowed at all.
Follow-ups
- Why did 1 + 2 < 4 give 2 before the fix?
- Should 1 < 2 < 3 be an error, or mean 1 < 2 and 2 < 3?
- How do you keep a new conflict from reaching the main branch?
- How do you test the grouping and not only the values?
From the lesson Lexing and parsing with ocamllex and Menhir
Model answer, Pro. Model answers open with any pass; prices are in the notice on this page.
Opening the model answers with your pass…
Model answers open with any MySmartCoPilot pass.
Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45
One payment; nothing renews unless you choose to. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so the model answers can’t be opened at the moment. If you have a pass, enter your licence key.
Choose a pass I have a licence key
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 4 minutes
Mid to senior

Users paste formulas of several lines into your calculator, and a message such as syntax error at offset 41 helps none of them. How do you report the line and the column of an error, and how would you say what was expected instead of only syntax error?
What it tests

Keeping line positions in an ocamllex lexer, reading the position after Parser.Error, columns that count bytes, and Menhir's tools for writing and maintaining one message per error state.

First step

Positions come from the lexer buffer, and the generated lexer advances only the offset: the line number and the start of the line change only when an action calls Lexing.new_line. Give the newline a rule of its own that calls it, then compute the column from the pos_cnum and pos_bol of Lexing.lexeme_start_p.
Follow-ups
- Why can the column be wrong after a tab or a character such as ×?
- The input ends in the middle of a formula. Which position do you report?
- How do you keep the messages right when the grammar changes?
From the lesson Lexing and parsing with ocamllex and Menhir
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 4 minutes
Mid to senior

A teammate's interpreter evaluates let k = 2 in let scale = fun x -> x + k in let k = 10 in scale 5 to 15, and the language definition says 7. A function returned from another function also fails with "unbound variable". What is wrong, how do you fix it, and which tests keep it fixed?
What it tests

Tying both symptoms to one cause, the environment a call runs in, and writing tests that tell lexical scope from dynamic scope.

First step

Work the program by hand under the rule the definition implies and note which k the call should see. Then read the evaluator case that handles a call and ask which environment it extends: the one stored in the function value, or the caller's.
Follow-ups
- What must a function value hold, and what does it cost to hold the whole environment?
- Why does the second symptom, a function returned from another function, appear together with the first?
- Which tests would have caught this before release, and how do you check them against a second implementation?
From the lesson Writing an interpreter and a type checker
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to staff

Your type checker accepts a program that then stops at run time with "if needs a bool". How do you find the missing rule, show that your fix is complete for small programs, and keep the bug from returning?
What it tests

Using a property, accepted programs never get stuck, as a test, and knowing what it proves, what it cannot prove and why rejecting runnable programs is allowed.

First step

Shrink the crash to the smallest program that still gets stuck, then compare the checker case for that constructor with the evaluator case that raised the error. A rule the evaluator relies on and the checker never states is the likely gap.
Follow-ups
- Why enumerate programs by size instead of generating random ones?
- Is a property that passes on every program up to a given size a proof of soundness?
- Should the checker also accept every program that runs fine, and what does it cost if it does not?
- What changes in the test when the language gains a recursive let?
From the lesson Writing an interpreter and a type checker
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Senior to staff

You add types to a small configuration language for people who are not programmers. Do you ask for annotations or infer the types, and how do you present a failure such as "'a occurs inside 'a -> 'b"?
What it tests

Choosing between a checker with annotations and Hindley-Milner inference for stated users, and explaining what unification and the occurs check mean for error messages.

First step

Write down who edits the files and what a wrong file costs them. Then list what each design needs from them, annotations on every function parameter or none, and what each error would say about their own text.
Follow-ups
- Where would you still ask for annotations in an inferring design, and why?
- What does let-polymorphism let users do that a lambda-bound name cannot?
- How would you turn the occurs check failure into a message the user can act on?
From the lesson Writing an interpreter and a type checker
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 2 minutes
Mid to staff

An interpreter that runs by substitution takes 40 seconds on a generated program of 5,000 chained lets, while a colleague's environment version takes 20 milliseconds. Why is the gap so large, how would you confirm it, and what else would you change?
What it tests

Reasoning about work as a function of program size, confirming it with a counter instead of a stopwatch, and knowing where an environment can also go quadratic.

First step

Count the nodes each version visits on chains of 100 and 200 lets and compare the two growth rates. Do not trust one stopwatch run: a counter gives the same answer on every machine.
Follow-ups
- How many visits do you expect at 5,000 lets, and how do you check the number?
- Can the environment version also be quadratic, and with which data structure?
- What would a compiler do instead of looking names up at run time?
From the lesson Writing an interpreter and a type checker
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 2 minutes

All OCaml interview questions · The OCaml track

Warm-up questions

What does the lexer decide, and what does it leave to the parser?

Would you start a new grammar with Menhir or with ocamlyacc?

What does a closure hold that the text of a function does not?

Questions with model answers

You add the comparisons < and = to a calculator grammar whose +, -, * and / already have precedence lines. Menhir now warns that 7 states have shift/reduce conflicts, yet the build succeeds. What do you change, and how do you make sure the grammar groups formulas the way you intend?

Users paste formulas of several lines into your calculator, and a message such as syntax error at offset 41 helps none of them. How do you report the line and the column of an error, and how would you say what was expected instead of only syntax error?

A teammate's interpreter evaluates let k = 2 in let scale = fun x -> x + k in let k = 10 in scale 5 to 15, and the language definition says 7. A function returned from another function also fails with "unbound variable". What is wrong, how do you fix it, and which tests keep it fixed?

Your type checker accepts a program that then stops at run time with "if needs a bool". How do you find the missing rule, show that your fix is complete for small programs, and keep the bug from returning?

You add types to a small configuration language for people who are not programmers. Do you ask for annotations or infer the types, and how do you present a failure such as "'a occurs inside 'a -> 'b"?

An interpreter that runs by substitution takes 40 seconds on a generated program of 5,000 chained lets, while a colleague's environment version takes 20 milliseconds. Why is the gap so large, how would you confirm it, and what else would you change?