[科普中国]-文法检查程序

简介

形式语言是：某个字母表上，一些有限长字串的集合，而形式文法是描述这个集合的一种方法，也可以称做文法。文法之所以这样命名，是因为它与人类自然语言中的文法相似的缘故。

文法检查程序是用于检查形式语言是否符合某种文法规则的程序。在计算机科学中，形式语言是编程语言及其语法的基础，因此文法检查程序也可以认为是对程序的语法分析和词法分析进行检查程序，这一过程发生在程序编译过程中。根据乔姆斯基体系将文法分为四个层次，不同层次对应的文法检查程序是有所差别的。文法检查程序主要目的是检查可能出现的语法和词法错误。

形式语言形式语言的字母是从该语言的字符串可以形成的一组符号，字母，或标记，通常它的要求是有限的。

字符串由这个称为字的字母形成，这些词属于一个特定的形式语言有时被称为形式公式。一个正式的语言，往往是通过一个正式的语法，如正则文法或上下文无关文法定义，称作形成规律。

形式语言理论主要研究的是内部结构模式这类语言的纯粹的语法领域。形式语言理论是从语言学衍生而来，作为一种理解自然语言的句法规律。在计算机科学中，形式语言通常作为定义编程语言和语法的基础，是正式版本的自然语言的子集。在计算复杂性理论中，决策问题通常定义为形式语言，复杂类被定义为形式语言的集合，它能被具有有限计算能力的机器所解析。在逻辑和数学基础中，形式语言是用来表示公理系统的语法。

乔姆斯基体系乔姆斯基体系是刻画形式文法表达能力的一个分类谱系，是由诺姆·乔姆斯基于1956年提出的。它包括四个层次：

0-型文法（无限制文法或短语结构文法）包括所有的文法1。该类型的文法能够产生所有可被图灵机识别的语言。可被图灵机识别的语言是指能够使图灵机停机的字串，这类语言又被称为递归可枚举语言。注意递归可枚举语言与递归语言的区别，后者是前者的一个真子集，是能够被一个总停机的图灵机判定的语言。

1-型文法（上下文相关文法）生成上下文相关语言。这种文法的产生式规则取如 αAβ -> αγβ 一样的形式。这里的A是非终结符号，而 α, β 和 γ 是包含非终结符号与终结符号的字串；α, β 可以是空串，但 γ 必须不能是空串；这种文法也可以包含规则 S->ε ，但此时文法的任何产生式规则都不能在右侧包含 S 。这种文法规定的语言可以被线性有界非确定图灵机接受。

2-型文法生成上下文无关语言。这种文法的产生式规则取如A-> γ 一样的形式。这里的A是非终结符号，γ 是包含非终结符号与终结符号的字串。这种文法规定的语言可以被非确定下推自动机接受。上下文无关语言为大多数程序设计语言的语法提供了理论基础。

3-型文法（正规文法）生成正规语言。这种文法要求产生式的左侧只能包含一个非终结符号，产生式的右侧只能是空串、一个终结符号或者一个非终结符号后随一个终结符号；如果所有产生式的右侧都不含初始符号 S ，规则 S -> ε 也允许出现。这种文法规定的语言可以被有限状态自动机接受，也可以通过正则表达式来获得。正规语言通常用来定义检索模式或者程序设计语言中的词法结构。

文法规则描述程序设计语言中的几类单词可用下述规则描述：

〈标识符〉→l|l〈字母数字〉

〈字母数字〉→l|d|l〈字母数字〉|d〈字母数字〉

〈无符号整数〉→d|d〈无符号整数〉

〈运算符〉→+|-|*|/|=|〈〈等号〉|〉〈等号〉……

〈等号〉→=

〈界符〉→，|；|(|)|……

其中l表示a～z中的任何一英文字母，d表示0～9中的任一数字。

关键字（保留字）也是一种单词，一般关键字（保留字）都是由字母构成，它的描述也极容易，实际上，关键字（保留字）集合是标识符集合的子集。

最复杂的一类单词要属无符号实数了，比如25.55e+5和2.1，它们可以由如下规则描述。

例

〈无符号数〉→d〈余留无符号数〉|.〈十进小数〉|e〈指数部分〉

〈余留无符号数〉→d〈余留无符号数〉|.〈十进小数〉|e〈指数部分〉|ε

〈十进小数〉→d〈余留十进小数〉

〈余留十进小数〉→e〈指数部分〉|d〈余留十进小数〉|ε

〈指数部分〉→d〈余留整指数〉|s〈整指数〉

〈整指数〉→d〈余留整指数〉

〈余留整指数〉→d〈余留整指数〉|ε

其中s表示正或负号(+，-)，d表示0～9中的任一数字。

词法分析词法分析的任务是对由字符组成的单词进行处理，从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。执行词法分析的程序称为词法分析程序或扫描器。

源程序中的单词符号经扫描器分析，一般产生二元式：单词种别；单词自身的值。单词种别通常用整数编码，如果一个种别只含一个单词符号，那么对这个单词符号，种别编码就完全代表它自身的值了。若一个种别含有许多个单词符号，那么，对于它的每个单词符号，除了给出种别编码以外，还应给出自身的值。

词法分析器一般来说有两种方法构造：手工构造和自动生成。手工构造可使用状态图进行工作，自动生成使用确定的有限自动机来实现。

语法分析编译程序的语法分析器以单词符号作为输入，分析单词符号串是否形成符合语法规则的语法单位，如表达式、赋值、循环等，最后看是否构成一个符合要求的程序，按该语言使用的语法规则分析检查每条语句是否有正确的逻辑结构，程序是最终的一个语法单位。编译程序的语法规则可用上下文无关文法来刻画。

语法分析的方法分为两种：自上而下分析法和自下而上分析法。自上而下就是从文法的开始符号出发，向下推导，推出句子。而自下而上分析法采用的是移进归约法，基本思想是：用一个寄存符号的先进后出栈，把输入符号一个一个地移进栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分归约成该产生式的左邻符号。