Positive Properties
of
Context-Free languages
Courtesy Costas Busch - RPI
1
Union
Context-free languages
are closed under:
Union
L1
is context free
L2
is context free
L1  L2
Courtesy Costas Busch - RPI
is context-free
2
Example
Language
Grammar
L1  {a b }
S1  aS1b | 
L2  {ww }
S2  aS2a | bS2b | 
n n
R
Union
L  {a b }  {ww }
n n
R
Courtesy Costas Busch - RPI
S  S1 | S2
3
In general:
For context-free languages
with context-free grammars
and start variables
The grammar of the union
has new start variable
and additional production
Courtesy Costas Busch - RPI
L1,
G1,
S1,
L2
G2
S2
L1  L2
S
S  S1 | S2
4
Concatenation
Context-free languages
Concatenation
are closed under:
L1
is context free
L1L2
L2
is context free
Courtesy Costas Busch - RPI
is context-free
5
Example
Language
Grammar
L1  {a b }
S1  aS1b | 
L2  {ww }
S2  aS2a | bS2b | 
n n
R
Concatenation
L  {a b }{ww }
n n
R
Courtesy Costas Busch - RPI
S  S1S2
6
In general:
For context-free languages
with context-free grammars
and start variables
L1,
G1,
S1,
L2
G2
S2
The grammar of the concatenation L1L2
S
has new start variable
and additional production S  S1S2
Courtesy Costas Busch - RPI
7
Star Operation
Context-free languages
Star-operation
are closed under:
L is context free
*
L is context-free
Courtesy Costas Busch - RPI
8
Example
Language
Grammar
L  {a b }
S  aSb | 
n n
Star Operation
L  {a b } *
n n
S1  SS1 | 
Courtesy Costas Busch - RPI
9
In general:
For context-free language
with context-free grammar
and start variable
L
G
S
The grammar of the star operation L *
S1
has new start variable
and additional production S1  SS1 | 
Courtesy Costas Busch - RPI
10
Negative Properties
of
Context-Free Languages
Courtesy Costas Busch - RPI
11
Intersection
Context-free languages
intersection
are not closed under:
L1
is context free
L2
is context free
L1  L2
Courtesy Costas Busch - RPI
not necessarily
context-free
12
Example
L1  {a b c }
L2  {a b c }
Context-free:
Context-free:
n n m
S  AC
A  aAb | 
C  cC | 
n m m
S  AB
A  aA | 
B  bBc | 
Intersection
L1  L2  {a b c } NOT context-free
n n n
Courtesy Costas Busch - RPI
13
Complement
Context-free languages
complement
are not closed under:
L is context free
L
Courtesy Costas Busch - RPI
not necessarily
context-free
14
Example
L1  {a b c }
L2  {a b c }
Context-free:
Context-free:
n n m
S  AC
A  aAb | 
C  cC | 
n m m
S  AB
A  aA | 
B  bBc | 
Complement
L1  L2  L1  L2  {a b c }
n n n
NOT context-free
Courtesy Costas Busch - RPI
15
Intersection
of
Context-free languages
and
Regular Languages
Courtesy Costas Busch - RPI
16
The intersection of
a context-free language and
a regular language
is a context-free language
L1
context free
L1  L2
L2
regular
context-free
Courtesy Costas Busch - RPI
17
Machine
Machine
M2
DFA for
L2
M1
NPDA for
L1
regular
context-free
Construct a new NPDA machine
that accepts L1  L2
M
simulates in parallel
M1
Courtesy Costas Busch - RPI
and
M
M2
18
NPDA
q1
DFA
M1
a, b  c
q2
a
p1
transition
M2
p2
transition
NPDA
M
q1, p1 a, b  c q2 , p2
transition
Courtesy Costas Busch - RPI
19
NPDA
q1
DFA
M1
, b  c
q2
M2
p1
transition
NPDA
M
q1, p1  , b  c q2 , p1
transition
Courtesy Costas Busch - RPI
20
NPDA
DFA
M1
M2
q0
p0
initial state
initial state
NPDA
M
q0 , p0
Initial state
Courtesy Costas Busch - RPI
21
NPDA
DFA
M1
p1
q1
final state
M2
p2
final states
NPDA
q1, p1
M
q1, p2
final states
Courtesy Costas Busch - RPI
22
Example:
context-free
L1  {w1w2 : | w1 || w2 |, w1 {a, b}*, w2 {c, d }*}
NPDA
a,   1
b,   1
M1
c,1  
d ,1  
q0  ,    q1  ,    q2  ,    q3
Courtesy Costas Busch - RPI
23
regular
*
L2  {a, c}
DFA
M2
a, c
p0
Courtesy Costas Busch - RPI
24
context-free
Automaton for: L1  L2  {a nc n : n  0}
NPDA
a,   1
q0 , p0
M
c,1  
 ,    q1, p0  ,    q2 , p0  ,   
Courtesy Costas Busch - RPI
q3 , p0
25
In General:
M
simulates in parallel
M1
and
M2
M accepts string w if and only if
M1
accepts string
w
M2
accepts string
w
and
L( M )  L( M1)  L( M 2 )
Courtesy Costas Busch - RPI
26
Therefore:
M is NPDA
L( M1)  L(M 2 )
L1  L2
is context-free
is context-free
Courtesy Costas Busch - RPI
27
Applications
of
Regular Closure
Courtesy Costas Busch - RPI
28
The intersection of
a context-free language and
a regular language
is a context-free language
L1
context free
Regular Closure
L1  L2
L2
regular
context-free
Courtesy Costas Busch - RPI
29
An Application of Regular Closure
Prove that:
n n
L  {a b : n  100, n  0}
is context-free
Courtesy Costas Busch - RPI
30
We know:
n n
{a b : n  0}
is context-free
Courtesy Costas Busch - RPI
31
We also know:
L1  {a
100 100
b
L1  {(a  b) }  {a
*
is regular
}
100 100
b
Courtesy Costas Busch - RPI
}
is regular
32
n n
{a b }
context-free
(regular closure)
n n
L1  {(a  b) }  {a
*
100 100
b
regular
{a b }  L1
n n
context-free
n n
{a b }  L1  {a b : n  100, n  0}  L
is context-free
Courtesy Costas Busch - RPI
33
}
Another Application of Regular Closure
Prove that:
L  {w : na  nb  nc }
is not context-free
Courtesy Costas Busch - RPI
34
If
L  {w : na  nb  nc }
is context-free
(regular closure)
Then
L  {a * b * c*}  {a b c }
context-free
n n n
regular
context-free
Impossible!!!
Therefore,
L is not context free
Courtesy Costas Busch - RPI
35
Decidable Properties
of
Context-Free Languages
Courtesy Costas Busch - RPI
36
Membership Question:
for context-free grammar
find if string w L(G )
G
Membership Algorithms: Parsers
• Exhaustive search parser
• CYK parsing algorithm
Courtesy Costas Busch - RPI
37
w L(G ) ?
38
The CYK Parser
Courtesy Costas Busch - RPI
39
The CYK Membership Algorithm
Input:
• Grammar
• String
G in Chomsky Normal Form
w
Output:
find if
w L(G )
Courtesy Costas Busch - RPI
40
The CYK Membership Algorithm
41
The CYK Membership Algorithm
42
43
The Algorithm
Input example:
• Grammar
G : S  AB
A  BB
Aa
B  AB
Bb
• String
w : aabbb
Courtesy Costas Busch - RPI
44
aabbb
a
a
b
b
aa
ab
bb
bb
aab
abb
bbb
aabb
abbb
b
aabbb
Courtesy Costas Busch - RPI
45
S  AB
A  BB
Aa
B  AB
Bb
a
A
a
A
b
B
b
B
aa
ab
bb
bb
aab
abb
bbb
aabb
abbb
b
B
aabbb
Courtesy Costas Busch - RPI
46
S  AB
A  BB
Aa
B  AB
Bb
a
A
a
A
b
B
b
B
aa
aab
ab
S,B
abb
bb
A
bbb
bb
A
aabb
abbb
b
B
aabbb
Courtesy Costas Busch - RPI
47
S  AB
A  BB
Aa
B  AB
Bb
a
A
a
A
b
B
b
B
aa
bb
A
bbb
S,B
bb
A
aab
S,B
ab
S,B
abb
A
aabb
A
abbb
S,B
b
B
aabbb
S,B
Courtesy Costas Busch - RPI
48
Therefore:
aabbb  L(G)
Time Complexity:
Observation:
3
| w|
The CYK algorithm can be
easily converted to a parser
(bottom up parser)
Courtesy Costas Busch - RPI
49
Empty Language Question:
for context-free grammar
find if L(G )  
G
Algorithm:
1. Remove useless variables
2. Check if start variable
Courtesy Costas Busch - RPI
S is useless
50
Infinite Language Question:
for context-free grammar
find if L(G ) is infinite
G
Algorithm:
1. Remove useless variables
2. Remove unit and

productions
3. Create dependency graph for variables
4. If there is a loop in the dependency graph
then the language is infinite
Courtesy Costas Busch - RPI
51
Example:
S  AB
A  aCb | a
B  bB | bb
C  cBS
Infinite language
Dependency graph
A
C
S
B
Courtesy Costas Busch - RPI
52
S  AB
A  aCb | a
B  bB | bb
C  cBS
S  AB  aCbB  acBSbB  acbbSbbb


S  acbbSbbb(acbb) S (bbb)

(acbb) S (bbb)
i
2
2
i
Courtesy Costas Busch - RPI
53
Undecidable CFL Problems
54
YACC
Yet Another Compiler Compiler
Courtesy Costas Busch - RPI
55
Yacc is a parser generator
Input:
A Grammar
Output: A parser for the grammar
Reminder: a parser finds derivations
Courtesy Costas Busch - RPI
56
Example grammar:
The yacc code:
expr -> ( expr )
| expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr
| - expr
| INT
;
expr : '(' expr ')'
| expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr
| - expr
| INT
;
Courtesy Costas Busch - RPI
57
Exampe Input:
10 * 3 + 4
Yacc Derivation:
expr => expr + expr => expr * expr + expr
=> 10*3 + 4
Courtesy Costas Busch - RPI
58
Resolving Ambiguities
%left '+', '-'
%left '*', '/'
%left UMINUS
%%
expr : '(' expr ')'
| expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr
| '-' expr
%prec UMINUS
| INT
;
Courtesy Costas Busch - RPI
59
Actions
%left '+', '-'
%left '*', '/'
%left UMINUS
%%
expr : '(' expr ')'
{$$ = $2;}
| expr '+' expr {$$ = $1 + $3;}
| expr '-' expr
{$$ = $1 - $3;}
| expr '*' expr
{$$ = $1 * $3;}
| expr '/' expr
{$$ = $1 / $3;}
| '-' expr
%prec UMINUS {$$ = -$2;}
| INT
{$$ = $1;}
;
Courtesy Costas Busch - RPI
60
A Complete Yacc program
%union{
int int_val;
}
%left '+', '-'
%left '*', '/'
%left UMINUS
%token <int_val> INT
%type <int_val> expr
%start program
%%
Courtesy Costas Busch - RPI
61
program : expr
{printf("Expr value = %d \n", $1);}
| error
{printf("YACC: syntax error near line %d \n", linenum);
abort();}
;
expr : '(' expr ')' {$$ = $2;}
| expr '+' expr {$$ = $1 + $3;}
| expr '-' expr {$$ = $1 - $3;}
| expr '*' expr {$$ = $1 * $3;}
| expr '/' expr {$$ = $1 / $3;}
| '-' expr
%prec UMINUS {$$ = -$2;}
| INT
{$$ = $1;}
;
%%
#include "lex.yy.c"
Courtesy Costas Busch - RPI
62
Execution Example
Input:
10 + 20*(3 - 4 + 25)
Output:
Expr value = 490
Courtesy Costas Busch - RPI
63
%{
int linenum=1;
int temp_int;
%}
%%
\n
The Lex Code
{linenum++;}
[\t ]
/* skip spaces */;
\/\/[^\n]* /* ignore comments */;
"+" {return '+';}
"-" {return '-';}
"*" {return '*';}
"/" {return '/';}
")" {return ')';}
"(" {return '(';}
Courtesy Costas Busch - RPI
64
[0-9]+ {sscanf(yytext, "%d", &temp_int);
yylval.int_val = temp_int;
return INT;}
. {printf("LEX: unknown input string found in line %d \n", linenum);
abort();}
Courtesy Costas Busch - RPI
65
Compiling:
yacc YaccFile
lex LexFile
cc y.tab.c -ly -ll -o myparser
Executable: myparser
Courtesy Costas Busch - RPI
66
Another Yacc Program
%union{
int int_val;
}
%left '+', '-'
%left '*', '/'
%left UMINUS
%token <int_val> INT
%type <int_val> expr
%start program
%%
Courtesy Costas Busch - RPI
67
program : stmt_list
| error
{printf("YACC: syntax error near line %d \n", linenum);
abort();}
;
stmt_list : stmt_list stmt
| stmt
;
stmt : expr ';'
;
{printf("Expr value = %d \n", $1);}
Courtesy Costas Busch - RPI
68
expr : '(' expr ')'
{$$ = $2;}
| expr '+' expr {$$ = $1 + $3;}
| expr '-' expr {$$ = $1 - $3;}
| expr '*' expr {$$ = $1 * $3;}
| expr '/' expr {$$ = $1 / $3;}
| '-' expr
%prec UMINUS {$$ = -$2;}
| INT
{$$ = $1;}
;
%%
#include "lex.yy.c"
Courtesy Costas Busch - RPI
69
Execution Example
Input:
10 + 20*(30 -67) / 4;
34 * 35 - 123 + -001;
17*8/6;
Output:
Expr value = -175
Expr value = 1066
Expr value = 22
Courtesy Costas Busch - RPI
70
Lex Code
%{
int linenum=1;
int temp_int;
%}
%%
\n
{linenum++;}
[\t ]
/* skip spaces */;
\/\/[^\n]* /* ignore comments */;
Courtesy Costas Busch - RPI
71
"+"
"-"
"*"
"/"
")"
"("
";"
{return '+';}
{return '-';}
{return '*';}
{return '/';}
{return ')';}
{return '(';}
{return ';';}
[0-9]+ {sscanf(yytext, "%d", &temp_int);
yylval.int_val = temp_int;
return INT;}
. {printf("LEX: unknown input string found in line %d \n", linenum);
abort();}
Courtesy Costas Busch - RPI
72
%union{
int int_val;
char *str_val;
}
Another Yacc Program
%left '+', '-'
%left '*', '/'
%left UMINUS
%token PRINT
%token NEWLINE
%token <str_val> STRING
%token <int_val> INT
%type <int_val> expr
%start program
%%
Courtesy Costas Busch - RPI
73
program : stmt_list
| error
{printf("YACC: syntax error near line %d \n", linenum);
abort();}
;
stmt_list : stmt_list stmt
| stmt
;
stmt : expr ';'
| PRINT expr ';'
| PRINT STRING ';'
| PRINT NEWLINE ';'
;
{printf("expression found\n");}
{printf("%d", $2);}
{printf("%s", $2);}
{printf("\n");}
Courtesy Costas Busch - RPI
74
expr : '(' expr ')' {$$ = $2;}
| expr '+' expr {$$ = $1 + $3;}
| expr '-' expr {$$ = $1 - $3;}
| expr '*' expr {$$ = $1 * $3;}
| expr '/' expr {$$ = $1 / $3;}
| '-' expr
%prec UMINUS {$$ = -$2;}
| INT
{$$ = $1;}
;
%%
#include "lex.yy.c"
Courtesy Costas Busch - RPI
75
Execution Example
Input:
Output:
print "The value of expression 123 * 25 is ";
print 123 * 25;
print newline;
10 + 5 * 8;
print "end of program";
print newline;
The value of expression 123 * 25 is 3075
expression found
end of program
Courtesy Costas Busch - RPI
76
Lex Code
%{
int linenum=1;
int temp_int;
char temp_str[200];
%}
%%
\n
{linenum++;}
[\t ]
/* skip spaces */;
\/\/[^\n]* /* ignore comments */;
Courtesy Costas Busch - RPI
77
"+"
{return '+';}
"-"
{return '-';}
"*"
{return '*';}
"/"
{return '/';}
")"
{return ')';}
"("
{return '(';}
";"
{return ';';}
"print" {return PRINT;}
"newline" {return NEWLINE;}
Courtesy Costas Busch - RPI
78
[0-9]+ {sscanf(yytext, "%d", &temp_int);
yylval.int_val = temp_int;
return INT;}
\"[^"\n]*\" {strncpy(temp_str, &(yytext[1]), strlen(yytext)-2);
temp_str[strlen(yytext)-2] = (char) 0;
yylval.str_val = temp_str;
return STRING;}
. {printf("LEX: unknown input string found in line %d \n", linenum);
abort();}
Courtesy Costas Busch - RPI
79
Descargar

Languages and Finite Automata