컴파일러구성 제 11 강 결정적구문분석
10.1 10.2 10.3 10.4 Introduction Syntax-Directed Translation Code Generation U-Code Translator
Formal Specification lexical structure : regular expression syntactic structure : context-free grammar the remaining phases of compilation : no such notations but, we use a syntax-directed translation scheme which is a method associating semantic rules(or actions) with production. SDTS ::= cfg + semantic actions cfg 의 production rule 에있는 grammar symbol 을이용하여직접 semantic action 을기술하는방법. AST generation Attribute grammar
Intermediate code generation the phase that generates an explicit intermediate code of the source program. after syntax and semantic analysis. A Model for Intermediate code generation Source Program Scanner Parser Intermediate Representation Intermediate Code Generation IC Our implementations: Source program : Mini C 프로그램 Intermediate Representation : Abstract Syntax Tree (AST) Intermediate code : U-Code Execution : U-Code Interpreter
Implementation Model Mini C Compiler data Source Program *.mc Scanner Token Stream Parser SDT AST ICG Ucode *.uco Ucode Interpreter scanner : shift action of parser parser : main program (LR parser) SDT : reduce action of parser (AST generation) ICG : Intermediate code generation by traversing AST. Semantic Analysis 와 Intermediate Code Generation 을효율적으로처리하기위해서 AST 의 design 은매우중요. result
Syntax-Directed Translation Scheme(SDTS) ::= a production rule + semantic action(no widely-accepted formalism) A Model for SDTS Parsing table Source Program Scanner get_token token Parser (main) Result call semantic... Semantic Actions whenever a reduction takes place, the semantic rule corresponding to the applied syntactic rule is activated.
Advantages of SDT Providing a method describing semantic rules and that description is independent of any particular implementation. Easy to modify - new productions and semantic actions can be added without disturbing the existing ones. Disadvantages of SDT 파싱도중에 error가일어난경우이제까지행한 semantic action이모두무의미해진다. input에대해 one pass이면서 syntax-directed하게처리하기때문에어떤경우에는정보가부족하여후에필요한정보가나타났을때 backpatching 등복잡하게처리해야한다. Solution Syntax-directed 한방법으로는의미분석과코드생성시에필요한정보만을구성하고다음단계에서그것을이용하여의미분석과코드생성을한다.
SDTS(Syntax-Directed Translation Scheme) ::= production rules + semantic actions Description of Semantic Actions (1) Conventional PL. (2) Meta Language - Formal Semantic Language(FSL) Semantic Description Preprocessor table Input SDT Output
Semantic Description using Attributes of the Grammar Symbol ::= We associate information with a programming language construct by attaching attributes to the grammar symbols representing the construct. Values for attributes are computed by "semantic rules" associated with the grammar productions. An attribute of symbol ex) ::= A value associated with a grammar symbol. Each grammar symbol has an associated set of attributes. An attribute can represent anything we choose: a string, a number, a type, a memory location, or whatever. Production Semantic Rules L E$ E E 1 + T E T T T 1 * F T F F (E) F digit print(e.val) E.val := E 1.val + T.val E.val := T.val T.val := T 1.val * F.val T.val := F.val F.val := E.val F.val := digit.lexval
Synthesized attribute ::= the value of the attribute of the nonterminal on the left side of the production is defined as a function of the grammar symbols on the right side. ex) A XYZ A := f(x,y,z) Inherited attribute ::= the value of the attribute of a nonterminal on the right side of the production is defined in terms of an attribute of the nonterminal on the left. ex) A XYZ Y.val := 2 * X.val Synthesized attribute is more natural than inherited attribute for mapping most programming language constructs into intermediate code.
Designing steps Input design - language construct에대한 grammar를 cfg를이용하여 design. Scanner, Parser의작성. Semantic Specification - conventional PL. SDT Translator 의완성 - interconnection. Examples : 1. Desk Calculator 2. Conversion infix into postfix 3. Construction of AST
Step 1: Input design 0. S -> E $ 1. E -> E + E 2. E -> E * E 3. E -> ( E ) 4. E -> num Step 2: Parsing table states symbols num + * 0 s 3 ( ) s 2 $ E 1 1 s 4 s 5 acc 2 s 3 3 r 4 r 4 4 s 3 s 2 s 2 r 4 6 r 4 7 5 s 3 s 2 8 6 s 4 s 5 s 8 7 r 1 s 5 r 1 r 1 8 r 2 r 2 r 2 r 2 9 r 3 r 3 r 3 r 3
Step 3: Semantic Specification Production L E$ E E 1 + E 2 E E 1 * E 2 E (E 1 ) E num Semantic Rules print E.val E.val := E 1.val + E 2.val E.val := E 1.val * E 2.val E.val := E 1.val E.val := num.lexval Step 4: Implementation of Desk Calculator Parsing stack : Symbol stack + State stack + Value stack Value stack : holding the values of the corresponding attribute.
Code fragments corresponding to semantic actions Production S E$ E E + E E E * E E (E) E num Code Fragment print (val[top]) val[top-2] := val[top-2] + val[top] val[top-2] := val[top-2] * val[top] val[top-2] := val[top-1] val[top] := num.lexval the code fragments do not show how variable top is managed. lexval : token value the code fragments are executed before a reduction takes place.
ex) 23 * 5 + 4 $ state input symbol value parse (0, 23 * 5 + 4$,,, ) s3 ==> (0 3, * 5 + 4$, num,, ) r4 ==> (0 1, * 5 + 4$, E, 23, 4 ) s5 ==> (0 1 5, 5 + 4$, E *, 23_, 4 ) s3 ==> (0 1 5 3, + 4$, E * num, 23, 4 ) r4 ==> (0 1 5 8, + 4$, E * E, 23_5, 4 4 ) r2 ==> (0 1, + 4$, E, 115, 4 4 2 ) s4 ==> (0 1 4, 4$, E +, 115_, 4 4 2 ) s3 ==> (0 1 4 3, $, E + num, 115, 4 4 2 ) r4 ==> (0 1 4 7, $, E + E, 115_4, 4 4 2 4 ) r1 ==> (0 1, $, E, 119, 4 4 2 4 1 ) ==> accept
Code fragments Production E E + E E E * E E E / E E (E) E a print + print * print / no action print a Code Fragment ex) a + (a + a) * a a a a + a * +
AST is a condensed form of parse tree useful for representing language constructs. ex) a = b + 1; = a + b 1 ex) if (a > b) x = a; else x = b; if > = = a b x a x b
Functions to create the nodes of AST for expressions with binary operators. Each function returns a pointer to a newly created node. 1. mktree(op,left,right) creates an operator node with label op and two fields containing pointers to left and right. 2. mknode(a) creates a terminal node for a and returns the node pointer. Semantic Specification Production E E 1 + T E E 1 T E T T (E) T a Semantic Rules E.nptr := mktree( +, E 1.nptr, T.nptr) E.nptr := mktree(, E 1.nptr, T.nptr) E.nptr := T.nptr T.nptr := E.nptr T.nptr := mknode(a) The synthesized attribute nptr for E and T keeps track of the pointers returned by the function calls.
AST for a - 4 + c + - id id num 4 to entry for c to entry for a
AST design Grammar form : production rule [ => nodename ] ; A α nodename ; nodename α 1 α 2 α n Note node name 의생략시에는부트리를구성하지않음.
Mini C Grammar with AST mini_c translation_unit PROGRAM; translation_unit external_dcl; translation_unit external_dcl; external_dcl function_def; declaration; function_def function_header compound_st FUNC_DEF; function_header dcl_spec function_name formal_param FUNC_HEAD; dcl_spec dcl_specifiers DCL_SPEC; dcl_specifiers dcl_specifier; dcl_specifiers dcl_specifier; dcl_specifier type_qualifier; type_specifier; Text p. 434-437 참조
Data Structures A node form of AST token son noderep brother tokennumber tokenvalue next brother node son node Node structure struct tokentype { int tokennumber; char * tokenvalue; }; typedef struct nodetype { struct tokentype token; enum {terminal, nonterm} noderep; struct nodetype *son; struct nodetype *brother; } Node; // 토큰번호 // 토큰값 // 토큰종류 // 노드종류 // 왼쪽링크 // 오른쪽링크
Production rule name enum nodenumber { ACTUAL_PARAM, ADD, ADD_ASSIGN, ARRAY_VAR, ASSIGN_OP,, WHILE_ST }; char *nodename[] = { "ACTUAL_PARAM", "ADD", "ADD_ASSIGN", "ARRAY_VAR", "ASSIGN_OP", "WHILE_ST" }; int rulename[] = { /* 0 1 2 3 4 */ 0, PROGRAM, 0, 0, 0, /* 95 96 97 */ 0, 0, 0 };
AST Generation Shift buildnode(simple and easy) Reduce buildtree(complex and difficult) Shift action of parsing : if the token is meaningful, then call buildnode. Node *buildnode(struct tokentype token) { Node *ptr; ptr = (Node *) malloc(sizeof(node)); if (!ptr) { printf("malloc error in buildnode()\n"); exit(1); } ptr->token = token; ptr->noderep = terminal; ptr->son = ptr->brother = NULL; return ptr; }
Reduce action of parsing : Basic concept if the production rule is meaningful 1. build subtree - linking brothers - making a subtree else 2. only linking brothers buildtree() function step 1: finding a first index with node in value stack. step 2: linking brothers. step 3: making subtree root and linking son if meaningful.
Node *buildtree(int nodenumber, int rhslength) Node *buildtree(int nodenumber, int rhslength) { // i = sp - rhslength + 1; // step 1: find a first index with node in value stack while (i <= sp && valuestack[i] == NULL) i++; if (!nodenumber && i > sp) return NULL; start = i; // step 2: linking brothers while (i <= sp-1) { j = i + 1; while (j <= sp && valuestack[j] == NULL) j++; } if (j <= sp) { } i = j; ptr = valuestack[i]; while (ptr->brother) ptr = ptr->brother; ptr->brother=valuestack[j]; } first = (start > sp)? NULL : valuestack[start]; // step 3: making subtree root and linking son if (nodenumber) { // memory allocation for ptr ptr->token.tokennumber = nodenumber; ptr->token.tokenvalue = NULL; ptr->noderep = nonterm; ptr->son = first; ptr->brother = NULL; return ptr; } else return first; // 1 // 2 // 3 // 4 // 5 // 6 // 7
buildtree() 함수의설명 1 현재 reduce 되는생성규칙의 rhs 에노드가매달려있는인덱스를값스택에서찾는다. 형제노드로연결할노드의첫번째인덱스를찾은것이다. 2 의미있는생성규칙이아니고연결할형제노드도없으면그냥복귀한다. 3 형제노드로연결할노드의다음인덱스를 1 과같은방법으로찾는다. 4 만약다음인덱스를찾았으면, 형제노드로연결한다. 5 연속해서다음인덱스를찾기위해위치를앞으로이동한다. 6 연결된형제노드들의첫번째노드의포인터를 first 에저장한다. 7 의미있는생성규칙이면, nonterminal 노드를만든후에연결된형제노드를 son 으로연결하고새로만든노드의포인터를복귀한다. 의미있는생성규칙이아니면, 연결된형제노드의포인터만을복귀한다.
Parsing Stack and Value Stack Parsing Stack : Value Stack : SP Note Parsing Stack 과 Value Stack 은병렬로운행
Confirming the AST structures Printing an AST using indentation Traversing an AST in depth-first order Two functions printtree() printing an AST structure printnode() printing a node information printtree() function void printtree(node *pt, int indent) { } Node *p = pt; while (p!= NULL) { } printnode(p, indent); if (p->noderep == nonterm) printtree(p->son, indent+5); p = p->brother;
printnode() function void printnode(node *pt, int indent) { extern FILE * astfile; int i; } for (i=1; i<=indent; i++) fprintf(astfile," "); if (pt->noderep == terminal) { if (pt->token.number == tident) fprintf(astfile," Terminal: %s", pt->token.value.id); else if (pt->token.number == tnumber) fprintf(astfile," Terminal: %d", pt->token.value.num); } else { // nonterminal node int i; i = (int) (pt->token.number); fprintf(astfile," Nonterminal: %s", nodename[i]); } fprintf(astfile,"\n");
Implement a syntax-directed translator producing an AST for Mini C program. mini C Program *.mc Scanner Parser SDT AST Mini C Program : Perfect.mc(Text pp.447) The Output form of AST using printtree() : Text pp.443-444