• Top-down:
• Predictive parsing
• Start with start symbol
• Try to derive string
• Bottop-up:
• Start with string
• Try to arrive at start symbol
• Use productions in reverse order

• Left-to-right
• Examine source string from left-to-right
• Right-to-left
• Start with last symbol and work your way backwards
• Not used for commpilers due to efficiency reasons

• First L means Left-to-right scan
• Second L means it constructs Leftmost defivation
• k is the k-symbol lookahead

Describing {"()", ...} using a regular expression is impossible as DFA statse have no memory

That is why Chomsky is used

• Type 3: Regular Languages
• Regular expressions, finite automata
• Type 2: Context-free languages
• CFGs, push-down automata
• Type 1: Context-Sensitive Languages
• CSGs (AB -> CB), LBAs
• Type 0: Recursive Enumerable
• Turing machine

Start with string S, select non-terminal n in string and one rule n -> s1,...sk and replace n by s1...sk - and repeat until you reach a string w with only terminal symbols

There can be Leftmost, rightmost derivations

• Leaves
• Terminal symbols
• Frontier: Generated string
• Internal nodes
• Non-terminal symbols
• Children: ordered, obtained using production rule
• Root
• Start symbol S

All productions of form A -> xB or A -> x

Regex/DFA/NFA 

• Given a string and a CFG, find a derivation for the string from the grammar or determine that no derivation exists
• Additional restrictions on CFGs are often required to facilitate efficient parsing
• Scan direction (right/left)
• Leftmost derivation -> reduces number of derivations
• Still ambiguous grammars exist

• Begins with the start symbol
• Parser code can be derived from the production rules of the grammar - one function for each nonterminal
• Left-to-right scanning
• Constructs a Left-most derivation
• Predict which production to apply based on current token and lookahead of next k tokens
• No backtracking -> requires unambiguous grammar
• LL(k) grammars are unambiguous
• Allows parsing in linear time
• Simple algorithm -> easy to understand and implement

How would you write this as a method in java/c?

[image]

• void S() { 
• switch (tok) {
• case IF: eat(IF); E(); eat(THEN); S(); eat(ELSE); S(); break;
• case BEGIN: eat(BEGIN); S(); L(); break;
• case PRINT: eat(PRINT); E(); break;
• default: error()
• }
• }

A type of top-down algorithm where we begin with the non-terminal, and we always try the rules for the non-terminal in order - needs backtracking in order to continue with the rules if one doesn't work.

Example with grammar:

E -> T | T + E

T -> int | int * T | (E)

Reading input  (int)

We start with (:

E would take us to T, and T would take us to int. int does not match '(', so we backtrack to T and we try again with the next one which is int * T, but it does not match either. So we backtrack with the last one and we get (E). '(' does match '(', so we go to the next element, which is int. We have E so we expand it to  T, then T is expanded to int - indeed int = int, so we proceed to the final one ')', which matches ')'.

• It is the set of terminal symbols that begin strings produced by y
• For a grammar with ε-productions, this is straightforward:
• FIRST(s) = {s} for s in T
• FIRST(A) = U First(B) for all A -> B
• FIRST(Ax) = FIRST(A) 
• FIRST(xA) = FIRST(x)

• It is the set of terminal symbols t that can immediately follow X, i.e. there exists a derivation from S -> ... -> aXnB

• For all non-terminals X do First(X) := {};
• For all terminals t do FIRST(t) := {t};
• DO
• For every production X->s1...sk 
• FIRST(X) := FIRST(X) U FIRST(S1);
• For i :=1 to k=1 do
• if nulllable(s1) then
• FIRST(X) := 
• FIRST(X) U FIRST(si+1);
• else exit;
• UNTIL NO MORE CHANGES

• for all non-terminals X do FOLLOW(X) := {};
• DO
• for every non-terminal X 
• for each production of the form A->yXB
• FOLLOW(X) := 
• FOLLOW(X) U FIRST(B);
• if nullable(B) then
• FOLLOW(X) := 
• FOLLOW(X) U FOLLOW(Y);
• UNTIL NO MORE CHANGES

• for all symbols x 
• nullablle(X) := false;
• DO
• change := false
• for every production X -> s1, ... sk
• if nullable(X) = false and s1 ...sk are nullabl
• nullable(X) := true;
• change := true;
• UNTIL CHANGE = FALSE

• Make table of applicable productions
• Rows: non-terminals X
• Columns: terminal symbols c (= next input token
• Production X-y is applicable iff
• c in FIRST(y) or
• NULLABLE(y) and c in FOLLOW(X)
• If more than one applicable production for some pair(X, c), then grammar is not LL(1).
• If no conflicts, to translate to java just one procedure per terminal as done in previous examples

• Compute Nullable, FIRST, and FOLLOW sets
• Compute predictive parsing table
• Generate parsing code if no conflicts(i.e. no duplicate entries in the parsing table)

• Ambiguous grammars
• Always lead to duplicate entres
• Either rewrite grammar without ambiguity or add a "disambiguating" rule:
• Where A -> x and A -> B are both applicable always use A -> x

• Let A -> X|B be productions of grammar G
• G is LL(1) iff:
• For no t in T, do both X and B derive strings that begin with t
• At most one of X and B is nullable
• If B is nullable, then X does not derive strings that begin with a in FOLLOW(A)

• Raise exception
• Insertion
• e.g. print error, pretend everything ok
• Deletion
• Skil until a token in FOLLOW is reached