编译原理 — 文法(一)
什么是文法
语言是由文法描述的,文法使用有限的规则将无限的语言描述出来,语言是文法所描述的所有句子的集合。简单来说,就是指怎么由一堆符号组成一个有含义的句子的规则,它是产生中间代码或目标代码的依据。
文法包含词法规则和语法规则。
- 词法规则:符号(单词)是由字符组成的有限串,是具有独立含义的最小语法单位。词法规则规定了什么样的字符串可以构成语言的有效符号,如标识符、无符号常数、界限符等。
- 语法规则:规定了如何从单词符号形成更大的结构(语法单位)。语法单位包括表达式、语句、函数、过程等。
终结符与非终结符
- 终结符:不能被分解成更小的单位。也就是说终结符不能再进行推导,不能单独出现在推导式左边。在程序语言中,基本字、标识符、常数、运算符号等都算做终结符号。当然,逗号、括号也都为终结符
- 非终结符:指的是可以被拆分的字符或串,它采取递归定义:一个非终结符是由终结符和至少一个非终结符组成的串
终结符和非终结符是两个不相交的集合。一般把非终结符用大写字母表示,终结符用小写字母表示。
例如有如下推导式:
- S->Ax
- S->By
- A->a
- A->cA
- B->b
- B->Bd
则表示:S 为开始符,S,A,B 为非终结符,而x,y,a,b,c,d 为终结符。
文法的定义
文法通过一个四元组定义。文法G是一个四元组(四元组的顺序不固定),可表示为
- :终结符号集,是一个非空有限集,其每个元素称为一个终结符
- :非终结符号集,是一个非空有限集,其每个元素称为一个非终结符
- P:产生式的有限集合。每个产生式是类似 α -> β的规则
- S:文法开始符,是一个特殊的非终结符号
文法分类
- 0型文法(短语文法)
- 1型文法(上下文有关文法)
- 2型文法(上下文无关文法)
- 3型文法(正规文法或线性文法)
四类文法的区别在于对产生式施加不同的限制。可以用下图说明它们之间的关系。