文法的形式化定义

柔光的暖阳◎ 2022-03-26 10:11 306阅读 0赞

### 文章目录 ###

*  句子的构成规则
 *   *  自然语言的例子
 *  文法的形式化定义
 *  产生式的简写
 *  符号的约定

# 句子的构成规则 #

## 自然语言的例子 ##

*  <句子> → \\rightarrow →<名词短语><动词短语>
 *  <形容词> → \\rightarrow →

**未用尖括号括起来的部分表示语言的基本符号，尖括号括起来的部分称为语法成分**

# 文法的形式化定义 #

**G = ( V T , V N , P , S ) G=(V\_T,V\_N,P,S) G=(VT,VN,P,S)**

*  G表示文法，文法由一个四元组定义
 *   V T V\_T VT：**终结符集合**
    
     *  终结符(terminal symbol)是文法所定义的语言的**基本符号**，有时也称为*token*。
     *  例如： V T = \{ a p p l e , b o y , e a t , l i t t l e \} V\_T=\\\{apple,boy,eat,little\\\} VT=\{ apple,boy,eat,little\}
 *   V N V\_N VN：**非终结符集合**
    
     *  非终结符(nonterminal) 是用来表示语法成分的符号，有时也称为“语法变量”
     *  例如： V N V\_N VN=\{<句子>,<名词短语>,<动词短语>,<名词>,…\}
     *  **因为从它们可以推出其他的语法成分，所以被称为非终结符**
 *  终结符集合和非终结符集合都是字母表
 *  **终结符集合与非终结符集合是不相交的， V T ∩ V N = ∅ V\_T\\cap V\_N = \\varnothing VT∩VN=∅**
 *  **而终结符集合与非终结符集合的并集是文法符号集**， V T ∪ V N V\_T\\cup V\_N VT∪VN：文法符号集。
 *  **P：产生式集合**，产生式描述了将终结符和非终结符组合成串的方法。
    
     *  产生式的一般形式： α → β \\alpha \\rightarrow\{\\beta\} α→β
     *  读作： α \\alpha α定义为$ \\beta $
     *   α ∈ ( V T ∪ V N ) + \\alpha\\in (V\_T\\cup V\_N)^+ α∈(VT∪VN)\+,且 α \\alpha α中**至少**包含 V N V\_N VN中的一个元素：称为产生式的**头(head)或左部(left side)**。
     *   β ∈ ( V T ∪ V N ) ∗ \\beta \\in (V\_T\\cup V\_N)^\* β∈(VT∪VN)∗：称为产生式的体（body）或者右部（right side）
 *   S ∈ V N S \\in V\_N S∈VN。**开始符号**表示的是该文法中最大的语法成分。
    
     *  例如：S=<句子>

# 产生式的简写 #

*  对一组有**相同左部**的 α \\alpha α产生式， α → β 1 \\alpha \\rightarrow\{\\beta\_1\} α→β1， α → β 2 \\alpha \\rightarrow\{\\beta\_2\} α→β2，…， α → β n \\alpha \\rightarrow\{\\beta\_n\} α→βn**可以简记为**， α → β 1 ∣ β 2 ∣ . . . ∣ β n \\alpha \\rightarrow\{\\beta\_1 | \\beta\_2 | ... | \\beta\_n\} α→β1∣β2∣...∣βn
 *  读作： α \\alpha α定义为 β 1 \\beta\_1 β1，或者 β 2 \\beta\_2 β2，…， β n \\beta\_n βn
 *   β 1 \\beta\_1 β1， β 2 \\beta\_2 β2，…， β n \\beta\_n βn被称为 α \\alpha α的候选式。

# 符号的约定 #

*  下列符号是**终结符**
    
     *  字母表中排在前面的小写字母，如a、b、c
     *  运算符，如+，\*等
     *  标点符号，如逗号，括号等
     *  数字，0、1、2…、9
     *  粗体字符串，如id、if等
 *  下列符号是**非终结符**
    
     *  字母表中排在前面的大写字母，如A、B、C
     *  字母S，通常表示开始符号
     *  小写、斜体的名字，如*expr、stmt*等
     *  代表程序构造的大写字母。如E（表达式）、T（项）和F（因子）
 *  字母表中排在后面的大写字母（如X、Y、Z）表示**文法符号**（即终结符或非终结符）
 *  字母表中排在后面的小写字母（主要是u、v、…、z）表示**终结符号串**（包括空串）
 *  小写**希腊字母**，如 α \\alpha α、 β \\beta β、 γ \\gamma γ，表示文法符号串（包括空串）
 *  如非特别说明，第一个产生式的左部就是开始符号