CPS 140 - Mathematical Foundations of CSDr. S. RodgerSection: LL Parsing (handout)LL(k) Parser:• top-down parser - starts with start symbol on stack, and repeatedly replace nonterminals until stringis generated.• predictive parser - predict next rewrite rule• first L of LL means - read input string left to right• second L of LL means - produces leftmost derivation• k - number of lookahead symbolsLL parsing process:• convert CFG to PDA (different method than before)• Use the PDA and lookahead symbols• Lookahead symbol is next symbol in input stringConvert CFG to NPDAIdea: To derive a string with a CFG, start with the start symbol and repeatedly apply production rulesuntil the string is derived. In order to simulate this process with an NPDA, start by pushing the startsymbol on the stack. Whenever a production rule A→w would be applied, the variable A should be on topof the stack. A is popped (or replaced) and the right hand side of the rule, w, is pushed onto the stack.Whenever a terminal is on top of the stack, if it matches the next symbol in the input string, then it ispopped from the stack. If it does not match, then this string is not in the language of the grammar. Ifstarting with the start symbol S, one can apply replacement rules, match all the terminals in the inputstring and empty the stack, then the string is in the language.The constructed NPDA:• Three states: s, q, fstart in state spush S on stack, move into qall rewrite rules in state q: If lhs of rewrite rule on top of stack, replace it with rhs of rewrite rule andstay in state qadditional rules in q to recognize nonterminals: read input symbol, pop input symbol, stay in state qpop z from stack, move into f, accept1Example:L = {anbbn: n ≥ 0} S → aSb | bA parsing routine for this grammar:symbol is the lookahead symbol and $ is the end of string marker.state = spush(S)state = qread(symbol) obtain the lookahead symbolwhile top-of-stack 6=zdocase top-of-stack ofS: if symbol == a then{pop(); push(aSb)} replace S by aSbelse if symbol == b then{pop(); push(b)} replace S by belse errora: if symbol 6= a, then errorelse {pop(); read(symbol)} pop a, get next lookaheadb: if symbol 6= b, then errorelse {pop(); read(symbol)} pop b, get next lookaheadend caseend whilepop() pop z from the stackif symbol 6= $ then errorstate = f2LL Parse Table - 2-dim arrayWhen the grammar is large, the parsing routine will have many cases. Alternatively, store the informationof which rule to apply in a table.• rows - variables• cols - terminals, $ (end of string marker)• LL[i,j] contains the rhs of a rule. This rhs is pushed onto the stack when the lhs of the rule is thevariable representing the ith row and the lookahead is the symbol representing the jth column.Example: Parse table forL = {anbbn: n ≥ 0}S → aSb | bA generic parsing routineIdea: To replace a variable on the top of the stack with its appropriate rhs, use the lookahead and the lhsto look up the rhs in the LL parse table. (LL[,] is the parse table.push(S)read(symbol) obtain the lookahead symbolwhile stack not empty docase top-of-stack ofterminal:if top-of-stack == symbolthen {pop(); read(symbol)} pop terminal and get next lookaheadelseerrorvariable:if LL[top-of-stack, symbol] 6= errorthen {pop() pop the lhspush(LL[top-of-stack,symbol])} push the rhselseerrorend caseend whileif symbol 6= $, then error3For previous example, try the following traces:Parse the string: aabbbParse the string: bExample:S → aSbS → ca b c $S aSb error c errorIn this example, it is clear that when S is on the stack and a is the lookahead, replace S by aSb. When S ison the stack and b is the lookahead, there is an error because there must be a c between the a’s and b’s.When S is on the stack and $ is the lookahead, then there is an error since S must be replaced by at leastone terminal. When S is on the stack, and c is the lookahead, then S should be replaced by c.Example:S → Ac | BcA → aAb | λB → bWhen the grammar has a λ-rule, it can be difficult to compute parse tables. In the example above, A candisappear (due to A → λ), so when S is on the stack, it can be replaced by Ac if either “a” or “c” are thelookahead or it can be replaced by Bc if “b” is the lookahead.We will use the following functions FIRST and FOLLOW to aid in computing the table.To construct an LL parse table LL[rows,cols]:1. For each rule A → w(a) For each a in FIRST(w)add w to LL[A,a](b) If λ is in FIRST(w)add w to LL[A,b] for each b in FOLLOW(A)where b∈T∪{$}2. Each undefined entry is error.4Example:S → aSc | BB → b | λWe have already calculated FIRST and FOLLOW for this Grammar:FIRST FOLLOWS a,b,λ $,cB b,λ $,cTo Compute the LL Parse Table for this example:• For S → aSc,FIRST(aSc) =• For S → B,FIRST(B) = {b, λ}FOLLOW(S) = {$, c}• For B → b,FIRST(b) =• For B → λFIRST(λ)=LL(1) Parse Table:a b c $Parse string: aaccAnother trace example:Trace aabccaaSSBbSScccccStack: S c c c c c c c csymbol:aaa’a’bbbcc’5where a’ is the second a in the string and symbol is the lookahead symbol. This table is an LL(1) tablebecause only 1 symbol of lookahead is needed.Example: Construct Parse Table for:L = {anbncamcbm: n ≥ 0,m≥0}S → AcBA → aAbA → λB → aBbB → cFIRST(A) =FIRST(S) =FIRST(B) =FOLLOW(A) =FOLLOW(S) =FOLLOW(B) =To compute the parse table:• For S → AcB,FIRST(AcB) =• For A → aAb,FIRST(aAb) =• For A → λ,FIRST(λ)=• For B → aBb,FIRST(aBb) =• For B → c,FIRST(c) =• All other entries are errors.6LL(1) Parse Table:a b c $parse string: abcacbparse string: ccparse string: abcab (not in language)Example:S → AcBA → aAbA → abB → aBbB → acbFIRST FOLLOWTry to construct LL(1) Parse tablea b c $7LL(2) Parse Table:aa ab ac a$ b c $S AcB AcB error error error error errorA aAb ab error error error error errorB aBb error acb error error error errorparse string: aabbcacbaaAA b bAbbbbb accccccc ccStack: S B B B B B B B B b b bsymbol:aaaaaaababbbbccaacaccbb$Example: L = {an: n ≥ 0}∪{anbn:n≥0}S→ AS→ BA→ aAA → λB → aBbB → λExample: L = {an:0≤n≤10}∪{anbn:0≤n≤10}Example: L = {anbbn: n ≥ 0}∪{anbn:n≥0}S→aSbS → bS →