►Programming Languages
▼Assignments, Actual
•4 — Core:   Validity
9.0.0.1
    contents    up   

4 — Core: Validity🔗

Due Thursday, 02 October 2025, 11:59:59pm

Purpose to build a basic validity checker

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

  • the executables xvalid as specified below;

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

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

The directory 4/ 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 Using your favorite programming language, you are implement a parser that determines whether an ExampleCC expression belongs to the Core language, an extension of Bare Bones with variable declarations. Additionally, you will need to implement the functionality to check the validity of an error-free AST.

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

See figure 5 for the grammar of the Core language.

The implementation of the parser should adapt your solution to 2 — Bare Bones: Parser.

The implementation of the validity checker must confirm that every occurrence of a variable in an expression or statement comes with a matching (local or global) declaration. It consumes an error-free AST of a Core program, walks the tree, and replaces all variable occurrence that violate the validity constraint so that an IDE would be able to notify a Core programmer in a suitable manner.

  Program     ::= (Declaration^* Statement^* Expression)

  

  Declaration ::= (def Variable Expression)

  

  Statement   ::= (Variable = Expression)

                | (if0 Expression Block Block)

                | (while0 Expression Block)

  

  Block       ::= Statement

                | (block Declaration^* 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 5: The concrete syntax of the Core language

The xvalid program reads one ExampleCC from STDIN, constructs the AST, performs the validity checks, and writes one of the following strings to STDOUT: The outcomes are listed in the order in which they may occur for a given program.

  • "parser error" if the given ExampleCC is not an element of the Core grammar;

  • "undeclared variable error" if in the well-formed Core program one of its variable references comes without declaration;

  • "undeclared variable error" if the given ExampleCC is an element of the Core grammar but at least one of its variable occurrences comes without declaration.

  • "belongs" if the given ExampleCC is well-formed and valid Core program.

  • "belongs" if the given ExampleCC is an element of the Core grammar and variable occurrences come with declarations.

Note Eli Barzilay uses an (expensive subscription) AI at work. Recently, he wanted to know whether the AI understood the scope of parameters and variables in a JS function header. So he asked the AI. Unsurprisingly, it gave wrong answers.

Testing Task Create 5 integration tests for xvalid.

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 Variable Declartions and Nested Blocks (Validity)

    contents    up