Section 9.5 Formal Languages
795
BC
abc
Then we have to detect that this will not work and try something else. Parsing techniques automate this process and attempt to minimize the amount of false starts
and backtracking required.
Notice the distinction between generating members of a set, which the programmer does, and deciding membership in a set, which the compiler does. Since
we ask the compiler to decide membership in a set, a decision algorithm must exist
for the set. It turns out that decision algorithms do exist for context-free languages,
another point in their favor.
S e c t i o n 9 . 5 review
tecHniQueS
• Describe L(G) for a given grammar G.
• Define a grammar to generate a given language L.
• Construct parse trees in a context-free grammar.
main iDeaS
• A grammar G is a generating mechanism for its language L(G).
• Formal languages were developed in an attempt to
describe correct syntax for natural languages; although this attempt has largely failed because of the
complexity of natural languages, it has been quite
successful for high-level programming languages.
W
exeRciSeS 9.5
1. Describe L(G) for the grammar G = (V, V T , S, P) where V = 5a, A, B, C, S6, V T = 5a6, and P consists of
S S A
B S A
A S BC
aC S l
A S a
What type of grammar is this?
2. Describe L(G) for the grammar G = (V, V T , S, P) where V = 50, 1, A, B, S6, V T = 50, 16, and P consists of
S S 0A
A S 1BB
B S 01
S S 1A
B S 11
What type of grammar is this?
• Special classes of grammars are defined by restricting the allowable productions.
• The various types of formal languages correspond
to the sets recognized by various automata; in particular, (1) regular languages are the sets recognized
by finite-state machines, (2) context-free languages
are the sets recognized by pushdown automata,
(3) context-sensitive languages are the sets recognized by linear bounded automata, and (4) type 0
languages are the sets recognized by Turing machines.
• Derivations in context-free grammars can be illustrated by parse trees.
• A compiler for a context-free programming language checks correct syntax by parsing.
795
BC
abc
Then we have to detect that this will not work and try something else. Parsing techniques automate this process and attempt to minimize the amount of false starts
and backtracking required.
Notice the distinction between generating members of a set, which the programmer does, and deciding membership in a set, which the compiler does. Since
we ask the compiler to decide membership in a set, a decision algorithm must exist
for the set. It turns out that decision algorithms do exist for context-free languages,
another point in their favor.
S e c t i o n 9 . 5 review
tecHniQueS
• Describe L(G) for a given grammar G.
• Define a grammar to generate a given language L.
• Construct parse trees in a context-free grammar.
main iDeaS
• A grammar G is a generating mechanism for its language L(G).
• Formal languages were developed in an attempt to
describe correct syntax for natural languages; although this attempt has largely failed because of the
complexity of natural languages, it has been quite
successful for high-level programming languages.
W
exeRciSeS 9.5
1. Describe L(G) for the grammar G = (V, V T , S, P) where V = 5a, A, B, C, S6, V T = 5a6, and P consists of
S S A
B S A
A S BC
aC S l
A S a
What type of grammar is this?
2. Describe L(G) for the grammar G = (V, V T , S, P) where V = 50, 1, A, B, S6, V T = 50, 16, and P consists of
S S 0A
A S 1BB
B S 01
S S 1A
B S 11
What type of grammar is this?
• Special classes of grammars are defined by restricting the allowable productions.
• The various types of formal languages correspond
to the sets recognized by various automata; in particular, (1) regular languages are the sets recognized
by finite-state machines, (2) context-free languages
are the sets recognized by pushdown automata,
(3) context-sensitive languages are the sets recognized by linear bounded automata, and (4) type 0
languages are the sets recognized by Turing machines.
• Derivations in context-free grammars can be illustrated by parse trees.
• A compiler for a context-free programming language checks correct syntax by parsing.