BUG-01 脚本引擎部分 --词法分析&语法树生成

感谢水王的大力支持
感谢各位仁兄的支持

下面入正题

本脚本语言的上下无关文法如下：

Script                           ->      function

        |       script function

 

Function                     ->      SCRIPT stmt_sequence SCRIPT_END

 

Stmt_sequence        ->      stmt

                                     |       stmt stmt_stmtsequence

 

Stmt                              ->      if_stmt

                                     |       assign_stmt

                                     |       decl_stmt

                                     |       loop_stmt

                                     |       cmd_stmt

 

If_stmt                       ->      IF expression THEN stmt_sequence END

                                     |       IF expression THEN stmt_sequence ELSE stmt_sequence END

 

decl_stmt                  ->      STRING param_sequence SEMI

                                     |       NUMBER param_sequence SEMI

                                     |       BOOL param_sequence SEMI

 

Cmd_stmt                 ->      COMMAND QUOTE_LEFT param_sequence QUOTE_RIGHT SEMI

 

Loop_stmt                 ->      LOOP stmt_sequence UNTIL expression SEMI

 

Assign_stmt              ->      factor ASSIGN expression SEMI

 

Param_sequence     ->      factor

                                     |       factor COMMA param_sequence

 

Expression                 ->      factor op expression

                                     |       factor

 

Op                                ->      =|<=|+|-|*|/

Factor                          ->      ID|NUM|STR

实现方式，词法分析跟语法树生成是同时进行的（因为没有回溯语法）
递归下降法，其实实现起来真的很简单，只要能实现一个最简单的语法，摸清楚细节之后，其余的就是拼！
未引入错误判断机制，请勿挑战语法错！
.h文件，上面一截是词法分析的，用于getToken，下面一截用于语法树生成。忽略词法分析

 1    int getNextToken();
 2    BScrToken getToken(char*& input);
 3
 4    bool isEmpty(char*& input);
 5    //getting tokens from script
 6    int getSpace(char*& input);
 7    int getID(char*& input);
 8    int getSymbol(char*& input);
 9    int getOp(char*& input);
10    int getNumber(char*& input);
11    int getString(char*& input);
12
13    //parser
14    bool match(TokenType expected);
15    PTNode * function();
16    PTNode * stmt_sequence();
17    PTNode * stmt();
18    PTNode * assign_stmt();
19    PTNode * if_stmt();
20    PTNode * cmd_stmt();
21    PTNode * loop_stmt();
22    PTNode * decl_stmt();
23    PTNode * param_sequence();
24    PTNode * expression();
25    PTNode * factor();

.cpp
  1PTNode * BScrScanner::script()
  2{
  3    PTNode * t = new PTNode();
  4    t->type = SCRIPT_NODE;
  5    int state = getNextToken();
  6    if(state == END_OF_SCRIPT)
  7    {
  8        t->error = true;
  9        return t;
 10    }
 11    else
 12    {
 13        t->child[0] = function();
 14        if(token.type == SCRIPT)
 15        {
 16            t->child[0]->sibling = function();
 17        }
 18    }
 19    return t;
 20}
 21PTNode * BScrScanner::function()
 22{
 23    PTNode * t = new PTNode();
 24    match(SCRIPT);
 25    t->type = FUNCTION_NODE;
 26    t->child[0] = factor();
 27    t->child[1] = stmt();
 28    match(SCRIPT_END);
 29    return t;
 30}
 31
 32/**************************/
 33//out of date
 34PTNode * BScrScanner::stmt_sequence()
 35{
 36    PTNode * t = new PTNode();
 37    t->type = STMT_SEQUENCE_NODE;
 38    t->child[0] = stmt();
 39    if(token.type != SCRIPT_END && token.type != UNTIL && token.type != END && !t->child[0]->error)
 40    {
 41        t->child[1] = stmt_sequence();
 42    }
 43    return t;
 44}
 45/***************************/
 46
 47PTNode * BScrScanner::stmt()
 48{
 49    PTNode * t;
 50    switch(token.type)
 51    {
 52    case ID: t = assign_stmt(); break;
 53    case IF: t = if_stmt(); break;
 54    case LOOP: t = loop_stmt();break;
 55    case COMMAND: t = cmd_stmt();match(SEMI); break;
 56    case NUMBER:
 57    case STRING:
 58    case BOOL:
 59        t = decl_stmt(); break;
 60    default: t = new PTNode(); t->error = true;break;
 61    }
 62    if(token.type != SCRIPT_END && token.type != UNTIL && token.type != END && !t->child[0]->error)
 63    {
 64        t->sibling = stmt();
 65    }
 66    return t;
 67}
 68
 69PTNode * BScrScanner::decl_stmt()
 70{
 71    PTNode * t = new PTNode();
 72    t->type = DECL_STMT_NODE;
 73    t->val = token.token;
 74    switch(token.type)
 75    {
 76    case NUMBER:
 77        match(NUMBER);
 78        break;
 79    case STRING:
 80        match(STRING);
 81        break;
 82    case BOOL:
 83        match(BOOL);
 84        break;
 85    default:
 86        t->error = true;
 87        break;
 88    }
 89    t->child[0] = factor();
 90    match(SEMI);
 91    return t;
 92}
 93
 94PTNode * BScrScanner::assign_stmt()
 95{
 96    PTNode * t = new PTNode();
 97    t->type = ASSIGN_STMT_NODE;
 98    t->child[0] = factor();
 99    match(ASSIGN);
100    t->child[1] = expression();
101    match(SEMI);
102    return t;
103}
104
105PTNode * BScrScanner::if_stmt()
106{
107    PTNode * t = new PTNode();
108    t->type = IF_STMT_NODE;
109    match(IF);
110    t->child[0] = expression();
111    match(THEN);
112    t->child[1] = stmt();
113    if(token.type == ELSE)
114    {
115        match(ELSE);
116        t->child[2] = stmt();
117    }
118    match(END);
119    return t;
120}
121
122PTNode * BScrScanner::loop_stmt()
123{
124    PTNode * t = new PTNode();
125    t->type = LOOP_STMT_NODE;
126    match(LOOP);
127    t->child[0] = stmt();
128    match(UNTIL);
129    t->child[1] = expression();
130    match(SEMI);
131    return t;
132}
133
134PTNode * BScrScanner::cmd_stmt()
135{
136    PTNode * t = new PTNode();
137    t->type = CMD_STMT_NODE;
138    match(COMMAND);
139    match(QUOTE_LEFT);
140    t->child[0] = factor();
141    match(QUOTE_RIGHT);
142    //match(SEMI);
143    return t;
144}
145
146/********************************/
147//out of date
148PTNode * BScrScanner::param_sequence()
149{
150    PTNode * t = new PTNode();
151    t->type = PARAM_NODE;
152    t->child[0] = factor();
153    if(match(COMMA))
154    {
155        t->child[1] = param_sequence();
156    }
157    return t;
158}
159/*********************************/
160
161PTNode * BScrScanner::expression()
162{
163    PTNode * t = new PTNode();
164    t->type = EXP_NODE;
165    if(token.type == COMMAND)
166    {
167        t->child[0] = cmd_stmt();
168    }
169    else
170    {
171        t->child[0] = factor();
172    }
173    if(token.type == OP)
174    {
175        t->child[1] = factor();
176        t->child[2] = expression();
177    }
178    return t;
179}
180
181PTNode * BScrScanner::factor()
182{
183    PTNode * t = new PTNode();
184    if(token.type == ID)
185    {
186        t->type = ID_NODE;
187        t->val = token.token;
188        match(ID);
189    }
190    else if(token.type == STR)
191    {
192        t->type = STR_NODE;
193        t->val = token.token;
194        match(STR);
195    }
196    else if(token.type == NUM)
197    {
198        t->type = NUM_NODE;
199        t->val = token.token;
200        match(NUM);
201    }
202    else if(token.type == OP)
203    {
204        t->type = OP_NODE;
205        t->val = token.token;
206        match(OP);
207    }
208    else
209    {
210        t->error = true;
211    }
212    if(match(COMMA))
213    {
214        t->sibling = factor();
215    }
216    return t;
217}


这是修改版本的语法树生成
也许会出现疑问：stmt_sequence和param_sequence为什么变成out of date了呢？
由于树节点的定义里面有个兄弟节点sibling，于是可以利用这个特性，使stmt的sibling指向下一条stmt，param同理，以减少不必要的树节点。

posted on 2009-06-19 11:21 whitech 阅读(657) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


<2024年12月>
日一二三四五六
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿(1)

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜