Context-free grammars (CFGs)
Copyright By PowCoder代写 加微信 powcoder
– RegExp == DFA
– Jlex: a tool for generating (Java code for) a lexer/scanner
• Mainly a collection of 〈regexp, action〉 pairs
– CFGs, the underlying abstraction for parsers
– 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
– 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
• A has to accept the string (N )N with some path
q0q1…qN…q2N+1
• By the pigeonhole principle some state has to
repeat: qi = qj for some i
Example.class: Example.java IO.class
javac Example.java
IO.class: IO.java
javac IO.java
Makefiles: Basic Structure
Example.class: Example.java IO.class
javac Example.java
IO.class: IO.java
javac IO.java
Makefiles: Basic Structure
Example.class: Example.java IO.class
javac Example.java
IO.class: IO.java
javac IO.java
Example.class depends on example.java and IO.class
Makefiles: Basic Structure
Example.class: Example.java IO.class
javac Example.java
IO.class: IO.java
javac IO.java
Example.class depends on example.java and IO.class
Example.class is generated by
javac Example.java
Makefiles: Dependencies
Example.class: Example.java IO.class
javac Example.java
IO.class: IO.java
javac IO.java
Example.class
Example.java IO.class
Makefiles: Dependencies
Example.class: Example.java IO.class
javac Example.java
IO.class: IO.java
javac IO.java
Example.class
Example.java IO.class
Internal Dependency graph
Makefiles: Dependencies
Example.class: Example.java IO.class
javac Example.java
IO.class: IO.java
javac IO.java
Example.class
Example.java IO.class
Internal Dependency graph
A file is rebuilt if one of it’s
dependencies changes
Makefiles: Variables
You can thread common configuration values through
your makefile
Makefiles: Variables
You can thread common configuration values through
your makefile
JC = /s/std/bin/javac
JFLAGS = -g
Makefiles: Variables
You can thread common configuration values through
your makefile
JC = /s/std/bin/javac
JFLAGS = -g Build for debug
Makefiles: Variables
You can thread common configuration values through
your makefile
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
– Write a target with no dependencies
(called phony)
– Will cause it to execute the command
every time
rm –f *.class
java –cp . Test.class
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
rm –f *.class
java –cp . Test.class
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
rm –f *.class
java –cp . Test.class
• 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
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com