编译原理与技术 文法和分析.ppt

2019/9/18,编译原理与技术讲义,1,编译原理与技术,文法和分析,2019/9/18,编译原理与技术讲义,2,文法和分析,形式语言中若干基本概念 语言 文法（上下文无关文法） 分析树与二义性 形式语言分类 乔姆斯基分类,2019/9/18,编译原理与技术讲义,3,若干基本概念,语言 语言L s | s 是上任一字符串， s称为语言L的一个句子。 字母表符号/字符的非空有限集合 e.g. 二进制数的0,1，而十进制数的0,1,9 *表示上所有字符串的集合；L* 字符串 上若干字符组成的有穷序列,2019/9/18,编译原理与技术讲义,4,若干基本概念,语言 字符串 e.g. 0,1上的0，1串（二进制数）如0111，10101；a,b上的 a, b, aa , abab, 空串， *， 串长|s|s中所含字符的个数，| |=0 串的连接运算任意串x，y，一般地，xyyx， x= x 串的前缀 任意串x，从其第一个字符（最左字符）起的字符序列是其前缀。亦是。 e.g. x = abc, 则，a，ab，abc均是x的前缀,2019/9/18,编译原理与技术讲义,5,若干基本概念,2019/9/18,编译原理与技术讲义,6,若干基本概念,语言 e.g. L=a,b,z, D=0,1,9, B= _ LD = LD= L*= L(LD)*= (L B)(LDB)*= D+=,2019/9/18,编译原理与技术讲义,7,若干基本概念,文法 文法G（VT,VN,S,P）定义为一个四元组，其中： VT终结符号集合； VN非终结符号集合，VTVN= ； S文法开始符号，SVN ； P文法产生式集合，每一产生式形如， 其中， （VTVN )*，至少含有一个非 终结符， 称为相应产生式的左部，则 为产生式的右部。,2019/9/18,编译原理与技术讲义,8,若干基本概念,文法是描述语言的语法结构的形式规则，其中，终结符号（集合）表示组成语言的基本成份，如标识符、常数，算符等；非终结符号（集合）代表语法实体（范畴），如算术表达式、条件语句、过程等；而开始符号作为一特殊的非终结符号则代表着语言中“最大”的语法实体语言的目标（也称为“句子”），如“程序”。产生式看作定义语法实体的一种书写规则，通过它，可以了解较“大”的语法实体如何由较“小”的语法实体（非终结符号）和/或语言基本成份（终结符号）来构成的。,2019/9/18,编译原理与技术讲义,9,若干基本概念,上下文无关文法（context-free grammar） 同样定义为四元组（VT,VN,S,P），P中的产生式 形式为： A， （VTVN )*，而A VN； 开始符号S须在产生式的左部出现至少一次。,2019/9/18,编译原理与技术讲义,10,若干基本概念,e.g.1 算术表达式（含，*运算） 递归定义如下： 1）变量是一个算术表达式； 2）若E1和E2是算术表达式，则 E1 + E2, E1 * E2和（E1）也 是算术表达式。,2019/9/18,编译原理与技术讲义,11,若干基本概念,文法 e.g.1 文法G1=(i,+,*,(,),E,E,P)，其中产生式集合（左递归形式） P: EE+E EE*E E(E) Ei,2019/9/18,编译原理与技术讲义,12,若干基本概念,文法 e.g. 1文法G1=(i,+,*,(,),E,E,P)，其中产生式集合 P: EE+E P: EE+E EE*E | E*E E(E) | (E) E i | i,相同左部的产生式,2019/9/18,编译原理与技术讲义,13,若干基本概念,文法 e.g.2 文法G2=(i,+,*,(,),E,T,F,E,P)，P： EE + T | T TT * F | F F( E ) | i,2019/9/18,编译原理与技术讲义,14,若干基本概念,文法G2，P： EE + T | T TT * F | F F( E ) | i,文法G1，P: EE+E | E*E | (E) | i,文法G1和G2描述了相同的语言 算术表达式,2019/9/18,编译原理与技术讲义,15,若干基本概念,文法产生的语言 e.g.3 i + i是算术表达式，那么文法G1是如何“描述”它的？文法G2呢？,2019/9/18,编译原理与技术讲义,16,若干基本概念,文法产生的语言 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,2019/9/18,编译原理与技术讲义,17,若干基本概念,文法产生的语言 e.g.3 G1的“描述”方式： 从文法的开始符号E出发，反复用产生式的右部对其左部的非终结符进行替换和展开，直至i+i出现为止。 所用产生式的顺序为： 1) EE+E 2) E i 3) E i,2019/9/18,编译原理与技术讲义,18,若干基本概念,文法产生的语言 e.g.3 G2的“描述”方式： 所用产生式的顺序为： 1) EE+T 5) T F 2) E T 6) F i 3) T F 4) F i,2019/9/18,编译原理与技术讲义,19,若干基本概念,文法产生的语言 我们称上述“描述”为从开始符号E到i+i的“推导”过程。“”表示一步“推导”。 一般地， A直接推导出，即 A 仅当A P, , （VTVN )*。 推导序列 ， ,2019/9/18,编译原理与技术讲义,20,若干基本概念,文法产生的语言 是句型，如果S ， （VTVN )*。 是句子，如果S ，且 VT*。 文法G产生的语言L(G),定义为， L(G)=文法G产生的所有句子,2019/9/18,编译原理与技术讲义,21,若干基本概念,文法产生的语言 e.g.4 文法G3产生的语言是什么？ P：S b A A a A | a SbAba SbAbaAbaa SbAbaAbaaAbaaa L(G3) = 以b开头后跟一个或多个a的串,2019/9/18,编译原理与技术讲义,22,若干基本概念,2019/9/18,编译原理与技术讲义,23,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,2019/9/18,编译原理与技术讲义,24,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,2019/9/18,编译原理与技术讲义,25,句型推导时，总是选择最左出现的非终结符进行替换,总是选择最右出现的非终结符进行替换，也称为规范推导,2019/9/18,编译原理与技术讲义,26,若干基本概念,规范推导（最右推导）和规范归约（最左归约） 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,推导方向,2019/9/18,编译原理与技术讲义,27,若干基本概念,规范推导（最右推导）和规范归约（最左归约） 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 （只有）开始符号,归约方向,2019/9/18,编译原理与技术讲义,28,2019/9/18,编译原理与技术讲义,29,2019/9/18,编译原理与技术讲义,30,若干基本概念,分析树 分析树看成是（句型）推导的图形表示；反之，（句型）推导可理解为分析树的线形表示。 分析树所有结点v（内部结点和叶子结点）由文法符号或标记，即v （VTVN ); 根结点由文法开始符号S标记； 内部结点A VN，其所有子结点从左往右排列构成以A为左部的某产生式的右部,2019/9/18,编译原理与技术讲义,31,若干基本概念,分析树与推导 文法G1推导句子i+i*i (最左)推导过程： 分析树 E E + E,E,E,E,+,圆圈内表示新构造的分析（子）树即推导所用产生式,2019/9/18,编译原理与技术讲义,32,若干基本概念,分析树与推导句子i+i*i (最左)推导过程： 分析树 E E + E i + E,E,E,E,i,+,2019/9/18,编译原理与技术讲义,33,若干基本概念,分析树与推导句子i+i*i (最左)推导过程： 分析树 E E + E i + E i + E * E,E,E,E,i,E,E,+,*,2019/9/18,编译原理与技术讲义,34,若干基本概念,分析树与推导句子i+i*i (最左)推导过程： 分析树 E E + E i + E i + E * E i + i * E,E,E,E,i,E,E,i,*,+,2019/9/18,编译原理与技术讲义,35,若干基本概念,分析树与推导句子i+i*i (最左)推导过程： 分析树 E E + E i + E i + E * E i + i * E i + i * i,E,E,E,i,E,E,i,i,+,*,1代结点,2代结点,3代结点,4代结点,2019/9/18,编译原理与技术讲义,36,若干基本概念,二义性文法 文法G是二义性文法，如果它的某个句子有两种不同的最左（或最右）推导；或有两棵不同的分析树。该句子称为文法G的二义性句子。 二义性语言 语言L是二义性的语言，如果不存在能产生它的非二义性的文法；或者能产生该语言的文法均为二义性文法。,2019/9/18,编译原理与技术讲义,37,若干基本概念 二义性文法,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,2019/9/18,编译原理与技术讲义,38,若干基本概念 二义性文法,e.g.9 文法G1是二义性文法。这是因为对于句子 i+i*i 有两棵不同的分析树。,E,E,E,i,E,E,i,i,+,*,E,E,i,E,E,i,i,+,*,E,i+i*i的一棵分析树,i+i*i的另一棵分析树,2019/9/18,编译原理与技术讲义,39,若干基本概念 二义性文法,e.g.10 文法G1对于句子 i+i*i 有两棵不同的分析树。,E,E,E,i,E,E,i,i,+,*,E,E,i,E,E,i,i,+,*,E,i+i*i的一棵分析树,i+i*i的另一棵分析树,2019/9/18,编译原理与技术讲义,40,若干基本概念 二义性文法,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,2019/9/18,编译原理与技术讲义,41,若干基本概念 二义性文法,e.g.12 文法G2是非二义性文法。对于句子i+i*i有唯一的分析树。,E,E,T,T,F,i,i,+,*,F,T,i,F,2019/9/18,编译原理与技术讲义,42,ifthenelse 问题,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 有两棵不同的分析树（推导）,2019/9/18,编译原理与技术讲义,43,stmt,if,expr,then,stmt,E1,if,expr,then,stmt,E2,S1,else,stmt,S2,stmt,if,expr,then,stmt,E1,if,expr,then,stmt,E2,S1,else,stmt,S2,2019/9/18,编译原理与技术讲义,44,ifthenelse 问题,解决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 仅有惟一的分析树（推导）,2019/9/18,编译原理与技术讲义,45,unmatched,if,expr,then,stmt,E1,if,expr,then,matched,E2,S1,else,S2,stmt,matched,matched,2019/9/18,编译原理与技术讲义,46,ifthenelse,下面的文法是否有二义性？ stmt if expr then stmt else-part | others else-part else stmt endif | endif,2019/9/18,编译原理与技术讲义,47,约化的CFG,CFG中不含有不可达、或者无法推出终结符串的非终结符。 文法G4 约化后的文法G5： S A | B S A A a A a B B b C c,2019/9/18,编译原理与技术讲义,48,形式语言分类,2019/9/18,编译原理与技术讲义,49,形式语言分类,2019/9/18,编译原理与技术讲义,50,任意正规集可以用一上下文文法来产生。 如：正规式(a|b)*ab，则如下的CFG产生相同语言集合（正规集）： A0 aA0 | bA0 | aA1 A1 bA2 A2 ,正规式 V.S 上下文无关文法,相应CFG的构造规则： （1）FA中若有状态i 状态j且标记为a的转换，则添加产生式 Ai aAj，Ai和Aj为状态i和j对应的非终结符 （2）FA中的终态f，引入产生式Af,2019/9/18,编译原理与技术讲义,51,语法分析,2019/9/18,编译原理与技术讲义,52,有两种通用的语法分析方法。第一种方法，称为自顶向下的（top-down）。如果一个分析器从树的顶端（开始符号）开始发现词法记号序列所对应的分析树，并随后以深度优先的方式（用产生式）对其进行扩展，则它被认为是自顶向下的。自顶向下的语法分析器对应分析树的前序遍历。自顶向下的语法分析技术本质上是预测性的（predictive），因为它们总是在实际匹配开始之前预测将要被匹配的产生式。自顶向下的（top-down）预测分析用的产生式对应着最左推导。,2019/9/18,编译原理与技术讲义,53,另一种方法属于自底向上的（bottom-up）语法分析器类。自底向上的语法分析器从分析树的底部（树的叶结点，它们都是终结符号）开始发现其结构，并确定用来生成叶结点的产生式。随后发现用来生成叶结点的直接父结点的产生式。自底向上的语法分析器对应分析树的后序遍历。自底向上的（bottom-up）语法分析所识别的产生式对应着最右分析即最左规约（最右推导的严格逆序）。,