Top down parsing
steps
- no left recursive and left factoring
- find FirstFirstfirst character in the terminal values !! if there are multiple terminal values (x | y), there can be many First values Status: #idea Tags: compilation-techniques References values (as many grammars that we have)
- find FollowFollowcharacter after the first character in the terminal values 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 You can only find the follow values of the terminal on the lines before it You can use this algorithm or a cheat method by looking at the result o value (as many grammars that we have)
- make Parsing TableParsing TableRows: Variables Columns: Terminals, and Values How to fill the table? 1. Look at the first of each variable, and fill where we got the first values 1. If there is an ε at the first, then look at follow value of the variable and write the variable -> ε for the follow values break it apart. theres no | (or) Status: #idea Tags: compilation-techniques References
- searchParsing SearchThe first stack is the start symbol and add $ before it Input will be given How to determine the output? * By comparing the right most of the stack and the left most of the input rules * Stack gets replaced by the production values or the thing that comes after the -> but reverse it * If stack == input POP STACK AND INPUT * if there is ε after -> POP STACK * if stack == $ and input == $ ACCEPT * if stack ≠ input REJECT Status: #idea Tags: compilation-techniques References through the parsing
Status: #idea
Tags: compilation-techniquesCompilation Techniques Notes* [ ] Assigments
RE to DFA
Example Kenny Jingga CT UTS Quiz
kennydfa1.png
kennydfa2.png
kennydfa3.png
Example Ivan Sebastian CT UTS Quiz
RE to E-NFA to DFA
Example Kenny Jingga CT UTS Quiz
kenny1.png
Example Ivan Sebastian CT UTS Quiz
ivan2.png WRONGGGG
Context Free Grammar
Top down parsing
Example Alvina Aulia Top Down Parsing
1. E -> TE'
1. E' -> +TE' | ε
1. T -> FT'
1. T' -> \FT'* | ε
1. F -> (E) | id
First Values:
1. First E = (, id (this is from E -> T -> F)
1. First E' =