Course Overview Nullable, First sets (starter sets), and Follow sets

[Pages:4]Course Overview

PART I: overview material

1 Introduction

2 Language processors (tombstone diagrams, bootstrapping)

3 Architecture of a compiler

PART II: inside a compiler

4 Syntax analysis

5 Contextual analysis

6 Runtime organization

7 Code generation

PART III: conclusion

8 Interpretation

9 Review

Syntax Analysis (Chapter 4)

1

Nullable, First sets (starter sets), and Follow sets

? A non-terminal is nullable if it derives the empty string

? First(N) or starters(N) is the set of all terminals that can begin a sentence derived from N

? Follow(N) is the set of terminals that can follow N in some sentential form

Next we will see algorithms to compute each of these.

Syntax Analysis (Chapter 4)

2

Algorithm for computing Nullable

For each terminal t

Nullable(t) = false

For each non-terminal N

Nullable(N) = is there a production N ::= ?

Repeat

For each production N ::= x1 x2 x3 ... xn If Nullable(xi) for all of xi then set Nullable(N) to true

Until nothing new becomes Nullable

Generalizing the definition of Nullable

Define Nullable(x1 x2 x3 ... xn) as: if n==0 then true else if !Nullable(x1) then false else Nullable(x2 x3 ... xn)

Syntax Analysis (Chapter 4)

3

Syntax Analysis (Chapter 4)

4

Algorithm for computing First sets

For each terminal t

First(t) = { t }

For each non-terminal N

First(N) = { }

Repeat

For each production N ::= x1 x2 x3 ... xn First(N) = First(N) First(x1) For each i from 2 through n If Nullable(x1 ... xi-1), then First(N) = First(N) First(xi)

Until no First set changes

Syntax Analysis (Chapter 4)

5

Generalizing the definition of First sets

Define First(x1 x2 x3 ... xn) as: if !Nullable(x1) then First(x1) else First(x1) First(x2 x3 ... xn)

Note: some textbooks add (empty string) to First(N)

whenever N is nullable, so that First(N) is never { } (empty set)

Syntax Analysis (Chapter 4)

6

1

Algorithm for computing Follow sets

Follow(S) = {$}

// the end-of-file symbol

For each non-terminal N other than S

Follow(N) = { }

Repeat

For each production N ::= x1 x2 x3 ... xn For each i from 1 through n-1

if xi is a non-terminal then Follow(xi) = Follow(xi) First(xi+1 ... xn)

For each i from n downto 1

if xi is a non-terminal and Nullable(xi+1 ... xn) then Follow(xi) = Follow(xi) Follow(N)

Until no Follow set changes

Syntax Analysis (Chapter 4)

7

Example of computing Nullable, First, Follow

S ::= TUVW | WVUT T ::= aT | e U ::= Ub | f V ::= cV | W ::= Wd |

Nullable?

S

false

T

false

U

false

V

true

W

true

First {a, e, d, c, f}

{a, e} {f}

{c} or {c, } {d} or {d, }

Follow {$} {f, $}

{c, d, $, a, e, b} {d, $, f} {$, c, f, d}

Syntax Analysis (Chapter 4)

8

Parsing

We will now look at parsing. Topics:

? Some terminology ? Different types of parsing strategies

? bottom up ? top down ? Recursive descent parsing ? What is it ? How to implement a parser given an EBNF specification

Syntax Analysis (Chapter 4)

9

Parsing: Some Terminology

? Recognition

To answer the question "does the input conform to the syntax of the language"

? Parsing

Recognition + also determine structure of program (for example by creating an AST data structure)

? Unambiguous grammar:

A grammar is unambiguous if there is only at most one way to parse any input. (i.e. for syntactically correct program there is precisely one parse tree)

Syntax Analysis (Chapter 4)

10

Different kinds of Parsing Algorithms

? Two big groups of algorithms can be distinguished:

? bottom up strategies

? top down strategies

? Example: parsing of "Micro-English"

SSeenntteennccee SSuubbjjeecctt OObbjjeecctt NNoouunn VVeerrbb

::::== SSuubbjjeecctt VVeerrbb OObbjjeecctt .. ::::== II || AA NNoouunn || TThhee NNoouunn ::::== mmee || aa NNoouunn || tthhee NNoouunn ::::== ccaatt || bbaatt || rraatt ::::== lliikkee || iiss || sseeee || sseeeess

The cat sees the rat. The rat sees me. I like a cat.

The rat like me. I see the rat. I sees a rat.

Syntax Analysis (Chapter 4)

11

Bottom up parsing

The parse tree "grows" from the bottom (leafs) up to the top (root).

Sentence

Subject

Object

Noun Verb

Noun

The cat sees a rat

.

Syntax Analysis (Chapter 4)

12

2

Top-down parsing

The parse tree is constructed starting at the top (root).

Sentence

Subject

Verb

Object

.

Noun

Noun

The cat sees a rat

.

Syntax Analysis (Chapter 4)

Quick review

? Syntactic analysis

? Lexical analysis ? Group letters into words (or group characters into tokens) ? Use regular expressions and deterministic FSM's

? Grammar transformations ? Left-factoring ? Left-recursion removal ? Substitution

? Parsing = structural analysis of program ? Group words into sentences, paragraphs, and documents (or tokens into expressions, commands, and programs) ? Top-Down and Bottom-Up

13

Syntax Analysis (Chapter 4)

14

Recursive Descent Parsing

? Recursive descent parsing is a straightforward top-down parsing algorithm.

? We will now look at how to develop a recursive descent parser from an EBNF specification.

? Idea: the parse tree structure corresponds to the recursive calling structure of parsing functions that call each other.

Syntax Analysis (Chapter 4)

15

Recursive Descent Parsing

SSeenntteennccee SSuubbjjeecctt OObbjjeecctt NNoouunn VVeerrbb

::::== SSuubbjjeecctt VVeerrbb OObbjjeecctt .. ::::== II || AA NNoouunn || TThhee NNoouunn ::::== mmee || aa NNoouunn || tthhee NNoouunn ::::== ccaatt || bbaatt || rraatt ::::== lliikkee || iiss || sseeee || sseeeess

Define a procedure parseN for each non-terminal N

pprriivvaatteevvooiiddppaarrsseeSSeenntteennccee(());; pprriivvaatteevvooiiddppaarrsseeSSuubbjjeecctt(());; pprriivvaatteevvooiiddppaarrsseeOObbjjeecctt(());; pprriivvaatteevvooiiddppaarrsseeNNoouunn(());; pprriivvaatteevvooiiddppaarrsseeVVeerrbb(());;

Syntax Analysis (Chapter 4)

16

Recursive Descent Parsing

ppuubblilciccclalassssMMicicrrooEEnngglilsishhPPaarrsseerr{{ pprriivvaatteeTTeerrmmininaalSlSyymmbboollccuurrrreennttTTeerrmmininaal;l; ////AAuuxxiliilaiarryymmeetthhooddsswwililllggoohheerree ...... ////PPaarrssininggmmeetthhooddsswwililllggoohheerree ......

}}

Syntax Analysis (Chapter 4)

Recursive Descent Parsing: Auxiliary Methods

ppuubblilciccclalassssMMicicrrooEEnngglilsishhPPaarrsseerr{{ pprrivivaatteeTTeerrmmininaalSlSyymmbbool lccuurrrreenntTtTeerrmmininaal;l; pprrivivaatteevvooididaacccceepptt((TTeerrmmininaalSlSyymmbbool leexxppeecctetedd)){{ ifif((ccuurrrreenntTtTeerrmmininaal lmmaatctchheesseexxppeecctetedd)) ccuurrrreenntTtTeerrmmininaal l==nneexxttininppuuttteterrmmininaal l;; eelslsee rreeppoorrttaassyynntataxxeerrrroorr }} ......

}}

17

Syntax Analysis (Chapter 4)

18

3

Recursive Descent Parsing: Parsing Methods

SSeenntteennccee ::::== SSuubbjjeecctt VVeerrbb OObbjjeecctt ..

pprrivivaatteevvooididppaarrsseeSSeenntetennccee(()){{ ppaarrsseeSSuubbjejecct(t());; ppaarrsseeVVeerrbb(());; ppaarrsseeOObbjejecct(t());; aacccceeppt(t(`.`'.)');;

}}

Syntax Analysis (Chapter 4)

19

Recursive Descent Parsing: Parsing Methods

SSuubbjjeecctt ::::== II || AA NNoouunn || TThhee NNoouunn

pprrivivaatteevvooididppaarrsseeSSuubbjejecct(t()){{

ifif((ccuurrrreenntTtTeerrmmininaal lmmaatctchheess`I`I')')

aacccceeppt(t(`I`I')');;

eelslseeifif((ccuurrrreenntTtTeerrmmininaal lmmaatctchheess` A` A')'){{

aacccceeppt(t(`A`A')');;

ppaarrsseeNNoouunn(());; }}

eelslseeifif((ccuurrrreenntTtTeerrmmininaal lmmaatctchheess`T`Thhee')'){{

aacccceeppt(t(`T`Thhee')');;

ppaarrsseeNNoouunn(());; }} eelslsee

rreeppoorrttaassyynntataxxeerrrroorr }}

Syntax Analysis (Chapter 4)

20

Recursive Descent Parsing: Parsing Methods

NNoouunn

::::== ccaatt || bbaatt || rraatt

pprrivivaatteevvooididppaarrsseeNNoouunn(()){{

ifif((ccuurrrreenntTtTeerrmmininaal lmmaatctchheess`c`caatt')') aacccceeppt(t(`c`caatt')');;

eelslseeifif((ccuurrrreenntTtTeerrmmininaal lmmaatctchheess`b`baatt')') aacccceeppt(t(`b`baatt')');;

eelslseeifif((ccuurrrreenntTtTeerrmmininaal lmmaatctchheess`r`raatt')') aacccceeppt(t(`r`raatt')');;

eelslsee rreeppoorrttaassyynntataxxeerrrroorr

}}

Syntax Analysis (Chapter 4)

21

Recursive Descent Parsing: Parsing Methods

OObbjjeecctt VVeerrbb

::::== mmee || aa NNoouunn || tthhee NNoouunn ::::== lliikkee || iiss || sseeee || sseeeess

pprrivivaatteevvooididppaarrsseeOObbjejecct(t()){{

??

}}

pprrivivaatteevvooididppaarrsseeVVeerrbb(()){{

??

}}

Test yourself: Can you complete parseObject( ) and parseVerb( ) ?

Syntax Analysis (Chapter 4)

22

Systematic Development of Rec. Descent Parser

(1) Express grammar in EBNF (2) Grammar Transformations:

Left factorization and Left recursion elimination

(3) Create a parser class with

? private variable currentToken ? methods to call the scanner: accept and acceptIt

(4) Implement a public method for main function to call:

? public parse method that ? fetches the first token from the scanner ? calls parseS (where S is start symbol of the grammar) ? verifies that scanner next produces the end?of?file token

(5) Implement private parsing methods:

? add private parseN method for each non terminal N

Syntax Analysis (Chapter 4)

23

4

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download