PowerPoint Presentation
Context-free grammars (CFGs)
Roadmap
Last time
RegExp == DFA
Jlex: a tool for generating (Java code for) a lexer/scanner
Mainly a collection of regexp, action pairs
This time
CFGs, the underlying abstraction for parsers
Next week
Java CUP: a tool for generating (Java code for) a parser
Mainly a collection of CFG-rule, action pairs
regexp : JLex :: CFG : Java CUP
RegExps Are Great!
Perfect for tokenizing a language
However, they have some limitations
Can only define a limited family of languages
Cannot use a RegExp to specify all the programming constructs we need
No notion of structure
Let’s explore both of these issues
Limitations of RegExps
Cannot handle “matching”
E.g., language of balanced parentheses
L() = { (n )n where n > 0}
No DFA exists for this language
Intuition: A given FSM only has a fixed, finite amount of memory
For an FSM, memory = the states
With a fixed, finite amount of memory, how could an FSM remember how many “(“ characters it has seen?
Theorem: No RegExp/DFA can describe the language L()
Proof by contradiction:
Suppose that there exists a DFA A for L() and A has N states
A has to accept the string (N )N with some path q0q1…qN…q2N
By the pigeonhole principle some state has to repeat: qi = qj for some i
Example
Example.class: Example.java IO.class
javac Example.java
IO.class: IO.java
javac IO.java
(tab)
50
Makefiles: Basic Structure
Example
Example.class: Example.java IO.class
javac Example.java
IO.class: IO.java
javac IO.java
(tab)
51
Makefiles: Basic Structure
Example
Example.class: Example.java IO.class
javac Example.java
IO.class: IO.java
javac IO.java
(tab)
Example.class depends on example.java and IO.class
52
Makefiles: Basic Structure
Example
Example.class: Example.java IO.class
javac Example.java
IO.class: IO.java
javac IO.java
(tab)
Example.class depends on example.java and IO.class
Example.class is generated by
javac Example.java
53
Makefiles: Dependencies
Example
Example.class: Example.java IO.class
javac Example.java
IO.class: IO.java
javac IO.java
Example.class
Example.java
IO.class
IO.java
54
Makefiles: Dependencies
Example
Example.class: Example.java IO.class
javac Example.java
IO.class: IO.java
javac IO.java
Example.class
Example.java
IO.class
IO.java
Internal Dependency graph
55
Makefiles: Dependencies
Example
Example.class: Example.java IO.class
javac Example.java
IO.class: IO.java
javac IO.java
Example.class
Example.java
IO.class
IO.java
Internal Dependency graph
A file is rebuilt if one of it’s
dependencies changes
56
Makefiles: Variables
You can thread common configuration values through your makefile
57
Makefiles: Variables
You can thread common configuration values through your makefile
Example
JC = /s/std/bin/javac
JFLAGS = -g
58
Makefiles: Variables
You can thread common configuration values through your makefile
Example
JC = /s/std/bin/javac
JFLAGS = -g
Build for debug
59
Makefiles: Variables
You can thread common configuration values through your makefile
Example
JC = /s/std/bin/javac
JFLAGS = -g
Example.class: Example.java IO.class
$(JC) $(JFLAGS) Example.java
IO.class: IO.java
$(JC) $(JFLAGS) IO.java
Build for debug
60
Makefiles: Phony Targets
You can run commands via make
Write a target with no dependencies (called phony)
Will cause it to execute the command every time
Example
clean:
rm –f *.class
test:
java –cp . Test.class
61
Makefiles: Phony Targets
You can run commands via make
Write a target with no dependencies (called phony)
Will cause it to execute the command every time
Example
clean:
rm –f *.class
test:
java –cp . Test.class
62
Makefiles: Phony Targets
You can run commands via make
Write a target with no dependencies (called phony)
Will cause it to execute the command every time
Example
clean:
rm –f *.class
test:
java –cp . Test.class
63
Recap
We’ve defined context-free grammars
More powerful than regular expressions
Learned a bit about makefiles
Next time: we’ll look at grammars in more detail
/docProps/thumbnail.jpeg