|
|
Formal Languages and Computability
(csc360)
Fall 2020
Dr. Gur Saran Adhar
Module 2: Context-Free Grammars
and their Normal Forms (Text: Chapters 3, 4)
Think of
yourself as a language processor. There are two parts of processing a
language: recognition, telling whether something is a legal sentence
of the language, and generation, producing legal structures of the
language. A language generator must "start" somewhere, and then
follow some "rules" that in a finite amount of time produces a
"string". The sequence of applications of some rule to produce a
string is called a derivation.
Regular
expressions can be viewed as language generators; they describe the rules for
producing strings using the operations "select", "repeat"
and "juxtapose". In this module we shall study a more complex type
of language generator, called context-free grammars. Context Free Grammar
are used to define most features in computer programming languages. Computer
programs written in any programming language must satisfy rigid criteria to
be syntactically correct and therefore amenable to interpretation by a
machine. Context-free grammars are used extensively in modeling the syntax of
programming languages. A compiler for a programming language must contain a parser,
an algorithm to determine whether a given string is in the language of the
grammar, and, if so, to construct the parse tree of the string. A
parse tree is a tree, rooted at a node labeled with the start symbol, and
whose leaves spell out a string of a language defined by the grammar that
produced the tree.
A parser
is top-down if the parse tree for the string is constructed top-down,
i.e., from the root down. Alternatively, if the parse tree is constructed
from the leaves to the root, it is said to be bottom-up . There is no
one best way to parse context-free languages, and different methods are
sometimes preferable for different grammars.
Context-free
grammars can be parsed efficiently. However, to be efficiently parsed, they
should be in an efficient format. In Chapter 5, we study ways of transforming
an arbitrary context-free grammar into an equivalent one (i.e., one that
generates the same language) that can be effectively parsed.
By the end
of this module, the student should know the following: How to construct and
apply context-free grammars and regular grammars Context Free Grammers
These
are some problems the student should be able to solve at the end of this
module:
- Use grammars to derive strings and produce derivation
trees. Sudkamp, Problem 3, page 82. Answer:
- a. S => SAB => SABAB => ABAB => aBAB
=> abBAB => abbBAB => abbAB => abbaAB => abbaaB =>
abbaabB => abbaab.
- b. S => SAB => SABAB => ABAB => aBAB
=> aAB => aaB => aa; or S => SAB => AB => aAB =>
aaB => aa.
- d. (a+b*)*
- Use set notation to describe the language of a
grammar. Sudkamp, Problem 6(e), p. 83.
- Solution: { a**n b**m | 0 < n <= m <= 2n }
- Construct a grammar for a language. Sudkamp, Problem
8, p. 83, Sudkamp, Problem 12, p. 84.
- Solution for problem 12. The grammar: S -> aSb |
bSa | SS | lambda will do.
- One solution for problem 8: S -> aScc | aAcc B
-> bBc | bc.
- Given a grammar, produce a regular expression for the
language defined by the grammar, Sudkamp, problem 14, p.84.
- a: a(a U b)*b
- b: a+b+
- c: a*bba*
- d: (a* U ba*b)*
- Understand the concept of ambiguity; Sudkamp, Problem
4, p. 111, Problem 5, p. 112. Solution for Problem 4:
- ambiguous grammar for a*: S -> aA | a | lambda, A
-> aA | lambda
- unambiguous grammar: S -> aS | lambda
Solution for Problem 5:
- L(G) = (a+b+)+
- unambiguous equivalent grammar: S -> aSb | SS |
ab
- Be able to trace the actions of the 4 parsing
techniques discussed in chapter 4; Sudkamp, Problems 15, 18, 21, 22, p.
114.
- Understand the purpose and mechanics of normalization
of grammars; Sudkamp, Problems 1, 7, 14, 18, pp. 147-150. Solution to
problem 18: S --> A'A | AC, A' --> a C -->BA', A --> AA | a,
B --> AD | B'B', D --> B'B.
|
