# LARA

## The Need for Follow

What if we have

X = Y Z | U

and U is nullable? When can we choose a nullable alternative (U)?

• if current token is either in first(U) or it could follow non-terminal X

t is in follow(X), if there exists a derivation containing substring X t

Example of language with 'named blocks':

statements ::= "" | statement statements
statement ::= assign | block
assign ::= ID "=" (ID|INT) ";"
block ::= "beginof" ID statements ID "ends"

Try to parse

beginof myPrettyCode
x = 3;
y = x;
myPrettyCode ends

Problem parsing 'statements':

• identifier could start alternative 'statement statements'
• identifier could follow 'statements', so we may wish to parse “”

Computing follow( ), given rule X =    • add first( ), if ,…, are all nullable
• add follow( ), if , …, are all nullable

Possible computation order:

• nullable
• first
• follow

Example: compute these values for grammar above

follow = {}
first
statements {ID, "beginof"}
statement  {ID, "beginof"}
assign     {ID}
block      {"beginof"}
follow
statements {ID}
statement  {ID, "beginof"}
assign     {ID, "beginof"}
block      {ID, "beginof"}

The grammar cannot be parsed because we have

statements ::= "" | statement statements

where

• statements nullable
• first(statements) follow(statements) = {ID} If the parser sees ID, it does not know if it should

• finish parsing 'statements' or
• parse another 'statement'