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)

Academic Honesty!
It is not our intention to break the school's academic policy. Projects posted are only used as a reference and should not be submitted as is. We are not held liable for any misuse of the solutions. Please see the frequently asked questions page for further questions and inquiries.
Kindly fill out the form. Please provide a valid email address and we'll get back to you in less than 24 hours. We will be sending an invoice through PayPal upon confirmation. We are a non profit organization however we need an amount to keep this organization running, and to be able to complete our research and development.