CS 3721: Programming Languages Lab

The purpose of this recitation is to lead you through a few exercises of expressing the syntax of simple programming languages.

1. Define BNF for the following languages. Is your grammar ambiguous? If yes, rewrite to be non-ambiguous.

• All strings composed over the set of terminals {a, b, c}. Give an input string of the language and draw a parse tree and an AST for your sample input.
• All strings composed over the set of terminals {a, b, c} that start with b.
• All strings composed over the set of terminals { a, b, c} that start with b and end with c.
• All strings composed over the set of terminals { a, b, c} that have length >= 4. Give an input string of the language and draw a parse tree and an AST for your sample input.
• All strings composed over the set of terminals { a, b, c} that start with b and end with c, and have length >= 4.
• All strings composed over the set of terminals { a, b, c} that contain an odd number of tokens.

2. Give a context-free grammar for a small graph description language. The terminals of the language include all integers composed of digits ‘0’, ‘1’, …, ‘9’, ‘(‘, ‘)’, ‘;’ and ‘->’. Each node of the graph is represented by an integer number. Each edge is represented by a pair of nodes connected with ‘->’. For example, 3 -> 4 is an edge from node ‘3’ to node ‘4’. Each graph description is a sequence of edges surrounded by a pair of parentheses. Write down the meaning of each non-terminal used in your BNF. Give a parse tree and an abstract syntax tree for the input graph ( 1 -> 2; 2 -> 5; 5 -> 1)