Online Resources: So far I haven't found much online about grammars. Here are three files, though:

• originally from Rochester

Notation: The main concept has many different names: formal grammar or context-free (CF) grammar or Backus-Naur-Form (BNF) grammar.

A grammar is made up of a sequence of rules or productions. The rules are made up of symbols: non-terminals, terminals, and metasymbols. Each rule consists of a single non-terminal, followed by an arrow metasymbol, followed by a sequence of one or more terminals or non-terminals. The rules are used to make replacements one-by-one, to form a replacement sequence or a derivation. Each replacement consists of replacing a non-terminal on the left side of a rule with all the symbols on the right side. Replacements are made one-at-a-time until only a sequence of terminals remains, so that no more replacements are possible. The sequence is written with arrows using a double line, as shown beneath each of the examples in the text. Each grammar must have a special start symbol that is used as the start of every derivation.

The final sequence of terminals is said to be described or derived by the grammar. Notice that there can be infinitely many possible derived sequences, each finite in length. A sequence of terminals described by the grammar is called a sentence and the set of all possible sentences is called the language described by the grammar.

In addition to the derivation, one can also construct a parse tree corresponding to the derivation. Start with the start symbol as a root node, and insert a sub-tree corresponding to each replacement.

A leftmost derivation replaces the leftmost non-terminal at each stage, and similarly for a rightmost derivation. In case there is more than one parse tree (or more than one leftmost derivation, or more than one rightmost derivation) for any string of terminals described by the grammar, the grammar is said to be ambiguous. For most (pleasant) grammars, it is possible to disambiguate the grammar, either by rewriting it or by giving special disambiguating rules.

Recitation Problems:

1. In each case below give an informal description of the language defined by the given grammar. "Informal" means short and simple. One way to get started is to try various derivation sequences and get intuition about what sentences can be generated. For example, in 1.a. below, one can write A ==> a A c ==> a b c, or A ==> a A c ==> a a A c c ==> a a b c c, and so forth.

   1.            
           A ---> a A c                 (A is start symbol)
           A ---> b
         

   2. 
           O ---> a  |  a E             (O is start symbol)
           E ---> a O
         

   3. 
           S ---> A B                   (S is start symbol)
           A ---> a A  |  a
           B ---> b B c  |  b c
         

   4. (This one is hard! (It's just for fun.) Don't spend too much time on it.)

      
           S ---> a B  |  b A           (S is start symbol)
           A ---> a S  |  b A A  |  a
           B ---> b S  |  a B B  |  b   
         

2. Consider the following grammar for an assignment statement (A), with an operator ^ representing exponentiation):

   
   A    ---> <id> = E
   E    ---> E + T | E - T | T
   T    ---> T * S | T / S | S
   S    ---> F ^ S | F
   F    ---> ( E ) | <id>
   <id> ---> a | b | c | d | . . .
   

   1. What are the terminal symbols? The non-terminal symbols? The metasymbols?

   2. Give parse trees for each of the following sentences:
      1. d = a + b + c
      2. d = a ^ b ^ c
      3. d = a + b * c ^ d
      4. d = a * (b + c)

   3. What do the trees in ii. and iii. above say about the precedence and associativity of the new operator ^?

3. Lists of arbitrarily many items often come up in programming languages, using different separators, such as blanks, commas, or semicolons.
   1. For example, consider a language consisting of simple declarations of int identifiers, as in C or Java:

      
          int <id>;
          int <id>, <id>;
          int <id>, <id>, <id>;
      

      and so forth with any number of identifiers. (Here int is a reserved word, and <id> stands for an identifier token.) Write a simple (recursive) grammar for this language.

   2. There is a convenient notation that is often used with grammar rules: Use {items} to mean "zero or more repetitions of items", that is: items or items items or items items items, and so forth. Here items could be anything at all: a sequence of several symbols. Use this notation to describe the language in a. above in a simpler way.

4. A regular grammar has only rules of the form:

   A ---> a        (a any terminal)
   A ---> a B      (a any terminal, B any non-terminal)
   

   1. Write a regular grammar for identifiers.

   2. Write a regular grammar for integers.

   3. Here is an algorithm to convert any regular grammar to a finite state machine:
      1. For each non-terminal A, construct a circled state labeled with A.

      2. Construct and extra double circled terminal state T.

      3. For each rule A ---> a, draw an arrow labeled with a from the state labeled with A to the state labeled with T.

      4. For each rule A ---> b B, draw an arrow labeled with b from the state labeled with A to the state labeled with B.

      Convert the following regular grammar to a finite state machine:

      
      A ---> a A  |  a B  |  b B  |  b
      
      B ---> b B  |  c
      

   4. There is a very similar algorithm to convert a finite state machine to a regular grammar. Figure out the algorithm (you don't need to state it formally) and use it to convert the finite state machine for a C-style comment to a regular grammar. (See FSM here.)

   5. (This question is also hard!) Consider the following grammar:

      
      A ---> a A b  |  a b
      

      First give the language described by this grammar.

      Then argue that no finite state machine can describe this language. (If there are 10 states in the machine, consider the sentence with 11 a's followed by 11 b's. As the first 11 a's are processed, you must be in the same state twice. From this state you must be able to get to the final state as you use up the remaining a's and all the b's.) Thus this is not a regular grammar.

Key ideas: A formal grammar allows one to describe the syntax of a programming language in a formal (mathematical) way that is not subject to misinterpretations like an English description would be. These grammars are now essential descriptive tools but are also used to construct compilers.