02-文法和语言

文法和语言

掌握：已知上下文无关文法和句型，构造推导，最左推导，最右推导，语法树，找出语法树的短语，直接短语，句柄

直观概念

语言

• 语法
  • 字母表：可以在程序中出现的字符
  • 词法规则：字符的排列组合组成词的规则（标识符，关键字等）
  • 语法规则：词的排列组合组成句子（表达式、函数等）
• 语义：指定程序意义的规则

文法

描述语言的语法结构的规则，即语法规则

符号和符号串

• 字母表：符号的非空有穷集合

• 符号：可以互相区别的记号

• 符号串（字、句子）：由符号组成的有穷序列

  • 由字母表零个或多个字母（字母可重复）构成

• 基本术语

  术语	表示	含义
  空串	$\epsilon$	没有任何符号的符号串
  长度	|a|=1 $	\epsilon	$=0	串的长度
  前缀（头） 后缀（尾）	ab中的a、ab、$\epsilon$都是前缀 ab中的b、ab、$\epsilon$都是后缀	删除头、尾若干个字母的符号串 (包括删0个和全部个）
  真前缀（固有头） 真后缀（固有尾）	ab中的a、$\epsilon$都是前缀 ab中的b、$\epsilon$都是后缀	删除头、尾至少删除一个字母的符号串 (不包括不删，但包括全删）
  子串	abc中a、b、c、ab、bc都是子串	删除前缀后缀的符号串 （包括本身和空串）
  逆转	ab逆转ba	将符号串逆序

符号串的运算

操作	含义
连接	相乘
方幂	n次幂就是n个符号串连接（0个连接是$\epsilon$）

符号串集合运算

操作	含义
乘积	笛卡尔积的符号串连接（空集乘任何集合都是空）
合并	非重复并集
方幂	n个集合的乘积（0个是{ $\epsilon$ }）
闭包	$A^*$，字符串的任意长度连接（包括$\epsilon$）
正闭包	$A^+$，字符串的任意长度连接（不包括$\epsilon$的闭包）

形式定义

四部分

• 终结符号集：$V_T$，一组字母表

• 非终结符号集（语法变量）：$V_N$，语法范畴

• 语法规则集合（产生式集合）：P，语法规则

• 开始符号：S，特殊的非终结符，一个文法的起始符只有一个

  写法

  • 习惯大写字母是非终结符，小写字母是终结符
  • ->(推)、::=（推）、|（或）、<>（非终结符）
  • 起始符写法：显式G:[S]，隐式默认G：第一个符号是起始符

其他概念

产生式：文法的一条规则

推导：由规则推出句子

归约：由句子推出规则

• $=>$一步
• $=^+>$一步或多步
• $=^*>$零步或多步（这就有可能左面等于右面）

句型：文法通过星步推到出来的（包括起始符号本身）

句子：终结符的组合（包括$\epsilon$），是特殊的句型

语言：文法的句子集合

文法类型

• 0型文法（短语文法）：$\alpha\longrightarrow \beta$，$\alpha$不允许是$\epsilon$，$\beta$允许是$\epsilon$
• 1型文法（上下文有关文法）：$\alpha\longrightarrow \beta$，$\alpha$的长度大于等于$\beta$的长度，但是除外$\alpha\longrightarrow \epsilon$
• 2型文法（上下文无关文法）：$\alpha\longrightarrow \beta$，$\alpha$是一个非终结符，$\beta$随意（语法分析）
• 3型文法（正规文法）：$\alpha\longrightarrow \beta$，$\alpha$是一个非终结符，$\beta$最多只能有一个非终结符并且非终结符还得在最右（左）面出现（词法分析）

2型文法（上下文无关文法）

语法树

语法树与推导的区别

一颗语法树对应多个推导过程，因为树的生长过程只表明了非终结符被谁替换了，未表明顺序

最左推导和最右推导

当有多个非终结符时，总紧着最左（最右）的非终结符推导

若文法没有二义性，则语法树唯一，最左推导和最有推到唯一

规范推导：最右推导

规范规约（最左规约）：最右推掉的逆过程

规范句型：由规范推导推导出的句型

句型分析

自上而下分析方法：推导

自下而上分析方法：规约

短语：多次规约成非终结符，即非叶节点为根的子树，叶节点序列

直接短语：一次规约成非终结符，即简单子树，只有两层的子树的叶子节点

句柄：最左直接短语

文法化简

• 有害规则：$\alpha\longrightarrow \alpha$，左右都一样，会引起二义性
• 多余规则
  • 不可到达：含有（除拉起始符号）非终结符未在右部出现过规则
  • 不可终止：含有不能推出终止符号的非终结符规则