本文共 6003 字，大约阅读时间需要 20 分钟。

• 一个程序语言是一个记号系统,
• 如同自然语言,它完整定义包括语法和语义。
• 语法指一组规则,
  • 用它可形成和产生一个合适的程序。
  • 目前广泛使用的手段是上下文无关文法,
  • 即用上下文无关文法作为
    • 程序设计语言语法的描述工具。
• 语法只定义什么样的符号序列是合法的,与这些符号的含义毫无关系,
• 对Pascal,一个上下文无关文法可定义符号串A:=B+C是合乎语法的,A:=B+不。
• 若B实型,C布尔,或B、C中任何一个没事先说明,
  • 则A:=B+C仍错,
  • 也就是说程序结构上的这种特点
    • 类型匹配、变量作用域等
    • 无法用上下文无关手段检査的,
    • 这些属语义分析
• 程序语言的语义分两:静态语义和动态语义
• 静态语义是一系列限定规则
  • 并确定哪些合乎语法的程序是合适的;
• 动态语义也称运行语义或执行语义,
  • 表明程序要做啥,要计算啥。

语言的完整含义包括语法和语义

语法只定义什么样的符号序列是合法的

• 阐明语法的一个工具是文法,
• 这是形式语言理论的基本概念。
• 本章介绍文法和语言的概念,
  • 重点论上下文无关文法及其句型分析中的有关问题

文法是一个工具，来阐明语法

上下文无关文法看来是文法这个工具的一种啊哈哈哈

• 阐明语义比阐明语法困难,
• 形式语义学的研究取大进展,
• 但仍没有哪一种公认的形式系统
  • 可用来自动构造正确的编译系统。
• 本书不对形式语义学介绍。

2.1 文法的直观概念

• 给出文法和语言的定义前,先直观认识文法的概念。

• 当表述一种语言时,
• 无非是说明这种语言的句子,
  • 如果语言只含有穷多个句子
  • 则只需列出句子的有穷集就行,
• 但对有无穷多个句子的语言
  • 如何给出它的有穷表示

• 自然语言
• 无法列出全部句子,但可给出一些规则,用这些规则来说明(或定义)句子的组成结构,
• “我是大学生”是个句子。
• 汉语句子可由主语后随谓语而成,
  • 构成谓语的是动词和直接宾语,
• 用1章的EBNF表示这种句子的构成规则

句子由主语和谓语组成

主语又有谁啊？？？

一个一个套下去啊

• “我是大学生”符合上规
  • “我大学生是”不符合,即它不是句子
  • 这些规则成为判别句子结构合法与否的依据,换句话说,将这些规则看成是一种元语言,用它描述汉语
  • 这里仅仅涉及汉语句子的结构描述。
  • 这样的语言描述称为文法

这特妈叫文法啊？

这些规则就特码叫文法啊？

有了规则，我就能生成一个句子了哈哈哈

• 一旦有了一组规则后,如下方式用它们去推导或产生句子。
• 开始去找::=左端的带有<句子>的规则
  • 并把它表示成::=右端的符号串,
  • 这个动作表示成:<句子>$\Rightarrow$<主语><谓语>,
  • 然后在得到的串<主语><谓语>中,选取<主语>或<谓语>,
  • 再用相应的规则::=右端代替
• 选取<主语>,并用规则<主语>::=<代词>,得到
  • <主语><谓语>$\Rightarrow$<代词><谓语>
  • 重复做下去,得到句子“我是大学生”的全部动作过程如下

• $\Rightarrow$
  • 使用一条规则,代替其左端的某个符号,产生其右端的符号串。

• 按上述办法,不仅生成“我是大学生”这样的句子
• 还可生成“王明是大学生”,王明学习英语”等其他句子
• 用文法作为工具,不仅为严格定义句子结构,也是为了用适当条数的规则把语言的全部句子描述出来
  • 可以说文法是以有穷的集合刻画无穷的集合的一个工具。

文法是以有穷的方式刻画无穷集合的工具

2.2符号和符号串

• 英语是由句子组成的集合
  • 句子由单词和标点符号组成的序列
• Pascal或C是由一切Pascal程序或C程序组成的集合
  • 程序由if begin、end的符号及字母和数字基本符号组成
  • 字面上每个程序都是个“基本符号”串,
• 设有一基本符号集,
  • Pascal或C可看成是在这个基本符号集上定义的、按一定规则构成的一切基本符号串组成的集合
• 为给出语言的形式定义,先讨论符号和符号串

1.字母表

• 是元素的非空有穷集合,字母表中的元素称为符号,因此字母表也称为符号集
• C的字母表由字母、数字、若干专用符号及char、 struct、if、do之类的保留字组成。

C 的字母表是啥

2.符号串

• 字母表中的符号组成的任何有穷序列称符号串
• 符号顺序是很重要
• 可用字母表示符号串,如x=STR表示“x是由符号S、T和R,并按此顺序组成的符号串”。

• 某符号串$x$中有$m$个符号,则称其长度为m
  • $|x|=m$

• 允许空符号串,即不含任何符号的符号串,长度为0

$$|\epsilon |=0$$

头尾，固有头，固有尾

• 1)符号串的头尾,固有头和固有尾
• $x=xy$是一符号串,
  • $x$是的头,$y$是的尾,
  • 如果$x$非空,那么$y$是固有尾;
  • 同样,如果y非空,那么x是固有头。
• $z=abc$,
  • $z$的头是$\epsilon$,$a$,$ab$和$abc$
    • 除$abc$外其都固有头
• $z$的尾是$\epsilon$,$c,bc和abc$;
  • 固有尾:$\epsilon$,$c$,$bc$

• 对符号$z=xy$的头感兴趣其余不感兴趣时
  • $z=x...$
• 只强调$x$在符号串$z$中的某处出现,
  • $z=...x...$
• 符号$t$是符号串$x$的第一个符号,则$x=t...$

• 2)符号串的连接
• $x=ST$,$y=abu$,
• 则它们的连接$xy$= $STabu$,
• 看出$|x|=2,|y|=3.|xy|=5$
• 显然$\epsilon x=x\epsilon =x$

• 3)符号串的方幂
• $x$是符号串,把$x$自身连接$n$次得到符号串$x$,即$z=xx\dots xx$,称为符号串$x$的方幂,$z=x^n$
• $x=AB$,
  • $x^0=\epsilon$
• 对于n>0有

$$x^n=x^{n-1}x=x{x}^{n-1}$$

符号串集合

• 4)符号串集合
• 若集合$A$中的元素都是某字母表上的符号串
  • 则称A为该字母表上的符号串集合
• 符号串集合$A$和$B$乘积

这里有一点没写啊

• 指定字母表$\Sigma$后
  • ${\Sigma }^{\ast }$表示$\Sigma$上所有有穷长的串的集合。
• {0,1}
  则${\Sigma }^{\ast }$={ $\epsilon$,0,1,00,01,10,11,000,001,010,…},
• 也可表为字母表的方幂形式

• ${\Sigma }^{\ast }$称为集合$\Sigma$的闭包

• ${\Sigma }^{\ast }$有可数的无穷数量的元素。
• 对所有的$\Sigma$,有$\epsilon \in {\Sigma }^{\ast }$

这里还有可数啊

2.3文法和语言的形式定义

• 这里用2.2节所引用的术语,
  • 将2.1节中描述汉语句子的规则加以形式化,
  • then给出文法和语言的形式定义

以前那个汉语的规则就叫文法

• 规则,也称重写规则、产生式或生成式,
  • 是形如$\alpha \to \beta$或$\alpha ::=\beta$的$(\alpha ,\beta )$有序对,
  • 规则的左部,规则的右部。
  • $\to (::=)$读作“定义为”
• $A\to a$读作“A定义为a”
  • 也把它说成是一条关于A的规则(产生式)。

关于句子的规则就是主语和谓语

• 定义2.1
• 文法$G$定义为四元组$(V_N,V_T,P,S)$
• $V_N$为非终结符(或语法实体,或变量)集;
• $V_T$为终结符集;
• $P$为规则$(\alpha \to \beta )$的集合
• $\alpha \in (V_N\cup V_T{)}^{\ast }$且至少包含一个非终结符,
  • $\beta \in (V_N\cup V_T{)}^{\ast }$
  • $V_N,V_T$和$P$是非空有穷集。
• $S$称识别符或开始符,是非终结符,
  • 至少要在一条规则中作为左部出现
• $V_N$和$V_T$不含公共

特码的，为啥左边至少包含一个非终结符，而且S至少要出现在一条规则的左部

• 常用$V$表示$V_N\cup V_T$,
• $V$称为文法$G$的字母表或字汇表

• 例2.1
• 文法$G=(V_N,V_T,P,S)$
  • V N = { S } V_N=\{S\} VN​={
    S}, V T = { 0 , 1 } V_T=\{0,1\} VT​={
    0,1}
  • P = { S → 0 S 1 , S → 01 } P=\{S\to 0S1,S\to 01\} P={
    S→0S1,S→01}。
  • 非终结符集中只含一个元素S;
  • 终结符集由两元素0和1
  • 有两条产生式;
  • 开始符是S

• 例2.2
• V N = { 标 识 符 , 字 母 , 数 字 } V_N=\{标识符,字母,数字\} VN​={
  标识符,字母,数字}
• V T = { a , b , c , … , x , y , z , 0 , 1 , … , 9 } V_T=\{a,b,c,…,x,y,z,0,1,…,9\} VT​={
  a,b,c,…,x,y,z,0,1,…,9}

• 尖括号括起非终结符。

尖括号括起的都是$V_N$

特码的，非终结符应该指的是标识符，字母，数字这三个东西，现在你理解了为啥$V_N$和$V_T$不相交了吧

• 不将文法G的四元组显式表示出,只将产生式写出
• 约定,第1条产生式的左部是识别符
• 尖括号括起的非终结符,
  • 不用尖括号括起来的是终结
• 或用大写非终结符,小写终结符。
• 也有习惯,将$G$写成$G[S]$,
  • $S$是识别符

不是说，S是开始符,识别符就是开始符啊！

• 例2.1写成

$$G:S\to 0S1$$

• 或

$$G[S]:S\to 0S1$$

• 为定义文法所产生的语言,还需引入推导的概念

• 定义$V^{\ast }$中的符号之间的关系

• 直接推导$\Rightarrow$

• 长度为$n(n\ge 1)$的推导$\stackrel{+}{\Rightarrow }$

• 和长度为$n(n\ge 0)$的推导$\stackrel{\ast }{\Rightarrow }$

• 定义2.2
• $\alpha \to \beta$是
• 文法$G=(V_N,V_T,P,S)$的规则(或说是$P$中的一个产生式)
• $\gamma$和$\delta$是$V^{\ast }$中任意符号
• 若有符号串$v,w$满足

$v=\gamma \alpha \delta$

• 则说$v$(应用规则谁)直接产生$w$,
• $w$是$v$的直接推导,
• $w$直接归约到$v$ $v\Rightarrow w$

• 例2.1的文法G,直接推导的例子
• $v=0S1$,$w=0011$,直接推导:
  • $0S1\Rightarrow 0011$,
  • 使用的规则:$S\to 01$,$\gamma =0,\delta =1$
• $S,0S1$,规则:$S\to 0S1$
  • 都$ϵ$
• 0S1,00S11,
  • 规则:S→0S1

• 例2.2的文法G直接推导例子

• 定义2.3
• 存在直接推导的序列

$v=w_0\Rightarrow w_1\Rightarrow w_2\cdots \Rightarrow w_n=w(n>0)$

• 则称$v$推导出(产生)$w$(推导长度为),
• 或称$w$归约到$v$
• $v\stackrel{+}{\Rightarrow }w$

• 定义2.4
• 若$v\stackrel{+}{\Rightarrow }w$，或$v=w$,
• 则记作$v\stackrel{\ast }{\Rightarrow }w$

转载地址：https://cyj666.blog.csdn.net/article/details/103228185 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！