首先生成抽象語法樹,方法如下:
1.根節點為0時表示沒有default標簽,為1時表示有default標簽
2.第0個根節點表示switch里的條件
3.若有default標簽,則最后一個根節點為default子樹
4.每個根節點為0時表示在此標簽下沒有stmt_list語句塊,這個節點的唯一孩子為要匹配的表達式;為1時表示有語句塊,根節點的左孩子表示要匹配的表達式,右孩子為要執行的語句塊
注意:Equal指令會彈出兩操作數,應此在Equal指令執行之前必須先保留switch里exp的副本(即Push一次),最后彈出副本
測試代碼:
1 integer aaa,bbb
2
3 function ccc()
4 switch aaa + 1 do
5 default:
6 aaa = 123
7 case 123:
8 do
9 aaa = aaa + 1
10 while aaa < 789 end
11 case 456:
12 aaa = 123
13 end switch
14 end function
生成虛擬機代碼:
posted @
2010-09-29 15:55 lwch 閱讀(1296) |
評論 (0) |
編輯 收藏
For語句的翻譯比較復雜,有3個前置條件和運行代碼,1個語句塊,也就有4*3*2*1=24種情況.應此在生成抽象語法樹的時候我采用的是2進制位來表示當前塊是否存在,其中最底位表示stmt_list語句塊,倒數第2位表示by之后的語句是否存在,倒數第3位表示to之后的表達式是否存在,倒數第4位表示for之后的語句是否存在.
代碼:
1 integer aaa,bbb
2
3 function ccc()
4 do
5 for aaa = 456 to by do
6 if aaa == 456 then
7 aaa = 789
8 end if
9 next
10 aaa = 123
11 while aaa == 123 end
12 end function
翻譯結果:
posted @
2010-09-22 12:20 lwch 閱讀(1628) |
評論 (0) |
編輯 收藏
已實現do,while,if和賦值語句的語法制導翻譯,這次將他們逐層嵌套起來看看翻譯結果是否正確.
代碼:
1 integer aaa
2
3 function ccc()
4 while aaa == 123 do
5 do
6 if aaa == 123 then
7 if aaa == 456 then aaa = 123
8 else aaa = 456
9 end if
10 end if
11 while aaa == 123 end
12 end while
13 aaa = 456
14 end function
翻譯結果:
posted @
2010-09-20 22:29 lwch 閱讀(1605) |
評論 (2) |
編輯 收藏1 integer aaa
2
3 function ccc()
4 if aaa and true then
5 end if
6 end function
1 integer aaa
2
3 function ccc()
4 if aaa and true then
5 aaa = 123
6 end if
7 end function
1 integer aaa
2
3 function ccc()
4 if aaa and true then
5 else
6 end if
7 end function
1 integer aaa
2
3 function ccc()
4 if aaa and true then
5 aaa = 123
6 else
7 end if
8 end function
1 integer aaa
2
3 function ccc()
4 if aaa and true then
5 else
6 aaa = 123
7 end if
8 end function
1 integer aaa
2
3 function ccc()
4 if aaa and true then
5 aaa = 123
6 else
7 aaa = 456
8 end if
9 end function
posted @
2010-09-19 07:27 lwch 閱讀(1639) |
評論 (0) |
編輯 收藏
首先生成抽象語法樹(AST)
生成方法:
1.移進時將Number,String或Symbol分別加入對應集合
2.歸約時從集合中取出對應的成員,并刪除這條產生式里的所有終結符
3.將產生的語法樹節點壓入棧中
4.當遇到產生式item_list->item_list item或stmt_list->stmt_list stmt時從棧中彈出兩顆語法樹并按順序連接起來
5.當遇到非終結符時彈出相應數量的語法樹節點,生成新的根節點并把彈出的語法樹節點都連接到這個新的根節點上
6.當歸約到第0條產生式時檢查棧的元素數量,1為正常值,然后對抽象語法樹進行前序遍歷并生成虛擬機代碼
posted @
2010-09-17 22:21 lwch 閱讀(759) |
評論 (0) |
編輯 收藏
摘要: 1 %token "function" "as" "end"; 2 %token "integer" "string" "bool" "pointer"; 3 %token "if" "then" "e...
閱讀全文
posted @
2010-09-17 22:04 lwch 閱讀(1077) |
評論 (0) |
編輯 收藏
輸入文件:
1 string abc,def;
2
3 void main()
4 {
5 int abc,def;
6 read(abc);
7 write(abc);
8 write("aaa");
9 }
10
11 void aaa()
12 {
13 int abc;
14 }
15
16 int ddd,fff;
生成虛擬機代碼為:
賦值語句邏輯比較復雜還未完成..
posted @
2010-09-01 16:09 lwch 閱讀(1422) |
評論 (0) |
編輯 收藏分析文件:
1 string abc;
2
3 void main()
4 {
5 int a,b,c;
6 read(a);
7 write("aaa");
8 write(a);
9 b = 10;
10 c = 100;
11 }
12
13 int cc()
14 {
15 }
結果:
下面的工作則是大量的語義處理...
posted @
2010-08-31 23:27 lwch 閱讀(639) |
評論 (0) |
編輯 收藏分析器文法:
1 %token "%token" "%start" ;
2 %token ";" "->" "|" ;
3
4 %start program ;
5
6 program -> item_list
7 ;
8
9 item_list -> item_list item
10 | item
11 ;
12
13 item -> token_def ";"
14 | start_def ";"
15 | rule_def ";"
16 | ";"
17 ;
18
19 token_def -> token_def "{String}"
20 | "%token" "{String}"
21 ;
22
23 start_def -> "%start" "{Symbol}"
24 ;
25
26 rule_def -> "{Symbol}" "->" rhs_list
27 ;
28
29 rhs_list -> rhs_list "|" rhs
30 | rhs
31 ;
32
33 rhs -> rhs "{String}"
34 | rhs "{Symbol}"
35 | "{String}"
36 | "{Symbol}"
37 ;
38
NScriptMacro 主要用來將給定的文法文件轉化為LALR(1)分析表,生成的cpp和h文件可使用分析器分析,out文件是語法分析表
里面有個簡單的CMinus的例子
posted @
2010-08-30 17:29 lwch 閱讀(1501) |
評論 (1) |
編輯 收藏
對于給定文法文件:
1 %token "if" "then" "else" "end" ;
2 %token "st" ;
3 %token "+" "*" ;
4
5 %start program ;
6
7 program -> if_stmt
8 ;
9
10 if_stmt -> "if" exp "then" stmt "end"
11 | "if" exp "then" stmt "else" stmt "end"
12 ;
13
14 exp -> exp1
15 ;
16
17 exp1 -> exp1 "+" exp2
18 | exp2
19 ;
20
21 exp2 -> exp2 "*" exp3
22 | exp3
23 ;
24
25 exp3 -> "{LQ}" exp1 "{RQ}"
26 | "{digit}"
27 ;
28
29 stmt -> "st"
30 ;
生成分析表得:
posted @
2010-08-28 15:28 lwch 閱讀(280) |
評論 (0) |
編輯 收藏 1 %token "%token" "%start" ;
2 %token ";" "->" "|" ;
3
4 %start program ;
5
6 program -> item_list
7 ;
8
9 item_list -> item_list item
10 | item
11 ;
12
13 item -> token_def ";"
14 | start_def ";"
15 | rule_def ";"
16 | ";"
17 ;
18
19 token_def -> token_def "{String}"
20 | "%token" "{String}"
21 ;
22
23 start_def -> "%start" "{Symbol}"
24 ;
25
26 rule_def -> "{Symbol}" "->" rhs_list
27 ;
28
29 rhs_list -> rhs_list "|" rhs
30 | rhs
31 ;
32
33 rhs -> rhs "{String}"
34 | rhs "{Symbol}"
35 | "{String}"
36 | "{Symbol}"
37 ;
38
去除了letter定義,暫時還不支持正則表達式..
posted @
2010-08-28 15:23 lwch 閱讀(231) |
評論 (0) |
編輯 收藏 1 #include <iostream>
2
3 template <typename _Type>
4 class HashTable
5 {
6 public:
7 HashTable(int Length)
8 {
9 Element = new _Type[Length];
10 for(int i=0;i<Length;i++)
11 Element[i] = -1;
12 this->Length = Length;
13 Count = 0;
14 }
15
16 ~HashTable()
17 {
18 delete[] Element;
19 }
20
21 // Hash函數
22 virtual int Hash(_Type Data)
23 {
24 return Data % Length;
25 }
26
27 // 再散列法
28 virtual int ReHash(int Index,int Count)
29 {
30 return (Index + Count) % Length;
31 }
32
33 // 查找某個元素是否在表中
34 virtual bool SerachHash(_Type Data,int& Index)
35 {
36 Index = Hash(Data);
37 int Count = 0;
38 while(Element[Index] != -1 && Element[Index] != Data)
39 Index = ReHash(Index,++Count);
40 return Data == Element[Index] ? true : false;
41 }
42
43 virtual int SerachHash(_Type Data)
44 {
45 int Index = 0;
46 if(SerachHash(Data,Index)) return Index;
47 else return -1;
48 }
49
50 // 插入元素
51 bool InsertHash(_Type Data)
52 {
53 int Index = 0;
54 if(Count < Length && !SerachHash(Data,Index))
55 {
56 Element[Index] = Data;
57 Count++;
58 return true;
59 }
60 return false;
61 }
62
63 // 設置Hash表長度
64 void SetLength(int Length)
65 {
66 delete[] Element;
67 Element = new _Type[Length];
68 for(int i=0;i<Length;i++)
69 Element[i] = -1;
70 this->Length = Length;
71 }
72
73 // 刪除某個元素
74 void Remove(_Type Data)
75 {
76 int Index = SerachHash(Data);
77 if(Index != -1)
78 {
79 Element[Index] = -1;
80 Count--;
81 }
82 }
83
84 // 刪除所有元素
85 void RemoveAll()
86 {
87 for(int i=0;i<Length;i++)
88 Element[i] = -1;
89 Count = 0;
90 }
91
92 void Print()
93 {
94 for(int i=0;i<Length;i++)
95 printf("%d ",Element[i]);
96 printf("\n");
97 }
98 protected:
99 _Type* Element; // Hash表
100 int Length; // Hash表大小
101 int Count; // Hash表當前大小
102 };
103
104 void main()
105 {
106 HashTable<int> H(10);
107 printf("Hash Length(10) Test:\n");
108 int Array[6] = {49,38,65,97,13,49};
109 for(int i=0;i<6;i++)
110 printf("%d\n",H.InsertHash(Array[i]));
111 H.Print();
112 printf("Find(97):%d\n",H.SerachHash(97));
113 printf("Find(49):%d\n",H.SerachHash(49));
114 H.RemoveAll();
115 H.SetLength(30);
116 printf("Hash Length(30) Test:\n");
117 for(int i=0;i<6;i++)
118 printf("%d\n",H.InsertHash(Array[i]));
119 H.Print();
120 printf("Find(97):%d\n",H.SerachHash(97));
121 printf("Find(49):%d\n",H.SerachHash(49));
122 system("pause");
123 }
運行結果:
由上圖可知給定的Hash表長度越長越不容易產生沖突,性能也就越高.
posted @
2010-08-10 23:37 lwch 閱讀(567) |
評論 (1) |
編輯 收藏基本語法:
1 %token "%token" "%letter" "%start" ;
2 %token ":" ";" "->" "|" ;
3
4 %letter string : "{string}" ;
5 %letter symbol : "{symbol}" ;
6
7 %start program ;
8
9 string_list -> string_list string
10 | string
11 ;
12
13 symbol_list -> symbol_list symbol
14 | symbol
15 ;
16
17 program -> item_list
18 ;
19
20 item_list -> item_list item
21 | item
22 ;
23
24 item -> token_def ";"
25 | letter_def ";"
26 | start_def ";"
27 | rule_def ";"
28 | ";"
29 ;
30
31 token_def -> "%token" string_list
32 ;
33
34 letter_def -> "%letter" symbol ":" string_list
35 ;
36
37 start_def -> "%start" symbol
38 ;
39
40 rule_def -> symbol "->" rhs_list
41 ;
42
43 rhs_list -> rhs_list "|" rhs
44 | rhs
45 ;
46
47 rhs -> term_list
48 ;
49
50 term_list -> term_list string
51 | term_list symbol
52 | string
53 | symbol
54 ;
生成的分析表:
由于狀態數量和非終結符數量過多,所以給出文件
《分析表》 下面是四則混合運算的文法文件:
1 %token "+" "-" ;
2 %token "*" "/" ;
3 %token "(" ")" ;
4
5 %letter AddOp : "+" "-" ;
6 %letter MulOp : "*" "/" ;
7 %letter ID : "{digit}" ;
8 %letter LQ : "(" ;
9 %letter RQ : ")" ;
10
11 %start Program ;
12
13 Program -> Exp
14 ;
15
16 Exp -> Exp AddOp Term
17 | Term
18 ;
19
20 Term -> Term MulOp Factor
21 | Factor
22 ;
23
24 Factor -> LQ Exp RQ
25 | ID
26 ;
posted @
2010-08-03 20:21 lwch 閱讀(305) |
評論 (0) |
編輯 收藏
對于給定表達式:
123 * 567 + 456 * (789 + 456)
生成四元碼得:
對于表達式:
123 + 456 * (789 + 456) / 123 + 789
生成四元碼得:
posted @
2010-08-01 01:05 lwch 閱讀(444) |
評論 (0) |
編輯 收藏
對于式子:10 + (5 + 9) / 3 - 7 * 3
求解過程如下:
主要在規約過程中增加了調用相關語義處理函數來實現計算.
posted @
2010-07-26 11:41 lwch 閱讀(378) |
評論 (0) |
編輯 收藏