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

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