1Lecture 10Syntax-Directed TranslationProf. Bodik CS164 Fall 2004 2Motivation: parser as a translatorsyntax-directed translationparsersyntax + translation rules(typically hardcoded in the parser)stream of tokensASTs, orassembly codeProf. Bodik CS164 Fall 2004 3Outline• Syntax directed translation: specification– translate parse tree to its value, or to an AST– typecheck the parse tree• Syntax-directed translation: implementation–during LR parsing– during LL parsingProf. Bodik CS164 Fall 2004 4Mechanism 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•constantsProf. Bodik CS164 Fall 2004 5To 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 available.Prof. Bodik CS164 Fall 2004 6Example 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.trans2Prof. Bodik CS164 Fall 2004 7Example 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)Prof. Bodik CS164 Fall 2004 8Example 2: Compute the type of an expressionE -> 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.transProf. Bodik CS164 Fall 2004 9Example 2 (cont)• Input: (2 + 2) == 41. parse tree:2. annotation:Prof. Bodik CS164 Fall 2004 10TEST YOURSELF #1• 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. Prof. Bodik CS164 Fall 2004 11Building Abstract Syntax Trees• Examples so far, streams of tokens translated into – integer values, or –types• Translating into ASTs is not very differentProf. Bodik CS164 Fall 2004 12AST 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 a better structure for later compiler stages– omits details having to do with the source language,– only contains information about the essentialstructure of the program.3Prof. Bodik CS164 Fall 2004 13Example: 2 * (4 + 5) parse tree vsASTETFTFETFETF*)*(int (2)int (5)*+254int(4)Prof. Bodik CS164 Fall 2004 14AST-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.transProf. Bodik CS164 Fall 2004 15TEST YOURSELF #2• Illustrate the syntax-directed translation defined above 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 subtree that is the translation of X. Prof. Bodik CS164 Fall 2004 16Syntax-Directed Translation and LR Parsing• add semantic stack, – parallel to the parsing stack: • each symbol (terminal or non-terminal) on the parsing stack stores its value on the semantic stack– holds terminals’ attributes, and– holds nonterminals' translations– when the parse is finished, the semantic stack will hold just one value: • the translation of the root non-terminal (which is the translation of the whole input). Prof. Bodik CS164 Fall 2004 17Semantic actions during parsing• when shifting– push the value of the terminal on the sem. stack• when reducing– pop k values from the sem. stack, where k is the number of symbols on production’s RHS– push the production’s value on the sem. stackProf. Bodik CS164 Fall 2004 18An LR exampleGrammar + translation rules:E1→ E2+ ( E3)E1.trans = E2.trans + E3.transE1→ int E1.trans = int.transInput:2 + ( 3 ) + ( 4 )4Prof. Bodik CS164 Fall 2004 19Shift-Reduce Example with evaluationsparsing stack semantic stackI int + (int) + (int)$ shift IProf. Bodik CS164 Fall 2004 20Shift-Reduce Example with evaluationsI int + (int) + (int)$ shift Iint I + (int) + (int)$ red. E d int 2 IProf. Bodik CS164 Fall 2004 21Shift-Reduce Example with evaluationsI int + (int) + (int)$ shift Iint I + (int) + (int)$ red. E d int 2 IE I + (int) + (int)$ shift 3 times 2 IProf. Bodik CS164 Fall 2004 22Shift-Reduce Example with evaluationsI int + (int) + (int)$ shift Iint I + (int) + (int)$ red. E d int 2 IE I + (int) + (int)$ shift 3 times 2 IE + (int I ) + (int)$ red. E d int 2 ‘+’ ‘(‘ 3 IProf. Bodik CS164 Fall 2004 23Shift-Reduce Example with evaluationsI int + (int) + (int)$ shift Iint I + (int) + (int)$ red. E d int 2 IE I + (int) + (int)$ shift 3 times 2 IE + (int I ) + (int)$ red. E d int 2 ‘+’ ‘(‘ 3 IE + (E I ) + (int)$ shift 2 ‘+’ ‘(‘ 3 IProf. Bodik CS164 Fall 2004 24Shift-Reduce Example with evaluationsI int + (int) + (int)$ shift Iint I + (int) + (int)$ red. E d int 2 IE I + (int) + (int)$ shift 3 times 2 IE + (int I ) + (int)$ red. E d int 2 ‘+’ ‘(‘ 3 IE + (E I ) + (int)$ shift 2 ‘+’ ‘(‘ 3 IE + (E) I + (int)$ red. E d E + (E) 2 ‘+’ ‘(‘ 3 ‘)’ I5Prof. Bodik CS164 Fall 2004 25Shift-Reduce Example with evaluationsI int + (int) +
View Full Document
Unlocking...