DOC PREVIEW
U of M CS 5641 - Syntax-Directed Translation

This preview shows page 1-2-3-4-5 out of 14 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1Syntax-Directed Translation Extending CFGs Grammar Annotation Parse Trees Abstract Syntax Trees (ASTs) Readings: Section 5.1, 5.2, 5.5, 5.6Motivation: parser as a translatorsyntax-directed translationparsersyntax + translation rules(typically hardcoded in the parser)stream of tokensASTs, orassembly code2Mechanism of syntax-directed translation syntax-directed translation is done by extending the CFG a translation rule is defined for each productiongiven X Æ d A B cthe translation of X is defined in terms of  translation of nonterminals A, B values of attributes of terminals d, c constantsTo translate an input string:1. Build the parse tree. 2. Working bottom-up• Use the translation rules to compute the translation of each nonterminal in the treeResult: the translation of the string is the translation of the parse tree's root nonterminal Why bottom up?  a nonterminal's value may depend on the value of the symbols on the right-hand side,  so translate a non-terminal node only after children translations are available3Example 1: arith expr to its valueSyntax-directed translation:the CFG translation rules E Æ E + T E1.trans = E2.trans + T.trans E Æ T E.trans = T.trans T Æ T * F T1.trans = T2.trans * F.trans T Æ F T.trans = F.trans F Æ int F.trans = int.valueF Æ ( E ) F.trans = E.transExample 1 (cont)Input: 2 * (4 + 5) Annotated Parse Tree E (18)T (18)F (9)T (2)F (2)E (9)T (5)F (5)E (4)T (4)F (4)*)*(int (2)int (4)int (5)4Example 2: Compute type of exprE -> E + E if ((E2.trans == INT) and (E3.trans == INT)then E1.trans = INT else E1.trans = ERROR E -> E and E if ((E2.trans == BOOL) and (E3.trans == BOOL) then E1.trans = BOOL else E1.trans = ERROR E -> E == E if ((E2.trans == E3.trans) and (E2.trans != ERROR)) then E1.trans = BOOL else E1.trans = ERROR E -> true E.trans = BOOL E -> false E.trans = BOOL E -> int E.trans = INT E -> ( E ) E1.trans = E2.transExample 2 (cont) Input: (2 + 2) == 41. parse tree:2. annotation:5Another Example A CFG for the language of binary numbers: B Æ 0 Æ 1 Æ B 0 Æ B 1  Define a syntax-directed translation so that the translation of a binary number is its base-10 value Draw the parse tree for 1001 and annotate each nonterminal with its translation Building Abstract Syntax Trees Examples so far, streams of tokens translated into  integer values, or  types Translating into ASTs is not very different6AST vs Parse Tree AST is condensed form of a parse tree operators appear at internalnodes, not at leaves "Chains" of single productions are collapsed  Lists are "flattened"  Syntactic details are ommitted e.g., parentheses, commas, semi-colons AST is better structure for later compiler stages omits details having to do with the source language only contains information about the essentialstructure of the program Ex: 2*(4+5) parse tree vs AST*+254ETFTFETFETF*)*(int (2)int (5)int (4)7Definitions of AST nodesclass ExpNode { } class IntLitNode extends ExpNode { public IntLitNode(int val) {...} } class PlusNode extends ExpNode { public PlusNode( ExpNode e1, ExpNode e2 ) { ... } } class TimesNode extends ExpNode { public TimesNode( ExpNode e1, ExpNode e2 ) { ... } }AST-building translation rulesE1Æ E2+ T E1.trans = new PlusNode(E2.trans, T.trans) E Æ T E.trans = T.trans T1Æ T2* F T1.trans = new TimesNode(T2.trans, F.trans) T Æ F T.trans = F.trans F Æ int F.trans = new IntLitNode(int.value) F Æ ( E ) F.trans = E.trans8Example Illustrate the syntax-directed translation defined previously by  drawing the parse tree for 2 + 3 * 4, and  annotating the parse tree with its translation  i.e., each nonterminal X in the parse tree will have a pointer to the root of the AST subtreethat is the translation of X Syntax-Directed Translation and LL Parsing not obvious how to do this, since  predictive parser builds the parse tree top-down, syntax-directed translation is computed bottom-up.  could build the parse tree (inefficient!) Instead, add a semantic stack:  holds nonterminals' translations when the parse is finished, the semantic stack will hold just one value:  the translation of the root nonterminal (which is the translation of the whole input).9How does semantic stack work? How to push/pop onto/off the semantic stack? add actions to the grammar rules  The action for one rule must:  Pop the translations of all rhs nonterminals  Compute and push the translation of the lhs nonterminal Actions are represented by action numbers action numbers become part of rhs of grammar rules action numbers pushed onto the (normal) stack along with the terminal and nonterminal symbols when an action number is the top-of-stack symbol, it is popped and the action is carried outKeep in mind action for X Æ Y1Y2... Ynis pushed onto the (normal) stack when the derivation step X Æ Y1Y2... Ynis made, but the action is performed only after complete derivations for all of the Y's have been carried out10Example: Counting ParenthesesE1Æ ε E1.trans = 0Æ ( E2) E1.trans = E2.trans + 1 Æ [ E2] E1.trans = E2.trans Example: Step 1 replace the translation rules with translation actions Each action must:  Pop rhs nonterminals' translations from semantic stack  Compute and push the lhs nonterminal's translation  Here are the translation actions: E Æ ε push(0);Æ ( E ) exp2Trans = pop(); push( exp2Trans + 1 );Æ [ E ] exp2Trans = pop(); push( exp2Trans );11Example: Step 2each action is represented by a unique action number,  the action numbers become part of the grammar rules: E Æ ε #1 Æ ( E ) #2Æ [ E ] #3 #1: push(0); #2: exp2Trans = pop(); push( exp2Trans + 1 ); #3: exp2Trans = pop(); push( exp2Trans ); Example: exampleinput so far stack semantic stack action ------------ ----- -------------- ------( E EOF pop, push "( E ) #2" ( (E) #2 EOF pop, scan ([ E) #2 EOF pop, push "[ E ]" ([ [E] ) #2 EOF pop, scan ([] E] ) #2 EOF pop, push ε #1 ([] #1 ] ) #2 EOF pop, do action ([] ] ) #2 EOF 0 pop, scan ([]) ) #2 EOF 0 pop, scan ([]) EOF #2 EOF 0 pop, do action ([]) EOF EOF 1 pop, scan ([]) EOF empty stack: input accepted!translation of input = 112What if the rhs has >1 nonterminal? pop multiple values from the semantic stack: CFG Rule: methodBody Æ { varDecls stmts }  Translation Rule: methodBody.trans = varDecls.trans + stmts.trans  Translation


View Full Document

U of M CS 5641 - Syntax-Directed Translation

Download Syntax-Directed Translation
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 Syntax-Directed Translation 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 Syntax-Directed Translation 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?