如何自己动手开发编译器（六）：探讨上下文无关语言与文法？

本文共计3094个文字，预计阅读时间需要13分钟。

回顾我们已学习的语法分析第一阶段——词法分析的理论和工具，介绍了正规表达式、正则语言和DFA等工具。此次，我们将开始涉及编译器前端最重要的阶段——词法分析。

上回我们已经学习了语法分析第一阶段——词法分析的原理和工具，介绍了正则表达式、正则语言和DFA等工具。今次我们要开始涉及编译器前端最重要的阶段——语法分析。简单而言，这一步就要完整地分析整个编程语言的语法结构。上回说到词法分析的结果是将输入的字符串分解成一个个的单词流，也就是诸如关键字、标识符这样有特定意义的单词。一种完整的编程语言，必须在此基础上定义出各种声明、语句和表达式的语法规则。观察我们所熟悉的编程语言，其语法大都有某种递归的性质。例如四则运算与括号的表达式，其每个运算符的两边，都可以是任意的表达式。比如1+a是表达式，(1+a)*(2 – c)也是表达式，((a+b) + c) * (d – e)也是表达式。再比如if语句，其if的块和else的块中还可以再嵌套if语句。我们在词法分析中引入的正则表达式和正则语言无法描述这种结构，如果用DFA来解释，DFA只有有限个状态，它没有办法追溯这种无限递归。所以，编程语言的表达式，并不是正则语言。我们要引入一种表现能力更强的语言——上下文无关语言。

要介绍上下文无关语言，我们先来了解一下定义上下文无关文法的工具——产生式的写法。我们还是使用编程语言的表达式作为例子，但这次我们假设表达式只有三种——单个表示变量名标识符、括号括起来的表达式和两个表达式相加。比如a是一个变量表达式，a+b是两个变量表达式相加的表达式，(a+b)是一个括号表达式。