①<句子>::=<主语短语> <动词短语> ②<主语短语>::= the <名词> ③<动词短语>::=<动词><宾语短语> ④<宾语短语>::=<冠词><名词>

英语语言为例。并设每个句 ⑤<名词>::=monkey 子都是“主-谓-宾”结构 文法——见右。其中，每个 ⑥<名词>::=banana 用< >括起来的部分是所要 ⑦<动词>::=eat

语义(semantics) 分类: 静态语义：一系列限定规则，确定哪些 合乎语法的程序是合适的 动态语义：表明程序要做什么 描述工具: 指称语义,操作语义等 作用: 检查类型匹配，变量作用域等
2.
文法的直观概念
(六)上下文无关文法及语法树
(七)句型的分析
(八)有关文法实用中的一些说明
(一)形式语言理论
(二)语言和文法的直观概念
(三)字母表、串、语言
(四)文法和语言的形式定义
(五)文法的类型
(六)上下文无关文法及语法树
(七)句型的分析
(八)有关文法实用中的一些说明
(二)语言和文法的直观概念（引例）


我们从“产生语言”的角度 出发,讨论文法和语言的形式 定义 语言生成——指制定出有限 条规则，借助它们产生的句 子的集合
推导序列 练习：请推导the banana eat a monkey
语法规则及其产生的语言


前面的语法规则可以产生16个不同的句子，由这16 个句子组成的集合，就是该规则所定义（或所产生） 的语言 应指出，所产生的句子中，有些句子的含义是荒谬 的（如 the banana eat a monkey和the banana eat the banana等）。然而，若不考虑语义，则我 们就必须承认它们是语法上合法的句子。
定义语言中的一个语法实体 （称为语法单位、语法结构、⑧<动词>::=has 语法范畴、语法变量等）。 “::=”是用于定义语法结构 ⑨<冠词>::=the 的符号，其含义（并读作） ⑩<冠词>::=a “定义为” 。文法也称为产 生式(Production)
(二)语言和文法的直观概念（引例）

例如
推导序列
用语法规则进行推导

从<句子>出发，经8步推导得到一个英语句子,则 称前面的推导为长度为8的推导

若不关心推导的中间过程，可将从一符号串到另

一符号串的推导用记号 表示, 例如上例中经过 5步的
句子 the m onkey 动词
规则的简化表示

在前面的语法规则定义中，有些语法范畴（如<名词 >、<动词>）有若干条不同的规则来定义它，为简 明起见，我们可以将它们写在同一个左部语法范畴 下，将其定义值用符号“|”（读作‘或’）隔开。 如<名词>、 <动词>、 <冠词>的定义规则可简记为
<名词>::= monkey | banana <动词>::= eat | has <冠词>::= the | a
推导 步 1 2 3 4 5 6 7 8
所用 所得的符号串 规则 ① <句子> <主语短语> <动词短语> ③ <主语短语><动词><宾语短语> ② the <名词><动词><宾语短语> ④ the <名词><动词><冠词><名词> ⑤ the monkey<动词><冠词><名词> ⑦ the monkey eat <冠词><名词> ⑩ the monkey eat a <名词> ⑥ the monkey eat a banana
(二)语言和文法的直观概念
1.


程序设计语言的定义 语言是一个记号系统。 汉语--符合汉语语法的句子的全体 英语--符合英语语法的句子的全体 程序设计语言--该语言的程序的全体 程序设计语言由语法和语义定义： 语法：定义每个程序构成的规则 语义：定义每个程序的意义
程序设计语言包括:语法和语义 语法(syntax) 定义: 是一组规则，用它可以形成和产生 一个合适的程序 描述工具:文法 作用: 定义什么样的符号序列是合法的， 与符号的含义无关。

<句子> <主语短语><动词短语>

所得符号串<主语短语><动词短语>含有两个语法实体，可 对其中任一个（例如对<动词短语>）进行新的推导


<句子> <主语短语><动词短语> <主语短语><动词><宾语短语>

重复上述过程，可得到一个推导序列（见下页）。
推导长度
推导 步 1 2 3 4 5 6 7 8 所用 所得的符号串 规则 ① <句子> <主语短语> <动词短语> ③ <主语短语><动词><宾语短语> ② the <名词><动词><宾语短语> ④ the <名词><动词><冠词><名词> ⑤ the monkey<动词><冠词><名词> ⑦ the monkey eat <冠词><名词> ⑩ the monkey eat a <名词> ⑥ the monkey eat a banana
应用领域

(一)形式语言理论
(二)语言和文法的直观概念
(三)字母表、串、语言
(四)文法和语言的形式定义
(五)文法的类型
(六)上下文无关文法及语法树
(七)句型的分析
(八)有关文法实用中的一些说明
(一)形式语言理论
(二)语言和文法的直观概念
(三)字母表、串、语言
(四)文法和语言的形式定义
(五)文法的类型
第二章
形式语言概论
形语言理论

什么是语言？


“为相当大地区的公众所懂得并使用的‘话’，以及组 成这些‘话’的方法的统一体” “某一字母表上符号串（句子）的集合”
定义仍需精确化 1）字母表 2）语法 3）语义

形式语言理论

由数学方法研究自然语言(如英语)和人工语言(如程 序语言)之语法的理论,主要讨论了语言和文法的数 学机制以及语言和文法的分类

推导(derivation)——从语言最大的一个语法实体（本例中 是<句子>）开始，反复用语法规则中“::=” 右侧的符号串 取代其左侧符号，直到所得的符号串中不再含有可被替换 语法实体。每次替换称为一步（直接）推导，并用符号 “”表示。 首先用规则①进行第一步推导，可得到<主语短语><动词短 语>，即