...
...
...
A playground for this interpreter is up on my website.
This project is a mostly-functioning interpreter for College Board's pseudocode specified on the AP Computer Science Principles Exam reference sheet. It's implemented in JavaScript for a simple web playground. The interpreter is a simple tree walker which walks an AST generated by a recursive descent parser.
Making this was heavily inspired by Robert Nystron's book Crafting Interpreters after I implemented Lox in TypeScript.
void
value rather than null
. void
would be unassignable or unusable to prevent the use of that type.INPUT
native procedure isn't implemented yet, but it should be simple to make a nice interface for it since the interpreter already uses async/await.Shown below are a few sample programs in the style of code on the APCSP Exam.
PROCEDURE Fibonacci (n)
{
IF (n ≤ 1)
{
RETURN (n)
}
RETURN (Fibonacci (n - 1) + Fibonacci (n - 2))
}
i ← 1
REPEAT 10 TIMES
{
DISPLAY (Fibonacci (i))
i ← i + 1
}
list ← [1, 1]
REPEAT 10 TIMES
{
length ← LENGTH (list)
next ← list[length] * length
APPEND (list, next)
}
FOR EACH number IN list
{
DISPLAY (number)
}
PROCEDURE Add (x)
{
PROCEDURE AddX (y)
{
RETURN (x + y)
}
RETURN (AddX)
}
Add5 ← Add (5)
DISPLAY (Add5 (10))
This language has a lot of really weird aspects:
Operators | Associativity | Description |
---|---|---|
← |
Right | Assignment |
OR |
Left | Logical OR |
AND |
Left | Logical AND |
NOT |
Right | Logical NOT |
= , ≠ |
Left | Equality |
< , ≤ , > , ≥ |
Left | Comparison |
+ , - |
Left | Addition |
* , / , MOD |
Left | Multiplication |
- |
Right | Unary Negation |
..(..) , ..[..] |
Left | Calls or Indexes |
(...) |
Left | Parentheses |
There are a few additions to the original reference sheet in this implementation. These include but are not necessarily limited to:
"
. They can be concatenated, and adding strings with other types will cast those types to their string variants. Strings can be indexed (with 1-indexing to be consistent with lists) but can't be modified since they should act immutable. The LENGTH
procedure will return the length of a string. This pretty fun because strings make it possible to write programs to interpret esoteric languages like Brainf*ck.INPUT
procedure only says that it takes user input. The type for this procedure is not specified, so the user can choose whether they enter a string, number, or boolean.<
, ≤
, >
, and ≥
don't have specified types they should compare, so I was relatively lenient by allowing comparisons between two strings or two lists. Comparing two strings gives the same result as comparing two strings in JavaScript (their alphabetical order). Comparing lists will compare their length.AND
and OR
don't have a specified precendece on the reference sheet, but in most languages, OR
has a lower precedence than AND
, so that was added to the grammar.RETURN
ed, so everything is allowed. Allowing procedures to be returned has the side effect of adding closures.DISPLAY
procedure, so there were a few arbitrary decisions to support this.INSERT
, APPEND
, and REMOVE
, don't have a return value specified, so this interpreter returns the list after modification. The DISPLAY
procedure returns the displayed value.a ← 1 b ← 1
is equivalent to:
a ← 1
b ← 1
This has some implications for writing code, because it's possible to write write code like:
a ← 1
(4 + 5)
which looks like it should be two separate statements, but is actually equivalent to:
a ← 1(4 + 5)
which is clearly an error.
This is a slightly more formalized version of the grammar from the official reference sheet.
program : statements ;
statements : statement* ;
block : "{" statements "}" ;
statement : exprStmt
| procedureStmt
| ifStmt
| repeatStmt
| forEachStmt
| returnStmt ;
exprStmt : expr ;
ifStmt : "IF" "(" expr ")" block ( "ELSE" block )? ;
repeatStmt : "REPEAT" "UNTIL" "(" expr ")" block
| "REPEAT" expr "TIMES" block ;
forEachStmt : "FOR" "EACH" ID "IN" expr block ;
procedureStmt : "PROCEDURE" ID "(" params? ")" block ;
params : ID ( "," ID )* ;
returnStmt : "RETURN" "(" expr ")" ;
expr : ( ID | ( call "[" expr "]" ) ) ( "←" expr )
| or ;
or : and ( "OR" and )* ;
and : not ( "AND" not )* ;
not : ( "NOT" )? equality ;
equality : comparison ( ( "=" | "≠" ) comparison )* ;
comparison : arithmetic ( ( ">" | "≥" | "<" | "≤" ) arithmetic )* ;
arithmetic : term ( ( "+" | "-" ) term )* ;
term : factor ( ( "*" | "/" | "MOD" ) factor )* ;
factor : ( "-" )? call ;
call : primary ( ( "(" exprList? ")" ) | ( "[" expr "]" ) )* ;
primary : NUMBER
| ID
| STRING
| "[" exprList? "]"
| "(" expr ")" ;
exprList : expr ( "," expr )* ;
NUMBER : DIGIT+ ;
ID : ALPHA ( ALPHA | DIGIT )* ;
STRING : '"' [^"]* '"' ;
DIGIT : [0-9] ;
ALPHA : [a-zA-Z_] ;