Parsing

Question 1

What is parsing?

Answer 1

The task of converting a program or other complex text into a parse tree

Question 2

How do we write code that can convert a grammar into a parser?

Answer 2

• Identify the terminals of the grammar (the concrete syntax of the language)
• Ensure that the resulting string of terminals is induced by the grammar (could have been generated)

Question 3

What are the two approaches to implementation?

Answer 3

Recursive descent

Table driven

Question 4

Describe the pipeline from source text to a parse tree

Answer 4

Source text
Tokeniser
Parser
Parse tree

Question 5

What is tokenisation?

Answer 5

The process that turns a sequence of characters into a symbol

Question 6

What are some advantages of describing the tokens using a FSA?

Answer 6

Small, tight, fast, low memory footprint

Only looking for simple things, so no back-tracking or other complicated operations

Question 7

Describe the approach of tokenisation using a FSA

Answer 7

Tokenise the input source, generating a stream of tokens for the grammar
Some tokens carry values with them
FSA keeps track of the characters it uses
Attaches them to the recognised symbol

Question 8

Describe recursive descent parsing

Answer 8

Treat each production as a small recogniser that looks at the token stream and tries to recognise itself
‘Try and see’ method (back up the token stream)

Question 9

Benefits of recursive descent parsing

Answer 9

Works with pretty much any grammar

Simple

Question 10

Disadvantages of recursive descent parsing

Answer 10

Deep stack of recursive calls
Slow
Potentially a lot of back tracking

Question 11

Describe table driven parsing

Answer 11

Start with the tokens
See which productions could have given rise to them
Build the tree as a constraints problem

Question 12

Advantages of table driven parsing

Answer 12

Smaller and faster than recursive descent
Little more sensitive to features of the
grammar
No need for back tracking

Question 13

Disadvantages of table driven parsing

Answer 13

Less clear

Can be tripped up by ambiguous grammars

Question 14

What are the two approaches to tokenisation?

Answer 14

Sub grammars

Finite state automata

Question 15

Advantages of using sub grammars for tokenisation

Answer 15

Just one thing to remember
Simply structure
Designed for pattern recognition

Question 16

Advantages of using FSA for tokenisation

Answer 16

Graphical, fast, and simple

Designed for simple patterns

Question 17

One important thing to remember about parsers

Answer 17

Parsers are a tool, nothing more and they often need to be tied together with other aspects

Question 18

Describe the ways to fix the dangling if problem

Answer 18

• make whitespace significant
• force else’s to every if statement
• force a block structure

Question 19

What does a production in a grammar become in a parser?

Answer 19

A function

Question 20

What is the responsibility of terminal recognisers during parsing?

Answer 20

Check if the current token in the token stream is the expected one

Question 21

What is the responsibility of non terminal recognisers during parsing?

Answer 21

Save and rewind the token stream

Check compound patterns, repetitions, etc

Question 22

What does logic do in the parsing process?

Answer 22

If token recognised, move past the tokens used

If not recognised, leave the tokens and try again

Question 23

What do table driven parses do with the grammar?

Answer 23

Convert it into a table and use that to drive a parser function

Question 24

What do recursive descent parsers do with the productions?

Answer 24

Turn them straight into code

Question 25

What is the goal of parsing?

Answer 25

To get from what a human can write to what a computer can execute with minimal pain

Question 26

What are the four functions needed in a recursive descent parser?

Answer 26

nextToken()
advanceTokenStream()
getTokenStreamPosition()
setTokenStreamPosition()