Notes for 9/12/06  courtesy of Alan Crouch

CS 430

3:30 PM

 

Pre Discussion:

 

 

During Class Discussion:

 

BNF – Backus-Naur Form – (FORTRAN and ALGOL)

What does it do for us?  Discusses language and Grammar format (i.e. what statements are legal in the language)

Syntactic Categories – Articles, Nouns, Verbs, Adjectives, Sentence (all together make non-terminals)

            <Sentence> ::= <article> <adjective> < noun> <verb>

Grammar à Generate valid strings or check the validity of a sentence

Noam Chomsky – categorized grammars (regular, context sensitive, context free)

10 Mini-Languages ßCLICK TO SEE ACM ABSTRACT

 

Core

            5 Statement Types – Assignment, Selection, Iteration, Input and Output

            < >  = indicates non-terminals which need to be replaced

            |       = alternation (EBNF) Added to BNF  means OR

            Meta-symbols (written in different typeface)

                        Program, begin, end, ‘:’, ‘,’, ‘;’, input, output, while, loop. ‘(‘, ‘)’

            Note: comparison used in IF and WHILE

            Existing Operations

                        Assignment (=), comparison(< = ≠ >), Expression (+ -), A-Z, 0-9, ( )

 

See Syntax, Semantics (the meaning of the words in the order they are in) from the online book (marked in red)

 

Terminal Symbols à 0-9 + - * / =

Nonterminal symbols à calculation, expression, value, number, unsigned, digit, sign, operator

Start symbol à calculation

 

 

                                                            <calculation>

 


                                    <expression>                                        =

 


            <values>          <operator>       <expression>

 

            <number>                *              <value>

            <unsigned>                               <number>

 


<digit>             <unsigned>                   <unsigned>

 


     9                 <digit>                         <digit>

 


     7                                  4

 

Extended BNF  adds

            Alternation - OR

            Optionality -  [ ] 0 or 1   { } 0, 1, or many  

            Parentheses (  ) force ordering

 

 

Some additional discussion of FORTRAN

 

Homework :

 

            Mini-core Language Program

            Pg. 171 (6, 8, 10, 11)