一门自定义的编程语言的设计及其编译器的实现

一门自定义编程语言的设计及其编译器的实现摘要编译程序是现代计算机必不可少的组成部分，它完成了将源程序转换为目标程序的全部过程。在我这次的毕业设计当中，定义和设计了一个类C的编程语言。由于我自身能力、时间和所学知识有限，设计出的这门语言十分简单，并没能提出一个准确有效的对现有编程语言的改进方案。当然，这个课题毕竟是一个很前沿的问题，作为大学毕业生的我只是对这个前沿问题进行了一些实践性的尝试。当然，我的毕业设计中最重要的部分就是实现了这门编程语言的编译器，它的主要功能包括了词法分析、语法分析、语义分析、中间代码生成（中间代码采用了四元式的结构），以及目标代码生成（目标代码采用了汇编语言），可以将符合语法的程序成功执行，并显示结果。由于技术所限，编译器没有进行进行代码优化和对错误的处理。但总体而言，这个编译器项目的功能性还是十分完备的。关键词编译器；程序设计语言；词法分析；语法分析ADESIGNOFCUSTOMPROGRAMMINGLANGUAGEANDTHEREALIZATIONOFITSCOMPILERABSTRACTTHECOMPILERISANESSENTIALPARTOFTHEMODERNCOMPUTER,ITCOMPLETEDTHESOURCETOTHETARGETPROGRAMTHEWHOLEPROCESSINMYCURRENTGRADUATIONDESIGNS,IDEFINITEDANDDESIGNEDASIMILARCPROGRAMMINGLANGUAGEBECAUSEOFMYOWNABILITY,LIMITEDTIMEANDTHEKNOWLEDGE,THELANGUAGEISVERYSIMPLE,ANDIDIDNOTABLETOPRESENTANACCURATEANDEFFECTIVEFORIMPROVEMENTPROGRAMEXISTINGPROGRAMMINGLANGUAGESOFCOURSE,THISSUBJECTISAFTERALLAVERYCUTTINGEDGEISSUES,ASUNIVERSITYGRADUATESONTHECUTTINGEDGEISSUES,IJUSTMADESOMEPRACTICALATTEMPTINADDITION,THEMOSTIMPORTANTPARTOFMYPROJECTISTOREALIZETHISPROGRAMMINGLANGUAGECOMPILER,ITSMAINFEATURESINCLUDELEXICALANALYSIS,PARSING,SEMANTICANALYSISANDCODEGENERATIONINTERMEDIATECODEUSINGAQUATERNIONTYPEOFSTRUCTURE,ANDTARGETCODEGENERATIONOBJECTCODEUSINGASSEMBLYLANGUAGE,INLINEWITHTHESYNTAXOFTHEPROGRAMCANBEEXECUTEDSUCCESSFULLY,ANDDISPLAYSTHERESULTSDUETOTECHNICALLIMITATIONS,NOCOMPILERFORCODEOPTIMIZATIONANDERRORHANDLINGOVERALL,HOWEVER,THEFUNCTIONALITYOFTHISCOMPILERPROJECTISSTILLVERYCOMPLETEDKEYWORDSCOMPLIERPROGRAMINGLANGUAGELEXICALANALYZERSSYNTAXANALYSIS目录摘要IABSTRACTII第一章绪论1一论文主要内容1（一）程序设计语言的设计1（二）编译器的实现1（三）在线编译思路的尝试1二文献综述1（一）前言1（二）研究概述2三研究编程语言的目的和意义3四研究编译器的目的和意义3第二章自定义语言的设计4一程序设计语言概述4（一）程序设计语言概念4（二）程序设计语言分类4（三）程序设计语言的实现4二程序设计语言发展现状4三程序设计语言的发展趋势5四自定义语言的设计5（一）词法的设计5（二）语法的设计6（三）中间代码的选择6第三章编译器概述7一编译器的基本概念7（一）编译器概述7（二）编译过程概述7二研发编译器的意义8三编译器的发展趋势8四尝试在线编译器的意义8五编译器的概要设计9（一）系统总体结构9（二）代码分析模块结构9（三）类结构的设计10第四章词法分析12一词法分析概述12（一）词法分析概念12（二）常用的LEX程序12二词法分析器设计12（一）词法的设计步骤12（二）正规式和DFA13（三）利用有限自动机的词法分析13三词法分析器的实现14（一）数据结构定义14（二）实现细则14第五章语法分析16一语法分析概述16二语法分析器设计16三语法分析器实现17（一）上下文无关文法17（二）LR分析方法17第六章语义分析及中间代码生成20一语义分析及中间代码生成的概念20二语义分析设计20三中间代码的选取21第七章目标代码生成22一目标代码定义22（一）简介22（二）目标代码格式22二目标代码生成概述23三实现过程23第八章系统的在线化尝试25一为什么要进行编译器在线化25（一）现有系统的局限性25（二）编译器在线化的优势26（三）在线编译器的发展现状26二在线化的设计思路26（一）开发技术概述26（二）正则表达式27（三）在线编译器功能的确立27（四）类与方法的建立27三在线化的具体实现28（一）基础页面部分28（二）逻辑部分29第九章系统测试31一测试方法概述31（一）测试方法综述31（二）本次选取的测试方法32二在线版本测试用例及结果32（一）基本运算32（二）输出字符串33（三）错误处理34三本地版本测试用例34（一）基本运算34（二）输出字符串35（三）IF语句36（四）FOR循环36四测试结果37结论38致谢40外文原文41中文翻译68第一章绪论一论文主要内容（一）程序设计语言的设计在这次的毕业设计中，为了更好的完成自己的编译器，我设计了一门自定义的编程语言，这门编程语言的设计初衷并非为了改善现有编程语言的不足或者是为了对编程语言进行某种探讨，而仅仅是为了更好的配合我的编译器的实现。不过，在设计过程中，我接触到了一些新的，有趣的知识，并在我的设计中进行了融合，并进行了一些小的尝试。之后我会用单独一章的篇幅来论述我的程序设计语言的理解和认识。（二）编译器的实现编译器的实现是我的毕业设计的主要内容，因而本篇论文的大部分章节会按照软件工程的开发流程来详细论述我的开发历程以及对编译器本身的理解。在语言选择上，我放弃了灵活的C而选择了我更为熟练的JAVA，这个决定使得我的程序在生成四元式再转为汇编的过程中遇到了一定程度的麻烦，或者说一定程度上影响了我毕业设计的质量，当然，直到开发尾声我才意识到这个问题。底层实现上，我借助了一些网上大牛写好的代码段，并配合一定量自定义的批处理，反复利用CMD来生成一个EXE文件，最终在执行这个EXE文件得到程序的运行结果。（三）在线编译思路的尝试将编译器转为在线编译器是我从做编译器一开始就有的想法，并且在整个过程中都在不断的尝试。然而，由于我的实现方式所限，最终也没能捕获执行结果，以至于我的编译器虽然拥有B/S的执行方式，但却只能在服务器端执行，唯一可行的方式是将执行结果打包，在用户执行完程序后为其提供下载服务。但是这无疑会影响用户体验。二文献综述（一）前言随机计算机技术的不断发展与进步，如今从事于软件开发行业的人越来越多。而既然选择了从事软件开发行业，就自然会与程序设计语言以及编译器结下不解之缘。但不论是谁来开发软件，都一定离不开程序设计语言，也一定离不开编译器，因为它们是一切程序之源。既然想要开发软件就必须有编程语言和编译器，那么，编程语言和编译器本身又是如何产生的呢本篇论文正是在探讨这个问题，在此之前，先需要介绍一些基本概念。程序设计语言，其实就是一组记号以及一些规则，跟句这些几号和规则组成的总体就称作计算机设计语言，它可以用来书写计算机程序。通常来讲，程序设计语言有三个要素，即语法、语义和语用。编译器，是一种基础的程序，它可以将用某种语言写成的源程序翻译成另一种编程语言，它可以将易于人类编写的高级语言翻译成复杂的低级语言，这种转换可以极大的提高人们编写程序的效率，降低程序编写的难度，所以从某种意义上说，编译程序的产生是一种历史的必然。由于编译技术历史较为久远，再加上编译器技术所涉及的技术内容十分宽泛，所以本篇论文所引用的参考文献内容也较为繁杂。论文所选用的文献涵盖了编译器技术的发展历程，各种编译器的开发背景，以及各种编程语言产生的目的和意义。同时，还有不少文献包涵了编译器的前端设计的简要介绍，同时阐述了编译所应该具有的功能以及其当前的发展现状，以及实现编译器所使用的工具甚至是参考资料。（二）研究概述上个世纪50年代，IBM的JOHNBACKUS带领着一个研究小组对FORTRAN语言及其编译器进行了开发工作。但是因为当时人们对编译理论了解很少，使得开发工作变得既复杂又艰苦。与此同时，NOAMCHOMSK带着他的团队开始了他对自然语言结构的研究工作。他的发现最终使得后来的编译器的结构变得异常简单，甚至还带有了一些自动化的属性。CHOMSKY的研究成果导致了根据语言文法的难易程度以及识别它们所需要的算法来对语言进行分类。正如现如今所称的CHOMSKY架构（CHOMSKYHIERARCHY），它包含了文法的四个层次0型文法、1型文法、2型文法和3型文法，而且其中每一个都是其前者的特殊情况。2型文法（上下文无关文法）被证明是程序设计语言中最为有用的，而且今天它已开始代表着程序设计语言结构的标准方式。分析问题（PARSINGPROBLEM，用于上下文无关文法识别的有效算法）的研究是在60年代和70年代，它相当完善的解决了这个困难的问题。现在，它已是编译原理中的一个必备的标准部分。有限状态自动机（FINITEAUTOMATON）以及正则表达式（REGULAREXPRESSION）同上下文无关文法十分紧密相关，它们与CHOMSKY的3型文法所对应。对它们的研究与CHOMSKY的研究几乎是同时开始的，并且还引出了表示程序设计语言的单词的符号表达方式。人们接着又去深化了生成有效的目标代码的方法，这就是最初的，最原始的编译器，它们被一直使用，直至今天。人们通常将把它称为优化技术（OPTIMIZATIONTECHNIQUE），但因为它从来没有真正地得到过被优化了的目标代码，而仅仅是改进了它的有效性，因此实际上它应被称作代码改进技术（CODEIMPROVEMENTTECHNIQUE）。直到现代的新编译器，大量的项目都贯注于编译器其它部分的实现生成自动化，这其中就包括了代码的生成。这些尝试并没能取得什么成果，这大概是因为操作太过复杂而人们又对其不甚了解的原因。三研究编程语言的目的和意义程序设计语言是一切软件开发活动的基础，程序设计语言的优劣直接决定了软件开发人员的开发效率，从而间接的影响到了软件的质量，因而程序设计语言的研究有着十分重要的意义。同时研究程序设计语言对于从事软件开发的人来说，也具有身份深远的意义，因为当软件开发人员开始研究和分析程序设计语言时，他就会进入一个更深层次的分析过程，这个过程将十分有利于他思考程序设计语言本身。这样的过程不仅仅可以软件开发人员更加了解程序设计语言，而且还可以使得新的程序开发软件更加的合理与高效。同时，软件开发的需求本来就是一直在进步的，程序设计语言一定会跟随着需求的变化而变化，所以，为了能更好的应对时代的需求，对编程语言的研究当然是无法避免的。四研究编译器的目的和意义编译器的设计涉及到了编译程序构造的一般原理、主要实现技术、基本设计方法和一些自动构造的工具。尽管“编译程序”是特指将高级程序设计语言翻译成低级语言的程序或者代码段，但编译程序构造的基本原理和相关技术也同样广泛应用于一般的设计和实现过程中，因此，这是一门对实践性要求较高的学问。目前，世界上有着数千种编程语言，既有FORTRAN和PASCAL这样老牌的传统程序设计语言，也有各个计算机应用领域中新出现的专用语言。目标语言的种类也同样广泛，目标语言可以是另一种程序设计语言，也可以是从微处理机到计算机的任何种类的计算机的机器语言。不同的语言需要不同的编译器。根据编译器的构造方法的不同，或者它们要实现的功能的不同，编译器通常被分为一遍编译器、多遍编译器、装入并执行编译器、调试编译器、优化编译器等等多种类别。从表面上来看，编译器的种类似乎千变万化，多种多样，不可琢磨，实质上，任何编译器所要完成的基本任务其实都是相同的。通过理解这些编译任务，我们可以利用同样的基本技术和基本方法为各种各样的源语言和目标机器构建编译器。这将很有益处。第二章自定义语言的设计一程序设计语言概述（一）程序设计语言概念程序设计语言通常是被设计成专门使用在计算机上的语言，但其实，它们也可以用来定义一些算法或者数据结构。正是因如此，程序员们才会试图通过改进使得程序代码更容易阅读。程序设计语言往往使程序员能够比使用机器语言更加准确的表达他们所想要表达的目的。对于那些从事计算机科学技术的人来说，懂得程序设计语言本身是十分重要的，因为，当今所有的计算都需要使用程序设计语言才能完成。（二）程序设计语言分类当今，有许多用于特殊用途的编程语言，它们只在特殊情况下使用。例如，PHP专门用来编辑网站服务器；而PERL则更适合文本处理；C语言却被广泛应用于操作系统和编译器等底层系统的开发。高级语言的出现使得现代的编程语言不再过度的倚赖某种特定的机器或者环境。这是因为高级语言在不同的平台上都会被编译成特定的机器语言，而不是直接就被机器执行。最早出现的编程语言之一FORTRAN的一个主要目标就是实现了平台的独立。（三）程序设计语言的实现虽然大多数的语言可以既可被编译又可被解释，但是，大多数语言仅在一种情况下能够良好的运行。在一些编译系统中，程序一般要经过几个阶段的编译，后阶段的编译往往更加接近机器语言。这种常用的使用技巧是编译程序先去编译一个叫做“0代码”的转换程序，然后再使用虚拟器，将程序转换到可以运行于机器上的底层代码。这种技巧后来又用于PASCAL和PCODE，以及SMALLTALK和二进制码，在很多时候，中间过渡的代码往往是解释，而不是编译的。如果所使用的翻译机制是将所要翻译的程序代码作为一个整体去翻译，并且在之后运行内部的格式，那么这个翻译过程就被称为编译。因此，一个编译器是把一个人可阅读的程序文本作为输入的数据，然后输出可执行文件。所输出的可执行文件是机器语言，由计算机的中央处理器直接运行，也可以是某种模拟器的二进制代码。二程序设计语言发展现状目前通用的编程语言有两种形式低级语言和高级语言。低级语言直接对硬件操作，其中汇编语言的指令采用了英文缩写的标识符，更容易识别和记忆。用汇编语言能完成的操作不是一般高级语言所能直接实现的，而且其源程序经汇编生成的可执行文件不仅体积比较小，而且执行速度非常快。而高级语言则是目前大多数编程者的选择。和汇编语言相比，它不但是将许多相关的机器指令合成为单条的指令，而且去掉了与具体操作有关但是与完成工作无关的细节，例如，使用堆栈、寄存器等等，这样就大大的简化了程序中使用的指令。于此同时，由于省略了很多细节，编程者也就不需要有太多的硬件知识。目前主流的高级语言有JAVA、C、PHYTHON、JAVASCRIPT等等，这些语言的语法、命令格式都各不相同，但它们所编制的程序都不能直接被计算机识别，必须经过转换才能被执行，因而，制作一个编译器才显得尤为重要。三程序设计语言的发展趋势程序设计语言是软件的重要方面。它的发展趋势是模块化、简明性和形式化。一、模块化。不仅语言具有模块成分，程序由模块组成，而且语言本身的结构也是模块化的。二、简明性。涉及的基本概念不多，成分简单，结构清晰，易学易用。三、形式化。发展合适的形式体系，以描述语言的语法、语义、语用。四自定义语言的设计（一）词法的设计1保留字表首先，需要定义全部的保留字，所以需要定义一个保留字表，如表21所示。表21保留字表保留字用途NULL空FOR类C的FOR循环MYPRINT输出语句BR换行语句IF条件语句BREAK跳出循环WHILEWHILE循环INT定义整型DOUBLE定义浮点型MAIN程序入口2标识符规则变量规则要求以字母开头，可由字母数字组成。函数名称规则要求全部使用字母组成。3特殊符号表与此同时，也必须在同时定义出全部的特殊符号，这里就涉及到了一张特殊符号表，这个表里面有全部的特殊符号，如表22所示。表22特殊符号表符号用途、/运算符赋值、定义优先级、|TYPE变量，变量；变量；标识符运算符标识符；变量|常量|/|IF表达式循环语句|条件语句|赋值语句赋值语句|条件语句|循环语句WHILE表达式赋值语句|条件语句|循环语句MYPRINT表达式三语法分析器实现（一）上下文无关文法在实现语法分析的过程中，使用了上下文无关文法，定义文法G，使用一个常规的四元组进行表示GV,T,P,S其中V表示文法中的非终结符号集，其中每个非终结符号都表示一个语法变量；T表示终结符号集，每个终结符号都表示一个基本符号，即词汇；P表示产生式集，文法使用产生式来定义每个非终结符号；S表示V中的一个非终结符号，称做开始符号。正常情况下，文法的每一个产生式都会由左、右两部分组成。其中，左部分是非终结符；右部分则是由零个或者若干个终结符与非终结符组合而成的符号串。（二）LR分析方法LR分析方法全称是自底向上的语法分析，它的功能非常强，适用于多种上下文无关文法。其中，L指的是从左向右去扫描输入串，R是指按照最右推导的逆过程进行归约。此处列举LR分析法的一些优点可以使用上下文无关的文法来描述程序设计的语言结构，都可以构造其LR分析器，然后进行识别。LR分析法具有一般性无回溯移进特性，是一种能被有效实现的规约文法。能使用LR分析器分析的文法类包含了能用LL1分析器去分析的全部文法。LR分析器在自左向右扫描输入串时，可以尽可能地发现语法错误。图52是一个LR分析器的结构示意图。其中，分析栈存放状态和移进、归约的文法符号S0X1S1XM1SM1S0其中，S表示状态，X表示符号，在实现过程中，文法符号不一定需要进分析栈。动作表中的项目ACTIONSM,AI的含义为当输入符号为AI、栈顶状态为SM时，分析算法应该执行的动作；若ACTIONSM,AISI，则表示移进，然后栈顶状态为IRJ时表示使用产生式J去归约；ACC在这里表示接收输入串，ERR则表示语法错误。状态转换表中的项目GOTOSI,X用来表示归约出非终结符号X后，若当前栈顶状态为SI时，分析栈应该转换到下一状态上，即所谓栈顶的新状态，这一过程参见图52。SMXMSM1XM1S1X1S0LRACTIONGOTO图52LR分析过程我所使用的LR分析算法具体为首先，要根据输入符号AI、栈顶状态SM以及动作表项ACTIONSM,AI的值，来决定当前分析应执行的动作，归约、移进、接收或出错，当移进或归约之后，要根据动作表或者状态转换表来设置分析栈的状态。其实，可以把分析栈中的串和等待输入的终结符号看作两个分量，而这两个分量构成了如下形式的二元组S0X1S1X2S2XMSM,AIAI1AN这个二元组的结构表示右句型X1X2XMAIAI1AN假设当前的分析栈栈顶为状态SM，此时下一个输入符号为AI，而分析器的下一个动作由动作表项ACTIONSM,AI决定。如果ACTIONSM,AI移进S，分析器执行移进操作，二元组变成S0X1S1X2S2XMSMAIS,AI1AN即分析器把输入符号AI以及状态S移进栈中，于是，AI1变成了下一个输入符号。如果ACTIONSM,AI归约A则分析器执行归约，二元组变成S0X1S1X2S2XMRSMRAS,AI1AN其中，S由GOTO表示确定SGOTOSMR,AI，R|，这是句柄号串的长度。当归约时，分析器从栈中弹出2R个元素其中有R个状态和R个文法符号，于是，这时使得状态SMR出现在栈顶，然后，再把归约产生式的左部的非终结符A和由GOTOSMR,A式确定的状态S压入栈。在归约的过程中，不去改变输入符号。这里，对LR分析器来说，从栈中弹出文法符号串XMR1XM总是去匹配归约产生式的右部的。若ACTIONSM,AIACC，则选择接收输入符号串，至此语法分析完成。若ACTIONSM,AIERR，则表示发现语法错误，开始调用错误处理程序。第六章语义分析及中间代码生成一语义分析及中间代码生成的概念这一阶段的任务可以概述为对前一部分，即语法分析过程所识别出的各类语法范畴做出分析，得到其具体含义，并进行初步翻译。在这里，初步翻译将会产生中间代码，即我所选择的四元式。简言之，这一部分就是根据前一阶段所产生的语法树，按照语言所定义好的语义去进行翻译，随后产生规定好的四元式这类中间代码。由于中间代码自身的特性，它们可以非常方便地转换为目标代码。例如，前面的语法树所产生的四元式序列为,_T1,10,M,_T2,Z,_T0,_T1,Y,_T1,X,_T1关于生成中间代码的原因，是因为中间代码全都非常接近于底层代码，所以中间代码的产生可以极大的简化生成目标代码的难度。同时，中间代码作为阶段性的成果出现，便于记录和标识，这也是必须的。二语义分析设计从语义分析开始，就正式开始了编译器的最主要功能翻译。在这个环节，编译器开始去理解程序代码的含义，而不仅仅是在分析代码的成分和结构。因而，在语义分析的环节，首先要明确语义分析的基本任务1类型的确定这里需要确定程序中的标识符所确定的数据类型。2类型的检查在检查环节，需要按照语言的类型给则要求，对运算符进行响应的类型转换等等。3确认含义更具语义的定义，需要去确认程序中个构造成分组合到一起的含义，并进行响应的语义处理。4其他语义检查在语义分析过程中穿插一些静态的语义检查，这里包括了不允许从循环外部转到循环内部等等。关于符号表的组织方面的一些要求和定义，编译程序一般用符号表来跟踪关于名称的汇聚信息以及它们的作用域，当词法分析器识别出标识符后，编译程序就开始查找符号表，来看它是否还在符号表中，如果不在的话，会把这个新标识符填入符号表中。而在语义分析阶段和代码生成阶段，同样也要通过查找符号来获得标识符的属性信息。可见，在编译程序运行过程中的符号表的查、填等动作非常之频繁，因而，提高符号表的查填效率就成为了提高编译程序运行效率的一个关键因素，这也是对符号表设计的一个根本的要求。三中间代码的选取由于中间代码本身对后续的代码优化以及目标代码生成有着密切的关系。同时，它的结构又和目标机器的体系结构存在一定程度的关联，所以，中间代码的选择对于编译器的效率以及质量有着很大的关系。中间代码十分接近于底层的语言，因而中间代码的选择将会直接影响转换的效率，以及最终转换成的底层代码的质量，所以，中间代码生成这一步才显得更加关键，中间代码要适应于自己的程序，这非常关键。相比较于复杂难懂的逆波兰式，四元式是一种更加接近于汇编语言的语言形式，而且四元式的结构非常易于理解，这也是我选择四元式的一个重要的原因。四元式实际上是一种所谓“三地址”语句的表示方式，它的成分是算符OP，第一和第二运算分量ARG1、ARG2，还有运算结果RESULT。四元式形如OP,ARG1,ARG2,RESULT此处特别留意了FOR循环的四元式转换过程。对于程序FORI1I|SINCEITTAKESADIFFERENTKINDOFABSTRACTMACHINETOPARSETHETWOTYPESOFGRAMMARS,ITMAKESSENSETOSEPARATETHESELOWERLEVELFUNCTIONSINTOASEPARATEMODULE,THELEXICALSCANNER,WHICHISBUILTAROUNDTHEIDEAOFASTATEMACHINETHEIDEAISTOUSETHESIMPLESTPARSINGTECHNIQUENEEDEDFORTHEJOBTHEREISANOTHER,MOREPRACTICALREASONFORSEPARATINGSCANNERFROMPARSERWELIKETOTHINKOFTHEINPUTSOURCEFILEASASTREAMOFCHARACTERS,WHICHWEPROCESSRIGHTTOLEFTWITHOUTBACKTRACKINGINPRACTICETHATISNTPOSSIBLEALMOSTEVERYLANGUAGEHASCERTAINKEYWORDSSUCHASIF,WHILE,ANDENDASIMENTIONEDEARLIER,WECANTREALLYKNOWWHETHERAGIVENCHARACTERSTRINGISAKEYWORD,UNTILWEVEREACHEDTHEENDOFIT,ASDEFINEDBYASPACEOROTHERDELIMITERSOINTHATSENSE,WEMUSTSAVETHESTRINGLONGENOUGHTOFINDOUTWHETHERWEHAVEAKEYWORDORNOTTHATSALIMITEDFORMOFBACKTRACKINGSOTHESTRUCTUREOFACONVENTIONALCOMPILERINVOLVESSPLITTINGUPTHEFUNCTIONSOFTHELOWERLEVELANDHIGHERLEVELPARSINGTHELEXICALSCANNERDEALSWITHTHINGSATTHECHARACTERLEVEL,COLLECTINGCHARACTERSINTOSTRINGS,ETC,ANDPASSINGTHEMALONGTOTHEPARSERPROPERASINDIVISIBLETOKENSITSALSOCONSIDEREDNORMALTOLETTHESCANNERHAVETHEJOBOFIDENTIFYINGKEYWORDSSTATEMACHINESANDALTERNATIVESIMENTIONEDTHATTHEREGULAREXPRESSIONSCANBEPARSEDUSINGASTATEMACHINEINMOSTCOMPILERTEXTS,ANDINDEEDINMOSTCOMPILERSASWELL,YOUWILLFINDTHISTAKENLITERALLYTHEREISTYPICALLYAREALIMPLEMENTATIONOFTHESTATEMACHINE,WITHINTEGERSUSEDTODEFINETHECURRENTSTATE,ANDATABLEOFACTIONSTOTAKEFOREACHCOMBINATIONOFCURRENTSTATEANDINPUTCHARACTERIFYOUWRITEACOMPILERFRONTENDUSINGTHEPOPULARUNIXTOOLSLEXANDYACC,THATSWHATYOULLGETTHEOUTPUTOFLEXISASTATEMACHINEIMPLEMENTEDINC,PLUSATABLEOFACTIONSCORRESPONDINGTOTHEINPUTGRAMMARGIVENTOLEXTHEYACCOUTPUTISSIMILARACANNEDTABLEDRIVENPARSER,PLUSTHETABLECORRESPONDINGTOTHELANGUAGESYNTAXTHATISNOTTHEONLYCHOICE,THOUGHINOURPREVIOUSINSTALLMENTS,YOUHAVESEENOVERANDOVERTHATITISPOSSIBLETOIMPLEMENTPARSERSWITHOUTDEALINGSPECIFICALLYWITHTABLES,STACKS,ORSTATEVARIABLESINFACT,ININSTALLMENTVIWARNEDYOUTHATIFYOUFINDYOURSELFNEEDINGTHESETHINGSYOUMIGHTBEDOINGSOMETHINGWRONG,ANDNOTTAKINGADVANTAGEOFTHEPOWEROFPASCALTHEREAREBASICALLYTWOWAYSTODEFINEASTATEMACHINESSTATEEXPLICITLY,WITHASTATENUMBERORCODE,ANDIMPLICITLY,SIMPLYBYVIRTUEOFTHEFACTTHATIMATACERTAINPLACEINTHECODEIFITSTUESDAY,THISMUSTBEBELGIUMWEVERELIEDHEAVILYONTHEIMPLICITAPPROACHESBEFORE,ANDITHINKYOULLFINDTHATTHEYWORKWELLHERE,TOOINPRACTICE,ITMAYNOTEVENBENECESSARYTOHAVEAWELLDEFINEDLEXICALSCANNERTHISISNTOURFIRSTEXPERIENCEATDEALINGWITHMULTICHARACTERTOKENSININSTALLMENTIII,WEEXTENDEDOURPARSERTOPROVIDEFORTHEM,ANDWEDIDNTEVENNEEDALEXICALSCANNERTHATWASBECAUSEINTHATNARROWCONTEXT,WECOULDALWAYSTELL,JUSTBYLOOKINGATTHESINGLELOOKAHEADCHARACTER,WHETHERWEWEREDEALINGWITHANUMBER,AVARIABLE,ORANOPERATORINEFFECT,WEBUILTADISTRIBUTEDLEXICALSCANNER,USINGPROCEDURESGETNAMEANDGETNUMWITHKEYWORDSPRESENT,WECANTKNOWANYMOREWHATWEREDEALINGWITH,UNTILTHEENTIRETOKENISREADTHISLEADSUSTOAMORELOCALIZEDSCANNERALTHOUGH,ASYOUWILLSEE,THEIDEAOFADISTRIBUTEDSCANNERSTILLHASITSMERITSSOMEEXPERIMENTSINSCANNINGBEFOREGETTINGBACKTOOURCOMPILER,ITWILLBEUSEFULTOEXPERIMENTABITWITHTHEGENERALCONCEPTSLETSBEGINWITHTHETWODEFINITIONSMOSTOFTENSEENINREALPROGRAMMINGLANGUAGES|REMEMBER,THEINDICATESZEROORMOREOCCURENCESOFTHETERMSINBRACKETS,ANDTHE,ONEORMOREWEHAVEALREADYDEALTWITHSIMILARITEMSININSTALLMENTIIILETSBEGINASUSUALWITHABARECRADLENOTSURPRISINGLY,WEAREGOINGTONEEDANEWRECOGNIZERRECOGNIZEANALPHANUMERICCHARACTERFUNCTIONISALNUMCCHARBOOLEANBEGINISALNUMISALPHACORISDIGITCENDYOUCANEASILYVERIFYTHATTHESEROUTINESWORKBYCALLINGTHEMFROMTHEMAINPROGRAMWRITELNGETNAMETHISPROGRAMWILLPRINTANYLEGALNAMETYPEDINMAXIMUMEIGHTCHARACTERS,SINCETHATSWHATWETOLDGETNAMEITWILLREJECTANYTHINGELSETESTTHEOTHERROUTINESIMILARLYWHITESPACEWEALSOHAVEDEALTWITHEMBEDDEDWHITESPACEBEFORE,USINGTHETWOROUTINESISWHITEANDSKIPWHITEMAKESURETHATTHESEROUTINESAREINYOURCURRENTVERSIONOFTHECRADLE,ANDADDTHETHELINESKIPWHITEATTHEENDOFBOTHGETNAMEANDGETNUMNOW,LETSDEFINETHENEWPROCEDURELEXICALSCANNERFUNCTIONSCANSTRINGBEGINIFISALPHALOOKTHENSCANGETNAMEELSEIFISDIGITLOOKTHENSCANGETNUMELSEBEGINSCANLOOKGETCHARENDSKIPWHITEENDYOUWILLHAVETOADDTHEDECLARATIONOFTHESTRINGTOKENATTHEBEGINNINGOFTHEPROGRAMMAKEITANYCONVENIENTLENGTH,SAY16CHARACTERSNOW,RUNTHEPROGRAMNOTEHOWTHEINPUTSTRINGIS,INDEED,SEPARATEDINTODISTINCTTOKENSSTATEMACHINESFORTHERECORD,APARSEROUTINELIKEGETNAMEDOESINDEEDIMPLEMENTASTATEMACHINETHESTATEISIMPLICITINTHECURRENTPOSITIONINTHECODEAVERYUSEFULTRICKFORVISUALIZINGWHATSGOINGONISTHESYNTAXDIAGRAM,OR“RAILROADTRACK“DIAGRAMITSALITTLEDIFFICULTTODRAWONEINTHISMEDIUM,SOILLUSETHEMVERYSPARINGLY,BUTTHEFIGUREBELOWSHOULDGIVEYOUTHEIDEA|OTHERERROR|STARTLETTEROTHERFINISH|,AND,BUTTHEYCOULDBEDEALTWITHASSPECIALCASESSTILL,OTHERLANGUAGESHAVEMULTICHARACTEROPERATORS,SUCHASTHEOFPASCALORTHEANDOFCSOWHILEWEMAYNOTNEEDMULTICHARACTEROPERATORS,ITSNICETOKNOWHOWTOGETTHEMIFNECESSARYNEEDLESSTOSAY,WECANHANDLEOPERATORSVERYMUCHTHESAMEWAYASTHEOTHERTOKENSLETSSTARTWITHARECOGNIZERRECOGNIZEANYOPERATORFUNCTIONISOPCCHARBOOLEANBEGINISOPCIN,/,ENDITSIMPORTANTTONOTETHATWEDONTHAVETOINCLUDEEVERYPOSSIBLEOPERATORINTHISLISTFOREXAMPLE,THEPARETHESESARENTINCLUDED,NORISTHETERMINATINGPERIODTHECURRENTVERSIONOFSCANHANDLESSINGLECHARACTEROPERATORSJUSTFINEASITISTHELISTABOVEINCLUDESONLYTHOSECHARACTERSTHATCANAPPEARINMULTICHARACTEROPERATORSFORSPECIFICLANGUAGES,OFCOURSE,THELISTCANALWAYSBEEDITEDNOW,LETSMODIFYSCANTOREADLEXICALSCANNERFUNCTIONSCANSTRINGBEGINWHILELOOKCRDOFINIFISALPHALOOKTHENSCANGETNAMEELSEIFISDIGITLOOKTHENSCANGETNUMELSEIFISOPLOOKTHENSCANGETOPELSEBEGINSCANLOOKGETCHARENDSKIPWHITEENDTRYTHEPROGRAMNOWYOUWILLFINDTHATANYCODEFRAGMENTSYOUCARETOTHROWATITWILLBENEATLYBROKENUPINTOINDIVIDUALTOKENSLISTS,COMMASANDCOMMANDLINESBEFOREGETTINGBACKTOTHEMAINTHRUSTOFOURSTUDY,IDLIKETOGETONMYSOAPBOXFORAMOMENTHOWMANYTIMESHAVEYOUWORKEDWITHAPROGRAMOROPERATINGSYSTEMTHATHADRIGIDRULESABOUTHOWYOUMUSTSEPARATEITEMSINALISTTRY,THELASTTIMEYOUUSEDMSDOSSOMEPROGRAMSREQUIRESPACESASDELIMITERS,ANDSOMEREQUIRECOMMASWORSTOFALL,SOMEREQUIREBOTH,INDIFFERENTPLACESMOSTAREPRETTYUNFORGIVINGABOUTVIOLATIONSOFTHEIRRULESITHINKTHISISINEXCUSABLEITSTOOEASYTOWRITEAPARSERTHATWILLHANDLEBOTHSPACESANDCOMMASINAFLEXIBLEWAYCONSIDERTHEFOLLOWINGPROCEDURESKIPOVERACOMMAPROCEDURESKIPCOMMABEGINSKIPWHITEIFLOOK,THENBEGINGETCHARSKIPWHITEENDENDTHISEIGHTLINEPROCEDUREWILLSKIPOVERADELIMITERCONSISTINGOFANYNUMBERINCLUDINGZEROOFSPACES,WITHZEROORONECOMMAEMBEDDEDINTHESTRINGTEMPORARILY,CHANGETHECALLTOSKIPWHITEINSCANTOACALLTOSKIPCOMMA,ANDTRYINPUTTINGSOMELISTSWORKSNICELY,EHDONTYOUWISHMORESOFTWAREAUTHORSKNEWABOUTSKIPCOMMAFORTHERECORD,IFOUNDTHATADDINGTHEEQUIVALENTOFSKIPCOMMATOMYZ80ASSEMBLERLANGUAGEPROGRAMSTOOKALLOF6SIXEXTRABYTESOFCODEEVENINA64KMACHINE,THATSNOTAVERYHIGHPRICETOPAYFORUSERFRIENDLINESSITHINKYOUCANSEEWHEREIMGOINGHEREEVENIFYOUNEVERWRITEALINEOFACOMPILERCODEINYOURLIFE,THEREAREPLACESINEVERYPROGRAMWHEREYOUCANUSETHECONCEPTSOFPARSINGANYPROGRAMTHATPROCESSESACOMMANDLINENEEDSTHEMINFACT,IFYOUTHINKABOUTITFORABIT,YOULLHAVETOCONCLUDETHATANYTIMEYOUWRITEAPROGRAMTHATPROCESSESUSERINPUTS,YOUREDEFININGALANGUAGEPEOPLECOMMUNICATEWITHLANGUAGES,ANDTHESYNTAXIMPLICITINYOURPROGRAMDEFINESTHATLANGUAGETHEREALQUESTIONISAREYOUGOINGTODEFINEITDELIBERATELYANDEXPLICITLY,ORJUSTLETITTURNOUTTOBEWHATEVERTHEPROGRAMENDSUPPARSINGICLAIMTHATYOULLHAVEABETTER,MOREUSERFRIENDLYPROGRAMIFYOULLTAKETHETIMETODEFINETHESYNTAXEXPLICITLYWRITEDOWNTHESYNTAXEQUATIONSORDRAWTHERAILROADTRACKDIAGRAMS,ANDCODETHEPARSERUSINGTHETECHNIQUESIVESHOWNYOUHEREYOULLENDUPWITHABETTERPROGRAM,ANDITWILLBEEASIERTOWRITE,TOBOOTGETTINGFANCYOK,ATTHISPOINTWEHAVEAPRETTYNICELEXICALSCANNERTHATWILLBREAKANINPUTSTREAMUPINTOTOKENSWECOULDUSEITASITSTANDSANDHAVEASERVICABLECOMPILERBUTTHEREARESOMEOTHERASPECTSOFLEXICALSCANNINGTHATWENEEDTOCOVERTHEMAINCONSIDERATIONISEFFICIENCYREMEMBERWHENWEWEREDEALINGWITHSINGLECHARACTERTOKENS,EVERYTESTWASACOMPARISONOFASINGLECHARACTER,LOOK,WITHABYTECONSTANTWEALSOUSEDTHECASESTATEMENTHEAVILYWITHTHEMULTICHARACTERTOKENSBEINGRETURNEDBYSCAN,ALLTHOSETESTSNOWBECOMESTRINGCOMPARISONSMUCHSLOWERANDNOTONLYSLOWER,BUTMOREAWKWARD,SINCETHEREISNOSTRINGEQUIVALENTOFTHECASESTATEMENTINPASCALITSEEMSESPECIALLYWASTEFULTOTESTFORWHATUSEDTOBESINGLECHARACTERSTHE,ANDOTHEROPERATORSUSINGSTRINGCOMPARISONSUSINGSTRINGCOMPARISONISNOTIMPOSSIBLERONCAINUSEDJUSTTHATAPPROACHINWRITINGSMALLCSINCEWERESTICKINGTOTHEKISSPRINCIPLEHERE,WEWOULDBETRU