跳转到内容

编程语言/语法简介

来自维基教科书,开放的书籍,开放的世界

一种编程语言由其语义及其语法的组合来描述。语义告诉我们该编程语言中所有可能构造的含义。语法告诉我们它的结构。描述编程语言语义有很多不同的方法;但是,经过数十年的研究,描述其语法的方法大多只有一种。我们称这种形式化方法为上下文无关文法

请注意,上下文无关文法不是计算机用来识别语言的唯一一种文法。实际上,存在一整套形式文法,这些文法最初是由诺姆·乔姆斯基研究的,今天我们通常称之为乔姆斯基层次结构。该层次结构中的一些成员,如正则文法非常简单,并且识别相对较少的语言。然而,这些文法仍然非常有用。例如,正则文法是编译器词法分析的核心。其他类型的文法非常强大。例如,无限制文法的计算能力与图灵机一样强大。然而,在这本书中,我们将重点关注上下文无关文法,因为它们是编译器用来将程序转换为易于处理的格式的主要工具。

文法使我们能够将程序(通常表示为ASCII字符的线性序列)转换为语法树。只有语法上有效的程序才能以这种方式转换。这棵树将是编译器解释器用来处理程序的主要数据结构。通过遍历这棵树,编译器可以生成机器代码,或者可以对程序进行类型检查。通过遍历这棵树,解释器可以模拟程序的执行。

用来表示文法的主要符号是巴克斯-诺尔范式(简称BNF)。这种符号是由约翰·巴克斯发明,并由彼得·诺尔进一步改进的,最初用于描述ALGOL编程语言的语法。BNF文法由一个由(T, N, P, S)表示的四元组定义。这些元素的含义如下:

  • T是一组标记。标记构成语言的词汇表,是语法的最小单位。这些元素是程序员在输入代码时看到的符号,例如,while、for、+、( 等。
  • N是一组非终结符。非终结符本身并不属于语言。相反,它们有助于确定可以从文法中推导出的推导树的结构。通常,我们将这些符号用尖括号括起来,以区分它们和终结符。
  • P是一组产生式规则。每个产生式都由一个左部、一个分隔符和一个右部组成,例如,<非终结符> := <表达式1> ... <表达式N>,其中 ':=' 是分隔符。为了方便起见,左部相同的产生式可以使用符号 '|' 来缩写。在这种情况下,管道用于分隔不同的备选方案。
  • S是一个起始符。任何最终产生语法上有效的程序的推导序列都从这个特殊的非终结符开始。

例如,下面是一个非常简单的文法,它识别算术表达式。换句话说,这种简单语言中的任何程序都表示诸如 'a'、'b' 和 'c' 之类的名称的乘积或总和。

<exp> ::= <exp> "+" <exp>
<exp> ::= <exp> "*" <exp>
<exp> ::= "(" <exp> ")"
<exp> ::= "a"
<exp> ::= "b"
<exp> ::= "c"

这种文法也可以用更方便的方式表示,使用一系列竖线符号,例如:

<exp> ::= <exp> "+" <exp> | <exp> "*" <exp> | "(" <exp> ")" | "a" | "b" | "c"

编程语言范式 · 解析

华夏公益教科书