详解文法的定义与分类(编译原理)_其他编程

编译原理-文法的定义与分类

前言

语言是一定的群体用来信息交流的工具，而信息交流的基础是需要按照共同约定的生成规则和理解规则去生成句子和理解句子。计算机的语言具有严格的语法、语义，易于形式化的特征。程序设计语言经过形式化提取后可以得到以下内容：

程序设计语言(programming language)：组成程序的所有语句的集合。

程序(program)：满足语法规则的语句序列。

语句(sentence) ：满足语法规则的单词序列。

单词(token) ：满足词法规则的字符串。

语言的描述形式——文法，对于单词和语句有不同的概念：

词法——单词
单词的组成规则
描述方法：bnf范式、正规式

语法——语句
语句的组成规则
描述方法：bnf范式、语法(描述)图

一、文法的定义

以赋值语句为例，首先进行如下四个定义：
非终结符号集v =
{<赋值语句>，<左部量>，<右部表达式>，<简单变量>，<下标变量>，<运算符>}
终结符号集t =
{a , b, c, m[1], m[2], m[3], +, -}
语法规则集p =
{<赋值语句> —> <左部量>=<右部表达式> ，……}
开始符号s = <赋值语句>

按照上述定义，则文法g的形式化定义为诶一个四元组：

ｇ=(ｖ，t，ｐ，ｓ)

ｖ：非终结符(variable )集
每个非终结符称为一个语法变量（成分）——代表某个语言的各种子结构。

t：终结符(terminal)集。
语言的句子中出现的字符，ｖ∩t = 空集

ｓ：开始符号(start symbol)，s∈ｖ
代表文法所定义的语言，至少在产生式左侧出现一次。

ｐ：产生式(product)集合。

二、文法的分类

根据语言结构的复杂程度（形式语言）（涉及文法的复杂程度、分析方法的选择、反映文法描述语言的能力）可以分为以下四种语言：
0型文法 (即：短语结构文法)
1型文法 (即：上下文有关文法)
2型文法 (即：上下文无关文法)
3型文法 (即：正规文法)

0.短语结构语言(psl)

如果g满足文法定义的要求，则ｇ是０型文法（短语结构文法psg: phrase structure grammar ）。

1.上下文有关文法(csg)

如果对于任意α —>β∈p，均有 **|β|≥|α|**成立，则称ｇ为１型文法。即：上下文有关文法（csg——context sensitive grammar）

2.上下文无关文法(cfg)

如果对于任意α —>β∈p，均有|β|≥|α|，并且α∈v成立，则称g为２型文法，即：上下文无关文法(cfg: context free grammar)（cfg能描述程序设计语言的多数语法成分）。

3.正规文法(rg)

设a、b∈v，a∈t+
右线性(right linear)文法：a→ab或a→a
左线性(left linear)文法：a→ba或a→a
都是３型文法(正规文法 regular grammar -rg)
其中左线性文法和右线性文法等价，只是识别句子的方向不同。

三、判断以下文法的类别

g1: s —> 0 | 1 | 00 | 11 （正则文法）
g2: s —> a | b | aa | bb, a —> 0, b —> 1 （上下文无关文法）
g3: s —> 0 | 1 | 0a | 1b, a —> 0, b —> 1 （正则文法）
g4: s —> a | b | bc, a —> 0, b —> 1,c —> 21, c —> 11, c—> 2 （上下文无关文法）
g5: s —> 0 | 0s （正则文法）
g6: s —> ε | 0s （短语结构文法）
g7: s —> ε | 00s111 （短语结构文法）
g8: a —> as | bs | cs | a | b | c （正则文法）
g9: s —> 0a | 1b | 2c | 0sa | 1sb | 2sc
0a —> a0 1a —> a1
2a —> a2 0b —> b0
1b —> b1 2b —> b2
0c —> c0 1c —> c1
2c —> c2
（上下文有关文法）
g10: s —> at | bt | ct
t —> ε | a | b | c | 0 | 1 | 2 | 3 | at | bt | ct | 0t | 1t | 2t | 3t （短语结构文法）