Context-free grammars (CFGs)
Roadmap
– 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
Last time
– RegExp == DFA
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 wheren>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:
• SupposethatthereexistsaDFAAforL()andAhas
N states
• A has to accept the string (N )N with some path
q0q1…qN…q2N+1
• Bythepigeonholeprinciplesomestatehasto
repeat: qi = qj for some i
Example
Example.class: Example.java IO.class
javac Example.java
IO.class: IO.java
javac IO.java
(tab)
Makefiles: Basic Structure
Example
Example.class: Example.java IO.class
javac Example.java
IO.class: IO.java
javac IO.java
(tab)
Makefiles: Basic Structure
(tab)
Example
Example.class depends on example.java and IO.class
Example.class: Example.java IO.class
javac Example.java
IO.class: IO.java
javac IO.java
Makefiles: Basic Structure
(tab)
Example
Example.class depends on example.java and IO.class
Example.class: Example.java IO.class
javac Example.java
IO.class: IO.java
javac IO.java
Example.class is generated by javac Example.java
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
Makefiles: Dependencies
Internal Dependency graph
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
Makefiles: Dependencies
Internal Dependency graph
Example.class
Example.java
IO.class
A file is rebuilt if one of it’s dependencies changes
Example
IO.java
Example.class: Example.java IO.class
javac Example.java
IO.class: IO.java
javac IO.java
Makefiles: Variables
You can thread common configuration values through your makefile
Makefiles: Variables
You can thread common configuration values through your makefile
Example
JC = /s/std/bin/javac JFLAGS = -g
Makefiles: Variables
You can thread common configuration values through your makefile
Example
JC = /s/std/bin/javac
JFLAGS = -g
Build for debug
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
Makefiles: Phony Targets • You can run commands via make
– Writeatargetwithnodependencies (called phony)
– Willcauseittoexecutethecommand every time
Example
clean:
rm –f *.class
test:
java –cp . Test.class
Makefiles: Phony Targets • You can run commands via make
– Writeatargetwithnodependencies (called phony)
– Willcauseittoexecutethecommand every time
Example
clean:
rm –f *.class
test:
java –cp . Test.class
Makefiles: Phony Targets • You can run commands via make
– Writeatargetwithnodependencies (called phony)
– Willcauseittoexecutethecommand every time
Example
clean:
rm –f *.class
test:
java –cp . Test.class
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