2/80 2
3/80 3
DSP2400 is a high performance Digital Signal Processor (DSP) designed and developed by author s laboratory. It is designed for multimedia and wireless application. To develop application easily on DSP2400 platform, a high level programming language compiler is needed. Because of good portability and performance, C programming language is used as developing language on all kinds of platforms, including embedded system and DSP platform, and there are plenty of source codes developed in C in the world. Using C as developing language of DSP2400 platform can take advantage of existing C program resource. This thesis presents the method of translating C source code to the target code with the two famous tools: LEX and YACC, and the detail design of a C compiler with these two tools. The compiler is composed of two parts: the front end and the back end. In the process of syntax 4/80 4
analysis, the front end of compiler performs semantic checking and code transfer by step. The front end gives a syntax tree as its output, which is the intermediate representation of the source code. Optimization modules of the back end of compiler take the syntax tree as the input and perform basic block division, control flow analysis, block optimization and iteration optimization based on the tree, and then output an optimized tree. The code generation module performs target codes generation based on the given tree. In the code generation module, according to optimization principles and features of the target processor, a new register allocation algorithm and some optimization methods are proposed and implemented to make the compiler generate effective codes. The structure of implemented compiler is very flexible, extensible and portable, and the compiler could generate effective codes for the target processor. This thesis will descript how to construct the modules of compiler in the order of compiling process. It presents the basic idea of module construction and gives the data structure and algorithm to implement the modules. KEY WORDS: dsp, compiler, c programming language, lex, yacc 5/80 5
2004 1 16 1
2
8/80 8
9/80 9
10/80 10 C
Figure 1-1 The compiler structure 11/80 11
2.2. 2.2.1. 13/80 13
2.2.2. Figure 2-1 The FSM model for recognizing the identifier 14/80 14
15/80 15 2.3.
2-2 Figure 2-2 The growth procedure of the syntax tree 16/80 16
2-3 Figure 2-3 The construct procedure of the syntax tree 2.3.2. LR 17/80 17
2-4 LR Figure 2-4 The work of LR analyzer 18/80 18
19/80 19 2.4.
20/80 20 2-5 Figure 2-5 The property transform
21/80 21 2.5.
2-6 Figure 2-6 Runtime memory allocation 2.6. 22/80 22
3-2 Figure 3-2 The back-end structure of the compiler 24/80 24
25/80 25
4-1 LEX Figure 4-1 LEX syntax description file format 26/80 26
4-2 Figure 4-2 The protype definition for class 27/80 27
4-3 LALR(1) Figure 4-3 The symbol set definition for LALR(1) grammar 28/80 28
4-4 Figure 4-4 The procedure of accidence analysis 29/80 29
4-5 YYSTYPE Figure 4-5 YYSTYPE definition 4-6 Figure 4-6 The recognition code for decimal integer 4.2. 30/80 30
31/80 31 translation_unit external_declaration translation_unit external_declaration external_declaration function_definition declaration
declaration declaration_specifiers declaration_specifiers init_declarator_list compound_statement { } {statement_list} {declaration_list} { declaration_list statement_list } statement_list statement_list statement statement_list statement 32/80 32
4-7 Figure 4-7 The structure of translation unit class 33/80 33
34/80 34
35/80 35
4-8 Figure 4-8 The class structure of a syntax sub-tree 36/80 36
37/80 37
4-9 Figure 4-9 An example of symbol specification list 38/80 38
4-10 Figure 4-10 The syntax sub-tree structure for select statement data 39/80 39
4-11 Figure 4-11 The syntax sub-tree structure for iteration statement data 40/80 40
4-12 Figure 4-12 A syntax tree for an expression 41/80 41
42/80 42
4-13 Figure 4-13 The structure of a function syntax tree 43/80 43
5.1. 5.1.1.1. 44/80 44
45/80 45 5.1.1.2.
46/80 46 5.1.2. 5.1.2.1.
47/80 47
48/80 48 5-1
5-1 Figure 5-1 The function descriptor for FIB function 49/80 49
5-2 Figure The program flow for FIB function 5.1.2.2. 50/80 50
51/80 51
5-1 52/80 52
53/80 53 5.1.2.3.
5.2. 5.2.1. 54/80 54
5-3 DSP2400 24 Figure The 24-bit operation for DSP2400 55/80 55
± ± ± 5-4 DSP2400 Figure 5-4 DSP2400 memory address sketch map 5.2.2. 56/80 56
57/80 57
5-5 Figure 5-5 The structure of the active record 5.2.3. 58/80 58
59/80 59 5-6 Figure 5-6 The code generation for expression
5-7 Figure 5-7 The code generation for if-else 60/80 60
5-8 switch DSP2400 Figure 5-8 The DSP2400 code generated by switch statement 61/80 61
5-9 DSP2400 Figure 5-9 DSP2400 code structure for loop statement 62/80 62
5-10 for DSP2400 Figure 5-10 The DSP2400 code for for statement 63/80 63
5.2.4. 5.2.4.1. 64/80 64
5-11 Figure 5-11 Code generation flow 65/80 65
5-12 Figure 5-12 The state for the middle result stack 5.2.4.2. 66/80 66
5-13 Figure 5-13 The layout for float point number s e 127 ( 1)2 (1. f ) 67/80 67
5-2 68/80 68
69/80 69 5.2.4.3.
5-14 Figure 5-14 The code generation algorithmic 5.2.4.4. 70/80 70
71/80 71
72/80 72
73/80 73
Kaufmann 1997 209-211 [20] Ken Kennedy Randy Allen Optimizing Compilers for Modern Architectures: A Dependence-based Approach Morgan Kaufmann 1997 [21] 1996.6 30 [22] 1982.1 73-81 75/80 75
77/80 77
78/80 78
80/80 80
DSP C 2004.1.16 7 DSP C 24 1. 2. 3. 4. 2004 1 16 81/80 81