《第四章语法分析,哈工大王宏志》由会员分享，可在线阅读，更多相关《第四章语法分析,哈工大王宏志（179页珍藏版）》请在金锄头文库上搜索。
1、语法分析回顾 一个语句的翻译P483附录：Pascal子 集的词法和语法第四章 语法分析1n语法分析方法递归子程序法n自顶向下预测分析法(LL（1）)算符优先分析法n自底向上LR(0)、SLR(1)LR(1)、LALRTop DownTop DownBottom UpBottom Up文法产生语 言自动机识别语言从根开始，逐 步为某语句构 造一棵语法树相反，将一句 子归约为开始 符号问题：解决确定性问题！假定文法是压缩的：即删除了单位产生式和无用产生式。4.1 4.1 语法分析的功能语法分析的功能n检查由扫描器输出的单词符号序列 是否符合该语言的文法句子n分析器的输入：Token序列n分析器的
2、输出uu分析树分析树uu出错处理出错处理: :定位、续编译定位、续编译分析方法 自顶向下（递归下降、预测分析 ) 自底向上（算符优先、LR分析器 ）4.2 自上而下分析面临的问题与CFG的改造n一、自上而下的分析n从文法的开始符号出发，寻求所给的输入符 号串的一个最左推导。n从树根S开始，构造所给输入符号串的语法树n例：G为：SxAy A*|*，输入串：x*yS Sx xA Ay yx x*y yS S x xA Ay y* * *二、存在问题回溯S xAy x*yS S x xA Ay y* *S S x xA Ay y* * *x * * yx * * yS S xAyxAy x*yx*y
3、 匹配成功匹配成功x * * yx * * y发现不匹配发现不匹配, ,需要回退需要回退输入串输入串x*yx*ySxAy A*|*存在回溯的原因n文法中每个非终结符A的产生式右部称为 A的候选式，如果有多个候选式左端第一个 符号相同，则语法分析程序无法根据当前 输入符号选择产生式，只能试探。二、存在问题左递归问题n文法SSay|* 与它的句子*ayay* *ayayayayS S* * 不对不对！S SSaySaySayaySayaySayayaySayayaySayaySayayayayayay一个无限一个无限 循环！循环！二、重要问题左递归问题n例 CFG:简单算术表达式的文法（语法）nE
4、E+T|E-T|TnTT*F|T/F|FnF(E)|idnNE,T,F,P,FUN,LnTid,+,-,*,/,(,)nE三、重要概念回顾n推导: (依据：)n最左(Left-most)推导最左分析n左句型n最左推导对应最右归约n最右(Right-most)推导最右分析n规范推导、规范句型（右句型）n最右推导对应最左归约（规范归约 ）n二义性(先天二义性语言、二义性文法)四、消除二义性例：简单算术表达式的文法 二义性文法nEE+E|E-E|E*E|E/E|(E)|id非二义性文法nEE+T|E-T|TnTT*F|T/F|FnF(E)|id 改造方法：使文法含有更多的信息，引入语法变量四、消除二
5、义性再例：If语句 Sif E then S Sif E then S else S Sother 设执行下列语句前b=0, If a0 then if a0 then b=1 else b=-1 当a=1时,b=1;当a=-1时，b=-1 If a0 then if a0 then b=1 else b=-1 当a=1时,b=1;当a=-1时，b=0一个句子有两棵不同的语法树SS E ES S If a0 then if a0 then b=1 else b=-1 SS E ES S If a0 then if a0 then b=1 else b=-1四、消除二义性 P174n重写文法：引
6、入新的语法变量 SU|M Uif E then S Uif E then M else U Mif E then M else M|other每个else与前面最近的没有配对的then配对，即：出现在then和 else之间的语句必须是配对的按照改造后的文法构造的语法树S U SMEEM MIf a0 then if a0 then b=1 else b=-1Mif E then M else M|otherMif E then M else M|other五、消除左递归n无法根据左递归文法进行自顶向下的分析 A a1a2aiann直接左递归nA A 当前变量 输入指针 (栈顶、最左变量)n
7、n间接左递归间接左递归uuA A+ +AAn n左递归的消除方法左递归的消除方法uu将将AA|AA|替换为替换为AAAA 和和 A A AA 例：表达式文法直接左递归的消除E E + TTT T * FFF ( E )idE T EE + T E|T F TT* F TF ( E )id例： 间接左递归的消除SAc|c ABb|b BSa|a 将B的定义代入A产生式得：ASab|ab|b 将A的定义代入S产生式得: SSabc|abc|bc|c 消除直接左递归：SabcS|bcS|cSSabcS| 删除“多余的”产生式：ASab|ab|b和 BSa|a 结果：SabcS|bcS|cSSabcS
8、|消除左递归的一般方法n用产生式组nA1 B|2 B |n BnB1 B|2 B |n B|n替换产生式组nAA1|A2|An|1|2|m n其中：B为新变量，相当于An消除左递归的算法见P117的算法4.1n为非终结符编号，再采用代入法将间接 左递归变为直接左递归，消除直接左递归六、 解决回溯问题提取左因子n例：if语句的原始文法nS if E then S n |if E then S else S n |othern影响分析:遇到 if 时难以 判断用哪一个产生式进行匹 配（推导）n存在左因子 if E then S左因子提取方法将形如 A1|2|n |1|2| | m 的规则改写为 A
9、A|1|2| | m和 A1|2|nn结果：nS if E then SS|othernS|else S七、七、CFGCFG的使用限制的使用限制n没有一种方法能够有效地分析所有上下文 无关文法n存在无法处理的型文法(CFG)n每种方法能够处理一部分上下文无关文法n每种方法都有适用范围八、常用文法与分析方法八、常用文法与分析方法nLL文法和 LR 文法都是CFG的子集(无二义性)n可用不同的文法来描述同一语言n对于不同的文法，可用不同的分析方法nLL文法 递归下降分析法、预测分析 法nLR文法 LR分析法nLL 文法多用于编译的手工实现nLR 文法多用于编译的自动生成4.3 自顶向下的分析方法n
10、基本思想n寻找输入符号串的最左推导n试图根据当前输入单词判断使用哪个产 生式n基本过程n从根开始，按与最左推导相对应的顺序 ，构造输入符号串(Token)的分析树例 符号串 id + id * id的分析nE T E nE + T E nT F T nT * F T nF ( E )id 按照最左推导过程，构造分析树id + id * id 最左推导与语法树的生成对应i di di d1、ETE 2、TFT 3、Fid 4、T5、 E+TE6、TFT 7、Fid8、 T*FT9、Fid 10、T 11、Eid + id * id的最左推导再现E TEE TEFTET FT idTEF idid
11、ETid+TEE+TEid+FTET FTid+idTEF idid+id*FTET*FTid+id*idTE F idid+id*idE Tid+id*id E候选式的确定与回溯候选式的确定与回溯n给定文法ScAdAab|a?句子cad是该文法定义语言的句子SScAdcAda ban产生式(候选式)的选择与回溯(Backtracking)：当要进行关于某个语法变 量的推导时，希望能够根据当前符号确定候选式。如果有几个候选式（右 部）左端第一个符号相同，则分析程序无法根据当前输入符号选择产生式 ，只能试探。无回溯的条件n设A1|2|n是所有的A产生式n如果各个i能推导出的首终结符各不相 同，则
12、可以构造无回溯的分析。4.3.1 FIRST 和 FOLLOW 集n对于(TN) *定义:的首符号集nFIRST()=a|*a，aT *n如果存在A这样的产生式，则需定义FOLLOW(A）n对于AN定义A的后续符号集： nFOLLOW(A)=a|S*Aa，aT 求FIRST( X ) 的算法1) 对xT，FIRST(x)=x ；2) 对XN，取FIRST(X)的初值：a|XaP； XPFIRST(X)=a|XaP； XP3)对XN，重复如下过程，直到所有FIRST集不变若 XYP ，且 YN，则 FIRST(X)= FIRST(X)(FIRST(Y)-) ；若 XY1YnP，且Y1.Yi-1*
13、，则 对k=1到i-1:FIRST(X)= FIRST(X)(FIRST(Yk)-) ；若 Y1.Yn*，则 FIRST(X)=FIRST(X) 。例 表达式文法的语法符号的 FIRST 集FIRST(F)=（,idFIRST(T)=FIRST(F)=（,id FIRST(E)=FIRST(T)=（,id FIRST(E)=+，FIRST(T)=*, FIRST(+)=+, FIRST(*)=*FIRST(（)=（FIRST(）)=）FIRST(id)=idETE ETE E+TE| E+TE| TFT TFT T*FT| T*FT| F(E)|idF(E)|id求FIRST() 的算法n令=
14、 X1Xnn初值nFIRST()= FIRST(X1)-;nk=1;n循环nwhile FIRST(Xk)2. 若a b, 则把fa和gb分在一组；3 . a，b VT，若a b，则从fa至gb画一条弧；若a b，则从gb至fa画一条弧;4 .若图中无环，则存在优先函数，f(a)和g(b)等于从fa 和gb出发的最长路径。.gidfidf*g*g+f+f$g$算符优先分析法小结n优点n简单、效率高n能够处理部分二义性文法n缺点n文法书写限制大n占用内存空间大n不规范、存在查不到的语法错误n1、习题:给出布尔表达式的文法，构造其 算符优先关系表 nbexpr bexpr OR bexprnbexpr bexpr AND bexprnbexpr NOT bexprnbexpr ( bexpr )nbexpr TRUEnbexpr FALSEn算符优先分析法存在的问题n强调算符之间的优先关系的唯一性， 这
