# CS代考 10/6/21 – cscodehelp代写

10/6/21

The Parsing Process

COMP712 Programming Languages

AUT

1

A typical view of the compilation process:

parsing

Your Program

Lexical Analyser

Syntax Analyser

What is generated?

Symbol Table Parse Tree Tokens = terminal words

2

12

A typical view of the compilation process:

parsing

What happens next?

Code generation

Interpretation i.e walk the tree

3

Your Program

Lexical Analyser

Syntax Analyser

A typical view of the compilation process:

parsing

But the above does not say whether one performs a complete lexical analysis prior to performing syntax analysis or doing both simultaneously.

Your Program

Lexical Analyser

Syntax Analyser

4

34

Thus, we could have a two-pass parser:

1 pass

Or, a single pass parser: 1 pass

2 pass

In the previous lecture, we look at parsing from the LA standpoint. Now we look at it from the SA standpoint

5

Your Program

Lexical Analyser

Syntax Analyser

Syntax Analyser

Lexical Analyser

Your Program

Consider (single) parsing the simple Algol-like program:

Begin integer x, y; x := 5;

y := x;

:

Begin real y;

: end;

: End;

First, what does parsing means?

It means syntax analyser calls lexical analyser to get tokens and use them to build a parse tree immediately

6

56

1

10/6/21

Consider parsing the simple Algol-like program:

Begin integer x, y; x := 5;

y := x;

:

Begin real y;

: end;

: End;

What happens when you read “begin”?

LA finds the entry “begin” in the hash table

It returns s.begin to the SA

What happens next?

7

Consider parsing the simple Algol-like program:

Begin integer x, y; x := 5;

y := x;

:

Begin real y;

: end;

: End;

SA knows what s.begin means. So, what action is taken?

SA ignores s.begin and starts the tree building process.

SA initialises tree:

Tree

8

78

Consider parsing the simple Algol-like program:

Begin integer x, y; x := 5;

y := x;

:

Begin real y;

: end;

: End;

What happens when you read “integer”?

LA finds the entry “integer” in the hash table. Why? What does it return to SA?

s.integer

9

Consider parsing the simple Algol-like program:

Begin integer x, y; x := 5;

y := x;

:

Begin real y;

: end;

: End;

SA knows what s.integer means. So, what actions are taken?

SA sets declaration = true

SA sets decl_type = s.integer

Global variables

10

9 10

Consider parsing the simple Algol-like program:

Begin integer x, y; x := 5;

y := x;

:

Begin real y;

: end;

: End;

What happens when you read “x”?

LA looks for the entry “x” in the hash table

But it is not there!

11

LA creates an entry “x” in the symbol table:

Begin integer x, y; x:=5;

y := x;

:

:

Begin real y;

: : end;

End;

/ “x” Isthatall? No

P1P2 flags /

Flags:

It starts gathering its runtime properties

Declared: yes

Type: s.integer Reserved or user-defined Block level: 0

Offset: 0

12

11 12

2

10/6/21

Continue parsing the simple Algol-like program:

Begin integer x, y; x := 5;

y := x;

:

Begin real y;

: end;

: End;

What happens when you read “,”?

It returns s.comma to the SA

SA ignores s.comma and knows more declaration coming.

13

Continue parsing the simple Algol-like program:

Begin integer x, y; x := 5;

y := x;

:

Begin real y;

: end;

: End;

What happens when you read “y”?

LA looks for the entry “y” in the hash table

Again, it is not there!

14

13 14

Begin integer x, y; x := 5;

y := x;

:

:

Begin real y;

: end;

: End;

/

………

“x”

LA creates another entry in the symbol table.

/ “y” P1P2 flags /

Flags:

Declared: yes

Type: integer Reserved or user-defined Block level: 0

Offset: 1

15

Block level tells you that these variables are at the same level i.e using the same data frame.

Enter a new block level, you reset offset value to zero and increase block level by 1.

Exit a new block level, you reset offset value to the previous value and decrease block level by 1.

Offset value allows you to index its location on the stack.

16

15 16

Recall what is a data frame?

The memory required by your program

In this program, we need 2 locations at the outer block

To get x, you do:

Base address + offset of x

Begin integer x, y; x := 5;

y := x;

:

:

Begin real y;

:

y := 0.5*x; end;

: End;

y:

x:

17

Continue parsing the simple Algol-like program:

Begin integer x, y; x := 5;

y := x;

:

Begin real y;

: end;

: End;

What happens when you read “;”?

It returns s.semicolon to the SA

SA ignores it and sets decl_type = nil.

18

17 18

3

10/6/21

Continue parsing the simple Algol-like program:

Begin integer x, y; x := 5;

y := x;

:

Begin real y;

: end;

: End;

What happens when you read “x”?

LA finds the entry “x” in the hash table

It returns s.name and a pointer to its runtime properties in the symbol table to SA

19

SA gets s.name and a pointer to the symbol table:

Flags:

Declared: yes Type: s.integer user-defined

Block level: 0 Offset: 0

/ “x”

P1 P2

flags /

Since SA did not encounter s.integer or s.real or s.procedure, it knows declaration has finished. So, declaration := false. It now expects an operator next.

20

19 20

Continue parsing the simple Algol-like program:

Begin integer x, y; x := 5;

y := x;

:

Begin real y;

: end;

: End;

After reading x, what is read?

: not := and reading ”:”, what happens next?

It has to check if the next symbol is “=“ and if so, returns?

s.becomes to SA

21

SA gets s.becomes and starts to build the first sentence which is an assignment expression.

/ “x”

:= ………

/ “y”

s.name

Note where

this arrow is pointing to

P1P2 flags /

22

21 22

Continue parsing the simple Algol-like program:

Begin integer x, y; x := 5;

y := x;

:

Begin real y;

: end;

: End;

What happens when you read “5”?

LA returns the value 5 and its type s.integer to SA

SA knows the right hand side is an arithmetic expression. Call a function to build such a tree.

23

Continue parsing the simple Algol-like program:

Begin integer x, y; x := 5;

y := x;

:

Begin real y;

: end;

: End;

What happens when you read “;”?

LA returns s.semicolon to SA

SA knows end of statement reached.

24

23 24

4

10/6/21

SA now completes the assignment expression tree. It checks that variable x is of the right type.

/ “x”

………

/ “y” P1P2 flags /

s.name

:=

s.value 5

25

SA builds the first statement tree in the program

Tree

/ “x”

:= ………

/ “y”

x5

P1 P2 flags /

26

25 26

So, after parsing the whole program, the

tree looks like

……

/ “x”

………

/ “y”

P1 P2 flags /

Tree

First statement

:=

x

5

27

Begin integer x, y; x := 5;

y : = x;

:

:

Begin real y;

: end;

: End;

What happens at this point after reading “;”?

Again, SA can now create a tree for the legal sentence, y := x. Draw the tree.

28

27 28

References to x and y are as follows:

/ “x”

:= ………

/ “y”

yx

P1P2 flags /

29

Begin integer x, y; x := 5;

y := x;

:

:

Begin real y;

: end;

: End;

Current situation

/ “x”

………

/ “y” P1P2 flags /

What happens when y is read?

30

29 30

5

10/6/21

Begin integer x, y; x := 5;

y := x;

:

:

Begin real y;

: end;

: End;

You create a new descriptor for this “y”

/ “y”

flags /

flags /

Which entry is for real y and which is for integer y?

31

From this point, every time you access y, you get the runtime properties of real y.

Begin integer x, y; :

x := 5;

y := x;

:

:

Begin real y;

: end;

: End;

/ “y” flags

flags

Flags:

Declared: yes Type : real User-defined Block level: 1 Offset : 0

/ /

What happens at this point, after reading “;”?

Flags:

Declared: yes Type : integer User-defined Block level: 0 Offset : 1

32

31 32

Begin integer x, y; :

x := 5;

y := x;

:

:

Begin real y;

: end;

: End;

You de-reference all variables declared in that block

/ “y”

flags /

flags /

You are here

After de-referencing, how do you know that this descriptor is variable “y”

33

Begin integer x, y; :

x := 5;

y := x;

:

:

Begin real y;

: end;

: End;

/ “y”

flags /

flags /

You are here

Because you still have P2, pointing to its name.

34

33 34

Begin integer x, y; :

x := 5;

y := x;

:

:

Begin real y;

: end;

print (y);

: End;

/ “y”

flags /

flags /

Where is the y in print (y) pointing to?

35

What was the design issue we encountered so far?

It is a question of where variables exist and when they become accessible.

Technically, we are referring to the scope and extend of a variable.

36

35 36

6

10/6/21

What is the scope and extend of x?

Begin integer x, y; :

x := 5; y := x;

:

Begin real y; :

end;

print (y);

: End;

Scope of X

Extend of X

37

y?

Begin integer x, y; :

:

print (y);

: End;

x := 5; y := x;

What is

the

scope

and

extend

of end; y y integer

Begin real y; :

Scope Extend of of integer integer

38

37 38

Begin integer x, y; :

What is x := 5; the y := x;

scope :

and Begin real y;

extend : of real end;

Scope of real y

Extend of real y

y?

print (y);

: End;

39

In Java, you can do:

[lbl] start: alert(“Lather”); alert(“rinse”); goto start;

What is the implication of allowing goto’s (from the symbol table standpoint)?

Can’t see it?

40

39 40

How about this classic use of GOTO in C:

for ……

for ………..

if (breakout-condition)

goto final; :

final:

Can you now see the difficulty handing

goto’s? Youneedforwardreferencing! How do you handle forward referencing?

41

Forward Referencing

Need to provide provisionally declared descriptors

When encountering them, have to change these descriptors to “declared”

Have to look out for those that are genuinely not declared and hence generate appropriate error messages.

42

41 42

7

10/6/21

Hence, in language design, having increasingly sophisticated/liberal linguistic structures require an increasingly sophisticated compiler.

From now on, when you learn to use a new language, you do not only learn where you can declare variables but also what storage management is needed to support such methods for declaring variables in the language.

43

Parsing Theory

COMP712 Programming Languages

AUT

44

43 44

Earlier I said:

The SA gets a s.integer and it

knows what to do.

What exactly do I mean by that? In other words, how does the SA know what to do?

45

Before we begin, a bit of history:

The Fortran project undertaken by IBM led the change in attitude that a programming language is not about writing codes for a particular computer but rather for the communication of algorithms to computers.

However, it was Algol-60 that became the major force in this change of attitude and much of what we know about compilers came from the challenge posed by the task of constructing compilers for Algol-60.

46

45 46

Parsing

• The goal is to decide if a string is a legal instance of S

In other words, we need to know:

X := X + 5; is an arithmetic expression of L

But how? Follow the grammar of the language

47

Parsing

• Alternatively,incompilerterms,toshowthatthere is a parse tree whose root is S and whose leaves form

the string STR.

:=

• Parsingmaybeseenasa x + constructive proof process –

why? x5

X := X + 5;

A legal assignment statement

Because it attempts to prove the legality or otherwise of STR by constructing THE parse tree.

48

47 48

8

10/6/21

Parsing

• Whatif,wecouldconstructatree,outofseveral,to show that the string STR is legal?

• Thatmeansthegrammarisambigousandtheparser is a non-deterministic parser.

• Analternativeviewofparsingisthatitisnotaproof process that would say yes or no but a process that attempts to construct the most reasonable partial parse.

49

Parsing

• Discoveringthetreeamountstodiscovering appropriate application instances of the rules which comprise the grammar G. Recall the tutorial 4:

Provide one derivation for the sentence aaabbbccc from the grammar G:

1. SàaBC

2. SàaSBC

3. aBàab

4. bBàbb

5. CBàBC

6. bC àbc

7. cCàcc

50

49 50

Parsing

Provide one derivation for the sentence aaabbbccc from the grammar G:

1. SàaBC

2. SàaSBC

3. aBàab

4. bBàbb

5. CBàBC

6. bC àbc

7. cCàcc

Sà2 aSBCà2 aaSBCBCà1 aaaBCBCBCà3 aaabCBCBCà5 aaabBCCBCà4 aaabbCCBCà5 aaabbCBCC*à5 aaabbBCCC à4 aaabbbCCCà6 aaabbbcCC à7 aaabbbccCà7 aaabbbccc

At step 7(marked *) you use rule 5 to shift the B to the front and not rule 6 to convert bC to bc.

51

Recall this example too

The man

The man