Compilers (contd.)
Single procedure PN corr. to each non-term. N
PN is responsible for every occurrence of N and
Copyright By PowCoder代写 加微信 powcoder
only occurrences of N
Will use this approach for parsing, printing, execution
Obtain abstract parse tree
Pass root node to PS (S is starting non-term.)
Each PN gets most of the work done by procedures correspoding to the children of the nodes it receives as argument
Recursive Descent
Recursive Descent (contd.)
void execIf( ?? ) {
bool b = evalCond( ??);
if (b) then { execSS(??); return; }
else if (?alt?) then {execSS(??); return; }
else return; }
Non-term. at current node
Alternative at current node
Info about children nodes so we
move to them
Knowledge check:
How do we evaluate
How do we execute
A two-dimensional array representation of parse trees:
Each node in tree ↔ one row in array;
Each row has 5 columns:
Number corresponding to the
non-terminal at the particular node;
Number corresponding to alternative used;
The row numbers of children nodes.
Knowledge check:
How would the
A simple representation of PTs
Recursive Descent (contd)
void execIf( int n ) { // n is row no. of
bool b = evalCond( PT[n,3]); // PT is the parse tree array
if (b) then { execSS(PT[n,4]); return; }
else if (PT[n,2] == 2) then {execSS(PT[n,5]); return; }
else return; }
Knowledge check:
Why do we need PT[n,1]?
Why 5 columns in a row?
What about
void printIf( int n ) { // n: row no. of
// check PT[n,1] to see if this is
write(“if”);
printCond( PT[n,3]);
write(“then”);
printSS(PT[n,4]);
if (PT[n,2]==2) { write(“else”); printSS(PT[n,5]); }
write(“end;”); }
Recursive Descent (contd)
Knowledge check:
Don’t we have to evaluate the condition?
What if it is not an
Is that even possible?
void printAssign( int n ) { // n: row no. of
// check PT[n,1] to see if this is
printId( PT[n,3] ); write(“=”);
print Exp( PT[n,4]);
Recursive Descent (contd)
Knowledge check:
What is the bug in the code?
Slide 16 notes
How to do this in pure BNF? Using ε it is easy.
Without it, the number of productions increases quite a bit.
But using ε can cause problems for compilers. In homeworks, exams, etc. you may use it unless I say otherwise.
Relation to book: So far, mostly chapter 1; and 3.1., 3.2, 3.3; rest of chapter 3 not inclded.
We will move to chapter 4; that will lead us to the project.
A lot of this should be familiar from 321 and 625. But going over it again should make it easier to see how it relates to PLs and lang. implementations. The project also has some relation to 560.
void printAssign( int n ) { // n: row no. of
// check PT[n,1] to see if this is
printId( PT[n,3] ); write(“=”);
print Exp( PT[n,4]);
Recursive Descent (contd)
Knowledge check:
What is the bug in this code??
Slide 16 notes
How to do this in pure BNF? Using ε it is easy.
Without it, the number of productions increases quite a bit.
But using ε can cause problems for compilers. In homeworks, exams, etc. you may use it unless I say otherwise.
Relation to book: So far, mostly chapter 1; and 3.1., 3.2, 3.3; rest of chapter 3 not inclded.
We will move to chapter 4; that will lead us to the project.
A lot of this should be familiar from 321 and 625. But going over it again should make it easier to see how it relates to PLs and lang. implementations. The project also has some relation to 560.
void execAssign( int n ) { // n: row no. of
// check PT[n,1] to see if this is
int x = evalExp(PT[n,4]);
// Knowledge check: don’t we have to first take care of PT[n,3]?
assignIdVal(PT[n,3], x);
// Knowledge check: what about PT[n,2]? PT[n,5]?
Recursive Descent (contd)
Parsing is harder:
No tree to descend!
The trick:
Build the tree *as* you descend!
Calling procedure will create an “empty” node -by grabbing the next free row from the PT array- and pass it to the appropriate parse procedure
(Note: “t” is the (global) Tokenizer.)
void parseIf( int n ) { // node created by *caller*
PT[n,1] = 8;
string s = t.getToken(); // if s != “if” error!
PT[n,3] = nextRow++; // next free row; initialize?
parseCond(PT[n,3]);
PT[n,4] = nextRow++;
parseSS(PT[n,4]);
s = t.getToken(); if (s!=“else”) {return;}
t.skipToken(); PT[n,5]=nextRow++;
parseSS(PT[n,5]); return;
Recursive Descent Parsing
Knowledge Check:
Who is the caller?
What is the bug?
What is the bug?
What is the bug?
Why is this a bad representation?
Are there multiple reasons?
Knowledge Check
/docProps/thumbnail.jpeg
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com