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

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