From Modern Programming Languages a practical introduction Exercise 1 Give a BNF

Question

From Modern Programming Languages a practical introduction

Exercise 1 Give a BNF grammar for each of the languages below. Show that you can derive a number of positive examples of the language in the constructed grammar below and also show that you are not able to derive a set of negative examples in the grammar below. (Please check textbook p. 24 for the full description of the questions.)

c) The set of all strings consisting of one or more instances of the letter a.

g) The set of all strings consisting of one or more instances of the letter a with a semicolon after each one.

j) The set of all strings consisting of an open bracket (the symbol ‘[‘) followed by a list of one or more digits separated by commas, followed by a closing bracket (the symbol ‘]’).

k) The set of all strings consisting of zero or more instances of the letter a, with a comma between each a and next. There should be no comma before the first or after the last.

Explanation / Answer

This will be “done right” in the next two chapters.

A context-free grammar (CFG) consists of

Example:

If no start symbol is specifically designated, the LHS of the first production is the start symbol.

2.2.2: Derivations

Watch how we can generate the input 7+4-5 starting with the start symbol, applying productions, and stopping when no productions are possible (we have only terminals).

This process of applying productions, starting with the start symbol and ending when only terminals are present is called a derivation and we say that the final string has been derived from the initial string (in this case the start symbol).

The set of all strings derivable from the start symbol is the language generated by the CFG

Given a grammar, parsing a string consists of determining if the string is in the language generated by the grammar. If it is in the language, parsing produces a derivation. If it is not, parsing reports an error.

The opposite of derivation is reduction. Given a production, the LHS produces the RHS (a derivation) and the RHS is reduced to the LHS (a derivation).

Homework: 1a, 1c, 2a-c (don't worry about justifying your answers).

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.