辽宁大学-编译原理part4课件

1、2022/9/251编译原理(Principles of Compiling)主讲：周翰逊Email：QQ：260540362022/9/25288pin88+pin*d88+pin*d2022/9/253编译程序总体结构中间代码目标代码生成器代码优化器语义分析与中间代码生成器语法分析器表 格 管 理出 错 处 理中间代码目标代码语法单位单词符号词法分析器源程序2022/9/2554.1 语法分析的任务语法分析(Syntax Analysis)检查扫描器输出的单词序列是否符合该语言的文法组成句子，并分析组成此句子的语法成分完成语法分析的程序叫做(语法)分析器ParserSyntax Analy

2、zer2022/9/2564.1 语法分析的任务扫描器分析器语义处理单词符号语法树源程序输入：Token序列输出语法成分及组成表现形式：语法树错误报告出错处理:定位、续编译2022/9/257语法分析方法EE+E|E-E|E*E|E/E|(E)|id ：id+id*idE+EEidEE*ididE+EEEid*ididE2022/9/258语法分析方法自顶向下Top Down自底向上Bottom Up文法产生语言自动机识别语言递归子程序法预测分析法(LL(1)算符优先分析法LR(0)、SLR(1)LR(1)、LALR归约!推导/派生!2022/9/2510二、重要概念回顾推导: (依据:)最左

3、(Left-most)推导最左分析左句型最左推导对应最右归约 EE+E a1+Ea1+E*Ea1+a2*Ea1+a2*a3 EE+EE+E*E E+E*a3E+a2*a3a1+a2*a3最右(Right-most)推导最右分析规范推导、规范句型(右句型)最右推导对应最左归约(规范归约)二义性(先天二义性语言、二义性文法)EE+E | E-E | E*E | E/E | (E) | id2022/9/2512三、重要问题回溯S x * * yS xAyx * * y发现不匹配,需要回退xAyx*ySxAy*SxAy*x*y匹配成功2022/9/2514三、重要问题二义性及其消除二义性文法EE+E

4、|E-E|E*E|E/E|(E)|id非二义性文法EE+T|E-T|TTT*F|T/F|FF(E)|id改造方法：引入语法变量，使文法含有更多的信息2022/9/2515三、重要问题二义性及其消除再例：If语句Sif E then SSif E then S else SSother设执行下列语句前b=0,理解1：if a0 then if a0 then b=1 else b=-1当a=1时,执行后b=1;当a=-1时，执行后b=-1理解1： if a0 then if a0 then b=1 else b=-1当a=1时,执行后b=1;当a=-1时，执行后b=0一个句子有两棵不同的语法树S

5、SE ES Sif a0 then if a0 then b=1 else b=-1SSE ES Sif a0 then if a0 then b=1 else b=-12022/9/2517三、重要问题二义性及其消除1.重写文法SU|MUif E then SUif E then M else UMif E then M else M|other2.设置一个规则实现“就近” 、“最长” 匹配原则改造1改造2STS|CSCif E thenT CS elseCConditionTElse每个else与前面最近的没有配对的then配对，即出现在then和else之间的语句必须是配对的按照“改造1

6、”构造的语法树SUSMEEMMif a0 then if a0 then b=1 else b=-1Mif E then M else M|other按照“改造2”构造的语法树STS(非最长)CCEE SSIf a0 then if a0 then b=1 else b=-1STS|CSCif E thenT CS else三、重要问题二义性及其消除SS S T (最长) T (最长) S C C C Cif E then if E then S else if E then S else if E then SSTS|CSCif E thenT CS else2022/9/2523三、重要问

7、题左递归及其消除例 简单算术表达式的文法左递归EE+T|E-T|T|-ETT*F|T/F|FFFP|PP(E)|id|const|FUN(L)FUN abs | sin | cos | ln | log | exp | sqrtLE|E,LVNE,T,F,P,FUN,LVTid,const,+,-,*,/,(,), , abs,sin,cos,log,ln,exp,sqrtSE2022/9/2524三、重要问题左递归及其消除无法根据左递归文法进行自顶向下的分析A a1a2aian直接左递归A A 当前变量 输入指针(栈顶、最左变量)间接左递归A+A左递归的消除方法将AA|替换为AA 和 AA2

8、022/9/2526编译原理(Principles of Compiling)主讲：周翰逊Email：QQ：260540362022/9/2527上次课主要内容两类不同的语法分析方法自顶向下的分析推导（派生）：自顶向下构造语法分析树自底向上的分析归约：自地向上构造语法分析树待处理的问题虚假匹配与回溯二义性文法2022/9/2528上次课主要内容消除左递归将产生式组AA1|A2|An|1|2|m 变换成A1 B|2 B |m BB1 B|2 B |n B|2022/9/2530消除左递归的一般方法对产生式组AA1|A2|An|1|2|m 用如下产生式组替换A1 B|2 B |m BB1 B|2

9、B |n B|其中：B为新变量，相当于A消除左递归的算法为非终结符编号，再采用代入法将间接左递归变为直接左递归，消除直接左递归2022/9/2531三、重要问题提取左因子例：if语句的原始文法S if E then S |if E then S else S |other遇到 if 时难以判断用哪一个产生式进行匹配（推导）存在左因子 if E then S2022/9/2532三、重要问题提取左因子提取作因子if E then SS if E then SS|otherS|else S另一种写法STS | CS | otherCif E thenT CS else2022/9/2533三、重要

10、问题提取左因子将形如 A1|2|m |1|2| | p的规则改写为AA |1|2| | p和 A1|2|m结果：S if E then SS|otherS|else S2022/9/2534四、CFG的使用限制没有一种方法能够有效地分析所有CFG (上下文无关文法)存在无法处理的CFG每种方法能够处理一部分CFG每种方法都有适用范围2022/9/2535五、常用文法与分析方法LL文法和 LR 文法都是CFG的子集无二义性可用不同的文法来描述同一语言对于不同的文法，可用不同的分析方法LL文法 递归下降分析法、预测分析法多用于编译的手工实现LR文法 LR分析法多用于编译的自动生成2022/9/25

11、364.3 自顶向下的分析方法回顾基本思想寻找输入符号串的最左推导试图根据当前输入单词确定使用哪个产生式基本过程从S出发，构造输入符号串(Token)的最左推导从根开始，按与最左推导相对应的顺序，构造输入符号串(Token)的语法分析树2022/9/2537例 符号串 id + id * id的分析E T E E + T E T F T T * F T F ( E )idE E + TTT T * FFF ( E )id按照最左推导过程，构造语法树id + id * id的最左推导与语法树的生成i di di d1、ETE2、TFT3、Fid4、T5、E+TE6、TFT7、Fid8、T*FT9

12、、Fid10、T11、EE T E E + T E T F T T * F T F ( E )idid + id * id的最左推导再现E TEE TE FTET FTidTEF id idET id+TEE+TE id+FTET FT id+idTEF id id+id*FTET*FT id+id*idTEF id id+id*idET id+id*id EE T E E + T E T F T T * F T F ( E )id分析真的就总是这么顺利？2022/9/2540候选式的确定与回溯(Backtracking)给定文法ScAdAab|e?句子ced是该文法定义语言的句子ecAdS当

13、需要用A派生时，可以根据输入符号e唯一的确定A的候选式2022/9/2541候选式的确定与回溯(Backtracking)给定文法ScAdAab|e?句子cad是该文法定义语言的句子cAdSba出现一次虚假的匹配，并且立即发现cad不是合法句子2022/9/2542候选式的确定与回溯(Backtracking)给定文法ScAdAab|a?句子cad是该文法定义语言的句子cAdSbaacAdS当需要用A派生时，无法根据输入符号a唯一的确定A的候选式2022/9/2543候选式的确定与回溯(Backtracking)给定文法ScABd Aab| Ba?句子cad是该文法定义语言的句子bac A B

14、dSc A BdSa当需要用A派生时，因为A使得无法根据输入符号a唯一的确定A的候选式2022/9/2544候选式的确定与回溯(Backtracking)给定文法ScABd Aba| Ba?句子cad是该文法定义语言的句子c A BdSa当需要用A派生时,虽然有A,仍然可以根据输入符号a唯一的确定A的候选式2022/9/2545候选式的确定与回溯(Backtracking)句子cad的分析对给定文法ScAd Aab|a,分析需要回溯对给定文法ScAd Aab|e ,分析不需要回溯对给定文法ScABd Aab| Ba，分析需要回溯对给定文法ScABd Aba| Ba，分析不需要回溯2022/9/

15、2546候选式的确定与回溯(Backtracking)当要进行某个语法变量的推导时，希望能够根据当前符号确定候选式如果有几个候选式左端第一个符号相同，则分析程序无法根据当前输入符号选择产生式一个候选式可空，另一个候选式的首符号可以跟在这个语法变量后面希望：寻找一类文法，可以方便地根据当前输入符号确定正确的候选式2022/9/25474.3.1 FIRST 和 FOLLOW 集A1|2|i|n对于 (VTVN) *定义:的首符号集FIRST()=a|*a，aVT*对于AVN定义A的后续符号集： FOLLOW(A)=a|S*Aa，aVT 2022/9/2548求FIRST( X ) 的算法1) 对

16、xVT，FIRST(x)=x ；2) 对XVN，取FIRST(X)的初值：FIRST(X)=a|XaPXPa|XaP XP3)对XVN，重复如下过程，直到所有FIRST集不变若 XYP ，且 YVN，则 FIRST(X)= FIRST(X)(FIRST(Y)-)；若 XY1YnP，且Y1.Yi-1*，则 对k=1到i:FIRST(X)= FIRST(X)(FIRST(Yk)-) ；若 Y1.Yn*，则 FIRST(X)=FIRST(X) 2022/9/2550例 表达式文法的语法符号的 FIRST 集FIRST(F)=(,idFIRST(T)=FIRST(F)=(,id FIRST(E)=FI

17、RST(T)=(,id FIRST(E)=+，FIRST(T)=*, FIRST(+)=+, FIRST(*)=*FIRST( ( )=(FIRST( ) )=)FIRST(id)=idETE E+TE| TFT T*FT| F(E)|id2022/9/2551求FIRST() 的算法令= X1Xn初值FIRST()= FIRST(X1)-;k=1;循环while FIRST(Xk)&kn doFIRST()= FIRST()(FIRST(Xk+1)-) ；K=k+1;结束处理if k=n&FIRST(Xn) then FIRST()=FIRST()2022/9/2552编译原理(Princi

18、ples of Compiling)主讲：周翰逊Email：QQ：260540362022/9/2553上次课主要内容自顶向下的分析方法基本思想分析的关键点输入指针栈的处理：需要栈、变量和终极符进栈问题希望根据当前变量（最左变量）唯一地确定候选式2022/9/2554上次课主要内容对文法的要求A1|2|nFIRST()=a|*a，aVTA1|2|n| FIRST()=a|*a，aVT FOLLOW(A)=a|S*Aa，aVT 2022/9/2555上次课主要内容求FIRST() 的算法xVT VN，求FIRST( X )XaP X PXYP求FIRST()= X1Xn2022/9/2556求F

19、OLLOW( A ) 的算法令#为句子的结束符，对于所有非终结符, 重复进行以下计算1) 将 # 加入到 FOLLOW(S)2) 若 AB，则 FOLLOW(B)=FOLLOW(B)(FIRST()3) 如果AB或AB，且*，AB，则 FOLLOW(B)=FOLLOW(B)FOLLOW(A) 2022/9/2557例 表达式文法的语法变量的 FOLLOW 集FOLLOW(E) = #, ) ETE E+TE|TFT T*FT|F(E)|idFIRST(F)=（,idFIRST(T)=FIRST(F)=（,id FIRST(E)=FIRST(T)=（,id FIRST(E)=+，FIRST(T)

20、=*,FIRST()= FIRST()FOLLOW(E)= FOLLOW( E ) = #, ) FOLLOW(T) = FIRST (E)FOLLOW(E)FOLLOW(E) = +,),#FOLLOW(T)= FOLLOW(T)= +,),#FOLLOW(F) = FIRST(T)FOLLOW(T)FOLLOW(T) =*,+,),# 2022/9/2558自顶向下分析中希望文法满足的条件希望：从左到右扫描输入串，寻找它的一个最左推导，每次有唯一的产生式可用对于 G 的每个非终结符 A 的任何两个不同的候选式 A|1) FIRST()FIRST()=2) 如果*，则 FIRST()FOLL

21、OW(A)=2)如果*，则 FIRST()FOLLOW(A)=文法是 LL(1) 的充要条件2022/9/25594.3.2 LL(1)文法对G的任意变量A， A1|2|n是所有A产生式，如果它们满足下列条件，则称G是LL(1)文法，FIRST(i)FIRST(j)= ij且当FIRST(j)时，FOLLOW(A)FIRST(i)=LL(1)文法是自顶向下方法能够处理的一类文法第一个 L 表示从左向右扫描输入符号串第二个 L 表示生成最左推导1 表示读入一个符号可确定下一步推导LL is the notation of the parsing strategy: the input strin

22、g is scanned in a left-to-right manner and the parser generates a leftmost derivation2022/9/2560表达式文法是 LL(1) 文法E T E E + T E T F T T * F T F ( E )id考察E : + 不在 FOLLOW( E ) = ), # T : * 不在 FOLLOW( T ) = +, ), # F: ( 和 id 不同为什么只考虑所列的三条？此文法不满足LL(1)文法的条件，不能保证分析的每一步是确定的，这就是非 LL(1)文法的不确定性例 对文法ScAdAab|a 输入

23、cad 的分析FIRST(ab)=aFIRST(a)=aSdcAbaSdcAa2022/9/2562例 对文法ScABdAab|Ba输入 cad 的分析FOLLOW(A)=aFIRST(ab)=abac A BdSc A BdSa此文法不满足LL(1)文法的条件，不能保证分析的每一步是确定的，这就是非 LL(1)文法的不确定性2022/9/2563不确定性的解决方法1) 采用回溯算法过于复杂2）改写文法将非 LL(1) 文法改写为等价的 LL(1) 文法并非总有效3）无法改写时增加其它的判别因素文法过于复杂，无法用自顶向下方法处理4.4 预测分析器（LL(1)分析器） a1a2aian # 输

24、入缓冲区栈XS#控制程序预测分析表M输出的产生式序列2022/9/25654.4 预测分析器（LL(1)分析器）系统维持一个分析表和一个分析栈，根据当前扫描到的符号，选择当前语法变量（处于栈顶）的候选式进行推导希望找到相应的输入符号串的最左推导组成一个通用的控制算法一个分析栈，#为栈底符号一个输入缓冲区，#为输入串结束符一个统一形式的分析表M不同语言使用内容不同的分析表2022/9/2566FOLLOW( E)= ), # FOLLOW( T)= +, ), # FIRST(TE)=(,id FIRST(+TE)=+FIRST(FT)=(,id FIRST(*FT)=*FIRST(E)=( F

25、IRST(id)=idETE E +TE | TFT T *FT | F(E)|id考虑简单算术表达式文法的实现表达式文法的预测分析表语法变量终极符号id+*()#EETTFFOLLOW( E)= ), # ; FOLLOW( T)= +, ), # ; FIRST(TE)=(,id; FIRST(id)=idFIRST(+TE)=+; FIRST(FT)=(,id; FIRST(*FT)=*;FIRST(E)=(ETE E +TE | TFT T *FT | F(E)|idTETE+TEFTFT*FTid(E)2022/9/2568上次课主要内容求FOLLOW( A ) 的算法FOLLOW(

26、S)=# AB， FOLLOW(B)=FOLLOW(B)(FIRST()AB ，AB FOLLOW(B)=FOLLOW(B)FOLLOW(A) AB，*，AB， FOLLOW(B)=FOLLOW(B)FOLLOW(A)2022/9/2569上次课主要内容预测分析表FOLLOW( E)= ), # ; FOLLOW( T)= +, ), # ; FIRST(TE)=(,id; FIRST(id)=idFIRST(+TE)=+; FIRST(FT)=(,id; FIRST(*FT)=*;FIRST(E)=(ETE E +TE |TFT T *FT |F(E)|id2022/9/2570表达式文法的

27、预测分析表语法变量终极符号id+*()#EETTFTETE+TEFTFT*FTid(E)2022/9/2571执行过程举例：分析 id+id*id（在黑板上同时画出语法树）输入缓冲区 栈 输出id+id*id# E #id+id*id# TE# ETEid+id*id# FTE # TFTid+id*id# idTE # Fid+id*id# TE # +id*id# E # T+id*id# +TE # E+TEid*id# TE #id*id# FTE # TFTid*id# idTE# Fid*id# TE#*id# *FTE# T*FTid# FTE#id# idTE# Fid# TE

28、# E# T# # E输出的产生式序列对应最左推导的过程，同时可以看成相应的分析树+id*id# +TE # （接上页）栈顶为变量：按分析表执行推导栈顶为终极符：匹配2022/9/2573系统的执行与特点初始化：输入指针指向输入串的第一个字符，分析栈中存放栈底符号#和文法的开始符号S根据栈顶符号A和读入的符号a，查看分析表M,以决定相应的动作优点1. 效率高2. 便于维护、自动生成关键分析表M的构造2022/9/2574预测分析表（LL(1)分析表）构造算法1. 对于每一产生式 A，执行2.和3.；2. 对于 FIRST()中的每一终结符a, 将 A 填入 MA,a；3. 如果属于 FIRST

29、()，则对FOLLOW(A)中的每个符号b，将A填入MA,b； 若属于 FIRST()，且#在FOLLOW(A)，则将A填入MA,#；4. 将所有无定义的 MA,b 标上错误标志LL(1)通用控制算法X为当前栈顶符号;a为当前输入符号； repeatif XVT# thenif X=a then if X# then 将X弹出,且前移输入指针else errorelse if MX,a=Y1Y2Yk then将X弹出;依次将YkY2Y1压入栈； 输出产生式XY1Y2Yk else erroruntil X=#2022/9/2576预测分析法总结1. 构造文法2. 改造文法：消除二义性、消除左递

30、归、提取左因子3. 求每个候选式的FIRST集和变量的FOLLOW集4. 检查是不是 LL(1) 文法若不是 LL(1),说明文法的复杂性超过LL(1)分析方法的分析能力，需要附加新的“信息”5. 构造预测分析表6. 实现预测分析器2022/9/2577一个设想对应每个变量设置一个处理子程序：procedure AAX1 X2 Xk Xn当遇到Xk是终极符号时直接进行匹配当遇到Xk是语法变量时就调用Xk对应的处理子程序要求处理子程序是可以递归调用的ETE E +TE| TFT T*FT| F(E)|id2022/9/25784.5 语法图例 4-9：表达式文法的描述+TEETEEETE E+T

31、E| TFTT*FT| F(E)|id2022/9/2579语法图化简规则YXYZYXZX 左因子提取右因子提取AYX|YZAY(X|Z)AYX|ZXA(Y|Z)X2022/9/2580语法图化简规则YXZX XYX|ZXY*Z2022/9/2581语法图的化简+TE+TTEE+TE|ETEET(+T)*简化的语法图+TEi d（）ET(+T)*TF(*F)*F(E)|id2022/9/2583构造语法图语法图是非常有用的设计工具语法图和词法分析器的状态转换图不同每个非终结符对应一个状态转换图，边上标记语法符号如果标记的是终极符号，且与下一个输入符号相同，表示匹配成功如果标记的是非终结符A，则

32、调用A对应的过程2022/9/2584构造语法图对文法的每个非终结符A，构造语法图创建一个开始状态和一个终止状态（返回状态）；对每个产生式AX1X2 Xn，创建一条从开始状态到终止状态的路径，边上的标记依次为X1，X2， ，Xn。2022/9/25854.6 递归子程序法对应每一个语法变量设置一个递归处理子程序，按照语法图，进行相应的处理开始时，分析器的输入指针指向输入符号串的第一个符号在处理过程中如果遇到标记是终结符a，就与当前输入符号进行匹配，并将输入指针向右移动一个字符如果遇到标记是非终结符A，则调用A所对应的递归处理程序此过程直到处理结束。 2022/9/2586例 简单算术表达式的分析器E的子程序(ET(+T)*)procedure E; begin T; 的过程调用 while lookhead=+ do begin 当前符号等于时 match(+); 处理终结符 T 的过程调用 end end; lo