作者：王博俊,张宇
出版社：清华大学出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
自己动手写编译器、链接器试读：
序言
因为工作的关系，我经常和各企业的技术负责人交流。话题谈着谈着常常会转到他们目前共同的难题——技术人员招聘。这时不少人都会感慨，中国能做系统软件开发的技术人员太少，这方面的人太难找了。随着中国企业的发展，做系统和平台的需求不断增加，这种供需矛盾将越来越明显。
究其原因，很容易想到的是我们的高校教育、课程设置。美国顶尖大学计算机系基础课程教学里都非常重视项目实践，操作系统课往往要真的开发一个像模像样的操作系统原型，编译器课也真的要自己设计并实现一门有创新性的小语言……
在计算机科学的各门课程中，编译器的设计实践有着特殊的重要性。“龙书”的主要作者、哥伦比亚大学教授Alfred V. Aho曾经列举过编译器实践有诸多好处：● 能让学生领悟到理论与实践的完美结合。比如编译原理所涵盖的
正则表达式和自动机，在各种场合的应用是极其广泛的，对正则
的掌握程度，从某种意义上讲甚至可以作为技术人员水平的一种
尺度。● 深入探索计算思维的多样性。与人类语言一样，不同类型的编程
语言其实代表了不同的思维方式。只用过命令式语言的人可能没
有想到，开启了大数据领域的Map与Reduce，其实在函数式语
言是一种非常常见的东西。
的确，深入了解编译器和编译原理，对于技术人员更好地理解和掌握自己最常用的语言和系统，从而提升自己的内力是有极大好处的。另一方面，随着DSL（领域特定语言）的流行，需要技术人员开发自己语言的机会也越来越多。
然而，编译原理是计算机科学里公认比较难的一门课。虽然目前国外比较重要的编译理论教材（比如龙书的《编译原理》、虎书《现代编译原理》的C语言和Java版本、鲸书《高级编译器设计与实现》）基本上都有了中文版和英文影印版，但这些书往往更偏重理论，而且门槛较高，不太适合指导一线技术人员实践和自学。我认识的一位美籍华人技术专家Ronald Mak在Wiley出版过一本基于Java的“Writing Compilers and Interpreters”，比较贴近实践，但部头较大，而且没有看到中文版。
偶然的机会，我得知王博俊在工作之余，写了一本以简化的C语言为例子讲述编译器和链接器实践的书。浏览了初稿之后，感觉全书内容简明，容易上手，又不失全面和系统，正好弥补了这方面的空白。特向大家推荐。CSDN暨《程序员》杂志总编 刘江2015年1月
自序
纸上得来终觉浅，绝知此事要躬行。——陆游编译原理与技术的一整套理论在整个计算机科学领域占有相当重要的地位，学习它对程序设计人员有很大的帮助。我们考究历史会发现那些人人称颂的程序设计大师都是编译领域的高手，像写出BASIC语言的比尔·盖茨，Sun公司的Java之父等，在编译领域都有很深的造诣。曾经在世界首富宝座上稳坐多年的比尔·盖茨也是从给微机编写BASIC语言编译器起家的，也正是这个BASIC编译器为比尔·盖茨和保罗·艾伦的微软帝国奠定了基础。这个编写BASIC语言编译器的经历，开启了比尔·盖茨的辉煌职业生涯。
编译器是一种相当复杂的程序，编写甚至读懂这样的一个程序都非易事，大多数的计算机科学家和专业人员也从来没有编写过一个完整的编译器。但是，几乎所有形式的计算都要用到编译器，而且任何一个与计算机打交道的专业人员都应掌握编译器的基本结构和操作。除此之外，计算机应用程序中经常遇到的一个任务就是命令解释程序和界面程序的开发，这比编译器要小，但使用的却是相同的技术。因此，掌握这一技术具有非常大的实际意义。
李国杰院士说：“随着微处理器技术的飞速发展，处理器性能在很大程度上取决于编译器的质量，编译技术成为计算机的核心技术，地位变得越来越重要。我国要发展自己的微处理器事业，必然要有自己的编译技术作为后盾。”
回过头来说一说是什么样的原因使我萌生了写这样一本书的想法。作者学习其他计算机课程感觉没有特别难懂的，唯独看编译原理的教材，看完了云里雾里的，感觉一知半解，我感觉可能是学的教材过于理论化，于是到书店把所有跟编译原理有关的书籍统统买回家，当然这也包括大家公认的编译原理三大经典书籍（龙书、虎书、鲸书）在内，每一本我都从头到尾翻一遍，好像什么都懂了，又感觉要真的自己动手写个编译器仍然是只有大师才能完成，对自己还是可望而不可即的事情。并且作者也了解到许多关于编译原理实践的悲观论调：“现有的编译器都是用Lex和Yacc构造的，从头开始手工编写一个完整的编译器几乎是不可能的。”可作者偏偏是那种“明知山有虎，偏向虎山行”的人，要知道早期的编译器可都是纯手工构造的，苦辣酸甜的征程就此开始，可是写个什么语言的编译器？这个编译器怎么定位？这一切都很茫然。
我开始研究编译原理书上的样例，希望能从中找到灵感，给上述问题找到答案。世界著名计算机科学家N.Worth编写的PL/0语言的编译程序是作者最先研究的编译器，它功能简单、结构清晰、可读性强，被认为是一个非常合适的小型编译程序的学习模型，可这个编译程序不支持数组、结构体、字符串，并且是以假想的栈式机器为例来编写的，而不是直接生成在某种CPU，某种操作系统环境下直接可以运行的目标语言程序。“PL/0语言的编译程序”作为编译器的学习模型，也只能算“矬子里面拔将军”，因为没有更好的，也只好将就着用了。至此，编译器定位问题算有了些眉目，作者希望构造一个更适合学习的编译器。
可是，另一个问题接踵而至，为什么那么多开源编译器不能直接用作编译器学习模型呢？我开始研究各个开源编译器的源代码，其中包括GCC的源代码，由于GCC支持多个前端语言和各种后端机器平台、AST（Abstract Syntax Tree）和RTL（Register Transfer Language）又成了绕不过去的坎，还没学会怎么编写针对一种源语言、一种目标机器的编译器，就要去学习支持多种源语言多个机器平台的编译器，就好比一个婴儿还没学会走路就要学跑，这注定是要跌跟头的。
一面是过于简化的编译器学习模型，另一面是过于复杂的开源编译器，作为学习模型都不太合适。到这里，编译器定位问题算是彻底想清楚了，作者要构造一个教大家如何自己动手写编译器的学习模型。这个模型包括两大部分，第一部分是语言定义，第二部分是这个语言编译器的实现，这个编译器只支持一种源语言，目标语言也只支持一种。这个语言应该具备目前流行的高级语言的最主要特征。这个编译器要结构清晰，代码量要尽可能少，要能体现编写一个实用的编译器的完整过程与技术。这个编译器可以生成在操作系统中直接运行的exe文件，只要双击或在命令行执行就能看到结果的那种。
接下来作者开始思考另一个问题，编写个什么语言的编译器？作者研究了目前最流行的几种编程语言C、C++、C#、Objective-C、Java，其中C语言是最简单的了，只有32个关键字，但是作者研究发现，C语言还是有许多冗余的成分，作为学习模型还可以更简单一些。作者最终以C语言为蓝本，进行适当简化定义了一门新的语言，仅有15个关键字，称为SC语言。目标语言选择大家熟悉的Intel x86机器语言，编译器命名为SCC编译器。
在本书中，读者将看到从SC语言定义，到SCC编译器开发的完整过程。读完本书你将知道一门全新的语言如何定义，一个真实的编译器如何编写，这些对你来说将不再神秘，编译原理讲的理论与本书中讲述的SC语言定义及SCC编译器开发过程，是理论联系实际在编译领域的最好阐释。
如本书作为编译原理实践教材，作者建议安排10学时讲授。
本书投稿后，有幸请CSDN暨《程序员》杂志总编、刘江老师阅读了本书的初稿，并为本书作序，在此向刘老师表示最衷心的感谢。
本书临近出版之际，承蒙清华大学王生原老师阅读了本书终稿，并对书稿做了中肯评价：“本书特色鲜明，内容有深度，文笔也很不错，很值得出版。本书最大的特色是所选的目标平台，即x86处理器以及微软系统的COFF目标文件格式，这在教材中很少见到，可为国内的编译教学实践提供别具一格的素材。”同时，王老师还对本书提出了宝贵建议。在这里，向王老师表示由衷的敬意和最诚挚的感谢。
我还要感谢我的家人，他们的支持与鼓励是本书得以完成的保障。
要列出所有对本书出版有所帮助的人名是不可能的，因为有些困难是通过互联网解决的，我甚至不知道他们的名字。在此，谨向他们一并表示感谢！
最后，回想本书6年的写作历程，愿以蒲松龄的一副对联与读者共勉：
有志者，事竟成，破釜沉舟，百二秦关终属楚；
苦心人，天不负，卧薪尝胆，三千越甲可吞吴。王博俊2015年1月
第1章 引言
世上无难事，只怕有心人——民谚编译器是将一种语言翻译为另一种语言的计算机程序。编译器将源语言编写的程序作为输入，而产生用目标语言编写的等价程序。通常，源语言为高级语言（面向人的语言），如C、C++、FORTRAN等，而目标语言为机器语言（面向目标机的语言），如Intel x86、ARM、MIPS、SPARC等。
本书将和读者一起编写一个完整的SCC（Simplified C Compiler）编译器，源语言是新定义的一门语言，称为SC（Simplified C）语言，也就是简化的C语言，目标语言是Intel x86机器语言。SCC编译器编译过程如图1.1所示。图1.1 SCC编译器编译过程
让我们一起踏上编写SCC编译器的美妙旅程，一路上可能鲜花烂漫，也可能荆棘丛生，作者作为本次旅行的导游，接下来要先给大家讲一下旅行指南，让大家对本次旅程有个大概了解。
1.1 HelloWorld编译过程分析
马克思主义认识论认为，认识是一个在实践基础上，由感性认识上升到理性认识，又由理性认识回到实践的辨证发展过程。本书的开头首先分析SC语言编写的HelloWorld程序的编译过程，以便对本书将要实现的SCC编译器的各个阶段的功能有个感性认识，第2章学习编写SCC编译器用到的编译原理知识，从第3章开始SCC编译器的实践过程。
1.1.1 HelloWorld程序源文件
HelloWorld作为所有编程语言的入门程序，占据着无法改变的地位，这个例程是从Kernighan & Ritchie合著的The C Programme Language开始有的，因为它的简洁、实用，可谓麻雀虽小，五脏俱全，一门语言的HelloWorld程序可以看作这门语言语法结构的一个缩影，因此后来几乎所有学习各种计算机语言的书都以HelloWorld程序作为学习这门语言的入门程序。下面就先看看用SC语言编写的HelloWorld程序。 1. /*********************************************************** 2. * HelloWorld.c源文件 3. **********************************************************/ 4. int main() 5. { 6. printf("Hello World!\n"); 7. return 0; 8. } 9. 10. void _entry() 11. { 12. int ret; 13. ret=main(); 14. exit(ret); 15. } 16.
上面的程序似乎与C语言编写的没什么区别。但是，仔细一看会发觉用SC语言编写的HelloWorld程序多出一个_entry函数，它是干什么用的？从字面上理解应该是程序的入口点，没错，_entry是上面SC语言HelloWorld程序的真正入口点。可能你认为，看来SC语言程序与C语言的入口点是有区别的，SC语言程序的入口点是_entry，C语言程序的入口点是main函数。
讲述C语言的书上都说“main是C语言程序的入口”，不知道大家是否对这句话的正确性怀疑过，是否深入探究过。在Visual C++下，控制台程序的入口函数是mainCRTStartup，由mainCRTStartup调用用户编写的main函数；图形用户界面（GUI）程序的入口函数是WinMainCRTStartup，由WinMainCRTStartup调用用户编写的WinMain函数；mainCRTStartup及WinMainCRTStartup函数的代码封装在已经编译好的lib库中，由链接器自动链接到生成的可执行文件中，所有这一切都是链接器悄悄干的，当然悄悄干的可不一定都是坏事，也可能无名英雄做好事。mainCRTStartup及WinMainCRTStartup函数就是这样的无名英雄，它们将该类程序开始都要做的一些必备且有技术含量的工作，悄悄地做了，并且背着广大程序员“悄悄”地做。SCC编译器是一个学习模型，目的是让可执行文件中的每一函数都由用户自己的代码产生，不要有那么多“潜规则”，这样更有助于对编译过程的深入理解。
从SC语言编写的HelloWorld程序源代码中，大致可以了解以下内容：SC语言还是保持了C语言的绝大多数功能，支持函数，函数以{开始，以}结束，支持变量声明，变量可以为int型，函数可以返回int型值，也可以返回void表示没有返回值，支持函数调用，支持字符串的处理。
1.1.2 词法分析
词法分析器读入HelloWorld.c源程序字符流，将它们组织为一系列具有词法含义的单词，词法分析器将给每个单词编上号，以便为语法分析提供便利。HelloWorld程序的单词编码表如表1.1所示。表1.1 HelloWorld单词编码表
单词列比较清楚，就是程序中一个个独立单词，编码列中KW_INT、TK_OPENPA、TK_CSTR、TK_IDENT等，代表什么呢，它们都是单词枚举类型中的标识符，当成整型常量来理解就可以了。从表1.1中可以看出单词将被分为关键字、运算符、常量及标识符，每一个标识符都将有一个独立编码。
HelloWorld单词编码看上去有些枯燥，好像也并不是很有意思，那么词法分析完成时有什么拿得出手的成果吗？请看图1.1，这里将关键字显示为绿色，运算符分隔符显示为红色，常量显示为黄色。
1.1.3 语法分析
语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出单词序列是否是给定文法的正确句子（程序）。如果在语法分析阶段语法分析程序仅仅告诉我们“你的HelloWorld.c程序符合SC语言语法”，恐怕多少有点令人沮丧，花了多少天辛辛苦苦写出来的语法分析程序，就能干这点事，恐怕我们一点成就感都没有，因为HelloWorld.c符合SC语言语法，我们早就知道的。那么费不少工夫写出来的语法分析程序能不能干点有技术含量的活呢？请看图1.3，语法分析程序实现了对HelloWorld源程序语法缩进功能。图1.3与图1.2有什么区别呢？请读者仔细对比一下。有了语法缩进程序，用SC语言写的代码再乱也不用担心了，哪怕程序完全写在一行也没关系，只要用语法自动缩进程序处理一下就美观了。图1.2 HelloWorld词法着色成果展示图1.3 HelloWorld语法缩进成果展示
1.1.4 语义分析
编译器必须要忠实地将SC语言写的程序编译成机器指令，在语义分析阶段SCC编译器要当好“傀儡”，循规蹈矩，将“主子”（SC语言）的意思忠实的传达给Intel x86处理器。在语义分析阶段将生成目标文件HelloWorld.obj，它保存了语义分析的成果，来看一下目标文件生成过程，如图1.4所示。图1.4 HelloWorld编译生成目标文件
图1.5是HelloWorld.obj文件内容，是不是看上去跟天书一样，这是我们看到的第一封天书，第7章、第8章和第9章将对这封天书从不同侧面进行全方位解读。图1.5 HelloWorld.obj文件内容
1.1.5 链接器
严格地说，链接器不属于SCC编译器的工作范畴，但SCC编译器如果就停留在此处，恐怕有些扫兴。上面的HelloWorld.obj文件只能算是个半成品，还没法直接执行，就像一家汽车生产企业，将轮胎、发动机、车身等零部件生产出来了，但是还没有组装，这样的汽车当然没法跑起来，链接器充当着组装车间的角色，它将HelloWorld.obj与C运行时库链接生成HelloWorld.exe可执行文件。这个链接及执行过程如图1.6所示。图1.6 HelloWorld.obj文件内容
这可是令人激动的时刻，具有里程碑的意义。SCC编译器最终可以生成可执行文件，执行HelloWorld.exe就会在命令行显示“Hello World！”，同样的HelloWorld.exe执行结果，但心情大不一样，因为这可是用自己亲手写的SCC编译器编译生成的。
HelloWorld.exe既熟悉，又神秘，熟悉的是，运行HelloWorld.exe就会在命令行打印出“Hello World！”，神秘的是这个文件中到底存着什么，这个文件为什么能够“指挥”计算机打印出“Hello World！”。
表1.2就是HelloWorld.exe的文件内容，省略了部分全0的内容，这是我们见到的第二封天书，这封天书将在第10章进行全方位解读，请大家拭目以待。表1.2 HelloWorld.exe文件内容
1.2 SCC编译器简介
1.2.1 SCC编译器架构
通过上述HelloWorld编译过程分析，大家已经对SCC编译器有了大致了解，本节讨论SCC编译器整体架构，参见图1.7。图1.7 SCC编译器架构
读者可能对这个图很熟悉，感觉没有什么新意，每本讲编译原理的书中都会有这个编译过程图。但大多是纸上谈兵，本书可是要实现图1.1中所有功能。有了前面对HelloWorld编译过程的分析，上面的SCC编译器架构也很容易理解，所以这里不多解释。给出这个图的目的，可用古人的话来表达为“不谋万世者，不足谋一时；不谋全局者，不足谋一域。”，SCC编译器实现过程是一项复杂的、整体的过程，各个阶段既相对独立，又紧密相关，要求在每个阶段的程序设计上要考虑后续阶段能够方便使用。
1.2.2 SCC编译器开发环境
SCC编译器是在Windows操作系统中，使用Visual Studio 6.0中的Visual C++ 6.0开发的，读者可能会问为什么不用Visual Studio .Net呢？Visual Studio 6.0虽然是Microsoft公司开发环境的老版本，但是鉴于其后继版本的主要功能变化都是为了支持.Net平台，并且安装后身躯庞大，体态臃肿，所以对于开发非.Net平台的程序，这个经典稳定的开发环境仍然是首选。
有必要对Visual Studio 6.0开发环境做一个简单介绍，以便读者对Visual Studio 6.0与Visual C++ 6.0的关系有个清晰的认识。Visual Studio 6.0 是微软公司在1998年前后推出的一个编程组件，Visual Studio 6.0中含有Visual Basic 6.0、Visual C++ 6.0、Visual J++ 6.0、Visual FoxPro 6.0、Visual SourceSafe 6.0等，而SCC编译器开发只用到了其中的Visual C++ 6.0。
Visual C++ 6.0 IDE（Integrated Development Environment，即集成开发环境）界面如图1.6所示。IDE是用于程序开发环境的应用程序，一般包括代码编辑器、编译器、链接器、调试器和图形用户界面工具等，是集成了代码编写功能、分析功能、编译功能、调试功能等一体化的开发软件套件。人们习惯上把IDE称为编译器，这个称呼有些名不符实，并且会形成误导。其实在Visual C++ 6.0 IDE中，编译时IDE会安排CL.EXE来编译，当链接时IDE会指挥LINK.EXE来链接，这时IDE整个就是一甩手掌柜，被称作编译器完全是“浪得虚名”。CL.EXE与LINK.EXE才是真正的幕后英雄，通过图1.8可看到在IDE背后一直默默奉献的两位“无名英雄”。图1.8 VC6中的编译器和链接器
讲完Visual C++6.0 IDE，这里讲一下SCC编译器使用的开发语言，VC6编译器支持C语言及C++语言的编译，当源文件后缀为.c时按C语言来编译，当源文件后缀为.cpp时，按C++来编译，SCC编译器则完全使用C语言来开发。
1.2.3 SCC编译器运行环境
这里说一下SCC编译器的运行环境，主要包括支持的处理器和操作系统两方面。Intel 80x86平台和Windows是桌面计算机上最流行的配置仍是不争的事实，所以SCC编译器目前只支持Windows操作系统，处理器只支持兼容Intel x86指令集的处理器。
这里介绍一下x86指令集处理器，Intel 8086/8088/80186/80286 CPU都为16位处理器，在市面上的PC中这些很多年前就已经销声匿迹，所以SCC编译器将不支持这些16位处理器的指令系统。1985年，Intel公司正式公布了32位处理器80386，它采用32位指令系统，有32条地址线。80386处理器在设计的时候考虑了多用户及多任务的需要，在芯片中增加了保护模式、优先级、任务切换和片内的存储单元管理等硬件单元。直到现在，运行于80x86处理器之上的多任务操作系统都是以80386的运行模式为基础的。本书中，x86指兼容80386指令集的处理器。
从80386开始，在Intel公司向市场大量推出处理器芯片的同时，其他一些电脑公司和厂商如AMD和Cyrix等，也纷纷投入大量的人力财力进行处理器的开发和研制，并很快把研制出的产品推向市场。这些CPU芯片和80386芯片兼容，在编程上可以使用与Intel处理器相同的指令集。Intel公司后来推出的80486及奔腾、赛扬、酷睿系列CPU都兼容80386指令集。
所谓SCC支持的操作系统有两层含义：一是SCC编译器所运行的操作系统；二是用SCC编译器编译生成的可执行文件所运行的操作系统。SCC编译器所运行的操作系统及生成的可执行文件所运行的操作系统皆为Win 32操作系统或者可以兼容运行Win 32应用程序的操作系统，即PC上装的Windows 2000、Windows XP、Windows Server 2003、Windows Vista、Windows 7、Windows 8都支持。
第2章 文法知识
宜未雨而绸缪，毋临渴而掘井。——朱柏庐在正式开始编写编译器之前，需要学习一点编译原理的基础知识，这里不会像《编译原理》书籍那样长篇大论面面俱到地讲那些枯燥的理论。本书对理论知识讲授本着够用就行的原则，对于不好理解的知识，还会附以生动形象的例子帮助理解。
在正式介绍文法的知识之前，先来看一下西天取经团队成员的文法定义，以便对文法有个感性认识。
① <西天取经团队成员>::=<师父>|<徒弟成员>
② <师父>::="唐僧"
③ <徒弟成员>::="孙悟空"|"猪八戒"|"沙和尚"|"白龙马"
不用多解释，大家也知道上面文法的含义吧。西天取经团队成员是师父或徒弟，师父是“唐僧”，徒弟是“孙悟空”、“猪八戒”、“沙和尚”或“白龙马”。
问大家一个问题，西天取经团队成员中，有一位他的名字中第一字是“孙”，问这位成员是谁？读者可能会说，这么弱智的问题还好意思拿出来问，当然是“孙悟空”。
再举一个例子：
<陈述句>::=<陈述句内容>。
再问大家一个问题，根据<陈述句>的方法定义，<陈述句内容>以什么结尾？当然是以句号结尾。
如果上述两个问题你都答对了，那么恭喜你，你读这本书的词法分析和语法分析部分，将不会遇到太大的困难，因为本书的词法语法部分，用到的就是这个原理。后面文绉绉的对First集、Follow集的定义，其实描述的就是这点事。请大家带着如下两个问题来阅读本章内容，第一如何定义一门语言，第二如何对一门语言进行词法分析、语法分析。
2.1 语言概述
语言是由句子组成的集合，是由一组符号所构成的集合。汉语是所有符合汉语语法的句子的全体。英语是所有符合英语语法的句子的全体。程序设计语言是所有符合该语言语法定义的程序的全体。
语言有两方面来构成：语法和语义。语法表示构成语言句子的各个记号之间的组合规律，语义表示按照各种表示方法所表示的各个记号的特定含义，即各个记号和记号所表示的对象之间的关系。每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。下面以<句子>的定义为例来说明一下语法与语义的关系。
① <句子>::=<主语><谓语>{<宾语>}
② <主语>::=<名词>
③ <宾语>::=<名词>
④ <谓语>::=<动词>
⑤ <名词>::="人"|"狗"|"花"|"鸟"|"虫"|"鱼"|"水"
⑥ <谓语>::="吃"|"喝"|打|"咬"|"睡觉"|"游泳"|"开"
根据上面的语法定义，如果说“人打狗”，“狗喝水”，“花开”，“鸟睡觉”，“虫咬人”，“鱼游泳”这些句子符合语法，语义上也没问题。但是如果说“狗打人”，“水喝狗”，“花咬鱼”，“水睡觉”，“虫游泳鸟”，“鱼打狗”，这些句子语法确实没有问题，但是语义上非常荒谬。
下面给出语法与语义关系的官方描述：语法能够描述程序设计语言的大部分语法但不是全部，例如，标识符的先声明后使用无法用上下文无关文法描述。因此，语法分析器接受的语言是程序设计语言的超集。必须通过语义分析来剔除一些符合文法、但不合法的程序。语言是语义和语法的统一，语法结构是外表，语义结构是内在。
上述官方描述，现在有些不太理解没关系，等读完本章就完全理解了。
2.2 形式语言
如果不考虑语义，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究，是程序设计语言语法分析研究的基础。
2.2.1 字母表和符号串
正如英语是由句子组成的集合，而句子又是由单词和标点符号组成的序列那样。SC程序设计语言，是由一切SC程序所组成的集合，而SC程序是由if、else、for等关键字符号，+、-、*、/等运算符，；、，、{、}等分隔符号，字母数字及下划线组成的标识符等基本符号所组成。从字面上看，每个程序都是一个“基本符号”串，设有一基本符号集，那么SC语言可看成在这个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合，因此有必要将有关符号串的一些概念做一下介绍，作为文法和语言的形式定义的预备知识。
字母表：字母表是元素的非空有穷集合，把字母表中的元素称为符号，因此字母表也称为符号集。不同语言可以有不同的字母表，例如汉语的字母表中包括汉字、数字及标点符号等。这里读者可要注意了，“字母表”可不要只机械地理解成英文字母表的26个英文字母。对于SC语言定义来说，语法定义时的字母表是指经词法分析识别出的一个个单词符号，如if、else、for、+、-、*、/、；、，、{、}等。词法分析的字母表则是a～z、A～Z、_、+、-、*、/等源码字符。
符号：字母表中的元素，语法分析时指一个个单词，词法分析指一个个源码字符。
符号串：由字母表中的符号组成的任何有穷序列称为符号串。语法分析时int abc=1代表一个符号串。词法分析时abc就代表一个符号串。在符号串中，符号的顺序是很重要的，例如符号串abc就不同于cba。可以使用字母表示符号串，如x=abc表示“x是由符号a、b和c，并按此顺序组成的符号串”。
空符号串：无任何符号的符号串或长度为零的符号串，记为ε。
符号串集合：若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。
符号串相等：若x、y是集合上的两个符号串，则x＝y当且仅当组成x的每一个符号和组成y的每一个符号依次相等。
符号串的长度：x为符号串，其长度|x|等于组成该符号串的符号个数。
例：x＝abc，|x|＝3
符号串的连接：若x、y是定义在∑上的符号串，且x＝XY，y＝YX，则x和y的连接xy＝XYYX也是∑上的符号串。注意，一般xy≠yx，而εx＝xε。
符号串集合的乘积运算：令A、B为符号串集合，定义AB＝{xy|x∈A，y∈B}
符号串集合的幂运算：有符号串集合A，定义
符号串集合的闭包运算：设A是符号串集合，定义称为集合A的正闭包。称为集合A的闭包。
SC语言程序是定义在B上的符号串。若令C为SC语言程序集合，则，程序。
2.2.2 文法与语言的形式定义
文法是对语言结构的定义与描述，即从形式上用于描述和规定语言结构的称为文法（或称为“语法”）。
当表述一种语言时，就是要说明这种语言的句子。如果语言只含有有穷多个句子，则只需列出句子的有穷集。如果语言含有无穷多个句子，则存在如何给出它的有穷表示的问题。这需要一种规则，用这些规则来描述语言的结构，可以把这些规则看成一种元语言，这些规则就称为文法。下面给出文法的定义。进而在文法定义的基础上，给出推导的概念，句型、句子和语言的定义。
定义 文法G定义为四元组（V，V，P，S）。其中V为非终NTN结符（是可以被取代的符号）集；V为终结符（语言中用到的基本T元素，不能再被分解成更小的单位）集；P为产生式（也称规则）的集合；V、V和P是非空有穷集。S称作识别符号或开始符号，它是NT一个非终结符，至少要在一条产生式中作为左部出现。
V和V不含公共的元素，即。通常用V表示V∪V，NTNTV称为文法G的字母表或字汇表。其中产生式，是形如α→β或α::=β的*（α，β）有序对，其中α是字母表V的正闭包V+中的一个符号，β是V中的一个符号。α称为规则的左部，β称为规则的右部。*
为定义文法所产生的语言，还需要引入推导的概念，即定义V中的符号之间的关系：直接推导、长度为n（n≥1）的推导和长度为n（n≥0）的推导。
定义 如α→β是文法的规则（或说是P中*的一产生式），γ和δ是V中的任意符号，若有符号串v、w满足：则说v（应用规则α→β）直接产生w，或者说，w是v的直接推导，也可以说，w直接归约到v，记作。
定义 如果存在直接推导的序列：则称v推导出（产生）w（推导长度为n），或称w归约到v。记作。
定义 若有，或v=w，则记作。
定义 设G［S］是一文法，如果符号串x是从识别符号推导出来的，即有，则称x是文法G［S］的句型。若x仅由终结符号组成，即，则称x为G［S］的句子。
定义 文法G所产生的语言定义为集合，其中S为文法识别符号，且。可用L（G）表示该集合。
从这个定义看出两点：第一，符号串x可从识别符号推出，也即x是句型。第二，x仅由终结符号组成，即x是文法G的句子。也就是说，文法描述的语言是该文法一切句子的集合。
定义 若，则称文法G和G是等价的。也就是12说，如果两个文法定义的语言一样，则称这两个文法是等价的。
定义 如果在推导的任何一步，其中v、w是句型，都
试读结束[说明：试读内容隐藏了图片]