编译原理（二）

川长思鸟来 2023-10-09 12:29 7阅读 0赞

### 编译原理（二） ###

*  文法的直观概念
 *  符号和符号串
 *  文法和语言的形式定义

# 文法的直观概念 #

1.  BNF:  
    <> 表示需要加以说明的一种语法上的概念，通常叫语法成分或非终结符号。  
    ::= 表示该符号的左部由右部定义，读作“可以是”或“定义为”，也可写作“→”。  
    | 表示用其连接的符号之间是或的关系，读作“或”或“或者”。
2.  EBNF  
    \{\} 表示\{\}内的语法成分可以重复，不加上下界时可重复0到任意次，有上下界时（即\{\} ）表示对重复次数的限制，上标n表示最多可重复的次数，下标m表示至少要重复的次数。  
    \[\] 表示方括号内的成分为可选项。例如，ab\[c\]可表示ab或abc，\[x\]表示ε或x。  
    () 表示圆括号内的成分优先。

# 符号和符号串 #

1.  字母表：元素的非空有穷集合，字母表中的元素称为符号，故字母表又称符号集
2.  符号串：由字母表中的符号组成的任何有穷序列称为符号串
3.  有关符号串的一些运算  
    (1)符号串的头、尾、固有头和固有尾  
    若z=xy是一符号串，则x是z的头，y是z的尾；  
    若x是非空的，则y是z的固有尾；  
    若y是非空的，则x是z的固有头。  
    （2）符号串的省略写法  
    如果只对符号串z=xy的头感兴趣，则可写成z=x…；  
    如果只为强调x在符号串z中的某处出现，则可写成z=…x…  
    （3）符号串的连接  
    设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串。、  
    （4）符号串的方幂  
    设x是符号串，把x自身连接n次得到的符号串z，即z=xx…x(共n个x)，称为符号串x的方幂，记作 z = x n z=x^n z=xn。  
    （5）符号串的集合  
    若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上符号串的集合。  
    （6）符号串集合的乘积  
    符号串集合A和B的乘积定义如下：  
    AB=\{xy|x∊A且y∊B\}，即AB是满足x∊A且y∊B的所有符号串xy所组成的集合。  
    （7）字母表Σ的闭包 ∑ ∗ \\sum^\* ∑∗和正闭包 ∑ + \\sum^+ ∑\+

# 文法和语言的形式定义 #

1.  规则：又称重写规则，产生式或生成式，是形如α→β或α::=β的(α,β)有序对，其中α是某字母表V的正闭包 V + V^+ V\+中的一个符号，β是 V ∗ V^\* V∗中的一个符号，α称为规则的左部，β称为规则的右部
2.  文法的直观定义：规则的非空有穷集合。
3.  文法的形式定义：  
    文法G定义为四元组 ( V N , V T , P , S ) (V\_N,V\_T,P,S) (VN,VT,P,S)，其中， V N V\_N VN为文法的非终结符号集合， V T V\_T VT为文法的终结符号集合，P为规则的集合，  
    S称为文法的识别符号或开始符号，且S∊ V N V\_N VN并至少在一条规则的左部出现。  
    注：  
    (1)  V N ， V T ， P V\_N，V\_T ，P VN，VT，P三个集合均为非空有穷集;  
    (2)  V N ⋂ V T = ∅ V\_N \\bigcap V\_T=\\varnothing VN⋂VT=∅，即不含公共元素；  
    (3)用 V = V N ⋃ V T V= V\_N \\bigcup V\_T V=VN⋃VT表示文法G的字母表或字汇表。
4.  推导：  
    若 α → β α \\rightarrow β α→β是文法G\[S\]的一条规则，γ和δ是 V ∗ V^\* V∗中的任意符号，若有符号串v,w满足  
    v=γαδ 和w=γβδ，则说v（应用规则α→β）直接产生w，或说w是v的直接推导（或w直接归约到v），  
    也叫一步推导。记作v⇒w，其中“⇒”读作“直接推导”。  
    如果存在直接推导的序列v=w0⇒w1⇒w2⇒…⇒wn=w,(n≧1)，则称v推导出w（推导长度为n），或称w归约到v，记作 v ⇒ + w v \\overset\{+\}\{\\Rightarrow\} w v⇒\+w，  
    若 v ⇒ + w v \\overset\{+\}\{\\Rightarrow\} w v⇒\+w或v=w，则记作 v ⇒ ∗ w v \\overset\{\*\}\{\\Rightarrow\} w v⇒∗w。
5.  句型、句子和语言的定义  
    设G\[S\]是一个文法，如果符号串x是从识别符号推导出来的，即有 S ⇒ ∗ x S \\overset\{\*\}\{\\Rightarrow\} x S⇒∗x，则称x是文法G\[S\]的句型。  
    若x仅由终结符号组成，即 S ⇒ ∗ x ， x ∈ V T ∗ S \\overset\{\*\}\{\\Rightarrow\} x，x \\in V\_T^\* S⇒∗x，x∈VT∗，则称x为G\[S\]的句子。  
    文法G所产生的语言定义为集合 \{ x ∣ S ⇒ ∗ x \\\{x|S \\overset\{\*\}\{\\Rightarrow\} x \{ x∣S⇒∗x，其中S为文法的识别符号，且 x ∈ V T ∗ x \\in V\_T^\* x∈VT∗\}，可用L(G)表示该集合。
6.  文法等价的概念: 若L(G1)=L(G2)，则称文法G1和G2是等价的。
7.  文法的分类  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]
8.  短语、直接（简单）短语和句柄  
    若G\[S\]是一文法，αβδ是G的一个句型。如果有 S ⇒ ∗ α A δ S\\overset\{\*\}\{\\Rightarrow\} αAδ S⇒∗αAδ且 A ⇒ ∗ β A \\overset\{\*\}\{\\Rightarrow\} β A⇒∗β则称β是句型αβδ相对于非终结符A的短语。  
    特别地，若A⇒β则称β是句型αβδ相对于规则A→β的直接（简单）短语。一个句型的最左直接短语称为该句型的句柄。  
    短语、直接短语、句柄和语法树中的结点存在一定的对应关系：  
    语法树子树的末端结点符号串就是语法树所描述句型的短语（相对于子树的根），简单子树（只有父子两代）的末端结点符号串就是直接短语，  
    最左简单子树的末端结点符号串就是句柄。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190925185921459.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70