close

Вход

Забыли?

вход по аккаунту

?

Languages and Finite Automata

код для вставкиСкачать
Context-Free Languages
Fall 2006
Costas Busch - RPI
1
Context-Free Languages
n n
{ a b : n п‚і 0}
{ ww
R
}
Regular Languages
a*b*
Fall 2006
(a пЂ« b) *
Costas Busch - RPI
2
Context-Free Languages
Context-Free
Grammars
Pushdown
Automata
stack
automaton
Fall 2006
Costas Busch - RPI
3
Context-Free Grammars
Fall 2006
Costas Busch - RPI
4
Grammars
Grammars express languages
Example:
sentence
the English language grammar
п‚® noun _ phrase
noun _ phrase
predicate
Fall 2006
п‚® article
predicate
noun
п‚® verb
Costas Busch - RPI
5
article
п‚® a
article
п‚® the
noun
п‚® cat
noun
п‚® dog
verb п‚® runs
verb п‚® sleeps
Fall 2006
Costas Busch - RPI
6
Derivation of string “the dog walks”:
sentence
пѓћ noun _ phrase
predicate
пѓћ noun _ phrase
verb
пѓћ article
verb
пѓћ the
noun
noun
пѓћ the dog
verb
verb
пѓћ the dog sleeps
Fall 2006
Costas Busch - RPI
7
Derivation of string “a cat runs”:
sentence
пѓћ noun _ phrase
predicate
пѓћ noun _ phrase
verb
пѓћ article
verb
пѓћ a
noun
noun
пѓћ a cat
verb
verb
пѓћ a cat runs
Fall 2006
Costas Busch - RPI
8
Language of the grammar:
L = { “a cat runs”,
“a cat sleeps”,
“the cat runs”,
“the cat sleeps”,
“a dog runs”,
“a dog sleeps”,
“the dog runs”,
“the dog sleeps” }
Fall 2006
Costas Busch - RPI
9
Productions
noun
sentence
Variables
Fall 2006
Sequence of
Terminals (symbols)
п‚® cat
п‚® noun _ phrase
predicate
Sequence of Variables
Costas Busch - RPI
10
Another Example
Sequence of
terminals and variables
Grammar:
S п‚® aSb
S п‚® пЃ¬
Variable
Fall 2006
The right side
may be пЃ¬
Costas Busch - RPI
11
Grammar:
S п‚® aSb
S п‚® пЃ¬
Derivation of string ab :
S пѓћ aSb пѓћ ab
S п‚® aSb
Fall 2006
S п‚®пЃ¬
Costas Busch - RPI
12
Grammar:
S п‚® aSb
S п‚® пЃ¬
Derivation of string aabb :
S пѓћ aSb пѓћ aaSbb пѓћ aabb
S п‚®пЃ¬
S п‚® aSb
Fall 2006
Costas Busch - RPI
13
Grammar: S п‚® aSb
S п‚® пЃ¬
Other derivations:
S пѓћ aSb пѓћ aaSbb пѓћ aaaSbbb пѓћ aaabbb
S пѓћ aSb пѓћ aaSbb пѓћ aaaSbbb
пѓћ aaaaSbbbb
Fall 2006
пѓћ aaaabbbb
Costas Busch - RPI
14
Grammar:
S п‚® aSb
S п‚® пЃ¬
Language of the grammar:
n n
L пЂЅ { a b : n п‚і 0}
Fall 2006
Costas Busch - RPI
15
A Convenient Notation
*
We write:
S пѓћ aaabbb
for zero or more derivation steps
Instead of:
S пѓћ aSb пѓћ aaSbb пѓћ aaaSbbb пѓћ aaabbb
Fall 2006
Costas Busch - RPI
16
In general we write:
If:
*
w1 пѓћ w n
w1 пѓћ w 2 пѓћ w 3 пѓћ пЃЊ пѓћ w n
in zero or more derivation steps
Trivially:
Fall 2006
*
w пѓћ w
Costas Busch - RPI
17
Example Grammar
Possible Derivations
S п‚® aSb
*
SпѓћпЃ¬
S п‚® пЃ¬
*
S пѓћ ab
*
S пѓћ aaabbb
пЂЄ
пЂЄ
S пѓћ aaSbb пѓћ aaaaaSbbbb b
Fall 2006
Costas Busch - RPI
18
Another convenient notation:
S п‚® aSb
S п‚® aSb | пЃ¬
S п‚® пЃ¬
article
п‚® a
article
п‚® the
Fall 2006
article
Costas Busch - RPI
п‚® a | the
19
Formal Definitions
Grammar: G пЂЅ пЂЁV , T , S , P пЂ©
Set of
variables
Fall 2006
Set of
terminal
symbols
Start
variable
Costas Busch - RPI
Set of
productions
20
Context-Free Grammar: G пЂЅ (V , T , S , P )
All productions in P are of the form
A п‚® s
Variable
Fall 2006
String of
variables and
terminals
Costas Busch - RPI
21
Example of Context-Free Grammar
S п‚® aSb | пЃ¬
productions
P пЂЅ { S п‚® aSb , S п‚® пЃ¬ }
G пЂЅ пЂЁV , T , S , P пЂ©
V пЂЅ {S }
variables
Fall 2006
T пЂЅ { a , b}
terminals
Costas Busch - RPI
start variable
22
Language of a Grammar:
For a grammar G with start variable S
*
L ( G ) пЂЅ { w : S пѓћ w , w пѓЋ T *}
String of terminals or пЃ¬
Fall 2006
Costas Busch - RPI
23
Example:
context-free grammar G : S п‚® aSb | пЃ¬
n
L (G ) пЂЅ { a b
n
:
n п‚і 0}
Since, there is derivation
пЂЄ
n
S пѓћa b
Fall 2006
n
Costas Busch - RPI
for any
n п‚і 0
24
Context-Free Language:
A language L is context-free
if there is a context-free grammar G
with L пЂЅ L (G )
Fall 2006
Costas Busch - RPI
25
Example:
n
L пЂЅ {a b
n
:
n п‚і 0}
is a context-free language
since context-free grammar G :
S п‚® aSb | пЃ¬
generates L (G ) пЂЅ L
Fall 2006
Costas Busch - RPI
26
Another Example
Context-free grammar G :
S п‚® aSa | bSb | пЃ¬
Example derivations:
S пѓћ aSa пѓћ abSba пѓћ abba
S пѓћ aSa пѓћ abSba пѓћ abaSaba пѓћ abaaba
L (G ) пЂЅ { ww
R
: w пѓЋ { a , b }*}
Palindromes of even length
Fall 2006
Costas Busch - RPI
27
Another Example
Context-free grammar G :
S п‚® aSb | SS | пЃ¬
Example derivations:
S пѓћ SS пѓћ aSbS пѓћ abS пѓћ ab
S пѓћ SS пѓћ aSbS пѓћ abS пѓћ abaSb пѓћ abab
L (G ) пЂЅ { w : n a ( w ) пЂЅ n b ( w ),
Describes
matched
parentheses:
Fall 2006
and n a ( v ) п‚і n b ( v )
in any prefix
() ((( ))) (( ))
Costas Busch - RPI
v}
a пЂЅ (,
b пЂЅ)
28
Derivation Order
and
Derivation Trees
Fall 2006
Costas Busch - RPI
29
Derivation Order
Consider the following example grammar
with 5 productions:
1 . S п‚® AB
Fall 2006
2 . A п‚® aaA
4 . B п‚® Bb
3. A п‚® пЃ¬
5. B п‚® пЃ¬
Costas Busch - RPI
30
1 . S п‚® AB
2 . A п‚® aaA
4 . B п‚® Bb
3. A п‚® пЃ¬
5. B п‚® пЃ¬
Leftmost derivation order of string aab :
1
2
3
4
5
S пѓћ AB пѓћ aaAB пѓћ aaB пѓћ aaBb пѓћ aab
At each step, we substitute the
leftmost variable
Fall 2006
Costas Busch - RPI
31
1 . S п‚® AB
2 . A п‚® aaA
4 . B п‚® Bb
3. A п‚® пЃ¬
5. B п‚® пЃ¬
Rightmost derivation order of string aab :
1
4
5
2
3
S пѓћ AB пѓћ ABb пѓћ Ab пѓћ aaAb пѓћ aab
At each step, we substitute the
rightmost variable
Fall 2006
Costas Busch - RPI
32
1 . S п‚® AB
2 . A п‚® aaA
4 . B п‚® Bb
3. A п‚® пЃ¬
5. B п‚® пЃ¬
Leftmost derivation of aab :
1
2
3
4
5
S пѓћ AB пѓћ aaAB пѓћ aaB пѓћ aaBb пѓћ aab
Rightmost derivation of aab :
1
4
5
2
3
S пѓћ AB пѓћ ABb пѓћ Ab пѓћ aaAb пѓћ aab
Fall 2006
Costas Busch - RPI
33
Derivation Trees
Consider the same example grammar:
S п‚® AB
A п‚® aaA | пЃ¬
B п‚® Bb | пЃ¬
And a derivation of aab :
S пѓћ AB пѓћ aaAB пѓћ aaABb пѓћ aaBb пѓћ aab
Fall 2006
Costas Busch - RPI
34
B п‚® Bb | пЃ¬
A п‚® aaA | пЃ¬
S п‚® AB
S пѓћ AB
S
A
B
yield AB
Fall 2006
Costas Busch - RPI
35
B п‚® Bb | пЃ¬
A п‚® aaA | пЃ¬
S п‚® AB
S пѓћ AB пѓћ aaAB
S
A
a
Fall 2006
a
B
A
Costas Busch - RPI
yield aaAB
36
B п‚® Bb | пЃ¬
A п‚® aaA | пЃ¬
S п‚® AB
S пѓћ AB пѓћ aaAB пѓћ aaABb
S
A
a
a
B
A
B
b
yield aaABb
Fall 2006
Costas Busch - RPI
37
B п‚® Bb | пЃ¬
A п‚® aaA | пЃ¬
S п‚® AB
S пѓћ AB пѓћ aaAB пѓћ aaABb пѓћ aaBb
S
A
a
a
B
A
пЃ¬
Fall 2006
Costas Busch - RPI
B
b
yield
aa пЃ¬ Bb пЂЅ aaBb
38
B п‚® Bb | пЃ¬
A п‚® aaA | пЃ¬
S п‚® AB
S пѓћ AB пѓћ aaAB пѓћ aaABb пѓћ aaBb пѓћ aab
Derivation Tree
S
(parse tree)
A
a
a
B
A
B
b
yield
пЃ¬
Fall 2006
Costas Busch - RPI
пЃ¬
aa пЃ¬пЃ¬ b пЂЅ aab
39
Sometimes, derivation order doesn’t matter
Leftmost derivation:
S пѓћ AB пѓћ aaAB пѓћ aaB пѓћ aaBb пѓћ aab
Rightmost derivation:
S пѓћ AB пѓћ ABb пѓћ Ab пѓћ aaAb пѓћ aab
S
Give same
derivation tree
A
a
Fall 2006
a
Costas Busch - RPI
B
A
B
пЃ¬
пЃ¬
b
40
Ambiguity
Fall 2006
Costas Busch - RPI
41
Grammar for mathematical expressions
E п‚® EпЂ«E
| E пЂЄ E | (E ) | a
Example strings:
( a пЂ« a ) пЂЄ a пЂ« ( a пЂ« a пЂЄ ( a пЂ« a ))
Denotes any number
Fall 2006
Costas Busch - RPI
42
E п‚® EпЂ«E
| E пЂЄ E | (E ) | a
E пѓћ E пЂ«E пѓћ aпЂ«E пѓћ aпЂ«EпЂЄE
E
E
a
пЂ«
E
a
Fall 2006
пѓћ a пЂ« aпЂЄE пѓћ a пЂ« a*a
E
пЂЄ
A leftmost derivation
for a пЂ« a пЂЄ a
E
a
Costas Busch - RPI
43
E п‚® EпЂ«E
| E пЂЄ E | (E ) | a
E пѓћ EпЂЄE пѓћ E пЂ«EпЂЄE пѓћ aпЂ«EпЂЄE
пѓћ aпЂ« aпЂЄE пѓћ aпЂ« aпЂЄa
Another
leftmost derivation
for a пЂ« a пЂЄ a
E
a
Fall 2006
Costas Busch - RPI
E
E
пЂЄ
E
пЂ«
E
a
a
44
E п‚® EпЂ«E
E
E
a
пЂ«
E
a
Fall 2006
| E пЂЄ E | (E ) | a
Two derivation trees
for a пЂ« a пЂЄ a
E
пЂЄ
E
E
a
a
Costas Busch - RPI
E
E
пЂЄ
E
пЂ«
E
a
a
45
take a пЂЅ 2
a пЂ« a пЂЄa пЂЅ 2 пЂ« 2пЂЄ2
E
E
2
пЂ«
E
2
Fall 2006
E
E
пЂЄ
E
E
2
2
Costas Busch - RPI
E
пЂЄ
E
пЂ«
E
2
2
46
Good Tree
Bad Tree
2пЂ« 2пЂЄ2 пЂЅ 6
6
E
2
E
пЂ«
2
2
E
2
Fall 2006
2пЂ« 2пЂЄ2 пЂЅ 8
Compute expression result 8
E
using the tree
4
E
пЂЄ
2
E
2
E
2
2
Costas Busch - RPI
4
E
пЂЄ
2
E
пЂ«
2
E
2
2
47
Two different derivation trees
may cause problems in applications which
use the derivation trees:
• Evaluating expressions
• In general, in compilers
for programming languages
Fall 2006
Costas Busch - RPI
48
Ambiguous Grammar:
A context-free grammar G is ambiguous
if there is a string w пѓЋ L (G ) which has:
two different derivation trees
or
two leftmost derivations
(Two different derivation trees give two
different leftmost derivations and vice-versa)
Fall 2006
Costas Busch - RPI
49
Example: E п‚® E пЂ« E
| E пЂЄ E | (E ) | a
this grammar is ambiguous since
string a пЂ« a пЂЄ a has two derivation trees
E
E
E
a
пЂ«
E
a
Fall 2006
E
пЂЄ
E
E
a
a
Costas Busch - RPI
E
пЂЄ
E
пЂ«
E
a
a
50
E п‚® EпЂ«E
| E пЂЄ E | (E ) | a
this grammar is ambiguous also because
string a пЂ« a пЂЄ a has two leftmost derivations
E пѓћ E пЂ«E пѓћ aпЂ«E пѓћ aпЂ«EпЂЄE
пѓћ a пЂ« aпЂЄE пѓћ a пЂ« a*a
E пѓћ EпЂЄE пѓћ E пЂ«EпЂЄE пѓћ aпЂ«EпЂЄE
пѓћ aпЂ« aпЂЄE пѓћ aпЂ« aпЂЄa
Fall 2006
Costas Busch - RPI
51
Another ambiguous grammar:
IF_STMT п‚® if EXPR then STMT
|
if EXPR then STMT else STMT
Variables
Terminals
Very common piece of grammar
in programming languages
Fall 2006
Costas Busch - RPI
52
If expr1 then if expr2 then stmt1 else stmt2
IF_STMT
if
expr1
if
then
expr2
STMT
then
expr1
if
Fall 2006
then
expr2
else
stmt2
Two derivation trees
IF_STMT
if
stmt1
STMT
then
else
stmt2
stmt1
Costas Busch - RPI
53
In general, ambiguity is bad
and we want to remove it
Sometimes it is possible to find
a non-ambiguous grammar for a language
But, in general we cannot do so
Fall 2006
Costas Busch - RPI
54
A successful example:
Equivalent
Ambiguous
Grammar
Non-Ambiguous
Grammar
E п‚® E пЂ«E
E п‚® E пЂЄE
E п‚® (E )
E п‚® E пЂ« T |T
T п‚®T пЂЄF |F
F п‚® (E ) | a
E п‚® a
generates the same
language
Fall 2006
Costas Busch - RPI
55
E пѓћ E пЂ«T пѓћ T пЂ«T пѓћ F пЂ«T пѓћ aпЂ«T пѓћ aпЂ«T пЂЄF
пѓћ aпЂ« F пЂЄF пѓћ aпЂ« aпЂЄF пѓћ aпЂ« aпЂЄa
E
E п‚® E пЂ« T |T
пЂ«
T п‚®T пЂЄF |F
E
F п‚® (E ) | a
T
T
F
F
a
a
Unique
derivation tree
for a пЂ« a пЂЄ a
Fall 2006
Costas Busch - RPI
T
пЂЄ
F
a
56
An un-successful example:
n n m
n m m
L пЂЅ {a b c } пѓ€ {a b c }
n, m п‚і 0
L is inherently ambiguous:
every grammar that generates this
language is ambiguous
Fall 2006
Costas Busch - RPI
57
Example (ambiguous) grammar for L :
n n m
n m m
L пЂЅ {a b c } пѓ€ {a b c }
S п‚® S1 | S 2
Fall 2006
S 1 п‚® S 1c | A
S 2 п‚® aS 2 | B
A п‚® aAb | пЃ¬
B п‚® bBc | пЃ¬
Costas Busch - RPI
58
The string a n b n c n пѓЋ L
has always two different derivation trees
(for any grammar)
For example
S1
Fall 2006
S
S
S1
S2
c
a
Costas Busch - RPI
S2
59
Документ
Категория
Презентации
Просмотров
4
Размер файла
876 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа