Grammars


Lists of Numbers

 <radix10>     ==> <empty> | #d
 <radix2>      ==> #b

 <digit2>      ==> 0 | 1
 <digit10>     ==> <digit>
 <digit>       ==> 0 | 1 | ... | 9

 <number>      ==> <number2> | <number10>
 <number2>     ==> <radix2> <digit2>+
 <number10>    ==> <radix10> <digit10>+

 <token>       ==> <number> | `(' | `)'
 <whitespace>  ==> tab | space | newline

 <datum>       ==> <number> | <list>
 <list>        ==> `(' <datum>* `)'

Restrictions on R4RS tokens

R4RS tokens may contain anything from the normal R4RS grammar with the following simplification (allowd by R4RS):

<number>       ==> <sign> <digit>+
<sign>         ==> - | + | <empty>
<digit>        ==> 0 | 1 | ... | 9

So the whole token grammar is:

<token>        ==> <identifier> | <boolean> | <number>
                   | <character> | <string>
                   | ( | ) | #( | ' | ` | , | ,@ | .
<delimiter>    ==> <whitespace> | ( | ) | " | ;
<whitespace>   ==> <space or newline>
<comment>      ==> ; <all subsequent characters up to a line break>
<atmosphere>   ==> <whitespace> | <comment>
<intertoken space> ==> <atmosphere>*

<identifier>   ==> <initial> <subsequent>*
                   | <peculiar identifier>
<initial>      ==> <letter> | <special initial>
<letter>       ==> a | b | c | ... | z
<special initial> ==> ! | $ | % | & | * | / | : | < | =
                   | > | ? | ~ | _ | ^
<subsequent>   ==> <initial> | <digit>
                   | <special subsequent>
<digit>        ==> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<special subsequent> ==> . | + | -
<peculiar identifier> ==> + | - | ...

<number>       ==> <sign><digit>+
<sign>         ==> - | + | <empty>

<boolean>      ==> #t | #f
<character>    ==> #\ <any character>
                   | #\ <character name>
<character name> ==> space | newline


<string>       ==> " <string element>* "
<string element> ==> <any character other than " or \>
                   | \" | \\


Source Form

The following grammars are considered to be extensions to the normal R4RS grammar.

 <program>             ==> <expression>
 <expression>          ==> <reference> 
                         | <literal> 
                         | <procedure-call> 
                         | <lambda-expression> 
                         | <conditional> 
                         | <assignment> 
                         | <begin-expression>
                         | <derived expression>
 <reference>           ==> <variable>
 <begin-expression>    ==> ( begin <sequence> )
 <body>                ==> <sequence>
 <formals>             ==> ( <variable>* )
 <alternate>           ==> <expression>    
 <derived expression>  ==> ( let ( <binding spec>* )
                             <body> )
                         | ( letrec ( <binding spec>* )
                             <body> )

Core Form

 <begin-expression>    ==> ( begin <expression> <expression> )
 <body>                ==> <expression>
 <literal>             ==> <quotation>
 <derived expression>  ==> <empty>

Analyzed Form

 <lambda-expression>   ==> ( lambda <formals> 
                           ( quote ( assigned <variable>*) )
                           ( quote ( free     <variable>*) )
                           <body> )
 <literal>             ==> ( quote <immediate-datum> )
 <immediate-datum>     ==> ( ) | <boolean> | <number> | <character>
 <program>             ==> ( let ( <quotation-binding>* ) <expression> )
 <quotation-binding>   ==> ( <variable> (quote <heap-datum>) )
 <heap-datum>          ==> <symbol> | <string>
                         | ( <datum>+ )
                         | ( <datum>+ . <datum> )
                         | #( <datum>* )

Assignmentless Form

 <assignment>          ==> <empty>
 <lambda-expression>   ==> ( lambda <formals> ( quote ( free <variable>* ) )
                           <body> )

Immediate Literal Form

 <program>             ==> <symbol-less-program>
                         | ( ( lambda ( <variable>+ ) <symbol-less-program> )
                           <symbol-expression>+ )
 <symbol-expression>   ==> ( string->uninterned-symbol
                           ( string <character>+ ) )
 <symbol-less-program> ==> <expression>
                         | ( ( lambda ( <variable>+ ) <expression> )
                           <expression> )

Code-Generation Form

 <reference>           ==> ( bound <uinteger 10> <variable> )
                         | ( free <uinteger 10> <variable> )
 <lambda-expression>  ==> ( build-closure ( lambda <formals> <body> )
                           <reference>* )

Sparc Assembly Language (as Lists)

 <inst> ==>
     (ld   <reg-off> <reg>          )  ; load word                         
   | (st   <reg>     <reg-off>      )  ; store word                        
   | (ldb  <reg-off> <reg>          )  ; load byte                         
   | (stb  <reg>     <reg-off>      )  ; store byte                        
   | (set  <number>  <reg>          )  ; load immediate to register        
   | (mov  <reg>     <reg>          )  ; move register to register         
                                                                     
   | (sll  <reg> <reg-or-imm> <reg> )  ; logical left shift                
   | (srl  <reg> <reg-or-imm> <reg> )  ; logical right shift               
   | (sra  <reg> <reg-or-imm> <reg> )  ; arithmetic right shift            
   | (add  <reg> <reg-or-imm> <reg> )  ; addition                          
   | (sub  <reg> <reg-or-imm> <reg> )  ; subtraction                       
   | (and  <reg> <reg-or-imm> <reg> )  ; logical and                       
   | (or   <reg> <reg-or-imm> <reg> )  ; logical or                        
   | (andn <reg> <reg-or-imm> <reg> )  ; logical and-not                   
   | (smul <reg> <reg-or-imm> <reg> )  ; signed multiplication             
   | (sdiv <reg> <reg-or-imm> <reg> )  ; signed division                   
                                                                     
   | (nop                           )  ; nothing                           
   | (jmp  <reg>                    )  ; jump to address in register       
                                                                     
   | (cmp  <reg> <reg-or-imm>       )  ; compare (sets condition codes,    
                                       ;          used with branches)      
   | (ba   <label>                  )  ; branch always                     
   | (be   <label>                  )  ; branch if last compare was equal  
   | (bne  <label>                  )  ; branch if not equal               
   | (bl   <label>                  )  ; branch if less than               
   | (bge  <label>                  )  ; branch if not less than           
 
 <directive>  ==> (label <symbol>) | (comment <string>)                                                                         
 <reg>        ==> fp | cp | ap | ac | t1 | t2 | t3
 <reg-off>    ==> (<reg> <number>)
 <reg-or-imm> ==> <reg> | <number>

ehilsdal@cs.indiana.edu