From Modern Programming Languages a practical introduction (2nd Edition) Exercis

Question

From Modern Programming Languages a practical introduction (2nd Edition)

Exercise 1 Give a BNF grammar as we have done in class for each of the descriptions below. Also show that you can derive a number of positive examples of the language in the constructed grammar and also show that you are not able to derive a set of negative examples in the grammar. (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

Components of a context-free grammar

A set of rules is the core component of a grammar.

Each rule has two parts: (1) a name and (2) an expansion of the name.

For instance, if we were creating a grammar to handle english text, we might add a rule like:

noun-phrase may expand into article noun.

from which we could ultimately deduce that "the dog" is a noun-phrase.

Or, if we were describing a programming language, we could add a rule like:

expression may expand into expression + expression

If we're working with grammars as mathematical objects, then instead of writing "may expand into," we'd simply write :

noun-phrase article noun
expression expression + expression

As an example, consider the classic unambiguous expression grammar:

exprterm+exprexprtermtermtermfactortermfactorfactor(expr)factorconstconstinteger

So, how do we know that 3 * 7 is a valid expression?

Because:

expr may expand into term;
which may expand into term * factor;
which may expand into factor * factor;
which may expand into const * factor;
which may expand into const * const;
which may expand into 3 * const;
which may expand into 3 * 7.

Backus-Naur Form (BNF) notation

When describing languages, Backus-Naur form (BNF) is a formal notation for encoding grammars intended for human consumption.

Many programming languages, protocols or formats have a BNF description in their specification.

Every rule in Backus-Naur form has the following structure:

name ::= expansion

The symbol ::= means "may expand into" and "may be replaced with."

In some texts, a name is also called a non-terminal symbol.

Every name in Backus-Naur form is surrounded by angle brackets, < >, whether it appears on the left- or right-hand side of the rule.

An expansion is an expression containing terminal symbols and non-terminal symbols, joined together by sequencing and choice.

A terminal symbol is a literal like ("+" or "function") or a class of literals (like integer).

Simply juxtaposing expressions indicates sequencing.

A vertical bar | indicates choice.

For example, in BNF, the classic expression grammar is:

Naturally, we can define a grammar for rules in BNF:

rule name ::= expansion
name < identifier >
expansion expansion expansion
expansion expansion | expansion
expansion name
expansion terminal

We might define identifiers as using the regular expression [-A-Za-z_0-9]+.

A terminal could be a quoted literal (like "+", "switch" or "<<=") or the name of a class of literals (like integer).

The name of a class of literals is usually defined by other means, such as a regular expression or even prose.

Extended BNF (EBNF) notation

Extended Backus-Naur form (EBNF) is a collection of extensions to Backus-Naur form.

Not all of these are strictly a superset, as some change the rule-definition relation ::= to =, while others remove the angled brackets from non-terminals.

More important than the minor syntactic differences between the forms of EBNF are the additional operations it allows in expansions.

Option

In EBNF, square brackets around an expansion, [ expansion ], indicates that this expansion is optional.

For example, the rule:

allows factors to be negated.

Repetition

In EBNF, curly braces indicate that the expression may be repeated zero or more times.

For example, the rule:

defines a conventional comma-separated argument list.

Grouping

To indicate precedence, EBNF grammars may use parentheses, (), to explictly define the order of expansion.

For example, the rule:

defines an expression form that allows both addition and subtraction.

Concatenation

In some forms of EBNF, the , operator explicitly denotes concatenation, rather than relying on juxtaposition.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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