Bottom Up Parsing


steps
  1. Perform Go To operationGo To operationSteps: 1. Make sure that one grammar has only 1 production result by removing the OR (essentially splitting the grammar) 1. Add augmented grammar (added grammar than can result a start symbol) 1. Add numbers to each grammar except augmented grammar 1. Add . at the front of each production result (used for kernel method) 1. Use the kernel method starting from the top most grammar 1. Group the grammars 1. Input the thing after the . to each grammar and group them 1. If the result has a .
  2. Find FollowFollowcheat: terminal or symbol after the variable Algorithm 1. If S is the start symbol, ex: S -> Ab | c, then $ is the Follow value of S 1. If A -> αBβ, then all First of β is the Follow of B except ε 1. a. A -> αB, then all Follow of *A* is the Follow of B 1. b. A -> αBβ and First of β is ε, then all Follow of *A* is the Follow of B Special case If A -> α, i.e production result contains only 1 variable, add ε in front of the variable to conform to rule 3.a. A -> α\*B You can only find the value
  3. Create SLR Tablerules for creating SLR TableRows are the number of groups that have ex: i0-ix Columns are all the symbols, terminals, and variables If the input is a variable, input the number of the group it results to If input is a terminal or symbol, do the same as variable but add S before the number If there is a grammar that is completed (. is at the end) and is an augmented grammar, put accepted in the dollar column If its complete and NOT augmented grammar , check i0 which line does it correspond / similar to, and use R + l
  4. Searchhow to do parsing search for bottom upThe first stack is the first group 0 and add $ AFTER it Input will be given and add $ AFTER it How to determine the output? * By comparing the left most of the stack and the left most of the input rules * if the output is SX then append number X as the left most of the stack, followed by the input that resulted the output and the stack from the previous operation when input is moved to the stack, it gets removed from the input * If the output is RX then replace the production result of through parsing

no need to remove Left RecursiveLeft RecursiveA -> Aα | β A -> βA' A' -> αA' | ε E -> E + T | E - T | T | C A -> A α A α β β E -> TE' | CE' E' -> +TE' | -TE' | ε A no longer exists and is now A' placed at the end of β at the top and α at the bottom min 1 α and 1 β Status: #idea Tags: compilation-techniques References

Example Alvina Aulia Bottom Up Parsing

  1. E -> E + T | T
  2. T -> T * F | F
  3. F -> (E) | id

Perform Go To operationGo To operationSteps: 1. Make sure that one grammar has only 1 production result by removing the OR (essentially splitting the grammar) 1. Add augmented grammar (added grammar than can result a start symbol) 1. Add numbers to each grammar except augmented grammar 1. Add . at the front of each production result (used for kernel method) 1. Use the kernel method starting from the top most grammar 1. Group the grammars 1. Input the thing after the . to each grammar and group them 1. If the result has a .:

i0:
E' -> .E

  1. E -> .E + T
  2. E -> .T
  3. T -> .T * F
  4. T -> .F
  5. F -> .(E)
  6. F -> .id

(Input E to i0)

i1:
E' -> E.

  1. E -> E. + T

(Input T to i0)

i2: 2. E -> T.

  1. T -> T. * F

(Input F to i0)

i3: 4. T -> F.

Screenshot 2024-11-17 at 9.39.19 PM.png

Find FollowFollowcheat: terminal or symbol after the variable Algorithm 1. If S is the start symbol, ex: S -> Ab | c, then $ is the Follow value of S 1. If A -> αBβ, then all First of β is the Follow of B except ε 1. a. A -> αB, then all Follow of *A* is the Follow of B 1. b. A -> αBβ and First of β is ε, then all Follow of *A* is the Follow of B Special case If A -> α, i.e production result contains only 1 variable, add ε in front of the variable to conform to rule 3.a. A -> α\*B You can only find the value:

Screenshot 2024-11-18 at 12.40.57 PM.png

Creating SLR Tablerules for creating SLR TableRows are the number of groups that have ex: i0-ix Columns are all the symbols, terminals, and variables If the input is a variable, input the number of the group it results to If input is a terminal or symbol, do the same as variable but add S before the number If there is a grammar that is completed (. is at the end) and is an augmented grammar, put accepted in the dollar column If its complete and NOT augmented grammar , check i0 which line does it correspond / similar to, and use R + l :

Screenshot 2024-11-18 at 1.00.50 PM.png

Searchhow to do parsing search for bottom upThe first stack is the first group 0 and add $ AFTER it Input will be given and add $ AFTER it How to determine the output? * By comparing the left most of the stack and the left most of the input rules * if the output is SX then append number X as the left most of the stack, followed by the input that resulted the output and the stack from the previous operation when input is moved to the stack, it gets removed from the input * If the output is RX then replace the production result of through parsing

Screenshot 2024-11-18 at 1.25.10 PM.png

Status: #idea
Tags: compilation-techniques > Final ExamCompilation Techniques NotesMid Exam RE to DFA RE to E-NFA to DFA Context Free Grammar Top down parsing Final Exam Bottom Up Parsing Directed Acyclic Graph TAC, Triples, Quadriples Intermediate Code Generator Annotated Parse Tree Three Address Statement https://www.youtube.com/watch?v=\_Jng5xgLxkI&list=PLB2GiO0mMjw9J_OwnDMAqtsANzWsIylQz&index=9&ab_channel=HIMTIBINUS Status: #MOC Tags:


References