【php精品源码栏目提醒】:网学会员为需要php精品源码的朋友们搜集整理了【精品】动手编Basic解释器 - 其它资料相关资料,希望对各位网友有所帮助!
这个呵呵那些客套话咱就不扯那么多了,啥写编译器是多少程序员梦想阿,多牛逼阿之类云云这之类的话咱就不聊了,主要是这里是 C不是 java,C 程序没 java 那么多套路,直接单刀赴会了。
好了既然我们是写 basic 解释器,那我们至少先要明白 两件事情:第一,什么是解释器;第二,basic 语法这个至少要了解大概 吧。
第一,什么是解释器?编译器大家应该都知道,GCC,VC++当然这个不纯粹是编译器了,简单的说呢,编译器将程序的源代码转化为可执行代码的形式。
通常情况下,这种可执行代码由计算机的 CPU 指令组成,因此可以直接在
计算机上执行。
而解释器就不同了,它顺序读入程序的源代码,然后依次执行每一条语句。
因此,解释器并不真正将源代码转化为目标代码,而是直接执行程序。
第二,basic 语法以及我们为什么选择 basic 解释器作为编写目标先说第一个为什么写 basic? 因为 basic 语法简单,你听名字也大概知道了,比如我不会选择advance 作为编写目标,名字就比较吓人。
basic 我们不来详细讲了,因为我们做得这个解释器本来就很小,没涉及到多少东东,有需要的可以 google 一下。
这里先贴一小段代码,混个脸熟:PRINT quotA Simple Small BASIC Programquot 打印字符串FOR X 1 TO 10 for 循环GOSUB 100 跳到标号 100 语句执行 注意这里 100 是标号NEXT 下一个 x 表示 x 要加一END ‘程序结束100 PRINT X 这里相当于 C 中函数RETURN 返回代码一目了然,我们解释器基本上也就处理这几个关键字。
现在摆在我们面前的就是如何处理这些关键字,换句话来说,我们如何在程序读取到相应关键字时,做出相应反应了。
比如 我们执行 print,我们就要用 printf 把 print 后面的东东打印出来。
这还比较好办,但是如果是一个 for 循环呢,我们又该如何处理?关键字处理是个大麻烦,因为我们面对不同关键字,要做出不同反应来。
这个还是后话,眼前我们还是把主要框架先看看。
第一步 装载
源代码用过 gcc 么?郁闷 gcc 都没用过! 在 windows 下生活滋润惯了 看来 ,学计算机还是要来 opensource 阵营阿,话扯远了。
我们用 gcc 编译 c 文件时,都是 gcc -o target source 。
所以我们也仿照这格式,直接用命令行 图形界面我们就不用实现了,再说俺也不 懂。
main int argcchar argv char p_buf char t if argc2 printf quotusage: s ltfilenamegtnquotargv0 exit 1 / allocate memory for the program / if p_bufchar mallocPROG_SIZE printf quotallocation failurequot exit 1 / load the program to execute / if load_programp_bufargv1 exit1这里我 们开辟一个 PROG_SIZE 大小空间,供装载程序
源码用。
然后我们把程序代码用load_program 函数装入内存。
代码如下:/ Load a program /load_program char pchar fname FILE fp int i0 if fpfopenfnamequotrbquot return 0 i0 do p getcfp pi while feoffpampampiltPROG_SIZE p-2 0 / null terminate the program / fclose fp return 1代码很简单。
因为我们现在还没有开始处理语法,下面才是正式开始。
上次我们把程序装载入内存,这里我们开始做词法分析了。
hoho 开始一开始我们先再来回顾下:当我们的解释器在执行时,每次读入一条语句,并且根据这条语句执行特定的操作;然后再读入下一条语句,依此执行下去。
也就是说解释器执行时,每次从程序的源代码中读入一个标识符。
如果读入的是关键字,解释器就按照该关键字的要求执行规定的操作。
举例来说,当解释器读入一个 PRINT 后,它将打印 PRINT 之后的字符;当读入一个 GOSUB 时,它就执行指定的子
程序。
在到达程序的结尾之前,这个过程将反复进行。
按照上面的分析,我们所做的第一步就是要读取标识符,要一个单词一个数字的区分,比如print 要作为一个关键字读入,2345 要作为一个数字读入,而 a=3 这里要作为三个标识符读入,分别是变量 a、赋值符号=以及数值 3。
看来我们在读取标识符时,我们还需要给标识符分类。
define DELIMITER 1 //分界符 比如逗号 分号 等号 都属于这之列define VARIABLE 2 //变量define NUMBER 3 //数字define COMMAND 4 //关键字命令define STRING 5 //字符串这个比较特殊 既包括关键字 又包括常量字符串define QUOTE 6 //常量字符串 比如quothello worldquot这里仔细谈分类收获不大,待看了 get_token 这个取标识符的函数之后我们就大致明白为什么要这样分了。
token 主要目的就是读取当前的标识符,放入 token 字符数组中,并确定标识符类型,放入 token_type 中,如果是关键字,那么我们还需要处理 tok,标记为相应关键字。
/ get a token 从 basic
源码中读取一个符号token 并且区分出符号类型 我们把获取的符号放在 token 字符数组里面 在 token_type 中设置符号类型 在 tok 中设置 /get_token register char temp token_type 0 //记录标识符的类型 tok 0 //记录关键字 temp token / / if prog 0 / 文件结束 / token 0 tok FINISHED //设置文件结束符号 return token_type DELIMITER / 标号类型设置为分界符/ while iswhiteprog prog / 这里主要是除去字符串里面的空格 / if prog r / 换行符处理 / pro
gprog //这里跳过的字符quotrnquot tok EOL //设置一行结束的标识 EOLEnd Of Line token rtoken1 ntoken2 0 return token_type DELIMITER //设置为分界符 if strchrquot-/gtltquotprog / 在quot-/gtltquot查找 prog / temp prog //把这个分界符拷贝到 token 中 prog / advance to next position / temp temp0 //最后补上零 这样让 token 形成字符串 return token_type DELIMITER / 这里quot表明后面的是字符串 basic 中常常出现的情况是 print quothello worldquot 下面的例子就以此举例了 / if prog quot prog //prog 指向了字符h,注意这里已经进入了字符串 while progquotampampprogr tempprog //只要字符串没结束prog遇到双引号,或者是没换行r 我们就要把原代码拷贝到 token 中 if progr serror1 //字符串不能换行 progtemp0 //prog 已经走出字符串啦,照样的 token 要补上结束符 return token_type QUOTE //token_type 为字符串 / 数字处理 唯一要注意的是我们现在的数字是字符串形式的... / if isdigitprog while isdelimprog tempprog //如果没有分界符,拷贝之 temp 0 return token_type NUMBER / 处理字符 仍举例 print quothello worldquot 这里我们得到 print 注意该代码块没有马上返回 / if isalphaprog while isdelimprog tempprog //没有分界符拷贝之 token_type STRING //string 类型 这只是一个中间类型 具体要划分为变量、关键字 你会想为什么不会是我们打印的常量字符串呢 因为上面我们已经处理了 temp 0 //不过这一句放在外面 其实没多大意义 前面的情况都 return 了, 剩下一个孤零零 因为接下来我们还要处理这玩意儿 / 查看究竟是个命令呢还是一个变量拭目以待... / if token_type STRING tok look_uptoken / 在变量 hash 表中查之 / if tok token_type VARIABLE //变量 else token_type COMMAND //关键字 return token_typeget_token 里面还有一些小函数,这里我们同样也罗列出来。
里面嵌套的函数我都注释了的,都比较好懂,注意点我都有解释/ 回滚 /void putback char t t token for tt prog-- // / 这丫是帮我们在关键字 table 表里面搜索是否包含当前字符串 /look_upchar s register int ij char p / 命令因为我们全都用小写字符 这里不得不转换了 / p s while p p tolowerp p / 顺序查找 呃 这个是个 tiny 所以效率不太考虑了 想想如果我们关键字很多的话 应该做一个 hash 表 这里如果查找成功返回一个标号 失败返回 0 请参阅 table 结构 / for i0tablei.commandi if strcmptablei.commands return tablei.tok return 0/ 查字符 c 是否是分界符 恩 有一点要注意 比如我们的数字是 909 那么这里传进来的 c 的 ASCII 码可不是 909 应该是 90090/isdelimchar c if strchrquot-ltgt/ quotcc9crc0 //所以这里 c9 表示t 0 自然是0 return 1 return 0/ 查是不是quot空白quot就是空格和 tab 键/iswhite char c if c ct return 1 else return 0至此 标识符处理我们全部完成,
工作完成了一大块,剩下就是关键字处理了,里面涉及到语句逻辑。
经过 get_token,我们可以获取一个标识符,按理说来下步可以进行程序逻辑处理了,但是标识符获取后我们离后面的真正程序逻辑运行还有一个大障碍,这就是表达式求解的问题。
比如说我们遇到一条语句 PRINT 3ab ,这里 print 倒是能识别是个关键字,我们按照程序逻辑应该打印后面的东东,是字符串就直接打印,是变量就取值打印,但是这里偏偏是一个表达式,我们需要事先计算出表达式的值。
接下来的
问题就演变成了如何计算一个表达式,或者说写一个四则运算器。
关于如何写四则运算器,网上相关资料很多,源代码里的函数我没有解读,主要是看着不爽,逻辑性不够。
再者这个东西其实我大一自学数据结构的时候写过,主要思想是建立二叉树,然后类似一个中序遍历即可。
这里稍作解释,具体代码分析就不写了。
大家可以参照我原来 《重言式判别》的博客《四则运算》 。
我们策略是设置运算符权值,具体规则是设置初始权值为 0,扫描整个表达式,遇到+ - 号权值加 1,赋给当前运算符号,遇到乘除号,权值加 2,赋值;遇到乘方号,权值加 3,赋值;遇到左括号,权值加 4,遇到右括号,权值减 4。
比如3+34-2 初始权值赋值为 0 第一个加号,加上 1,赋给加号。
第二个乘号权值加上 2,权值为 2注意前面权值加一只是为了赋值,本身不变,赋给乘号。
后面遇到左括号,权值本身再加 4,这时权值为 4,但是这里不赋值,因为括号不参与运算,当然这只是我这里图方便,你说要赋值也不是不可,就是后面麻烦点儿。
马上又是减号,权值加 1 赋值,减号的权值变 5,接着是右括号,权值减 4。
所以整个下来有3+34-2 表达式 1 2 5 权值权值分析完毕,然后就是找出最小权值的一个符号,作为二叉树的根,权值越大的越往下生长,叶子节点全是数字。
然后递归遍历解决。
我原来那个程序只能计算表达式,但其实稍作改动就能计算变量了。
在此不再赘述。
下面贴出计算核心代码:double calculatorbinarytree root ifroot ifroot-gtleftNULLampamproot-gtrightNULL return atofamproot-gtdata else switchroot-gtdata case : return calculatorroot-gtleftcalculatorroot-gtright break case /: return calculatorroot-gtleft/calculatorroot-gtright break case : return calculatorroot-gtleftcalculatorroot-gtright break case -: return calculatorroot-gtleft-calculatorroot-gtright break case : return powcalculatorroot-gtleftcalculatorroot-gtright default: break 经过表达式求解函数 get_expvalue处理后,我们就得到这个表达式的值了。
这样,万事具备,就等着程序的逻辑处理...表达式已求,下面可以进入程序逻辑处理了,这里的代码量比较大,不过都很简单,后面主要是以程序注释为主。
先来看看完整版的主函数:main int argcchar argv char in80 int answer char p_buf char t if argc2 printf quotusage: run ltfilenamegtnquot exit 1 / allocate memory for the program / if p_bufchar mallocPROG_SIZE printf quotallocation failurequot exit 1 / load the program to execute / if load_programp_bufargv1 exit1 if setjmpe_buf exit1 / initialize the long jump / prog p_buf scan_labels /
搜索所有的标签 / ftos 0 / 初始化栈指针 这个是为 for 循环作准备的 / gtos 0 / 初始化栈指针 这个是为 gosub 作准备的 / do token_type get_token / 如果当前是变量 / if token_typeVARIABLE putback / 回退 prog 指针到变量前 / assignment / 赋值 / else / 除了变量那就是关键字了 可能有同学会问 呃 那个比如一个数字怎么没考虑 请想想一个数字怎么会单独出现 / switch tok case PRINT: print break case GOTO: exec_goto break case IF: exec_if break case FOR: exec_for break case NEXT: next break case INPUT: input break case GOSUB: gosub break case RETURN: greturn break case END: exit0 while tok FINISHEDmain 函数其实没啥好说的,主要是这个函数是个花架子,真正实在的逻辑处理不在这里。
不过特别需要强调的是 prog 这个字符指针,这是程序的命根子,它打到哪儿我们就得运行到哪儿,get_token 就得取哪儿的标识符。
当然这种重要的东西肯定是掌握在我们自己手里。
另外是 setjmp 函数,这个可以理解为 windows 系统中的
系统还原,一旦出错我们程序可以跳到这个还原点。
在 while 循环里,我们一行一行处理源代码,注意是一行一行的进行,比如 print abc 我们会在 print 函数里面循环打印 abc 。
而不会多次调用 print,这种
设计很巧妙。
来先看看变量赋值函数 assignment:/ 给变量赋值 比如 a=3 注意这里为了简化起见,我们的变量就设置为 26 个字母 /assignment int varvalue / getthe variable name / get_token if isalphatoken //因为变量我们用字母代替 所以必定是字母类型 serror4 return var touppertoken-A //转化为大写字母 然后减去A 这样让变量在 hash 表中有了座次 比如 A 减去 A 为 0 这样 A 字符变量在变量 hash 表中第一个位置 / get the equals sign 这里我们取 a3 中间的等号/ get_token if token //既然赋值么 肯定有等号了 serror3 return / a3 等号取走了 我们来取数值 / get_expampvalue / 把我们取到的变量 比如 a 值为 3 存放在 hash 表中 / variablesvar value这里的变量我们用 26 个字母表示,比较简单,减少了我们代码逻辑判断,当然缺点就是变量不能见名知义,还有有时不够用,要知道我们这个 basic 没有所谓的全局变量和局部变量,都作为全局处理的。
这里面又嵌套了一个函数——serror,看名字就知道是错误处理的:/ display an error message /void serrorint error char e quotsyntax errorquot quotunbalanced parenthesesquot quotno expression presentquot quotequal sign expectedquot quotnot a variablequot quotlabel table fullquot quotduplicate labelquot quotundefined labelquot quotTHEN expectedquot quotTO expectedquot quottoo many nested FOR loopsquot quotNEXT without FORquot quottoo many nested GOSUBquot quotRETURN without GOSUBquot printf quotsnquoteerror longjmpe_buf1 / return to save point /这个函数就是个打印,里面有个 longjmp,就是上面所说的跳到quot系统恢复点quot,与 setjmp 隔江相望。
具体可以查查ltunix 高级环境编程gt。
是所谓先来后到,我们还是按照主函数出现的顺序,依次分析逻辑函数。
1、printprint 函数主要的关注两点,第一点是打印格式,第二点是打印方式。
比如我举两例:print aprint quothello world quot 要分清楚打印变量还是打印字符串 这是打印方式的问题print abprint ab 要分清楚打印格式,注意一个是分号一个是逗号 两者有区别print 代码:/ execute a simple version of the BASIC PRINT statement 执行打印 这里我们还是举例说明/void print int answer int len0spaces char last_delim do get_token / get next list item / if tokEOLtokFINISHED break //如果取到的符号是一行结束或者文件结束 自然的打印结束 //BASIC 中 print 一般有两种用法 第二种就是 print quothello worldquot 打印字符串 if token_typeQUOTE printf quotsquottoken lenstrlentoken ge.