編譯器實作 FRANCIS Compiler
FRANCIS Compiler
Copyright By PowCoder代写 加微信 powcoder
Lexical Analysis(1)
PROGRAM MAIN;
VARIABLE INTEGER:U,V,M;
CALL S1(U ,V , M );
SUBPOUTINE S1( INTEGER : X , Y , M ) ;
M = X + Y + 2.7;
FRANCIS語言所寫之程式
Lexical Analysis(2)
PROGRAM MAIN;
(2,21) (5,3) (1,1)
VARIABLE INTEGER: U , V , M ;
(2,25) (2,14) (1,12) (5,1) (1,11) (5,5) (1,11) (5,6) (1,1)
U = 5 ;
(5,1) (1,4) (3,1) (1,1)
V = 7 ;
(5,5) (1,4) (3,2) (1,1)
CALL S1 ( U , V , M ) ;
(2,3) (5,10) (1,2) (5,1) (1,11) (5,5) (1,11) (5,6) (1,3) (1,1)
(2,6) (1,1)
SUBPOUTINE S1 ( INTEGER : X , Y , M ) ;
(2,23) (5,10) (1,2) (2,14) (1,12) (5,8) (1,11) (5,4) (1,11) (5,9) (1,3) (1,1)
M = X + Y + 2.7 ;
(5,9) (1,4) (5,8) (1,5) (5,4) (1,5) (4,1) (1,1)
(2,7) (1,1)
FRANCIS語言所寫之程式，被轉換成記號的格式
如何抓Token A
Another character
available?
Read a character.
Identify the string in
the queue, if it exists,
as a token.
Delimiter?
Identify the string in
the queue, if it exists,
as a token.
Identify the delimiter
as a token.
Put this character
into the queue.
Lexical Analysis(Table 1)
Table 1 Delimiters
Lexical Analysis(Table 2)
2. BOOLEAN
3. CALL
4. DIMENSION
5. ELSE
13. INPUT
14. INTEGER
15. LABEL
20. OUTPUT
21. PROGRAM
22. REAL
23. SUBROUTINE
24. THEN
25. VARIABLE
Table 2 (Reserved Word Table)
Lexical Analysis(Table 3,4)
Table 3 (Integer Table)
Table 4 (Real Number Table)
Lexical Analysis(Table 5)
Identifier Subroutine Type Pointer
Table 5 (Identifier Table)
Syntax Analysis
1. 將Tokens分辨為Statement
• 不正確 : Report error message
3. 將一些資訊匯入表格內
Example 4.1
PROGRAM A1;
VARIABLE INTEGER:X,Y,I;
DIMENSION INTEGER:A(12);
LABEL L91, L92;
L91 IF X GT Y THEN GTO L92 ELSE X=X+2;
Quadruple form (Table 6)
1 (( 5, 8), , , ) X
2 (( 5,11), , , ) Y
3 (( 5, 2), , , ) I
4 (( 5, 7), , , ) A
5 (( 5,14), , , ) L91
6 (( 5,15), , , ) L92
7 (( 1, 4),(3,2), ,(5,2)) I=1
8 (( 1, 4),(3,3), ,(5,8)) X=5
9 (( 1, 4),(3,4), ,(5,11)) Y=11
10 (( 2,10),(5,8),(5,11),(0,1)) T1=X GT Y
11 (( 2,12),(0,1),(6,12),(6,13)) IF T1 GO TO 12, ELSE GO TO 13
12 (( 2,11), , ,(6,18)) GTO L92
13 (( 1, 5),(5,8),(3,5),(0,2)) T2=X+2
14 (( 1, 4),(0,2), ,(5,8)) X=T2
15 (( 1, 4),(5,8),(5,7),(5,2)) A(I)=X
16 (( 1, 5),(5,2),(3,2),(5,2)) I=I+1
17 (( 2,11), , ,(6,10)) GTO L91
18 ((2,6), , , ) L92 ENP
分辨Statement
◼ 以 ; 當作Statement之結束
◼ Statement 計有
PROGRAM GTO
SUBROUTINE assignment
VARIABLE CALL
LABEL INPUT
DIMENSION OUTPUT
處理PROGRAM(1)
◼ 文法 PROGRAM identifier;
e.g. PROGRAM main;
◼ 此程式的中間碼在哪裡
根據Recursive descent parser,
預期下一個應是ID Token,
若沒符合文法, 即為error
處理 PROGRAM(2)
◼ Pointer指向中間碼所在位置
Identifier Subroutine Type Pointer
指向中間碼table的
◼ VARIABLE INTEGER : U, V, M;
◼ Data Type :
CHARACTER 3
VARIABLE
◼ Subroutine 是哪個 routine 宣告的
◼ Type 是哪一種 Data Type
Identifier Subroutine Type Pointer
PROGRAM MAIN;
VARIABLE INTEGER:U,V,M;
CALL S1(U ,V , M );
SUBPOUTINE S1( INTEGER : X , Y , M ) ;
M = X + Y + 2.7;
FRANCIS語言所寫之程式
◼ 產生中間碼Table 6
1 ((5,1), , , )U
處理變數宣告範例(1)
VARIABLE INTEGER: U,V,M;
1 ((5,1), , , )U
2 ((5,5), , , )V
3 ((5,6), , , )M
處理變數宣告範例(2)
Identifier Subroutine Type Pointer
DIMENSION REAL: A(16,5);
◼ 必須紀錄此陣列的大小
DIMENSION
DIMENSION REAL: a(15), b(16, 18), c(13, 15, 16);
使用Information Table 7
←Real Array
←Dimensionality
←The size of the first dimension
←The size of the second dimension
◼ TYPE 1 為 ARRAY
◼ Pointer 21 指向information Table
((5,7), , , ) A
處理LABEL定義(1)
◼ 文法 LABEL identifier ;
e.g LABEL L91,L92;
◼ Type 5 表示為 LABEL
LABEL id {, id};
Forward Reference
處理LABEL定義(2)
((5,14), , , ) L91
((5,15), , , ) L92
處理LABEL(1)
◼ Pointer 指向要跳到的中間碼位置
處理LABEL(2)
處理LABEL(3)
5 ((5,14), , , ) L91
6 ((5,15), , , ) L92
10 ((1,5),(5,3),(5,10),(5,13)) L91 X=Y+Z
18 ((2,6), , , ) L92 ENP
◼ 至Table 5內找到L92指向之中間碼位置
((2,11), , ,(6,18)) GTO L92
中間碼TABLE 第18個位置
處理SUBROUTINE(1)
SUBROUTINE S1(INTEGER:X,Y,M);
◼ 可看做是PROGRAM及VARIABLE兩個部
◼ 要在TABLE 5之POINTER指向中間碼位置
◼ 要在TABLE 5之SUBROUTINE加上X,Y,M
◼ 產生X, Y, M的中間碼
Function definition or function call
Function name
處理SUBROUTINE(2)
CALL S1(W, 136, A, 57.9);
•將傳遞的參數建立在Information table
CALL id ( id {, id} )
Information table 7
((2 , 3) , (5 , 10), ,(7 , 59))
CALL S1
6.4 處理Assignment(1)
(+ , Y , Z , X)
((1,5) , (5,3) (5,10) , (5,13))
• X=Y+U*V ;
(* , U , V , T1)
(+ , Y , T1 , X)
1. 比對除了assignment以外的statement開頭,若都沒有吻合即為assignment
2. Assignment的開頭為id, 之後會接等號, 接下來為id, id後會是operator(如有下一個)
處理Assignment(2)
•使用Reverse Polish Notation
•可以透過stack來進行處理
Francis compiler 只有+ – * /和左右括號
1. 若‘(’在stack外,一定要push
2. ‘(’若是在stack內則按照正常順位
3. ‘)’ 一定要pop至 ’(’出現
( > ^ > *, / > +, – > (, ) > =
Reverse Polish Notation(1)
Input X=Y+U*V
Operand stack Operator stack
Initial 雙 stack
第一個如果是operand, push stack
第一個如果是operator, 比大小(與stack內)
Input : Y+U*V
Reverse Polish Notation(2)
Input : +U*V
Reverse Polish Notation(3)
Input : U*V
Reverse Polish Notation(4)
Reverse Polish Notation(5)
Reverse Polish Notation(6)
Reverse Polish Notation(7)
◼ 得到Reverse Polish Notation
Reverse Polish Notation(8)
X=(Y+(U*V))
1. pop一個operator, 2個operand
2. Intermediate code generation
(*, U, V, T1)
3. Push operand stack
(+, Y, T1, T2)
Y+(U*V) (=, T2, , X)
Example(1)
input X=(Y+U)*V
(+,Y,U, T1)
(*,T1,V,T2)
(=,T2, , X)
(+, Y, U, T1)
Example(2)
input X=(Y+U)*V
output (Y+U)
(*, T1, V, T2)
Example(3)
output (Y+U)*V
(=, T2, , X)
6.5 處理IF(1)
IF X GT Y AND Q THEN X=X+1 ELSE X=X+2;
14 (GT,X,Y,T4)
15 (AND,T4,Q,T1)
16 (IF,T1,(6,17),(6,20))
17 (+,X,1,T2) X=X+1
18 (=,T2, ,X)
19 (GTO, , ,(6,22))
20 (+,X,2,T3) X=X+2
21 (=,T3, ,X)
Condition Statement(true) Statement(false)
AND && GT > LE <= OR || GE >= EQ ==
NOT != LT < IF XGT Y AND Q THEN X=X+1 ELSE X=X+2 ◼ 條件部分用Reverse Polish Notation ◼ Statement則參照各statement處理 處理有陣列元素之statement(1) ◼ 算出元素所在位置 X=B(I,J)+4; 處理有陣列元素之statement(2) ◼ B(I,J)元素所在位置 (-,J,1,T1) T1=J-1 (*,T1,M,T2) T2=T1*M (+,T2,I,T3) T3=T2+I (=,B,T3,T4) T4=B(T3) (+,T4,4,T5) T5=T4+4 (=,T5, ,X) X=T5 Column major for Francis language Example 4.1 PROGRAM A1; VARIABLE INTEGER:X,Y,I; DIMENSION INTEGER:A(12); LABEL L91, L92; L91 IF X GT Y THEN GTO L92 ELSE X=X+2; Example 4.1 (Table) PROGRAM A1; VARIABLE INTEGER:X,Y,I; DIMENSION INTEGER:A(12); LABEL L91, L92; L91 IF X GT Y THEN GTO L92 ELSE X=X+2; Example 4.1(中間碼) Example 4.2 PROGRAM A2; VARIABLE INTEGER: I,J,K; DIMENSION INTEGER: A(20),B(4,5); CALL A3(I,J,K); A(K)=B(I,J)+2.7; SUBROUTINE A3(INTEGER:X,Y,K) ; VARIABLE INTEGER:Z K=(X-Z)↑2+Y; Example 4.2(Table) PROGRAM A2; VARIABLE INTEGER: I,J,K; DIMENSION INTEGER: A(20),B(4,5); CALL A3(I,J,K); A(K)=B(I,J)+2.7; SUBROUTINE A3(INTEGER:X,Y,K) ; VARIABLE INTEGER:Z K=(X-Z)↑2+Y; Example 4.2(Table) PROGRAM A2; VARIABLE INTEGER: I,J,K; DIMENSION INTEGER: A(20),B(4,5); CALL A3(I,J,K); A(K)=B(I,J)+2.7; SUBROUTINE A3(INTEGER:X,Y,K) ; VARIABLE INTEGER:Z K=(X-Z)↑2+Y; Example 4.2(中間碼) 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com