2007 Spring / SNU CSE / Prof. 이재진
Textbook - Compilers : Principles, Techniques and Tools 2/E by Aho, Lam, Sethi, Ullman (Pearson International Edition)
Chapter 2. A Simple Syntax-Directed Translator
This chapter is about the front end of a compiler : lexical analysis, parsing, intermediate code generation
Syntax-directed translator : infix arithmetic expressions into postfix expressions
2.1 Introduction
Three-address instruction : x = y op z (op:binary operator, x,y,z:addresses)
2.2 Syntax Definition
Context-free grammar (wikipedia)
ex) stmt → if ( expr ) stmt else stmt
such a rule is called a production
terminals : if else ( )
nonterminals : stmt expr
context-free : nonterminal → a sequence of terminals and/or nonterminals
2.2.5 Associativity of Operators
Left-associative : 9-5-2 : 5 belongs to the left - operator : (9-5)-2
Right-associative : a=b=c : b belongs to the rihgt = opertor : a=(b=c)
2.2.6 Precedence of Operators
Example grammar : * / have higher precedence than + -
expr → expr + term | expr - term | term
term → term * factor | term / factor | factor
factor → digit | ( expr )
2.3 Syntax-Directed Translation
Attributes : any quantity associated with a programming construct. : X.a (X:grammar symbol, a:attribute)
Translation Scheme : a notation for attaching program fragments to the productions of a grammar.
2.3.1 Postfix Notation
No parentheses are need in postfix notation.
ex) 952+-3*
1. find leftmost operator : +
2. its operands : 5 and 2 : 9(52+)-3* = 97-3*
3. next leftmost operator : -
4. its operands : 9 and 7 : (97-)3* = 23*
5. 23* = 6
2.3.2 Syntehsized Attributes
an attribute that its value at a parse-tree node N is determined from attribute values at the children of N and at N itself (bottom-up)
anotated parse tree : showing the attribute values at eache node
2.3.3 Simple Syntax-Directed Definitions
THE SAME ORDER concatenation of the translations of the nonterminals as in the production
2.3.5 Translations Schemes
semantic actions : program fragments : {print('+')}
need to perform a left-to-right depth-first postorder traversal
(to be continued)