►Programming Languages
▼Assignments, Actual
•2 — Bare Bones:   Parser
9.0.0.1
    contents    up   

2 — Bare Bones: Parser🔗

Due Thursday, 18 September 2025, 11:59:59pm

Purpose to build a basic parser A proper understanding of parsing requires a full-fledged course.

Delivery Deliver your solutions in a directory called 2 within your assigned GitHub repository. The directory should contain the following items:

  • the executables xparse as specified in the testing task below;

  • the sub-directory 2/Tests/ with the required integration test; and

  • an optional sub-directory called 2/Other/ for all auxiliary files.

The directory 2/ may also contain a Makefile (see —Make) in case you need us to build your executable. An executable should not be checked into a repository.

Programming Task You are to design an AST data representation for Bare Bones. Using your favorite language, implement a parser that consumes a ExampleBB expression and determines whether it belongs to Bare Bones.

ExampleBB is an Example whose Names also contain the following keywords: if0, while0, block, =, /, +, ==.

See figure 1, which specifies the grammar of the language as a subset of ExampleBB.

The parser constructs an AST as follows:

  • If the given ExampleBB belongs to Bare Bones, the AST consists of just grammar nodes.

  • If the given ExampleBB violates the grammar of Bare Bones, the AST contains error nodes for each violation.

  Program    ::= (Statement^* Expression)

  

  Statement  ::= (Variable = Expression)

               | (if0 Expression Block Block)

               | (while0 Expression Block)

  

  Block      ::= Statement

               | (block Statement^+)

  

  Expression ::= GoodNumber

               | Variable

               | (Variable + Variable)

               | (Variable / Variable)

               | (Variable == Variable)

  

  The set of Variables consists of all Names, minus keywords.

  

  The set of GoodNumbers comprises all inexact numbers

  (doubles) between -1000.0 and +1000.0, inclusive.

Figure 1: The concrete syntax of the Bare Bones language

The xparse program reads one ExampleBB from STDIN, constructs the AST, and writes one of the following strings to STDOUT:

  • "belongs" if the given ExampleBB is an element of Bare Bones;

  • "parser error" if the given ExampleBB is not an element of the Bare Bones grammar;

You may assume that the input is always an instance of ExampleBB.

Testing Task Create 5 integration tests for xparse.

A test always consists of inputs, expected output, and an automated procedure for comparing the actual output with the expected one. — For this course, an integration test consists of a pair of files: n-in.ss, the input file, and n-out.ss, the expected output file, where n is an integer between 0 and the requested number of tests (exclusive). The comparison procedure is (string or numeric) equality on the content of the output file and the actual output. — Constraint No test file may exceed the size limit of 5Kb.

Readings Syntax and Parsing

    contents    up