首先生成抽象語法樹,方法如下:
1.根節(jié)點(diǎn)為0時(shí)表示沒有default標(biāo)簽,為1時(shí)表示有default標(biāo)簽
2.第0個(gè)根節(jié)點(diǎn)表示switch里的條件
3.若有default標(biāo)簽,則最后一個(gè)根節(jié)點(diǎn)為default子樹
4.每個(gè)根節(jié)點(diǎn)為0時(shí)表示在此標(biāo)簽下沒有stmt_list語句塊,這個(gè)節(jié)點(diǎn)的唯一孩子為要匹配的表達(dá)式;為1時(shí)表示有語句塊,根節(jié)點(diǎn)的左孩子表示要匹配的表達(dá)式,右孩子為要執(zhí)行的語句塊
注意:Equal指令會(huì)彈出兩操作數(shù),應(yīng)此在Equal指令執(zhí)行之前必須先保留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
生成虛擬機(jī)代碼:
For語句的翻譯比較復(fù)雜,有3個(gè)前置條件和運(yùn)行代碼,1個(gè)語句塊,也就有4*3*2*1=24種情況.應(yīng)此在生成抽象語法樹的時(shí)候我采用的是2進(jìn)制位來表示當(dāng)前塊是否存在,其中最底位表示stmt_list語句塊,倒數(shù)第2位表示by之后的語句是否存在,倒數(shù)第3位表示to之后的表達(dá)式是否存在,倒數(shù)第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
翻譯結(jié)果:
已實(shí)現(xiàn)do,while,if和賦值語句的語法制導(dǎo)翻譯,這次將他們逐層嵌套起來看看翻譯結(jié)果是否正確.
代碼:
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
翻譯結(jié)果:
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
首先生成抽象語法樹(AST)
生成方法:
1.移進(jìn)時(shí)將Number,String或Symbol分別加入對(duì)應(yīng)集合
2.歸約時(shí)從集合中取出對(duì)應(yīng)的成員,并刪除這條產(chǎn)生式里的所有終結(jié)符
3.將產(chǎn)生的語法樹節(jié)點(diǎn)壓入棧中
4.當(dāng)遇到產(chǎn)生式item_list->item_list item或stmt_list->stmt_list stmt時(shí)從棧中彈出兩顆語法樹并按順序連接起來
5.當(dāng)遇到非終結(jié)符時(shí)彈出相應(yīng)數(shù)量的語法樹節(jié)點(diǎn),生成新的根節(jié)點(diǎn)并把彈出的語法樹節(jié)點(diǎn)都連接到這個(gè)新的根節(jié)點(diǎn)上
6.當(dāng)歸約到第0條產(chǎn)生式時(shí)檢查棧的元素?cái)?shù)量,1為正常值,然后對(duì)抽象語法樹進(jìn)行前序遍歷并生成虛擬機(jī)代碼
摘要: 1 %token "function" "as" "end"; 2 %token "integer" "string" "bool" "pointer"; 3 %token "if" "then" "e...
閱讀全文
輸入文件:
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;
生成虛擬機(jī)代碼為:
賦值語句邏輯比較復(fù)雜還未完成..
分析文件:
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 }
結(jié)果:
下面的工作則是大量的語義處理...
分析器文法:
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 主要用來將給定的文法文件轉(zhuǎn)化為LALR(1)分析表,生成的cpp和h文件可使用分析器分析,out文件是語法分析表
里面有個(gè)簡單的CMinus的例子
對(duì)于給定文法文件:
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 ;
生成分析表得:
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定義,暫時(shí)還不支持正則表達(dá)式..
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函數(shù)
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 // 查找某個(gè)元素是否在表中
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 // 設(shè)置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 // 刪除某個(gè)元素
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表當(dāng)前大小
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 }
運(yùn)行結(jié)果:
由上圖可知給定的Hash表長度越長越不容易產(chǎn)生沖突,性能也就越高.
基本語法:
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 ;
生成的分析表:
由于狀態(tài)數(shù)量和非終結(jié)符數(shù)量過多,所以給出文件
《分析表》 下面是四則混合運(yùn)算的文法文件:
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 ;
對(duì)于給定表達(dá)式:
123 * 567 + 456 * (789 + 456)
生成四元碼得:
對(duì)于表達(dá)式:
123 + 456 * (789 + 456) / 123 + 789
生成四元碼得:
對(duì)于式子:10 + (5 + 9) / 3 - 7 * 3
求解過程如下:
主要在規(guī)約過程中增加了調(diào)用相關(guān)語義處理函數(shù)來實(shí)現(xiàn)計(jì)算.