New version page

MIT 6 035 - Lecture Notes

Upgrade to remove ads
Upgrade to remove ads
Unformatted text preview:

MIT 6 035MIT 6.035 Introduction to Shift-Reduce Parsing Martin Rinard Laboratory for Computer Science Massachusetts Institute of TechnologyOrientation • Specify Syntax Using Context-Free Grammar Expr → ExprOpExpr •Nonterminals •Terminals Expr → ExprOpExpr Expr→ (Expr) Expr→ -Expr •Productions • Given a grammar, Parser Generator produces a p p Expr→ num Op→ + Generator produces a parser • Starts with input string Op→ -Op→ * • Produces parse treet•w•Today’s Lecture • How generated parser works H d• How parser generator produces parser • Central mechanism Pushdown automaton hich implements Pushdown automaton, which implements • Shift-reduce parsert•t t t tC i fShift:A h i iPushdown Automata • Consists of • Pushdown stack (can have terminals and nonterminals) Finite state automaton controlFinite state automaton control • Can do one of three actions (based on state and input): • Shift: • Shift current input symbol from input onto stack • Reduce: • If symbols on top of stack match right hand side of some grammar production NT →β • Pop symbols (β) off of the stack • Push left hand side nonterminal (NT) onto stack • Accept the input string •p*(+)Shift -R e duce P a rser Exam p lep Expr → Expr Op Expr Expr → ( Expr) Expr → -Expr Expr → num Op → + Stack Op → -Op → * Input String * ( + num )numnump*(+)Shift -R e duce P a rser Exam p lep Expr → Expr Op Expr Expr → ( Expr) Expr → -Expr Expr → num Op → + Op → -Op → * * ( + num )numnump*(+)Shift -R e duce P a rser Exam p lep Expr → Expr Op Expr Expr → ( Expr) Expr → -Expr Expr → num Op → + Op → -Op → * FTSHIF * ( + num )numnump*(+)Shift -R e duce P a rser Exam p lep Expr → Expr Op Expr Expr → ( Expr) Expr → -Expr Expr → num Op → + num Op → -Op → * FTSHIF * ( + num )numShift-Reduce Parser ExamplepExpr→Expr Op ExprExpr→ (Expr)Expr→ -ExprExpr→ numOp→ +numpOp→ -Op→ *UCE* ( + )REDU* ( + num )numRExpr→ nump*(+)Shift -R e duce P a rser Exam p lep Expr → Expr Op Expr Expr → ( Expr) Op → -Op → *Expr UCE num REDU * ( + num )numR Expr→ -ExprExpr→ numOp→ +p*(+)Shift -R e duce P a rser Exam p lep Expr → Expr Op Expr Expr → ( Expr) Expr → -Expr Expr → num Op → + Op → -Op → *Expr FT numSHIF * ( + num )nump(+)Shift -R e duce P a rser Exam p lep Expr → Expr Op Expr Expr → ( Expr) Expr → -Expr Expr → num Op → + Op → -Op → *Expr * FT numSHIF ( + num )numShift-Reduce Parser ExamplepExpr→Expr Op ExprExpr→ (Expr)Expr→ -ExprExpr→ numOp→ +pOp→ -Op→ *ExprOpUCE( + )numREDU*( + num )numRp(+)Shift -R e duce P a rser Exam p lep Expr → Expr Op Expr Expr → ( Expr) Expr → -Expr Expr → num Op → + Op → -Op → *Expr Op FT num *SHIF ( + num )nump+)Shift -R e duce P a rser Exam p lep Expr → Expr Op Expr Expr → ( Expr) Expr → -Expr Expr → num Op → +( Op → -Op → *Expr Op FT num *SHIF + num )nump+)Shift -R e duce P a rser Exam p lep Expr → Expr Op Expr Expr → ( Expr) Expr → -Expr Expr → num Op → +( Op → -Op → *Expr Op FT num *SHIF + num )nump+)Shift -R e duce P a rser Exam p lep Expr → Expr Op Expr Expr → ( Expr) Expr → -Expr Expr → num Op → +( num Op → -Op → *Expr Op FT num *SHIF + num )pFT+)SHIFShift -R e duce P a rser Exam p lep Expr → Expr Op Expr Expr → ( Expr) Expr → -Expr Expr → num Op → +( Expr Op → -Op → *Expr Op UCE num * num REDU + num )Rp+)Shift -R e duce P a rser Exam p lep Expr → Expr Op Expr Expr → ( Expr) Expr → -Expr Expr → num Op → +( Expr Op → -Op → *Expr Op FT num *SHIF num + num )p)Shift -R e duce P a rser Exam p lep Expr → Expr Op Expr Expr → ( Expr)+ Expr → -Expr Expr → num Op → +( Expr Op → -Op → *Expr Op FT num *SHIF num num )pFT)SHIFShift -R e duce P a rser Exam p lep Expr → Expr Op Expr Expr → ( Expr)Op Expr → -Expr Expr → num Op → +( Expr Op → -Op → *Expr Op UCE num * num REDU + num )Rp)Shift -R e duce P a rser Exam p lep Expr → Expr Op Expr Expr → ( Expr)Op Expr → -Expr Expr → num Op → +( Expr Op → -Op → *Expr Op FT num *SHIF num + num )p)Shift -R e duce P a rser Exam p lep Expr → Expr Op Expr Expr → ( Expr) num Op Expr → -Expr Expr → num Op → +( Expr Op → -Op → *Expr Op FT num *SHIF num + )pFT)SHIFShift -R e duce P a rser Exam p lep Expr → Expr Op Expr Expr → ( Expr)Op Expr Expr → -Expr Expr → num Op → +( Expr Op → -Op → *Expr Op UCE num * num + REDU num )RShift-Reduce Parser ExamplepExpr→Expr Op ExprExpr→ (Expr)Expr→ -ExprExpr→ numOp→ +(ExprExprExprpOp→ -Op→ *ExprOpExprOpFTUCE)num *SHIFnum +REDUnum)Rp)Shift -R e duce P a rser Exam p lep Expr → Expr Op Expr Expr → ( Expr) Expr → -Expr Expr → num Op → +( Expr Expr Op → -Op → *Expr Op Expr Op FT num *SHIF num + num )pShift -R e duce P a rser Exam p lep Expr → Expr Op Expr Expr → ( Expr)) Expr → -Expr Expr → num Op → +( Expr Expr Op → -Op → *Expr Op Expr Op FT num *SHIF num + numShift-Reduce Parser ExamplepExpr→Expr Op ExprExpr→ (Expr)Expr→ -ExprExpr→ numOp→ +E)ExprpOp→ -Op→ *ExprOp(OpExprExprUCEExprREDUnum * num + numRpShift -R e duce P a rser Exam p lep Expr → Expr Op Expr Expr → ( Expr) Expr → -Expr Expr → num Op → +E )Expr Op → -Op → * Expr Op ( Op Expr Expr Expr UCEExpr REDU num * num + num RpShift -R e duce P a rser Exam p lep Expr → Expr Op Expr Expr → ( Expr) Expr → -Expr Expr → num Op → +E )Expr Op → -Op → * Expr Op ( Op Expr Expr Expr EPT!Expr ACCE num * num + num At t t t•s sequences•Basic Idea • Goal: reconstruct parse tree for input string Rd i f l f i h• Read input from left to right • Build tree in a bottom-up fashion Use tack to hold pending of terminals Use stack to hold pending sequences of terminals and nonterminals••t t t tPotential Conflicts • Reduce/Reduce …


View Full Document
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?