byyl - 文法及语言

目录

• 文法为什么出现 ？
• 文法的表示形式
• 文法的分类
• BB...BBC类型文法
• ABB...BBC类型文法
• 文法的二义性
  • 例题一：" 后缀表达式的文法二义性"
  • 例题二："嵌套的括号文法二义性"
• ---------------------------
• 语言是什么？
• 语言的表示
• 等价文法
• 已知文法求语言
• 已知语言求文法（典型）
• ---------------------------
• 推导与语法树（例题）
• ---------------------------
• 句型的分析
  • 为什么要进行句型分析 ？
  • 如何证明一个符号串是某文法的句型？
  • 自上而下分析法
  • 自下而上分析法
  • 可归约串与"句柄"概念的引出
    • 测试：寻找短语、直接短语与句柄

---

---

<一> 文法

1> 文法为什么出现？

使用文法作为工具，可以严格定义句子的结构并且可以用适当条数的规则将语言全部描述出来；

文法是以有穷集合刻画无穷集合的一个工具；

2> 文法的表示形式

3> 文法的分类

0/1/2/3型文法，实际上是对产生式(规则)逐步进行更加严格的限制；

4> BB...BBC类型文法

☞ 允许0开头的偶正整数集合：

5> ABB...BBC类型文法

☞ 不允许0开头的偶正整数集合：

6> 文法的二义性

☞ 对于一个句子，使用该文法存在两个不同的最右推导、或可以构造两棵不同的语法树

☞ 例题一：" 后缀表达式的文法二义性 "

☞ 例题二："嵌套的括号文法二义性"

<二> 语言

1> 语言是什么？

2> 语言的表示：L(G)

3> 等价文法：L(G1) = L(G2)

4> 已知文法求语言

5> 已知语言求文法（典型）

<三> 推导及语法树

1> i + ( i + i )

2>  i + i * i

☞ 注意：最右推导 => 右句型/正规句型 => 只有右句型存在句柄！

<四> 句型的分析

1> 为什么要进行句型分析？

判断给定的符号串是某文法的句型（符合某文法）；

2> 如何证明一个符号串是某文法的句型？

☞ 存在推导序列/语法树；

3> 自上而下分析法

从文法的开始符号S开始，逐步使用各种产生式，寻找匹配符号串的推导（例题三）

4> 自下而上分析法

使用输入符号串来构造语法树，逐步下上规约（如何确定可归约串？）

5> 可归约串与"句柄"概念的引出

☞ 一个右句型的唯一句柄是所有直接短语中最左边的那个（ 无二义性文法句柄唯一 ）

6> 测试：寻找短语、直接短语与句柄