Забыли?

?

# Context-Free Languages - University of Virginia

код для вставкиСкачать
```Lecture 11:
Parsimonious
Parsing
cs302: Theory of Computation
University of Virginia
Computer Science
David Evans
http://www.cs.virginia.edu/evans
вЂў Fix proof from last class
вЂў Interpretive Dance!
вЂў Parsimonious Parsing (Parsimoniously)
PS3 will be returned Tuesday
Lecture 11: Parsimonious Parsing
2
Closure Properties of CFLs
If A and B are context free languages then:
AR is a context-free language TRUE
A* is a context-free language TRUE
A is a context-free language (complement)?
A пѓ€ B is a context-free language TRUE
A пѓ‡ B is a context-free language ?
Lecture 11: Parsimonious Parsing
3
Complementing Non-CFLs
Lww = {ww | w пѓЋ ОЈ* } is not a CFL.
Is its complement?
What is
the actual
language?
Yes. This CFG recognizes is:
S п‚® 0S0 | 1S1 | 0X1 | 1X0
X п‚® 0X0 | 1X1 | 0X1 | 1X0 | 0 | 1 | Оµ
Bogus Proof!
S п‚® 0X1 п‚® 01X01 п‚®
Lecture 11: Parsimonious Parsing
4
0101 пѓЋ Lww
CFG for Lww (L )
пѓ�ww
All odd length strings are in Lпѓ�ww
S п‚® SOdd | SEven
SEven п‚® XY | YX
X п‚® ZXZ | 0
Y п‚® ZYZ | 1
Zп‚®0|1
SOdd п‚® 0R | 1R | 0 | 1
R п‚® 0SOdd | 1SOdd
How can we prove this is correct?
Lecture 11: Parsimonious Parsing
5
Sodd generates all
odd-length strings
SOdd п‚® 0R | 1R | 0 | 1
R п‚® 0SOdd | 1SOdd
Proof by induction on the length of the string.
Basis. SOdd generates all odd-length strings of
length 1. There are two possible strings: 0 and 1.
They are produces from the 3rd and 4th rules.
Induction. Assume SOdd generates all odd-length
strings of length n for n = 2k+1, k п‚і 0. Show it can
generate all odd-length string of length n+2.
Lecture 11: Parsimonious Parsing
6
SOdd generates all
odd-length strings
SOdd п‚® 0R | 1R | 0 | 1
R п‚® 0SOdd | 1SOdd
Induction. Assume SOdd generates all odd-length strings
of length n for n = 2k+1, k п‚і 0. Show it can generate all
odd-length string of length n+2.
All n+2 length strings are of the form abt where t is an nlength string and a пѓЋ {0, 1}, b пѓЋ {0, 1}. There is some
derivation from SOdd пѓћ* t (by the induction hypothesis). We
can generate all four possibilities for a and b:
00t: SOddп‚® 0R п‚® 00SOdd пѓћ* 00t
01t: SOddп‚® 0R п‚® 01SOdd пѓћ* 01t
10t: SOddп‚® 1R п‚® 10SOdd пѓћ* 10t
11t: SOddп‚® 1R п‚® 11SOdd пѓћ* 01t
Lecture 11: Parsimonious Parsing
7
CFG for Lww (L )
пѓ�ww
S п‚® SOdd | SEven
SEven п‚® XY | YX
X п‚® ZXZ | 0
Y п‚® ZYZ | 1
Zп‚®0|1
SOdd п‚® 0R | 1R | 0 | 1
R п‚® 0SOdd | 1SOdd
?
Proof-by-leaving-as-вЂњChallenge
ProblemвЂќ (note: you cannot use this
Lecture 11: Parsimonious Parsing
8
Even Strings
Show S generates the set
of all even-length strings
that are not in Lww.
Even
SEven п‚® XY | YX
X п‚® ZXZ | 0
Y п‚® ZYZ | 1
Zп‚®0|1
Proof by induction on the length of the string.
Basis. SEven generates all even-length strings of
length 0 that are not in Lww. The only length 0
string is Оµ. Оµ is in Lww since Оµ = ОµОµ, so Оµ should not be
generated by SEven. Since SEven does not contain any right
sides that go to Оµ, this is correct.
Lecture 11: Parsimonious Parsing
9
Closure Properties of CFLs
If A and B are context free languages then:
AR is a context-free language TRUE
A* is a context-free language TRUE
A is not necessarily a context-free
language (complement)
A пѓ€ B is a context-free language TRUE
A пѓ‡ B is a context-free language ?
Lecture 11: Parsimonious Parsing
10
Left for you to solve
(possibly on Exam 1)
Where is English?
0n1n
0n
Described by DFA, NFA,
RegExp, RegGram
w
Regular Languages
Context-Free Languages
Lecture 11: Parsimonious Parsing
11
0n1n2n
A
ww
English пѓЏ Regular Languages
The cat likes fish.
The cat the dog chased likes fish.
The cat the dog the rat bit chased likes fish.
вЂ¦
This is a pumping lemma proof!
Lecture 11: Parsimonious Parsing
12
= DFA
= CFG
ChomskyвЂ™s
(Syntactic
Structures,
1957)
Lecture 11: Parsimonious Parsing
13
вЂў Most linguists argue that most
natural languages are not contextfree
вЂў But, it is hard to really answer this
question:
e.g.,
вЂњThe cat the dog the rat bit chased likes fish.вЂќ пѓЋ English?
Lecture 11: Parsimonious Parsing
14
Where is Java?
0n1n
0n
Described by DFA, NFA,
RegExp, RegGram
w
Regular Languages
Context-Free Languages
Lecture 11: Parsimonious Parsing
15
0n1n2n
A
ww
Interpretive Dance
Lecture 11: Parsimonious Parsing
16
Where is Java?
0n1n
0n
Described by DFA, NFA,
RegExp, RegGram
w
Regular Languages
Context-Free Languages
Lecture 11: Parsimonious Parsing
17
0n1n2n
A
ww
What is the Java Language?
public class Test {
In the Java
public static void main(String [] a) {
Language
println("Hello World!");
}
Test.java:3: cannot resolve symbol
}
symbol : method println (java.lang.String)
// C:\users\luser\Test.java
public class Test {
Not in the Java
public static void main(String [] a) {
Language
println ("Hello Universe!");
}
Test.java:1: illegal unicode escape
}}
// C:\users\luser\Test.java
Lecture 11: Parsimonious Parsing
18
// C:\users\luser\Test.java
public class Test {
public static void main(String [] a) {
println ("Hello Universe!");
> javac Test.java
}
Test.java:1: illegal unicode escape
}}
// C:\users\luser\Test.java
Scanning error
^
Test.java:6: 'class' or 'interface' expected
}}
^
Parsing errors
Test.java:7: 'class' or 'interface' expected
Static semantic errors
Lecture 11: Parsimonious Parsing
^
Test.java:4: cannot resolve symbol
symbol : method println (java.lang.String)
location: class Test
println ("Hello World");
^
4 errors
19
Defining the Java Language
{ w | w can be generated by the CFG
for Java in the Java Language
Specification }
{ w | a correct Java compiler can build
a parse tree for w }
Lecture 11: Parsimonious Parsing
20
Parsing
Lecture 11: Parsimonious Parsing
+
M
M
M
T
T
3
2
3
*
T
1
+ 2 * 1
21
Parsing
Programming
languages
are (should be)
designed to make
parsing easy,
efficient, and
unambiguous.
S
Derivation
Sп‚® S+M|M
Mп‚®M*T | T
T п‚® (S) | number
S
Unambiguous
S п‚® S + S | S * S | (S) | number
S
S
3
S
+
S
S
2
3
*
S
S
1
3
+ 2 * 1
3
Lecture 11: Parsimonious Parsing
*
S
22
+
S
S
1
2
+ 2 * 1
Ambiguity
How can one determine if a CFG is ambiguous?
Super-duper-challenge problem: create a program that
solve the вЂњis this CFG ambiguousвЂќ problem:
Input: CFG
Output: вЂњYesвЂќ (ambiguous)/вЂњNoвЂќ (unambiguous)
(Not only can you not do this, it is impossible
for any program to do this.)
(We will cover undecidable
problems after Spring Break)
Lecture 11: Parsimonious Parsing
23
Parsing
Lecture 11: Parsimonious Parsing
+
M
M
M
T
T
3
2
3
*
T
1
+ 2 * 1
24
Parsing
Programming
languages
are (should be)
designed to make
parsing easy,
efficient, and
unambiguous.
S
Derivation
Sп‚® S+M|M
Mп‚®M*T | T
T п‚® (S) | number
S
вЂњEasyвЂќ and вЂњEfficientвЂќ
вЂў вЂњEasyвЂќ - we can automate the
process of building a parser from a
description of a grammar
вЂў вЂњEfficientвЂќ вЂ“ the resulting parser can
build a parse tree quickly (linear time
in the length of the input)
Lecture 11: Parsimonious Parsing
25
Recursive Descent
Parsing
Sп‚® S+M|M
Mп‚®M*T | T
T п‚® (S) | number
Parse() { S(); }
S() {
вЂў Easy to produce
try { S(); expect(вЂњ+вЂќ); M(); }
and understand
catch { backup(); }
вЂў Can be done for
try { M(); } catch {backup(); }
any CFG
error(); }
M() {
try { M(); expect(вЂњ*вЂќ); T(); } catch вЂ¦ Problems:
вЂў Inefficient (might
try { T(); } catch { backup(); }
not even finish)
error (); }
вЂў вЂњNondeterministicвЂќ
T() {
try { expect(вЂњ(вЂњ); S(); expect(вЂњ)вЂќ); } catch вЂ¦;
try { number(); } catch вЂ¦; }
Lecture 11: Parsimonious Parsing
26
вЂў A CFG is an LL(k) grammar if it can
be parser deterministically with п‚Ј
Sп‚® S+M|M
Mп‚®M*T | T
T п‚® (S) | number
1
Sп‚® S+M
Sп‚®M
LL(1) grammar
Lecture 11: Parsimonious Parsing
27
+
Sп‚® S+M
2
Parse() { S(); }
S() {
if (lookahead(1, вЂњ+вЂќ)) { S(); eat(вЂњ+вЂќ); M(); }
else { M();}
M() {
if (lookahead(1, вЂњ*вЂќ)) { M(); eat(вЂњ*вЂќ); T(); }
else { T(); } }
T() {
if (lookahead(0, вЂњ(вЂњ)) { eat(вЂњ(вЂњ); S(); eat(вЂњ)вЂќ); }
else { number();}
Sп‚® S+M|M
Mп‚®M*T | T
T п‚® (S) | number
Lecture 11: Parsimonious Parsing
28
JavaCC
https://javacc.dev.java.net/
вЂў Input: Grammar specification
вЂў Output: A Java program that is a
recursive descent parser for the
specified grammar
DoesnвЂ™t work for all CFGs: only for LL(k) grammars
Lecture 11: Parsimonious Parsing
29
Language Classes
Scheme
0n1n
0n1n2n
ww
0n
Described by DFA, NFA,
RegExp, RegGram
w
Regular Languages
Java
Python
Lecture 11: Parsimonious Parsing
30
Next Week
вЂў Monday (2): Office Hours
(Qi Mi in 226D)
вЂў Monday (5:30): TA help session
вЂў TuesdayвЂ™s class (Pieter Hooimeyer): starting
to get outside the yellow circle: using
grammars to solve security problems
вЂў Wednesday (9:30am): Office Hours (Qi Mi
in 226D)
вЂў Wednesday (6pm): TAsвЂ™ Exam Review
вЂў Thursday: exam in class
Lecture 11: Parsimonious Parsing
31
```
###### Документ
Категория
Презентации
Просмотров
7
Размер файла
1 220 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа