符号约定
 
 
 
 
 
 
 
 
文法的形式化定义
 
 
$V_T$：终结符是文法所定义的语言的基本符号，有时也称为token。（对应词义分析）
 $V_N$：非终结符是用来表示语法成分的符号，有时也称为"语法变量"，可以推出其它的语法成分（对应语法分析）
 $P$:
 
 $S$：$S\in V_N$ ， 开始符号表示的是该文法中最大的语法成分
 
示例
 
 
 
产生式的简写
 
 
 
 
文法分类体系
 
0型文法
 
又称为无限制文法或短语结构文法（PSG）
 
 
例如，有0型文法 $G=（V_N，V_T，P，S）$，其中 
    
     
      
       
        
         V
        
        
         N
        
       
       
        =
       
       
        {
       
       
        A
       
       
        ，
       
       
        B
       
       
        ，
       
       
        S
       
       
        }
       
       
        ，
       
       
        
         V
        
        
         T
        
       
       
        =
       
       
        {
       
       
        0
       
       
        ，
       
       
        1
       
       
        }
       
      
      
       V_N=\{A，B，S\}，V_T=\{0，1\}
      
     
    VN​={A，B，S}，VT​={0，1}
 

    
     
      
       
        P
       
       
        =
       
       
        {
       
       
        S
       
       
        →
       
       
        0
       
       
        A
       
       
        B
       
       
        ，
       
       
        1
       
       
        B
       
       
        →
       
       
        0
       
       
        ，
       
       
        B
       
       
        →
       
       
        S
       
       
        A
       
       
        ∣
       
       
        01
       
       
        ，
       
       
        A
       
       
        1
       
       
        →
       
       
        S
       
       
        B
       
       
        1
       
       
        ，
       
       
        A
       
       
        0
       
       
        →
       
       
        S
       
       
        0
       
       
        B
       
       
        }
       
      
      
       P=\{S→0AB，1B→0，B→SA|01，A1→SB1，A0→S0B\}
      
     
    P={S→0AB，1B→0，B→SA∣01，A1→SB1，A0→S0B}
 
1型文法
 
又称为上下文有关文法（CSG）
CSG中不包含ε产生式
 
 
例如，有1型文法 $G=（V_N，V_T，P，S）$，其中 
    
     
      
       
        
         V
        
        
         N
        
       
       
        =
       
       
        {
       
       
        A
       
       
        ，
       
       
        B
       
       
        ，
       
       
        S
       
       
        }
       
       
        ，
       
       
        
         V
        
        
         T
        
       
       
        =
       
       
        {
       
       
        a
       
       
        ，
       
       
        b
       
       
        ，
       
       
        c
       
       
        }
       
      
      
       V_N=\{A，B，S\}，V_T=\{a，b，c\}
      
     
    VN​={A，B，S}，VT​={a，b，c}
 

    
     
      
       
        P
       
       
        =
       
       
        {
       
       
        S
       
       
        →
       
       
        a
       
       
        S
       
       
        A
       
       
        ∣
       
       
        a
       
       
        b
       
       
        B
       
       
        ，
       
       
        B
       
       
        A
       
       
        →
       
       
        B
       
       
        
         A
        
        
         ′
        
       
       
        ，
       
       
        B
       
       
        
         A
        
        
         ′
        
       
       
        →
       
       
        A
       
       
        
         A
        
        
         ′
        
       
       
        ，
       
       
        A
       
       
        
         A
        
        
         ′
        
       
       
        →
       
       
        A
       
       
        B
       
       
        ，
       
       
        b
       
       
        B
       
       
        →
       
       
        b
       
       
        c
       
       
        ，
       
       
        c
       
       
        B
       
       
        →
       
       
        c
       
       
        c
       
       
        }
       
      
      
       P=\{S→aSA|abB，BA→BA'，BA'→AA'，AA'→AB，bB→bc，cB→cc\}
      
     
    P={S→aSA∣abB，BA→BA′，BA′→AA′，AA′→AB，bB→bc，cB→cc}
 
2型文法
 
又称为上下文无关文法（CFG）
上下文无关文法可用于描述语法构造
 
 
例如，有2型文法 $G=（V_N，V_T，P，S）$，其中 
    
     
      
       
        
         V
        
        
         N
        
       
       
        =
       
       
        {
       
       
        A
       
       
        ，
       
       
        B
       
       
        ，
       
       
        S
       
       
        }
       
       
        ，
       
       
        
         V
        
        
         T
        
       
       
        =
       
       
        {
       
       
        a
       
       
        ，
       
       
        b
       
       
        }
       
      
      
       V_N=\{A，B，S\}，V_T=\{a，b\}
      
     
    VN​={A，B，S}，VT​={a，b}
 

    
     
      
       
        P
       
       
        =
       
       
        {
       
       
        S
       
       
        →
       
       
        a
       
       
        B
       
       
        ∣
       
       
        b
       
       
        A
       
       
        ，
       
       
        A
       
       
        →
       
       
        a
       
       
        ∣
       
       
        a
       
       
        S
       
       
        ∣
       
       
        b
       
       
        A
       
       
        A
       
       
        ，
       
       
        B
       
       
        →
       
       
        b
       
       
        ∣
       
       
        b
       
       
        S
       
       
        ∣
       
       
        a
       
       
        B
       
       
        B
       
       
        }
       
      
      
       P=\{S→aB |bA，A→a|aS|bAA，B→b|bS|aBB\}
      
     
    P={S→aB∣bA，A→a∣aS∣bAA，B→b∣bS∣aBB}
 
3型文法
 
又称为正则文法，包括左线性文法和右线性文法
正则文法可用来描述大多数单词，但是，它的生成能力有限，几乎描述不了语法构造
正则文法一般用于词法分析，通过NFA、DFA就可以识别
两套规则不能同时出现在一个语法中，只有完全满足其中的一个才能算 3型文法。
 
 
文法分类体系间的关系
 
 
 
有关文法的实用限制和变换
 
文法中不能含有形如 $A\to A$ 的规则，这种规则称为有害规则。这样的规则对描言显然是没有必要的，并且它还会引起文法的二义性。所以在设计文法时，应该避免定义里的规则。
文法中不能有多余规则。所谓多余规则是指文法中出现以下两种规则的情况，一是某条规则 $A\to \alpha$ 的左部符号 $A$ 不在所属文法的任何其他规则右部出现，即在推导文法的所有句子中始终都不可能用到的规则；二是对文法中的某个非终结符A，无法从它推导出任何终结符号串来。
 
参考地址：
 
 
 
https://www.icourse163.org/learn/HIT-1002123007?tid=1003246005#/learn/announce
 

语言的形式化定义
 
 
 
文法和语言之间的联系
 
给定一个文法，就能从结构上唯一地确定其语言，即 G → L(G)
 
给定一种语言，能确定其文法，但这种文法不是唯一的，即 $L\to G_1$ 或 $G_2$ 或…或 $G_n$
 
 
句子和句型
 
 
 
举例：
 
 
 
推导和规约
 
推导：用产生式的右部替换产生式的左部 （生成语言）
 
 
规约：用产生式的左部替换产生式的右式 （识别语言）
 
举例：根据下列文法，对 little boy eats apple 进行推导和规约
 
 
 
有了文法（语言规范），如何判定某一词串是否是满足文法的句子？
 
 
从生成语言的角度，如果从文法的开始符号可以推导出词串，则该词串是语言的句子
 
 
从识别语言的角度，如果词串可以规约出文法的开始符号，则该词串是语言的句子
 
 
 
参考地址：
 
 
 
https://www.icourse163.org/learn/HIT-1002123007?tid=1003246005#/learn/announce
 

语言的定义——编译原理
 
 
 
给定文法G=(VT,VN,P,S),如果α→β∈P,那么可以将符号串中的γαδ中的α替换为β,记作 γαδ⇒γβδ,此时称γαδ直接推导出γβδ.
 
 
推导(derivation)和规约(reduction)
 
 
有上述例子可知,推导是一个自顶向下的过程,而规约是自定向上的过程,换句话说:推导是由抽象到具体,而规约是由具体到抽象
 
句型和句子
 
 
 
语言的形式化定义
 
 
 
由文法G的开始符号S所推导出来的所有句子的集合称为文法G的生成的语言,记做
 
 
称为文法G的生成的语言,记做
 
 
 
 

 
编译原理-文法的定义与分类
 
前言
一、文法的定义
二、文法的分类
0.短语结构语言(PSL)
1.上下文有关文法(CSG)
2.上下文无关文法(CFG)
3.正规文法(RG)
  
三、判断以下文法的类别
总结

 
 
前言
 
语言是一定的群体用来信息交流的工具 ，而信息交流的基础是需要按照共同约定的生成规则和理解规则去生成句子和理解句子。计算机的语言具有严格的语法、语义，易于形式化的特征。程序设计语言经过形式化提取后可以得到以下内容：
 
程序设计语言(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 （短语结构文法）
 
总结
 
G = (V，T，P，S)是一个文法,α→β ∈ P
 
G是0型文法，L(G)是0型语言；
|α|≤|β|:G是1型文法，L(G)是1型语言(除Ｓ→ε);
α∈Ｖ : G是2型文法，L(G)是2型语言;
A→aB或A→a: G是右线性文法，L(G)是3型语言
 A→Ba或A→a : G是左线性文法，L(G)是3型语言
 
四种文法之间的关系是将产生式作进一步限制而定义的。
 
四种文法之间的逐级“包含”关系如下：