编译原理与技术 －－文法和分析 2018/9/17 《编译原理与技术》讲义

文法和分析 形式语言中若干基本概念 形式语言分类 语言 文法（上下文无关文法） 分析树与二义性 乔姆斯基分类 2018/9/17 《编译原理与技术》讲义

若干基本概念 语言 语言L＝{ s | s 是∑上任一字符串}， s称为语言L的一个句子。 字母表∑－符号/字符的非空有限集合 e.g. 二进制数的∑＝{0,1}，而十进制数的∑＝{0,1,…,9} ∑*－表示∑上所有字符串的集合；L∑* 字符串－ ∑上若干字符组成的有穷序列 2018/9/17 《编译原理与技术》讲义

若干基本概念 语言 字符串 e.g. ∑＝{0,1}上的0，1串（二进制数）如0111，10101；∑＝{a,b}上的 a, b, aa , abab, … 空串－， ∈ ∑*， 串长－|s|＝{s中所含字符的个数}，| |=0 串的连接运算－任意串x，y，一般地，xyyx， x= x 串的前缀－ 任意串x，从其第一个字符（最左字符）起的字符序列是其前缀。亦是。 e.g. x = abc, 则，a，ab，abc均是x的前缀 2018/9/17 《编译原理与技术》讲义

若干基本概念 语言的运算 描述 运算 语言L和语言M 连接（积） LM={ xy| x∈L 且 y∈M } 合并（和） L∪M={x| x∈L 或 x∈M } 闭包 L*=L0∪L1∪L2∪…= 正闭包 L+=L1∪L2∪L3∪…= 2018/9/17 《编译原理与技术》讲义

若干基本概念 语言 e.g. L={a,b,…,z}, D={0,1,…,9}, B={ _ } L∪D = {…} LD={…} L(L∪D)*={…} (L∪ B)(L∪D∪B)*={…} D+={} 2018/9/17 《编译原理与技术》讲义

若干基本概念 文法 文法G＝（VT,VN,S,P）定义为一个四元组，其中： VT－终结符号集合； VN－非终结符号集合，VT∩VN=∅ ； S－文法开始符号，S∈VN ； P－文法产生式集合，每一产生式形如， 其中， ∈ （VT∪VN )*，至少含有一个非 终结符，  称为相应产生式的左部，则 为产生式的右部。 2018/9/17 《编译原理与技术》讲义

若干基本概念 文法是描述语言的语法结构的形式规则，其中，终结符号（集合）表示组成语言的基本成份，如标识符、常数，算符等；非终结符号（集合）代表语法实体（范畴），如算术表达式、条件语句、过程等；而开始符号作为一特殊的非终结符号则代表着语言中“最大”的语法实体－语言的目标（也称为“句子”），如“程序”。产生式看作定义语法实体的一种书写规则，通过它，可以了解较“大”的语法实体如何由较“小”的语法实体（非终结符号）和/或语言基本成份（终结符号）来构成的。 2018/9/17 《编译原理与技术》讲义

若干基本概念 上下文无关文法（context-free grammar） 同样定义为四元组（VT,VN,S,P），P中的产生式 形式为： A，∈ （VT∪VN )*，而A ∈VN； 开始符号S须在产生式的左部出现至少一次。 2018/9/17 《编译原理与技术》讲义

若干基本概念 e.g.1 算术表达式（含＋，*运算） 递归定义如下： 1）变量是一个算术表达式； 2）若E1和E2是算术表达式，则 E1 + E2, E1 * E2和（E1）也 是算术表达式。 2018/9/17 《编译原理与技术》讲义

若干基本概念 文法 P: EE+E EE*E E(E) Ei e.g.1 文法G1=({i,+,*,(,)},{E},E,P)，其中产生式集合（左递归形式） P: EE+E EE*E E(E) Ei 2018/9/17 《编译原理与技术》讲义

若干基本概念 文法 P: EE+E P: EE+E EE*E | E*E E(E) | (E) E i | i e.g. 1文法G1=({i,+,*,(,)},{E},E,P)，其中产生式集合 P: EE+E P: EE+E EE*E | E*E E(E) | (E) E i | i 相同左部的产生式 2018/9/17 《编译原理与技术》讲义

若干基本概念 文法 e.g.2 文法G2=({i,+,*,(,)},{E,T,F},E,P)，P： EE + T | T TT * F 2018/9/17 《编译原理与技术》讲义

若干基本概念 文法G2，P： 文法G1，P: EE + T EE+E | T | E*E TT * F | (E) | F | i 文法G1和G2描述了相同的语言－ 算术表达式 2018/9/17 《编译原理与技术》讲义

若干基本概念 文法产生的语言 e.g.3 i + i是算术表达式，那么文法G1是如何“描述”它的？文法G2呢？ 2018/9/17 《编译原理与技术》讲义

若干基本概念 文法产生的语言 e.g.3 G1的描述： E ⇒ E + E ⇒ i + E ⇒ i + i G2的描述： E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ i + T ⇒ i + F ⇒ i + i 2018/9/17 《编译原理与技术》讲义

若干基本概念 文法产生的语言 e.g.3 G1的“描述”方式： 从文法的开始符号E出发，反复用产生式的右部对其左部的非终结符进行替换和展开，直至i+i出现为止。 所用产生式的顺序为： 1) EE+E 2) E i 3) E i 2018/9/17 《编译原理与技术》讲义

若干基本概念 文法产生的语言 e.g.3 G2的“描述”方式： 所用产生式的顺序为： 1) EE+T 5) T F 2) E T 6) F i 3) T F 4) F i 2018/9/17 《编译原理与技术》讲义

若干基本概念 文法产生的语言 我们称上述“描述”为从开始符号E到i+i的“推导”过程。“⇒”表示一步“推导”。 一般地， A直接推导出，即 A ⇒  仅当A ∈ P, ,, ∈ （VT∪VN )*。 推导序列－  ，   2018/9/17 《编译原理与技术》讲义

若干基本概念 文法产生的语言 是句型，如果S  ，  ∈ （VT∪VN )*。 是句子，如果S  ，且 ∈ VT*。 文法G产生的语言L(G),定义为， L(G)={文法G产生的所有句子} 2018/9/17 《编译原理与技术》讲义

若干基本概念 文法产生的语言 e.g.4 文法G3产生的语言是什么？ P：S b A A a A | a S⇒bA⇒ba S⇒bA⇒baA⇒baa S⇒bA⇒baA⇒baaA⇒…⇒baa…a L(G3) = { 以b开头后跟一个或多个a的串} 2018/9/17 《编译原理与技术》讲义

若干基本概念 e.g.5 文法产生的语言 L(G4)={ambn|m,n1} L(G5) = {anbn|n 1} G4: S A B A a A | a B b B | b G5: S a S b | ab 2018/9/17 《编译原理与技术》讲义

e.g.5 文法产生的语言 文法G4对句子aaabb的推导： S ⇒ A B S A B ⇒ a A B A a A ⇒ a a A B A a A ⇒ a a a B A a ⇒ a a a b B B b B ⇒ a a a b b B b 2018/9/17 《编译原理与技术》讲义

e.g.5 文法产生的语言 文法G5对句子aaaabbbb的推导： S ⇒ a S b S a S b ⇒ a a S b b S a S b ⇒ a a a S b b b S a S b ⇒ a a a a b b b b S a b 2018/9/17 《编译原理与技术》讲义

最左推导 最右推导 E⇒E + E ⇒i + E ⇒E + i ⇒i + i 句型推导时，总是选择最左出现的非终结符进行替换 总是选择最右出现的非终结符进行替换，也称为规范推导 最左推导 最右推导 E⇒E + E ⇒i + E ⇒E + i ⇒i + i 2018/9/17 《编译原理与技术》讲义

若干基本概念 规范推导（最右推导）和规范归约（最左归约） G1的句子i+i*i的规范推导过程： E 开始符号 ⇒ E + E E E + E ⇒ E + E * E E E * E ⇒ E + E * i E i ⇒ E + i * i E i ⇒ i + i + i E i 推导方向 2018/9/17 《编译原理与技术》讲义

若干基本概念 规范推导（最右推导）和规范归约（最左归约） G1的句子i+i*i的规范归约过程： i + i + i E i E + i * i E i E + E * i E i E + E * E E E * E E + E E E + E E （只有）开始符号 归约方向 2018/9/17 《编译原理与技术》讲义

最右推导 最左归约 如果右句型 可以“归约”到右句型 ，仅当存在最右推导序列 如果右句型 可以“归约”到右句型 ，仅当存在最右推导序列 从开始符号S出发，进行最右推导，用相应产生式右部文法符号串替换展开其左部非终结符号。目标为句子（右句型）。 从句子（右句型）出发，用最左归约，用相应产生式的左部非终结符号替换产生式右部（句柄）。目标为开始符号S。 2018/9/17 《编译原理与技术》讲义

最右推导 最左归约 推导中，关键是选择产生式 归约中，关键是确定句柄。而句柄与某产生式的右部相同且有某最右推导序列中的某一步对应；归约过程看成这一步最右推导的逆过程。 2018/9/17 《编译原理与技术》讲义

若干基本概念 分析树 分析树看成是（句型）推导的图形表示；反之，（句型）推导可理解为分析树的线形表示。 分析树所有结点v（内部结点和叶子结点）由文法符号或标记，即v∈ （VT∪VN∪{} ); 根结点由文法开始符号S标记； 内部结点A ∈ VN，其所有子结点从左往右排列构成以A为左部的某产生式的右部 2018/9/17 《编译原理与技术》讲义

圆圈内表示新构造的分析（子）树－即推导所用产生式 若干基本概念 分析树与推导 文法G1推导句子i+i*i (最左)推导过程： 分析树 E ⇒ E + E E E E + 圆圈内表示新构造的分析（子）树－即推导所用产生式 2018/9/17 《编译原理与技术》讲义

若干基本概念 分析树与推导－句子i+i*i (最左)推导过程： 分析树 E ⇒ E + E ⇒ i + E E E E + i (最左)推导过程： 分析树 E ⇒ E + E ⇒ i + E E E E + i 2018/9/17 《编译原理与技术》讲义

若干基本概念 分析树与推导－句子i+i*i (最左)推导过程： 分析树 E ⇒ E + E ⇒ i + E ⇒ i + E * E E E (最左)推导过程： 分析树 E ⇒ E + E ⇒ i + E ⇒ i + E * E E E E + E * E i 2018/9/17 《编译原理与技术》讲义

若干基本概念 分析树与推导－句子i+i*i (最左)推导过程： 分析树 E ⇒ E + E ⇒ i + E ⇒ i + E * E (最左)推导过程： 分析树 E ⇒ E + E ⇒ i + E ⇒ i + E * E ⇒ i + i * E E E E + E * E i i 2018/9/17 《编译原理与技术》讲义

若干基本概念 分析树与推导－句子i+i*i (最左)推导过程： 分析树 E ⇒ E + E ⇒ i + E ⇒ i + E * E (最左)推导过程： 分析树 E ⇒ E + E ⇒ i + E ⇒ i + E * E ⇒ i + i * E ⇒ i + i * i E …1代结点 E E + …2代结点 E * E …3代结点 i i i …4代结点 2018/9/17 《编译原理与技术》讲义

若干基本概念 二义性文法 文法G是二义性文法，如果它的某个句子有两种不同的最左（或最右）推导；或有两棵不同的分析树。该句子称为文法G的二义性句子。 二义性语言 语言L是二义性的语言，如果不存在能产生它的非二义性的文法；或者能产生该语言的文法均为二义性文法。 2018/9/17 《编译原理与技术》讲义

若干基本概念－ 二义性文法 e.g.8 文法G1是二义性文法。这是因为对于句子 i+i*i 有两种不同的最右推导。 推导1： E ⇒ E + E ⇒ E + E * E ⇒ E + E * i ⇒ E + i * i ⇒ i + i * i 推导2： E ⇒ E * E ⇒ E * i ⇒ E + E * i ⇒ E + i * i⇒ i + i * i 2018/9/17 《编译原理与技术》讲义

若干基本概念－ 二义性文法 e.g.9 文法G1是二义性文法。这是因为对于句子 i+i*i 有两棵不同的分析树。 E E E + E E E 2018/9/17 《编译原理与技术》讲义

若干基本概念－ 二义性文法 e.g.10 文法G1对于句子 i+i+i 有两棵不同的分析树。 E E E + E E E + E i E + 2018/9/17 《编译原理与技术》讲义

若干基本概念－ 二义性文法 e.g.11 文法G2是非二义性文法。对于句子i+i*i有唯一的最左推导过程。（why?） 推导过程： E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ i + T ⇒ i + T * F ⇒ i + F * F ⇒ i + i * F ⇒ i + i * i 2018/9/17 《编译原理与技术》讲义

若干基本概念－ 二义性文法 e.g.12 文法G2是非二义性文法。对于句子i+i*i有唯一的分析树。 E E + T F T T * F F 2018/9/17 《编译原理与技术》讲义

if－then－else 问题 e.g.13 文法G3如下： stmt  if expr then stmt | if expr then stmt else stmt | others G3是二义性文法，因为对输入串， if E1 then if E2 then S1 else S2 有两棵不同的分析树（推导） 2018/9/17 《编译原理与技术》讲义

stmt if expr then stmt E1 if expr then stmt else stmt E2 S1 S2 stmt if 2018/9/17 《编译原理与技术》讲义

if－then－else 问题 解决if-then-else的二义性 对输入串， stmt  matched | unmatched matched  if expr then matched else matched | others unmatched  if expr then stmt | if expr then matched else unmatched 对输入串， if E1 then if E2 then S1 else S2 仅有惟一的分析树（推导） 2018/9/17 《编译原理与技术》讲义

stmt unmatched if expr then stmt E1 matched if expr then matched else 2018/9/17 《编译原理与技术》讲义

if－then－else 下面的文法是否有二义性？ stmt  if expr then stmt else-part | others else-part  else stmt endif | endif 2018/9/17 《编译原理与技术》讲义

约化的CFG CFG中不含有不可达、或者无法推出终结符串的非终结符。 文法G4 约化后的文法G5： S  A | B S  A A  a A  a B  B b C  c 2018/9/17 《编译原理与技术》讲义

形式语言分类 0型文法 短语文法 1型文法 上下文有关文法 2型文法 上下文无关文法 3型文法 正规文法 或 图灵机 线性有界自动机 下推自动机 有限自动机 2018/9/17 《编译原理与技术》讲义

形式语言分类 0型文法 短语文法 1型文法 上下文有关文法 2型文法 上下文无关文法 3型文法 正规文法 L0={ } L1={ L2={ 2018/9/17 《编译原理与技术》讲义

正规式 V.S 上下文无关文法 任意正规集可以用一上下文文法来产生。 如：正规式(a|b)*ab，则如下的CFG产生相同语言集合（正规集）： A0  aA0 | bA0 | aA1 A1  bA2 A2  ε A0 A1 A2 a b 正规式(a|b)*ab对应FA 相应CFG的构造规则： （1）FA中若有状态i 状态j且标记为a的转换，则添加产生式 Ai aAj，Ai和Aj为状态i和j对应的非终结符 （2）FA中的终态f，引入产生式Afε 2018/9/17 《编译原理与技术》讲义

语法分析 分析树 词法分析 语法分析器 符号表 语义分析 错误处理 token 高级语言源程序 get_next_token 2018/9/17 《编译原理与技术》讲义

有两种通用的语法分析方法。第一种方法，称为自顶向下的（top-down）。如果一个分析器从树的顶端（开始符号）开始发现词法记号序列所对应的分析树，并随后以深度优先的方式（用产生式）对其进行扩展，则它被认为是自顶向下的。自顶向下的语法分析器对应分析树的前序遍历。自顶向下的语法分析技术本质上是预测性的（predictive），因为它们总是在实际匹配开始之前预测将要被匹配的产生式。自顶向下的（top-down）预测分析用的产生式对应着最左推导。 2018/9/17 《编译原理与技术》讲义

另一种方法属于自底向上的（bottom-up）语法分析器类。自底向上的语法分析器从分析树的底部（树的叶结点，它们都是终结符号）开始发现其结构，并确定用来生成叶结点的产生式。随后发现用来生成叶结点的直接父结点的产生式。自底向上的语法分析器对应分析树的后序遍历。自底向上的（bottom-up）语法分析所识别的产生式对应着最右分析－即最左规约（最右推导的严格逆序）。 2018/9/17 《编译原理与技术》讲义