▼DSSL2:   Data Structures Student Language
►1 Formal grammar
On this page:
1.1 Simplified grammar
8.18
  top  contents    up   

1 Formal grammar🔗ℹ

The DSSL2 language has a number of statement and expression forms, which are described in more depth below. Here they are summarized in Extended Backus-Naur Form. You can also find a simplified version of this grammar that omits contracts in the next section.

Non-terminal symbols are written in ⟨italic_with_pointies⟩, whereas terminal symbols are in colored typewriter. Conventions include:

  • { x }* for repetition 0 or more times

  • { x }+ for repetition 1 or more times

  • { x },* for repetition 0 or more times with commas in between

  • [ x ] for optional

The grammar begins by saying that a program is a sequence of zero or more statements, where a statement is either a simple statement followed by a newline, or a compound statement.

⟨program⟩

 

=

 

{ ⟨statement⟩ }*

 

 

⟨statement⟩

 

=

 

⟨simple⟩ NEWLINE

 

|

 

⟨compound⟩

 

 

⟨expr⟩

 

=

 

number

 

|

 

string

 

|

 

True

 

|

 

False

 

|

 

None

 

|

 

⟨lvalue⟩

 

|

 

⟨expr⟩ if ⟨expr⟩ else ⟨expr⟩

 

|

 

⟨expr⟩ ( { ⟨expr⟩ },* )

 

|

 

lambda { name },* : ⟨simple⟩

 

|

 

λ { name },* : ⟨simple⟩

 

|

 

struct_name { { name : ⟨expr⟩ },* }

 

|

 

[ { ⟨expr⟩ },* ]

 

|

 

[ ⟨expr⟩ ; ⟨expr⟩ ]

 

|

 

[ ⟨expr⟩ for [ name , ] name in ⟨expr⟩ [ if ⟨expr⟩ ] ]

 

|

 

⟨expr⟩ binop ⟨expr⟩

 

|

 

unop ⟨expr⟩

 

 

⟨simple⟩

 

=

 

assert ⟨expr⟩ ⟨opt_timeout⟩

 

|

 

assert_error ⟨expr⟩ [ , ⟨expr⟩ ] ⟨opt_timeout⟩

 

|

 

break

 

|

 

continue

 

|

 

⟨lvalue⟩ = ⟨expr⟩

 

|

 

⟨expr⟩

 

|

 

import ⟨mod_spec⟩

 

|

 

let name ⟨opt_ctc⟩ [ = ⟨expr⟩ ]

 

|

 

pass

 

|

 

return [ ⟨expr⟩ ]

 

|

 

⟨simple⟩ ; ⟨simple⟩

 

 

⟨lvalue⟩

 

=

 

name

 

|

 

⟨expr⟩ . name

 

|

 

⟨expr⟩ [ ⟨expr⟩ ]

 

 

⟨compound⟩

 

=

 

class name ⟨opt_cvars⟩ ⟨opt_implements⟩ : ⟨class_block⟩

 

|

 

def name ⟨opt_cvars⟩ ( { name ⟨opt_ctc⟩ },* ) ⟨opt_res_ctc⟩ : ⟨block⟩

 

|

 

if ⟨expr⟩ : ⟨block⟩ { elif ⟨expr⟩ : ⟨block⟩ }* [ else : ⟨block⟩ ]

 

|

 

interface name ⟨opt_cvars⟩ : ⟨interface_block⟩

 

|

 

for [ name , ] name in ⟨expr⟩ : ⟨block⟩

 

|

 

struct name : ⟨struct_block⟩

 

|

 

test [ ⟨expr⟩ ] ⟨opt_timeout⟩ : ⟨block⟩

 

|

 

time [ ⟨expr⟩ ] : ⟨block⟩

 

|

 

while ⟨expr⟩ : ⟨block⟩

 

 

⟨block⟩

 

=

 

⟨simple⟩ NEWLINE

 

|

 

NEWLINE INDENT { ⟨statement⟩ }+ DEDENT

 

 

⟨class_block⟩

 

=

 

NEWLINE INDENT { ⟨field_def⟩ }* { ⟨meth_proto⟩ : ⟨block⟩ }+ DEDENT

 

 

⟨interface_block⟩

 

=

 

pass

 

|

 

NEWLINE INDENT { ⟨meth_proto⟩ NEWLINE }+ DEDENT

 

 

⟨struct_block⟩

 

=

 

pass

 

|

 

NEWLINE INDENT { ⟨field_def⟩ }+ DEDENT

 

 

⟨meth_proto⟩

 

=

 

def name ⟨opt_cvars⟩ ( name { , name ⟨opt_ctc⟩ }* ) ⟨opt_res_ctc⟩

 

 

⟨field_def⟩

 

=

 

let name ⟨opt_ctc⟩ NEWLINE

 

 

⟨opt_timeout⟩

 

=

 

[ , time < ⟨expr⟩ ]

 

 

⟨opt_implements⟩

 

=

 

[ ( { name },* ) ]

 

 

⟨opt_ctc⟩

 

=

 

[ : ⟨ctc⟩ ]

 

 

⟨opt_res_ctc⟩

 

=

 

[ -> ⟨ctc⟩ ]

 

 

⟨opt_cvars⟩

 

=

 

[ [ { name },* ] ]

 

 

⟨ctc⟩

 

=

 

⟨expr⟩

 

 

⟨mod_spec⟩

 

=

 

mod_name

 

|

 

mod_string

 

 

binops are, from tightest to loosest precedence:

unops are ~, +, -, and not.

1.1 Simplified grammar🔗ℹ

This section presents a version of the DSSL2 grammar that is simplified by omitting contracts:

⟨statement⟩

 

=

 

⟨simple⟩ NEWLINE

 

|

 

⟨compound⟩

 

 

⟨expr⟩

 

=

 

number

 

|

 

string

 

|

 

True

 

|

 

False

 

|

 

None

 

|

 

⟨lvalue⟩

 

|

 

⟨expr⟩ if ⟨expr⟩ else ⟨expr⟩

 

|

 

⟨expr⟩ ( { ⟨expr⟩ },* )

 

|

 

lambda { name },* : ⟨simple⟩

 

|

 

λ { name },* : ⟨simple⟩

 

|

 

struct_name { { name : ⟨expr⟩ },* }

 

|

 

[ { ⟨expr⟩ },* ]

 

|

 

[ ⟨expr⟩ ; ⟨expr⟩ ]

 

|

 

[ ⟨expr⟩ for [ name , ] name in ⟨expr⟩ [ if ⟨expr⟩ ] ]

 

|

 

⟨expr⟩ binop ⟨expr⟩

 

|

 

unop ⟨expr⟩

 

 

⟨simple⟩

 

=

 

assert ⟨expr⟩ [ , time < ⟨expr⟩ ]

 

|

 

assert_error ⟨expr⟩ [ , ⟨expr⟩ ] [ , time < ⟨expr⟩ ]

 

|

 

break

 

|

 

continue

 

|

 

⟨lvalue⟩ = ⟨expr⟩

 

|

 

⟨expr⟩

 

|

 

import ⟨mod_spec⟩

 

|

 

let name [ = ⟨expr⟩ ]

 

|

 

pass

 

|

 

return [ ⟨expr⟩ ]

 

|

 

⟨simple⟩ ; ⟨simple⟩

 

 

⟨lvalue⟩

 

=

 

name

 

|

 

⟨expr⟩ . name

 

|

 

⟨expr⟩ [ ⟨expr⟩ ]

 

 

⟨compound⟩

 

=

 

class name [ ( { interface_name },* ) ] : ⟨class_block⟩

 

|

 

def name ( { name },* ) : ⟨block⟩

 

|

 

if ⟨expr⟩ : ⟨block⟩ { elif ⟨expr⟩ : ⟨block⟩ }* [ else : ⟨block⟩ ]

 

|

 

interface name : ⟨interface_block⟩

 

|

 

for [ name , ] name in ⟨expr⟩ : ⟨block⟩

 

|

 

struct name : ⟨struct_block⟩

 

|

 

test [ ⟨expr⟩ ] : ⟨block⟩

 

|

 

time [ ⟨expr⟩ ] : ⟨block⟩

 

|

 

while ⟨expr⟩ : ⟨block⟩

 

 

⟨block⟩

 

=

 

⟨simple⟩ NEWLINE

 

|

 

NEWLINE INDENT { ⟨statement⟩ }+ DEDENT

 

 

⟨class_block⟩

 

=

 

NEWLINE INDENT { ⟨field_def⟩ }* { ⟨meth_proto⟩ : ⟨block⟩ }+ DEDENT

 

 

⟨interface_block⟩

 

=

 

pass

 

|

 

NEWLINE INDENT { ⟨meth_proto⟩ NEWLINE }+ DEDENT

 

 

⟨struct_block⟩

 

=

 

pass

 

|

 

NEWLINE INDENT { ⟨field_def⟩ }+ DEDENT

 

 

⟨meth_proto⟩

 

=

 

def name ( name { , name }* )

 

 

⟨field_def⟩

 

=

 

let name NEWLINE

 

 

⟨mod_spec⟩

 

=

 

mod_name

 

|

 

mod_string

 

 

  top  contents    up