COMP 320: Programming Languages

Exercises involving Real-World BNF Grammars

Useful resources for this set of exercises:

• Appendix A.13 and p. 53 from K&R, Second Edition (available in Kit)
• Jay Grammar (incomplete)
• Yacc input for subset Jay Grammar
• Wikipedia Intro to Syntax Diagrams
• Syntax Diagrams from Appendix D of Pascal: User Manual and Report by Jensen and Wirth (available in Kit)

Exercises

1. Looking at the (incomplete) grammar for Jay:
   • Find at least two Jay constructs that are not covered by this grammar.
   • How would you add those to the grammar?
   • Find at least one language construct that this grammar supports that is not part of the basic Jay language.
2. Looking at the grammar for C:
   • How can you tell the associativity (order of operation) for various operators (e.g., are multiple additions grouped left-to-right or right-to-left)? Work through how a concrete expression would be parsed, e.g., x + y - 32 + z
   • Find one binary operation whose associativity is not like the others. Does it make sense that it would be different? Thinking back to earlier discussions about C and other languages, it should be surprising that it’s even an operator (although not to us) – why do you think it was made an operator?
   • How can you tell the precedence of various operators? How could you use the grammar to derive the Precedence and Associativity of Operators table on p. 53 of K&R if I hadn’t given it to you (after the last page of the grammar)?
   • How does the grammar explain what is happening in the following common novice error:

            while ( i < 3 ) ;
            {
                printf("%d\n", i);
                i++;
            }

3. Comparing the two grammars:
   • Notice the different ways the two grammars specify operator precedence (e.g., is multiplication higher precedence than addition?) and associativity (e.g., are multiple additions grouped left-to-right or right-to-left?).
4. Why is it fair to consider the collection of Pascal diagrams a formal grammar? (See the Wikipedia entry on syntax diagrams and Appendix D from the Pascal: User Manual and Report on Kit for more information and examples of syntax diagrams.)