码文不易，希望支持，谢谢->支持原创

高级语言及其文法

让系统知道组成规则并按规则执行

目录

• 语言的概述
• 基本定义
• 文法定义
• 语法树
• 文法的分类
• 支持原创

语言的概述

语言是用来交换信息的工具

 语言

• 自然语言(Natural Language)
• 计算机语言(Computer Language)

 自然语言

是人与人之间的通讯工具
语义(Semantics):环境、背景知识、语气、二义性——难以形式化

 计算机语言

计算机系统间、人机间通讯工具
严格的语法(Grammar)、语义(Semantics) ——易于形式化：严格

 形式化的内容提取

 自然语言

• 字符(Character) 语言的基本字符
• 单词(Token) 满足一定规则的字符串
• 句子(Sentence) 满足一定规则的单词序列(在计算机语言中一个程序就是一个句子)
• 语言(Language) 一定规则的句子的集合、

 程序设计语言

• 程序(Program) 满足语法的语句序列
• 语句 (Statement) 满足语法规则的单词序列
• 单词(Token) 满足语法规则的字符串

语言是字和组合字的的规则——结构性描述

基本定义

 字母表

字母表（Alphabet） ∑$\sum$是一个非空有穷集合，字母表中的元素称为该字母表的一个字母（Letter），也叫字符（Character）

 符号串

字母表∑$\sum$上符号串(String)
(1) E$\mathcal{E}$是∑$\sum$上的一个符号串(叫做空串)；
(2) 若x是∑$\sum$上的符号串，而a是∑的元素,则xa是∑$\sum$上的符号串；
(3) y是∑$\sum$上的符号串,当且仅当它由(1)和(2)导出

对于字符串s
前缀：移走s的尾部的零个或多于零个符号
后缀：删去s的头部的零个或多于零个符号
子串：从s中删去一个前缀和一个后缀
子序列: 从s中删去零个或多于零个符号(这些符号不要求是连续的）
长度：是该符号串中的符号的数目。

由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串,也称作“字”(Word)

 正闭包

∑$\sum$的正闭包(Positive Closure)：
∑+$\sum ^{+}$={x | x是∑$\sum$上的非空字符串}
∑+$\sum ^{+}$=∑⋃∑2⋃∑3⋃∑4⋃......$\sum \bigcup \sum ^2\bigcup \sum ^3\bigcup \sum ^4\bigcup ......$

 克林闭包

∑$\sum$的克林闭包(Kleene Closure)：
∑∗$\sum ^{\ast }$ ={E$\mathcal{E}$} ⋃∑+$\bigcup \sum ^{+}$
∑∗$\sum ^{\ast }$= ∑0⋃∑⋃∑2⋃∑3⋃∑4⋃......$\sum ^0\bigcup \sum \bigcup \sum ^2\bigcup \sum ^3\bigcup \sum ^4\bigcup ......$

 乘积

设∑1$\sum _1$、∑2$\sum _2$是两个字母表，∑1$\sum _1$与∑2$\sum _2$ 的乘积(Product)∑1∑2$\sum _1\sum _2$={ ab | a∈∑1$\in \sum _1$，b∈∑2$\in \sum _2$ }

 语言&句子

设∑$\sum$是一个字母表，∀L⊆∑∗$\mathrm{\forall }L\subseteq \sum ^{\ast }$，L称为字母表∑$\sum$上的一个语言（Language），∀x∈L$\mathrm{\forall }x\in L$，x叫做L的一个句子。

 连接

设x和y是符号串，它们的连接(Concatenation )xy是把y的符号写在x的符号之后得到的符号串。

 幂

设x是符号串,x的n次幂(power)为x0=ε$x^0=\epsilon$，xn=xn−1x$x^n=x^{n-1}x$，n>0。

文法定义

码文不易，希望支持，谢谢->支持原创

 文法的形式定义

文法G为一个四元组:

G=(VT.VN.P,S)$$G=(V_T.V_N.P,S)$$

VT$V_T$：终结符(Terminal)集 在产生式右边且自身不会再生成
VN$V_N$：非终结符(Variable)集，VT⋂VN=ϕ$V_T\bigcap V_N=\varphi$
语法范畴——某个语言结构
S$S$：开始符号(Start Symbol)，S∈VN$S\in V_N$
至少在产生式左侧出现一次
P$P$：产生式(Product)集合
α→β，被称为产生式（定义式），读作：α定义为β。
其中α∈(VT⋃VN)+$\alpha \in (V_T\bigcup V_N{)}^{+}$，且α中至少有VN$V_N$中元素的一个出现。β∈(VT⋃VN)∗$\beta \in (V_T\bigcup V_N{)}^{\ast }$。α称为产生式α→β的左部(Left Part)，β称为产生式α→β的右部(Right Part) 。

一般的非终结符用大写 终结符小写

 产生式的简写

对一组有相同左部的产生式
α→β1,α→β2,…,α→βn$\alpha \to {\beta }_1,\alpha \to {\beta }_2,\dots ,\alpha \to {\beta }_n$
简单地记为：α→β1|β2|…|βn$\alpha \to {\beta }_1|{\beta }_2|\dots |{\beta }_n$
读作：α定义为β1，或者β2${\beta }_2$，…，或者βn${\beta }_n$，并且称它们为α产生式。β1${\beta }_1$，β2${\beta }_2$，…，βn${\beta }_n$称为候选式(Candidate)。

 直接推导与归约

A→γ$A\to \gamma$是文法G的一个产生式，且α,β∈(VT⋃VN)∗$\alpha ,\beta \in (V_T\bigcup V_N{)}^{\ast }$，称αAβ$\alpha A\beta$直接推导/派生(Derive)出αγβ$\alpha \gamma \beta$，也称 αγβ$\alpha \gamma \beta$直接归约(Reduce)为αAβ$\alpha A\beta$
注意到是根据A→γ$A\to \gamma$而将αγβ$\alpha \gamma \beta$中的γ$\gamma$变成了A$A$，所以，一般称将γ$\gamma$归约为A$A$
记为 αAβ⇒αγβ$\alpha A\beta \Rightarrow \alpha \gamma \beta$（ αγβ⇐αAβ$\alpha \gamma \beta \Leftarrow \alpha A\beta$）

 多步推导/归约

α0⇒α1⇒α2⇒…⇒αn${\alpha }_0\Rightarrow {\alpha }_1\Rightarrow {\alpha }_2\Rightarrow \dots \Rightarrow {\alpha }_n$
记为 α0⇒nαn${\alpha }_0{\Rightarrow }^n{\alpha }_n$ (恰用n步)
α0⇒+αn${\alpha }_0{\Rightarrow }^{+}{\alpha }_n$（至少一步）
α0⇒∗αn${\alpha }_0{\Rightarrow }^{\ast }{\alpha }_n$ （若干步:零步或多步）

 句型与句子

如果S⇒∗α,α∈(VT⋃VN)∗$S{\Rightarrow }^{\ast }\alpha ,\alpha \in (V_T\bigcup V_N{)}^{\ast }$则称α是*生的一个句型(Sentential Form)。

如果S⇒∗x,$S{\Rightarrow }^{\ast }x,$且x∈VT∗$x\in {V_T}^{\ast }$，则称x是*生的一个句子(Sentence)

句型 包括句子
句子 没有非终结符

 文法*生的语言

L(G)={x|S⇒∗x&x∈VT∗}$L(G)=\{x|S{\Rightarrow }^{\ast }x\mathrm{\&}amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;x\in {V_T}^{\ast }\}$
产生式集合、终结符集合、非终结符集合是有限的，
递归实现从有限到无限

文法的分类(chomsky体系)

短语结构化语言0型 图灵机
上下文有关文法1型 线性有限自动机
上下文无关 2型 多数语言 下推自动机
正则文法正规文法 (左线性 右线型)3型

 短语结构文法

如果G满足文法定义的要求，则G是０型文法（短语结构文法PSG: Phrase Structure Grammar ）

 上下文有关文法

除形如α→ε的ε产生式外,若α→β满足｜α｜≤｜β｜则G是1型文法,又叫上下文有关文法（CSG—Context Sensitive Grammar）

 上下文无关文法

若 α→β满足α∈VN,β∈(VN⋃VT)∗$\alpha \in V_N,\beta \in (V_N\bigcup V_T{)}^{\ast }$ ，则 G 是２型文法，又叫上下文无关文法(CFG: Context Free Grammar)

 正规文法

设A,B∈VN,a∈VT⋃{ε}$A,B\in V_N,a\in V_T\bigcup \{\epsilon \}$
右线性(Right Linear)文法：A→aB或A→a
左线性(Left Linear)文法：A→Ba或A→a
都是3型文法(正规文法 Regular Grammar -RG)

 总结

四种文法之间的关系是将产生式作进一步限制而定义的，他们呈逐级“包含”关系，分析方法越来越简单，所能实现功能越来越有限。

语法树

码文不易，希望支持，谢谢->支持原创

语法树(Parse Tree，语法分析树，分析树)

用树的形式表示句型的结构
用VN⋃VT⋃{ε}$V_N\bigcup V_T\bigcup \{\epsilon \}$中的符号标记结点, 标记ε$\epsilon$时为独子
树根：开始符号；中间结点：非终结符
如果一个中间结点v标记为A，v的儿子从左到右依次为v1$v_1$，v2$v_2$，……，vn$v_n$，并且它们分别标记为X1$X_1$，X2$X_2$，……，Xn$X_n$，则A→X1X2……Xn∈P$A\to X_1{X}_2\dots \dots X_n\in P$

 结果

设有文法G的一棵语法树T， T的所有叶子顶点从左到右依次标记为
X1,X2…,Xn$X_1,X_2\dots ,X_n$
则称符号串
X1X2…Xn$X_1{X}_2\dots X_n$
是T的结果(Yield)

 短语与句柄

文法G的一棵语法子树的“结果”表示一个句型中某一部分的结构 ——子结构
子树B表示其“结果”Y1Y2…Ym$Y_1{Y}_2\dots Y_m$的结构。Y1Y2…Ym$Y_1{Y}_2\dots Y_m$称为短语(Phrase)

如果S⇒∗αAβ&A⇒+γ$S{\Rightarrow }^{\ast }\alpha A\beta \mathrm{\&}A{\Rightarrow }^{+}\gamma$，则称γ是句型αγβ的相对于变量A的短语

如果S⇒∗αAβ&A⇒γ$S{\Rightarrow }^{\ast }\alpha A\beta \mathrm{\&}A\Rightarrow \gamma$，则称γ是句型αγβ的相对于变量A的直接短语

最左直接短语叫做句柄(Handle)

 用子树解释短语，直接短语，句柄

短语：子树的结果是相对于子树根的短语
直接短语：仅有父子两代的子树的结果
句柄：一个句型的分析树中最左那棵只有父子两代的子树的结果

支持原创

码文不易，希望支持，谢谢->支持原创

再次感谢，大家对本人的支持。