SX-ALGOL: S-expression syntax for ALGOL 60

APL is like a diamond. It has a beautiful crystal structure; all of its parts are related in a uniform and elegant way. But if you try to extend this structure in any way—even by adding another diamond—you get an ugly kludge. LISP, on the other hand, is like a ball of mud. You can add any amount of mud to it and it still looks like a ball of mud.

— (attributed to) Joel Moses

SX-ALGOL is used as an intermediate representation in the Naur compiler, but can also be used to write programs directly. It is designed to look like procedure applications that build up the SX-ALGOL AST.

This document describes the BNF grammar of SX-ALGOL in the same terms as the Report. It is based off of an LL(1) grammar of ALGOL 60.

Some differences:

1. There are no named parameters, as they are not semantically important.
2. One-armed if is not allowed.
3. All types are explicit, and typeless procedures use typeless.

Basic grammar

⟨empty⟩ ::=

⟨identifier⟩ ::=

⟨A Scheme identifier⟩

⟨number⟩ ::=

⟨A Scheme number without complex or rational parts⟩

⟨string⟩ ::=

⟨A Scheme string⟩

Programs

⟨block⟩ ::=

(begin(⟨declaration list⟩)⟨statement list⟩)

⟨declaration list⟩ ::=

(⟨declaration⟩)⟨declaration list⟩

| ⟨empty⟩

⟨statement list⟩ ::=

⟨statement⟩⟨statement list⟩

| ⟨empty⟩

Declarations

⟨type name⟩ ::=

real

| integer

| Boolean

⟨type name or typeless⟩ ::=

⟨type name⟩

| typeless

⟨identifier list⟩ ::=

⟨identifier⟩⟨identifier list⟩

| ⟨empty⟩

⟨expression list⟩ ::=

⟨expression⟩⟨expression list⟩

| ⟨empty⟩

⟨type declaration⟩ ::=

⟨type name⟩⟨identifier list⟩

⟨declaration⟩ ::=

own⟨after own declaration⟩

| procedure⟨type name or typeless⟩⟨identifier⟩(⟨argument specification list⟩)⟨statement list⟩

| ⟨array declaration⟩

| ⟨type declaration⟩

| switch⟨identifier⟩⟨expression⟩⟨expression list⟩

| string⟨identifier⟩⟨identifier list⟩

Array declarations

⟨array declaration⟩ ::=

array⟨type name⟩(⟨identifier⟩⟨identifier list⟩)⟨expression pair list⟩

⟨expression pair list⟩ ::=

(⟨expression⟩⟨expression⟩)⟨expression pair list continue⟩

⟨expression pair list continue⟩ ::=

⟨expression pair list⟩

| ⟨empty⟩

Own declarations

⟨after own declaration⟩ ::=

⟨type declaration⟩

| ⟨array declaration⟩

Procedure declarations

⟨argument specification list⟩ ::=

(⟨specifier⟩⟨identifier⟩⟨identifier list⟩)⟨argument specification list⟩

| ⟨empty⟩

⟨specifier⟩ ::=

string

| array⟨type name⟩

| procedure⟨type name or typeless⟩

| ⟨type name⟩

| label

| switch

Statements

⟨statement⟩ ::=

(for⟨for statement next⟩)

| (if⟨expression⟩⟨statement⟩⟨statement⟩)

| (label⟨statement list⟩)

| ⟨unconditional statement⟩

⟨unconditional statement⟩ ::=

⟨block⟩

| (go to⟨expression⟩)

| (set!(⟨identifier⟩⟨identifier list⟩)⟨expression⟩)

| (⟨procedure statement⟩)

| ()

For statements

⟨for statement next⟩ ::=

⟨identifier⟩(⟨for element⟩⟨for element list⟩)⟨statement list⟩

⟨for element⟩ ::=

(step⟨expression⟩⟨expression⟩⟨expression⟩)

| (while⟨expression⟩⟨expression⟩)

⟨for element list⟩ ::=

⟨for element⟩⟨for element list⟩

| ⟨empty⟩

Procedure statements

⟨procedure statement⟩ ::=

⟨identifier⟩⟨expression list⟩

⟨expression list⟩ ::=

⟨expression⟩⟨expression list⟩

| ⟨empty⟩

Expressions

Boolean, arithmetic, and relational expressions are expressed in procedure form and hence omitted from the grammar.

⟨expression⟩ ::=

(if⟨expression⟩⟨expression⟩⟨expression⟩)

| (subscript⟨identifier⟩⟨expression⟩⟨expression list⟩)

| (⟨identifier⟩⟨expression list⟩)