IT/강의

Compiler : Chapter 2. A Simple Syntax-Directed Translator

zzun 2007. 3. 13. 23:51
반응형

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)

반응형