PCF Interpreter — ANTLR + Scala

Authors

• PUNZANO CORIMBABA Leandro
• PEREZ RAMIREZ Julian

Description

This project implements a small interpreter/compiler for the PCF (Programming Computable Functions) language using ANTLR 4 for parsing and Scala 3 for evaluation.

It includes:

• A grammar definition (Pcf.g4)
• ANTLR-generated parser/lexer classes
• An AST builder in Scala
• A typer for parsed expressions
• An evaluator for parsed and well-typed expressions
• A test suite for parsing and evaluation
• A VM to execute abstract code
• A generator of WASM code

To test

Run the main function located at src/main/scala/pcf/Pcf.scala. If you want only to interpret an expression, run with the argument -i.

If you want to run the automated test suite, execute the desired object in src/main/scala/test/Tests.scala

Dependency: Make sure you have ScalaTest 3.2.19 (org.scalatest:scalatest_3:3.2.19) configured in your project.

Disclaimer about testing: the folder src/test contains our test scripts for individual components of the project, while the src/main/scala/test contains the actual test suites (provided by the teacher).

What is working?

For interpretation/evaluation

PCF blue, green and red are working totally, while PCF black is partially due to some misbehavior with FIX (it accepts only FUN as argument).

For compilation

From src/main/scala/test/Tests.scala, we have:

• Green: 10 successful tests out of 10
• Blue: 11 successful tests out of 11
• Red: 18 successful tests out of 19
• Black: 5 successful tests out of 5

The one test case that fails is red19.pcf. Apparently, it is linked to our grammar definition. We noticed that the generated AST is just a function that receives a parameter x and returns x, when in reality, it should be an application of that function on itself. In order to correct ir, we would need to rethink the order of recognition of the terms, as well the labels for each token.

Use of Generative AI

We used generative AI in order to help us to fix some problems with Scala syntax (specially to implement recursion), and also to understand, with concrete examples, how to use the ANTLR autogenerated code.

Project Structure

src
├── main
│   ├── java
│   │   └── parserANTLR
│   │       ├── ConcreteParser.java
│   │       ├── ErrorFlag.java
│   │       ├── ErrorListener.java
│   │       ├── PcfBaseListener.java
│   │       ├── PcfBaseVisitor.java
│   │       ├── Pcf.interp
│   │       ├── PcfLexer.interp
│   │       ├── PcfLexer.java
│   │       ├── PcfLexer.tokens
│   │       ├── PcfListener.java
│   │       ├── PcfParser.java
│   │       ├── Pcf.tokens
│   │       ├── PcfVisitor.java
│   │       ├── ReportingPcfLexer.java
│   │       └── SyntaxError.java
│   └── scala
│       ├── evaluator
│       │   └── Evaluator.scala
│       ├── generator
│       │   └── Generator.scala
│       │   └── Ins.scala
│       ├── parser
│       │   ├── AbstractParser.scala
│       │   ├── ASTBuilder.scala
│       │   ├── AST.scala
│       │   └── TestParser.scala
│       ├── pcf
│       │   └── Pcf.scala
│       ├── test
│       │   └── Test.scala
│       │   └── TestBlack.scala
│       │   └── TestBlue.scala
│       │   └── TestGreen.scala
│       │   └── TestInterp.scala
│       │   └── TestRed.scala
│       │   └── Tests.scala
│       └── typer
│           └── Typer.scala
│       └── vm
│           └── VM.scala
│   └── wat
│       ├── prelude.wat
├── test
│   └── scala
│       └── generator
│           └── GeneratorTest.scala
│       └── parser
│           └── ParserTest.scala
│       └── pcf
│           └── PcfTest.scala
├── Pcf.g4
├── am.wat

Generating ANTLR Parser Files

To generate the Java parser and lexer classes under src/main/java/parserANTLR:

1. Install the ANTLR v4 plugin for IntelliJ (Preferences → Plugins → Search for “ANTLR v4”).
2. Open Pcf.g4.
3. Click the “Generate ANTLR Recognizer” icon (the green “G”). Make sure Output directory is set to:

src/main/java/parserANTLR