首页 > 代码库 > 编译器--支持条件语句和循环语句的计算器(三)

编译器--支持条件语句和循环语句的计算器(三)

在上篇文章中实现了支持变量和赋值语句的计算器,这次加入了条件语句和循环语句。

    语法简介

下面是条件语句的一个例子,能够对条件语句的格式有一个感性认识:

if  var1 > 5

then 

var2 := 10;

end

条件语句以if开始,后跟一个条件表达式,如果其为真则执行then后面的语句块,条件语句以end结束。

条件语句也可以支持else分支语句,比如

if var1 > 5

then

var2 := 10;

else

var2 := -10;

end


接下来是一个循环语句的例子:

var0 := 0;

var1 :=0;

repeat

var0 := var0 + var1;

var1 := var1 + 1;

until var1 > 100

上面这个例子是从1累加到100,结果保存在变量var0中。循环语句以repeat开始,后面是循环体,until后面是循环结束条件。


语法规则

条件语句和循环语句在代码中的实现与前一篇文章中赋值语句的实现原理相同,首先要定义出它们的语法规则,有了语法规则,在之前框架上面加入条件语句和循环语句的功能就比较简单了。下面列出两种语句的语法规则:

stmt -> id := expr;   |

    if lexpr then stmts end |

    if lexpr then stmts else stmts end |

    repeat stmts until lexpr


lexpr -> expr lop expr | expr


lop -> ‘<‘ |  ‘>‘ | ‘=‘ | ‘!=‘ | ‘>=‘ | ‘<=‘

可见主要修改的是stmt,在其中新增了if开头的两条条件表达式语法规则和repeat开头循环表达式规则。lexpr是条件表达式的语法规则,lop是几个条件操作符,lexpr条件表达式的运算符是expr算术表达式。


下面是之前提到的的语法规则,一并列出以方便查看:

stmts -> stmts stmt | stmt 


id -> (letter|_) (letter | num)*       


expr -> term |  term+term | term-term  

                  

term -> factor | factor * factor | factor/factor


factor -> number | (expr) | id


number -> (0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9)*


语法树

之前有提到,求值的过程是在语法树的基础上进行的。对于条件表达式和循环表达式同样要建立对应的语法树,下面分别对应举两个例子:

对于如下条件语句:

if var0 > 5

then

var1 := 10 * 2;

else

var1 := -3 / 3;

end

会生成如下的语法树:


if根节点存在三个子结点child,child[0]对应条件表达式,child[1]对应then后面的语句块,child[2]对应else后面的语句块。对该表达式求值的过程是先求条件表达式child[0]的值,若返回值非0,则计算then语句块child[1]的值,否则计算else语句块child[2]的值。


下面是一个repeat循环语句的例子:

repeat

 var0 := var0 + var1;

var1 := var1 + 1;

until var1 > 100

为该循环语句生成语法树如下:

        

repeat根节点有两个子结点,左子结点是repeat后语句块,右子节点是until后的条件表达式。repeat后语句块中的每一个语句都是一个节点,语句之间互为兄弟节点,图中的横向箭头就指向其兄弟节点。对repeat语法树求值的过程是先对repeat语句块进行求值,然后计算条件表达式的值,如果该值为假,那么继续循环对语句块求值,直到语句块的值为真则退出循环。repeat是一个其循环体至少会执行一次的循环。


if的语法树生成

下面是stmt函数中新增对if语句进行求值的case分支:

case IF:
		        node = newNode();
		        node->kind = Stmt;
		        node->attr.s = IfK;
		        node->val.tt = IF;
		        /*匹配if*/
		        match(IF);

		        lnode = lexp();
                <span style="white-space:pre">	</span>node->child[0] = lnode;
                <span style="white-space:pre">	</span>/*匹配then*/
		        match(THEN);
                <span style="white-space:pre">	</span>lnode = stmts();
               <span style="white-space:pre">	</span> <span style="white-space:pre">	</span>node->child[1] = lnode;
                <span style="white-space:pre">	</span>/*存在else*/
                <span style="white-space:pre">	</span>if (ELSE == token)
                <span style="white-space:pre">	</span>{
                     <span style="white-space:pre">		</span>match(ELSE);
                     <span style="white-space:pre">		</span>rnode = stmts();
                     <span style="white-space:pre">		</span>node->child[2] = rnode;
                <span style="white-space:pre">	</span>}
                <span style="white-space:pre">	</span>/*匹配end*/
                <span style="white-space:pre">	</span>match(END);
		        break;

这段代码的逻辑很清晰,先建立一个if的节点,然后匹配if标识符,接下来调用lexp来匹配一个条件表达式,然后匹配then,后面是调用stmts进行语句块的的匹配。如果存在else,匹配else后再次调用stmts进行语句块的匹配。最后匹配end。


repeat的语法树生成

下面是对repeat语句进行求值的case分支:

		case REPEAT:
				node = newNode();
				node->kind = Stmt;
				node->attr.s = RepeatK;
				node->val.tt = REPEAT;

				/*匹配repeat*/
				match(REPEAT);

				lnode = stmts();

				/*匹配until*/
				match(UNTIL);
				/*条件表达式*/
				rnode = lexp();

				node->child[0] = lnode;
				node->child[1] = rnode;
				break;
这段代码与if语句的处理分支类似,了解repeate的语法格式就很容易理解这段代码了。


逻辑表达式的语法树生成

条件表达式匹配函数lexp与算术表达式exp类似,不过其优先级要低于算术表达式,下面是条件表达式和算术表达式对应的语法规则,集中列出来更容易看清楚他们的优先级:

lexpr -> expr lop expr | expr

            expr -> term |  term+term | term-term  

term -> factor | factor * factor | factor/factor

factor -> number | (expr) | id


从上到下依次代表条件表达式,加减表达式,乘除表达式,最后是最小的语法单元(数字,变量以及用括号括起来的表达式)。

下面是处理逻辑表达式的函数lexp,其逻辑与其语法规则是对应的:

/*逻辑表达式*/
TreeNode *lexp()
{
    TreeNode *node;
    TreeNode *lnode, *rnode;

    node = exp();

    while ((GT == token) || (LT == token) ||(GE == token) || (LE == token) ||
        (NE == token) || (EQ == token))
    {
              /*左节点*/
		lnode = node;
		
		/*操作符节点,即根节点*/
		node = newNode();
		node->attr.e = OpK;
		node->val.tt = token;
		node->child[0] = lnode;
		
		match(token);

		/*右节点*/
		rnode = exp();

		node->child[1] = rnode;
    }

    return node;
}
由于逻辑操作符的左侧是算术表达式,所以先调用exp来处理算术表达式,接下来判断算术表达式后面是否跟着逻辑操作符,如果是的话,就处理逻辑操作符右侧的算术表达式。while循环用来处理逻辑操作符连续的情况,逻辑操作符的为左结合。


if的语法树求值

下面的代码是calc函数中对应if语句求值的分支:

<span style="white-space:pre">			</span>case IfK:
		      		    val = calc(node->child[0]);             /*计算条件表达式*/
		      		    if (val)
		      		    {
		      		          val = calc(node->child[1]);       /*计算then*/
		      		    }
		      		    else if (node->child[2] != NULL)
		      		    {
		      		          val = calc(node->child[2]);       
		      		    }
		      	            break;
可以看出代码很简单,先调用calc对if语法树的第一个子结点求值,该子结点对应条件表达式,检查返回值如果为真,则计算then后的语句块,否则检查是否存在else语句,如果存在就计算else后语句块的值。


repeat的语法树求值

下面代码是calc函数对应repeat语句的求值的分支:

		      	    case RepeatK:
		      	    	do
		      	    	{
		      	    		val = calc(node->child[0]);				/*先执行语句块*/
		      	    		val1 = calc(node->child[1]);			/*计算条件表达式的值*/
		      	    	}while (val1 == 0);
		      	    	break;
可以看出求值的过程相当简单,先计算repeat后面语句块的值,然后计算until后条件表达式的值,如果条件表达式的值为假,则循环一直继续,当条件表达式的值为真时,退出循环。


保留字

if和repeat语句中出现的这些控制流程的字符串都是保留字,比如if, then, end,repeat,until,下面是在代码中用到的保留字

Reserve reservewords[] = 
{
   {"if", IF},
   {"then", THEN},
   {"else", ELSE},
   {"end", END},
   {"repeat", REPEAT},
   {"until", UNTIL},
   {NULL, NONUSE}
};
在getToken函数中解析到一个ID类型的token后,会判断是否是保留字,如果是保留字,就返回保留字相应的token类型。

位于getToken函数最后的这段代码执行了判断保留字的任务:

<span style="white-space:pre">	</span>tval[index] = '\0';
	/*判断ID是否是保留字*/
	if (ID == token)
	{
	    tt = isreserve(tval);
	    if (NONUSE != tt)
	    {
	        token = tt;
	    }
	}


好了,条件语句和循环语句的实现要点基本就介绍ok了,下面就举一个例子。

首先编译源代码得到可执行文件mycpl。

然后保存下面需要计算的代码到任意文件,比如test

a:=1;
b:=0;
d:=-1;
if d < 0
then
	d:=10;
end

repeat
b := b+a;
a := a+1;
until a > 5

b :=b+d;

执行: ./mycpl test

得到结果:The result is 25.


注意:打印出来的结果是最后一个赋值语句返回的值,这里即是变量b的值。


源代码下载链接:http://download.csdn.net/detail/luo3532869/8053303

代码可以任意使用和传播。

Email: robin.long.219@gmail.com 欢迎交流^_^

编译器--支持条件语句和循环语句的计算器(三)