一种文法自然地描述许多编程语言构造的层次型结构。例如C的if-else语句
if (expression) statement else statement
使用变量expre代表一个表达式，变量stmt代表一个语句，上面的规则可以表达为：
stmt → if (expr) stmt else stmt (2.1)
其中箭头可以读为"具有形式"。这样一条规则叫做一个production产生式。在一个产生式中，词法元素例如关键字if和括号叫做tokens。expr和stmt等代表token序列的变量叫做nonterminals。非终结符一个context-free grammer 具有四个组成部分：
- 一系列token，叫做终结符号terminal symbols
- 一系列非终结符
- 一系列产生式，其中每一个产生式由一个非终结符，叫做产生式的left side左边，一个箭头，以及一系列token和/或非终结符，叫做产生式的right side右边组成
- 指定的某一个非终结符叫做start symbol开始符号
传统上，文法是通过列出它们的产生式来指定的，
- start symbol列在第一个。
- 我们假定数字、象<=这样的符号，以及粗体字符串如while是终结符。
- 一个斜体的名字是一个非终结符
- 任何非斜体的名字和符号可以假设为token。
Example 2.1 本章的几个例子使用数字、加减号组成的表达式，例如9-5+2,3-1和7等等。因为一个加号或者减号必须出现在两个数字之间，我们把这样的表达式称为"由加减号分隔的数字列表"。下面的文法描述这些表达式的语法，这些产生式为：
list → list + digit (2.2)
list → list - digit (2.3)
list → digit (2.4)
digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (2.5)
按照我们的约定，文法的token是
+ - 0 1 2 3 4 5 6 7 8 9
而非终结符是斜体的list和digit，其中list是开始非终结符，因为它的产生式出现在第一条
我们说一个产生式是针对for一个非终结符的，如果这个非终结符出现在产生式的左边。一个token字符串是0个或多个token组成的一个序列。包含0个token的字符串，写作ε，叫做空字符串empty string.
一个文法派生字符串，从start符号symbol开始，用一个非终结符产生式的右边重复替换该非终结符。能够从start symbol派生出来的token字符串形成该文法定义的语言language。
Example 2.2 由文法Example2.1 定义的语言由用加减号分隔的数字列表组成。
非终结符digit的10个产生式允许它代表任何一个token 0,1,.....,9。根据产生式(2.4)，一个数字本身是一个列表。产生式(2.2)和(2.3)表示，我们可以取任意列表，后面加上一个加号或减号，再后跟一个数字，我们就可以得到一个新的列表。
因此，产生式(2.2)到(2.5)可以让我们定义感兴趣的语言。例如，我们可以推断9-5+2是一个list,按照：
- a) 9是一个list(2.4)，因为9是一个digit
- b) 9-5是一个list(2.3)，因为9是一个list，而5是一个digit
- c)9-5+2是一个list(2.2)，因为9-5是一个list,而2是一个digit
Example 2.3 有点不同类型的列表是Pascal begin-end 块中的用分号隔开的语句序列。这些列表可能是一个空的语句列表在begin和end之间。我们可能开始一个文法如下：
block → begin opt_stmts end
opt_stmt → stmt_list | ε
stmt_list → stmt_list; stmt | stmt
注意opt_stmts第2个可能的右边是ε,代表空字符串。也就是说，opt_stmts可以被一个空字符串替换，因此一个block可由两个token字符串begin end组成。注意stmt_list的产生式和Example 2.1中的list相似。只不过分号代替了算术操作符，而stmt代替了digit。我们没有展示stmt的产生式。我们马上就会讨论各种不同语句的产生式，例如if语句、赋值语句等等。
Parse Tree
一棵解析树能够非常形象化地显示文法的开始符号是如何派生语言的字符串的。如果非终结符A有一个产生式A → XYZ，那么解析树就具有一个内部节点A和三个子节点X,Y,Z，从左到右
正式讲，给定一个上下文无关文法，一棵解析树parse tree是具有下列属性的一棵树：
- 根标以开始符号
- 每一个叶节点标以一个token或者ε
- 每一个内部节点都标以非终结符
- 如果A是一个标以非终结符的内部节点，而且X1,X2,....Xn是节点所有子节点的标签（从左到右）,那么A → X1X2...Xn是一个产生式。这里，X1,X2...Xn可以是一个终结符或者非终结符。特殊情况下，如果A → ε,那么标签为A的节点可能只有一个子标签为ε。
Example 2.4 在Fig2.2中，root标签是list，Example 2.1的开始节点。根节点的子从左到右分别标以list,+和digit，注意
list → list + digit
是Example 2.1文法的一个产生式。
一个解析树的叶子从左到右阅读形成tree的yield，它是一个从解析树的根节点的非终结符生成或派生的字符串。在Fig2.2，生成的字符串是9-5+2。在那个图中所有的叶子都显示在底层。以后，我们没有必要再这样排列叶子。任何树的叶子都分出一个自然的从左到右的顺序，因为如果a和b是同一个节点的两个子节点，并且a在b的左边，那么所有a的后代肯定在b后代的左边。
一种文法生成的语言的另一个定义是能够用某些解析树声称的字符串集合。根据一个给定的token字符串寻找一个解析树的过程叫做parsing解析这个字符串。
Ambiguity
我们必须小心谈论一个字符串的结构按照一个文法。虽然，每一棵解析树可以确定它派生的字符串，但是一种文法可以有多个解析树生成一个给定的token字符串。这样的文法成为ambiguous.为了显示一种文法是ambiguous的，我们只需要找出一个token字符串具有多棵解析树。这样的一个字符串通常具有多种含义，为了编译应用程序，我们必须设计无二义性的文法，或者用特殊的规则来解决文法中的二义性。
Example 2.5 假设我们不区分Example 2.1中的数字和列表，我们可以写作：
string → string + string | string - string | 0 | 1 | 2 | 3| 4| 5|6|7 |8 | 9
把digit和list合并成为非终结符string看起来是可行的，因为一个digit是list的一种特殊情况。
但是， Fig. 2.3显示象9-5+2这样的表达式现在有多棵解析树。9-5+2的两棵解析树对应表达式的两种括号形式(9-5)+2和9-(5+2)。而Example 2.1的文法不允许后面一种解释。
Associativity of Operators
按照习惯，9+5+2和(9+5)+2是等价的，而9-5-2和(9-5)-2是等价的。当一个操作数例如5左边和右边有操作符的时候，需要有约定来决定哪个操作符使用该操作数。
我们说操作符+ 结合到左边 associates to the left，因为如果一个操作符的左右两边都有加号的话，那么取左边那个操作符。在绝大多数编程语言中，四个算术操作符，加减乘除是左结合的。
某些常用的操作符例如指数是有右结合的。另外一个例子，C里面的赋值操作符=也是右结合的，在C里面表达式a=b=c和a-(b=c)是等价的。
象a=b=c这样具有右结合操作符是由下列文法生成的。
right → letter = right | letter
letter → a | b | ... | z
一个象-一样的左结合操作符和一个象=这样的右结合操作符的解析树之间的对比如图2.4:
注意9-5-2的解析树朝左下方增长，而a=b=c的解析树朝右下方增长
Precedence of Operators
考虑表达式9+5*2.有两种可能的解释方式：(9+5)*2和9+(5*2)。+和*的结合性不能解决这种模糊性。因此我们必须知道操作符的相对优先级（如果同时出现两个操作副的时候）
我们说*比+优先级更高,如果先取*后取+。在普通算术中，乘法和除法比加法和减法的优先级高。因此，5被*所取，不管是9+5*2还是9*5+2，也就是说，分别等价于9+(5*2)和((*5)+2
Syntax of expression 表达式语法。算术表达式的文法可以用一张表构造，其中显示操作符的结合性和优先级。我们从4个常见的算术操作符和一个优先级表开始，按递增的优先级显示，相同的优先级写在同一行
左结合: + -
左结合: * /
我们创建两个非终结符expr和term，分别对应这两个层次的优先级，以及一个额外的非终结符factor用来生成表达式的基本单位。表达式的基本单位是数字和括号的表达式：
factor → digit | (expr)
现在考虑二元操作符，*和/，具有最高优先级。因为这些操作符是左结合的，因此类似于那些左结合的列表
term → term * factor
| term / factor
| factor
类似的，expr生成加减
expr → expr + term
| expr - term
| term
结果文法依次为：
expr → expr + term | expr - term | term
term → term * factor | term / factor | factor
factor → digit | (expr)
该文法把表达式看作+ 或 - 分隔的item ,而一个term则是* 或/分割的factor。注意任何括号的表达式也是一个factor，因此用括号我们可以开发具有任意深度的嵌套（也就是任意深度的树).
Syntax of statements 语句的语法 关键字允许我们识别绝大多数语言中的语句。任何Pascal语句开始一个关键字，除了赋值和过程调用。某些Pascal语句可以用下面的文法（具有两义性）来定义，其中token id代表一个标识符。
stmt → id := expr
| if expr then stmt
| if expr then stmt else stmt
| while expr do stmt
| begin opt_stmts end
非终结符opt_stmts在Example 2.3中定义。
没有评论:
发表评论