Original Grammar for Algebra Programs Change #1: Move ...

Original Grammar for Algebra Programs

::= *

::= () =

::= ( + )

::= ( ? )

::= ()

::= |

::= a variable name: f, x, y, z, ...

::= a number: 1, 42, 17, ...

Change step-by-step to Scheme

Change #1: Move Parens and Add "define"

::=

::=

::=

::=

::=

::=

::=

::=

*

(define ( ) )

(+ )

(? )

( )

|

a variable name: f, x, y, z, ...

a number: 1, 42, 17, ...

Open parenthesis for function call moved to before the function name

Change #1: Move Parens and Add "define"

::= *

::= (define ( ) )

::= (+ )

::= (? )

::= ( )

::= |

::= a variable name: f, x, y, z, ...

::= a number: 1, 42, 17, ...

+ and ? moved to initial position

Change #1: Move Parens and Add "define"

::= *

::= (define ( ) )

::= (+ )

::= (? )

::= ( )

::= |

::= a variable name: f, x, y, z, ...

::= a number: 1, 42, 17, ...

Definition use the define keyword, and parenthesis moved

1-6

Change #1: Move Parens and Add "define"

::=

::=

::=

::=

::=

::=

::=

::=

f(x) = (x + 1)

f((2 + 3))

*

(define ( ) )

(+ )

(? )

( )

|

a variable name: f, x, y, z, ...

a number: 1, 42, 17, ...

::=

::=

::=

::=

::=

::=

::=

::=

...

(+ *)

(? +)

(? *)

+

(/ )

(modulo )

(expt )

...

(+) ¡ú 0

...

(+ *)

(? +)

(? *)

+

(/ )

(modulo )

(expt )

...

(+ 1 2 3 7) ¡ú 13

(define (f x) (+ x 1))

(f (+ 2 3))

Change #2: Generalize + and -, Add Primitives

::=

::=

::=

::=

::=

::=

::=

::=

Change #2: Generalize + and -, Add Primitives

Change #2: Generalize + and -, Add Primitives

::=

::=

::=

::=

::=

::=

::=

::=

...

(+ *)

(? +)

(? *)

+

(/ )

(modulo )

(expt )

...

(? 1) ¡ú ?1

7-11

Change #2: Generalize + and -, Add Primitives

::=

::=

::=

::=

::=

::=

::=

::=

...

(+ *)

(? +)

(? *)

+

(/ )

(modulo )

(expt )

...

Change #2: Generalize + and -, Add Primitives

::=

::=

::=

::=

::=

::=

::=

::=

...

(+ *)

(? +)

(? *)

+

(/ )

(modulo )

(expt )

...

(?) ¡ú 1

(/ 2) ¡ú 1/2

Change #2: Generalize + and -, Add Primitives

Change #3: Generalize Defined Functions

::=

::=

::=

::=

::=

::=

::=

::=

...

(+ *)

(? +)

(? *)

+

(/ )

(modulo )

(expt )

...

::=

::=

::=

(define ( *) )

...

( *)

(define (f a b) (+ a b))

(f 1 2)

¡ú

(define (f a b) (+ a b))

3

(expt 13 20) ¡ú 19004963774880799438801

12-16

Change #3: Generalize Defined Functions

::=

::=

::=

(define ( *) )

...

( *)

... (define (0 1...k) 0) ...

... (0 1...k) ...

¡ú

... (define (0 1...k) 0) ...

... 3 ...

Change #4: Add Booleans

::=

::=

::=

::=

::=

::=

::=

::=

...

(and *)

(or *)

(zero? )

...

#f

#t

(and #t #f) ¡ú #f

where 3 is 0 with i replaced by i

Change #4: Add Booleans

Change #4: Add Booleans

::=

::=

::=

::=

::=

::=

::=

::=

::=

::=

::=

::=

::=

::=

::=

::=

...

(and *)

(or *)

(zero? )

...

#f

#t

(zero? 1) ¡ú #f

...

(and *)

(or *)

(zero? )

...

#f

#t

(zero? 0) ¡ú #t

17-21

Change #5: Add Symbols

::= ...

::=

::= (eq? )

::= ...

::= ¡¯

Change #5: Add Symbols

::=

::=

::=

::=

::=

...

(eq? )

...

¡¯

(eq? ¡¯a ¡¯a) ¡ú #t

(eq? ¡¯a ¡¯b) ¡ú #f

Change #6: Add Conditionals

Change #6: Add Conditionals

::=

::=

::=

::=

...

(cond *)

[ ]

[else ]

(cond [#t 1]) ¡ú 1

::=

::=

::=

::=

...

(cond *)

[ ]

[else ]

(cond [#f 1] [#t 2]) ¡ú (cond [#t 2])

(cond [#t 2]) ¡ú 2

22-28

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download