语法分析哈工大王宏志

《语法分析哈工大王宏志》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、语法分析回顾一个语句的翻译P483附录：Pascal子集的词法和语法第四章语法分析1语法分析方法递归子程序法自顶向下预测分析法(LL（1）)算符优先分析法自底向上LR(0)、SLR(1)[LR(1)、LALR]TopDownBottomUp文法产生语言自动机识别语言从根开始，逐步为某语句构造一棵语法树相反，将一句子归约为开始符号问题：解决确定性问题！假定文法是压缩的：即删除了单位产生式和无用产生式。4.1语法分析的功能检查由扫描器输出的单词符号序列是否符合该语言的文法——句子分析器的输入：Token序列分析器的输出分析树出错处理:定位、续编译分析方法自顶向下（递归下降、预测分析)自底向上

2、（算符优先、LR分析器）4.2自上而下分析面临的问题与CFG的改造一、自上而下的分析从文法的开始符号出发，寻求所给的输入符号串的一个最左推导。从树根S开始，构造所给输入符号串的语法树例：G为：S→xAyA→**

3、*，输入串：x**ySxAyx**ySxAy**二、存在问题——回溯SxAyx*ySxAy*SxAy**x**ySxAyx**y匹配成功x**y发现不匹配,需要回退输入串x**yS→xAyA→**

4、*存在回溯的原因文法中每个非终结符A的产生式右部称为A的候选式，如果有多个候选式左端第一个符号相同，则语法分析程序无法根据当前输入符号选择产生式，只能试探。二、存在问题——

5、左递归问题文法S→Say

6、*与它的句子*ayay*ayayS*不对！SSaySayaySayayay……Sayay……ayay一个无限循环！二、重要问题——左递归问题例CFG:简单算术表达式的文法（语法）E→E+T

7、E-T

8、TT→T*F

9、T/F

10、FF→(E)

11、idＶN＝{E,T,F,P,FUN,L｝ＶT＝{id,+,-,*,/,(,)｝Ｓ＝E三、重要概念回顾推导:αＡβαγβ(依据：Ａ→γ)最左(Left-most)推导——最左分析左句型最左推导对应最右归约最右(Right-most)推导——最右分析规范推导、规范句型（右句型）最右推导对应最左归约（规范归约）二义性(先天二义

12、性语言、二义性文法)四、消除二义性例：简单算术表达式的文法二义性文法E→E+E

13、E-E

14、E*E

15、E/E

16、(E)

17、id非二义性文法E→E+T

18、E-T

19、TT→T*F

20、T/F

21、FF→(E)

22、id改造方法：使文法含有更多的信息，引入语法变量四、消除二义性再例：If语句S→ifEthenSS→ifEthenSelseSS→other设执行下列语句前b=0,Ifa≠0thenifa>0thenb=1elseb=-1当a=1时,b=1;当a=-1时，b=-1Ifa≠0thenifa>0thenb=1elseb=-1当a=1时,b=1;当a=-1时，b=0一个句子有两棵不同的语法树SSEESSIfa≠0

23、thenifa>0thenb=1elseb=-1SSEESSIfa≠0thenifa>0thenb=1elseb=-1四、消除二义性P174重写文法：引入新的语法变量S→U

24、MU→ifEthenSU→ifEthenMelseUM→ifEthenMelseM

25、other每个else与前面最近的没有配对的then配对，即：出现在then和else之间的语句必须是配对的按照改造后的文法构造的语法树SUSMEEMMIfa≠0thenifa>0thenb=1elseb=-1M→ifEthenMelseM

26、other五、消除左递归无法根据左递归文法进行自顶向下的分析Aa1a2……ai……an直接左递

27、归AAα当前变量输入指针(栈顶、最左变量)间接左递归A+Aα左递归的消除方法将A→Aα

28、β替换为A→βA′和A′→αA′｜ε例：表达式文法直接左递归的消除E→E+T｜TT→T*F｜FF→(E)｜idE→TE’E’→+TE’

29、εT→FT’T’→*FT’｜εF→(E)｜id例：间接左递归的消除S→Ac

30、cA→Bb

31、bB→Sa

32、a将B的定义代入A产生式得：A→Sab

33、ab

34、b将A的定义代入S产生式得:S→Sabc

35、abc

36、bc

37、c消除直接左递归：S→abcS’

38、bcS’

39、cS’S’→abcS’

40、ε删除“多余的”产生式：A→Sab

41、ab

42、b和B→Sa

43、a结果：S→abcS’

44、bcS’

45、cS’

46、S’→abcS’

47、ε消除左递归的一般方法用产生式组Aβ1B

48、β2B

49、…

50、βnBBα1B

51、α2B

52、…

53、αnB

54、ε替换产生式组A→Aα1

55、Aα2

56、…

57、Aαn

58、β1

59、β2

60、…

61、βm其中：B为新变量，相当于A’消除左递归的算法见P117的算法4.1为非终结符编号，再采用代入法将间接左递归变为直接左递归，消除直接左递归六、解决回溯问题－提取左因子例：if语句的原始文法S→ifEthenS

62、ifEthenSelseS

63、other影响分析:遇