程序语言的定义

  • 语法
    • 语法规则
      • 上下文无关文法 CFG (Context-free Grammar)
    • 词法规则
    • 语法单位
  • 语义
    • 语义规则

高级语言分类

  • 强制性语言 Imperative Language

    命令驱动,面向语句。如 C, FORTRAN, Pascal, etc.

  • 应用式语言 Applicative Language

    从前面已有的函数出发构造更复杂的函数。

  • 基于规则的语言 Rule-based Language

    也称逻辑程序设计语言,基本允许条件是谓词逻辑表达式。

  • 面向对象语言 Object-Oriented Language

    支持封装性继承性多态性等。

语法表述

symbol meaning
有穷字母表
空字
有穷字母表上所有符号串的全体(Kleene闭包)
不含任何元素的空集

闭包的子集 U 和 V 的积定义为:

V 自身的 n 次(连接)积记为:

则称 V* 是 V 的闭包。

则 V+ 是 V 的正则闭包

上下文无关文法

其所定义的语法范畴(或语法单位)是完全独立于这种范畴可能出现的环境的。

组成部分

  • 终结符号

    语言组成基本符号。

  • 非终结符号

    代表语法范畴。

  • 开始符号

    特殊的非终结符号。

  • 产生式

    定义语法范畴的一种书写规则。

四元式

  • 是一个非空有限集,它的每个元素称为终结符号
  • 是一个非空有限集,它的每个元素称为非终结符号
  • 是一个非终结符号,称为开始符号;
  • 是一个产生式集合(有限),每个产生式的形式是 ,其中,。开始符号 必须在某个产生式的左部出现一次。

可称为是 的一个候选式

元语言符号:

  • :定义为
  • :或
默认表示
  • 大写字母表示非终结符:
  • 小写字母表示终结符:
  • 希腊字母表示符号串:

    符号串由终结符和非终结符组成。

推导

  • 直接推导:
  • 一步或若干步推导:
  • 零步或若干步推导:
最左推导

任何一步 都是对 中的最左非终结符进行替换的。

最右推导

任何一步 都是对 中的最右非终结符进行替换的。

句型、句子与语言

假设 是一个文法, 是它的开始符号。

句型

句子

仅含终结符号的句型。

语言

文法 所产生的句子的全体。

语法分析树

语法分析树

二义性

若一个文法存在某个句子,它有两种不同的最左(最右)推导,则这个文法是二义的。

即一个文法中存在某个句子对应两颗不同的语法树。

压缩文法

  • 文法中不含有任何形如 的产生式;
  • 每个非终结符号 必须都有用处。即

Chomsky 文法

  • 0 型文法 (短语文法)

    产生式的结构为 ,且

  • 1 型文法 (上下文有关文法)

    的任何产生式 均满足 ,仅仅 除外,但 不得出现在任何产生式的右部。

  • 2 型文法 (上下文无关文法)

    的任何产生式为

  • 3 型文法 (正规文法 / 左线性文法 / 右线性文法)

    的任何产生式为 ,其中 ,且

文法关系

3 型语言类 2 型语言类 1 型语言类 0 型语言类

四种文法的关系

    分享到:
分类: 课程笔记

发表评论

电子邮件地址不会被公开。 必填项已用*标注

验证码 *