哈工大编译原理4-5.ppt

《哈工大编译原理4-5.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章语法分析14.5LR分析方法对二义文法的应用任何二义文法都不是LR文法某些二义文法对语言的说明和实现非常有用，如描述表达式的文法：E→E＋E

2、E*E

3、(E)

4、id规定优先级和结合率无二义文法：E→E+T

5、TT→T*F

6、FF→(E)

7、id计算机学院2辛明影例：描述if语句的文法：stmt→ifexprthenstmt

8、ifexprthenstmtelsestmt

9、other规定匹配原则无二义文法stmt→matched_stmt

10、unmatched_stmtmatched_stmt→ifexprthenmatched_stmtel

11、sematched_stmt

12、otherunmatched_stmt→ifexprthenmatched_stmtelseunmatched_stmt

13、ifexprthen_stmt计算机学院3辛明影E´EI0EE+EEE*EE(E)EidE´EI1EE+EEE*EEE(E)EE+EEE*EE(E)EidI2(EidI3idid(+EE+EEE+EEE*EE(E)EidI4EEE*EEE+EEE*E例：E→E＋E

14、E*E

15、(E)

16、idE(E.)I

17、6EE+EEE*EEE+EEE+EEE*EE(E).I9EE*EEE+EEE*EE(E)EidI5I7I8(idI3*E(id*)+计算机学院4辛明影FOLLOW(E’)={$}FOLLOW(E)={$,+,*,)}EE+EI7EE+EEE*E在I7状态，遇+，根据左结合率，应对栈内+归约规定*优先级高于+*、+为左结合率在I7状态，遇*，根据优先级，应将*移入栈内EE*EI8EE+EEE*E在I8状态，遇*，根据左结合率，应对栈内*归约在I8状态，遇+，根据优先级，应

18、对栈内*归约计算机学院5辛明影表4.11文法G4.4的SLR分析表计算机学院6辛明影描述if语句的文法：stmt→ifexprthenstmt

19、ifexprthenstmtelsestmt

20、other悬空else的二义性用I表示ifexprthen，e表示else,a表示other,文法可改为：S’→SS→iSeS

21、iS

22、a计算机学院7辛明影S’SI0SiSeSSiSSaS’SI1SiSeSI2SiSSiSeSSiSSaSaI3SiSeSI4SiSSiSeSI5SiSeSS

23、iSSaSiSeSI6SiaSiaeSia在I4状态遇e，栈内符号为iS，根据最近匹配原则应移入eFollow(S)={$,e}计算机学院8辛明影计算机学院9辛明影LR(k)和LL(k)的比较1.A12LL(k)根据FIRST(i)确定使用哪条产生式；而LR(k)是在识别出整个后,再往后看k个符号,然后确定使用哪条产生式。wAwA计算机学院10辛明影LL(k)文法都是LR(k)文法。2.都能用形式化方法实现；3.非LR结构例：L={wwRw{a,b}*}G[S]:SaSabSb4.LR(k)分

24、析用手工构造是不可能的。类Pascal语言的LR(1)分析表，估计要数千个状态；由于有软件工具，LR分析受到广泛重视。计算机学院11辛明影4.5分析器的生成器Yacc一.用生成器Yacc构造翻译器的过程Yacc编译器yacc源程序translate.yy.tab.cC编译器y.tab.ca.outa.out源程序输出计算机学院12辛明影二.Yacc源程序有三部分组成            声明            ％％            翻译规则            ％％C写的支持例程三.例4.21台式计算器G[E]:

25、EE+TTTT*FFF(E)digit读入一个表达式，计算它的值并输出。计算机学院13辛明影%{#include%}%tokendigit%%line:expr´´{printf(“%d”,$1);};expr:expr´+´term{$$=$1+$3;}:term;计算机学院14辛明影term:term´*´facter{$$=$1*$3;}:facter;facter:´(´expr´)´{$$=$2;}:digit;%%yylex(){intc;c=getchar();if(isdigit(

26、c){yylval=c-´0´;returndigit;}returnc;}计算机学院15辛明影声明部分有任选的两节。第一节处于分界符%{和%}之间，它是一些普通的C的声明；第二节是文法记号的声明。翻译规则部分每条翻译规