程序代写代做代考 Java PowerPoint Presentation

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