资源描述：
《编译原理第4章 语法分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第四章语法分析9/18/20211编译原理第四章语法分析第四章语法分析§1、概述一.语法分析器的功能9/18/20212编译原理第四章语法分析语法分析：在词法分析的基础上，根据语法规则，从单词符号串中识别出各种语法成分，同时进行语法检查，检查各种语法成分在语法结构上的正确性。9/18/20213编译原理第四章语法分析二.语法分析方法自上向下分析法：从文法的开始符号出发，以给定的符号串为目标，根据文法规则，正向推导出给定符号串的一种方法。自下向上分析法：从给定的符号串出发，反复使用文法中有关产生式的左部去替换当前符号串中的相应子串，逐步归约成文法开始符号的一种方法。自上向下分析法：递归下降、
2、LL(1)分析法自下向上分析法：算符优先、LR分析法9/18/20214编译原理第四章语法分析§2、自上而下分析方法 一、带回溯的自上而下分析法基本思想：对任何输入串，试图用一切可能的方法，从文法的开始符号出发，采用最左推导，自上而下为输入串建立一棵语法树。例如：设有文法：S→xAyA→**
3、*输入串：x*y看匹配过程SAxySAxySAxy***9/18/20215编译原理第四章语法分析二、存在的问题以及解决的方法1.左递归：当文法为左递归时，会使分析程序进入无限循环之中。若文法中有非终结符P=>Pα(文法左递归)输入某输入串w=a1a2…an就有P=>Pα=>Pαα…如此循环，不会终止
4、+9/18/20216编译原理第四章语法分析①消除直接左递归方法一：引进新的非终结符，改写文法规则式。P→Pα
5、βP→βP′P′→αP′
6、ε（将文法中的左递归结构变成等价的右递归结构）例如：算术表达式文法左递归E→E+T
7、TE→TE′T→T*F
8、FE′→+TE′
9、εF→(E)
10、iT→FT′T′→*FT′
11、εF→(E)
12、i9/18/20217编译原理第四章语法分析一般情况：有多个直接左递归：P→Pα1
13、Pα2
14、…
15、Pαm
16、β1
17、β2
18、…
19、βn其中，每个α都不等于ε，而每个β都不以P开头，则上式改写为P→β1P′
20、β2P′
21、…
22、βnP′P′→α1P′
23、α2P′
24、…
25、αmP′
26、ε例如：A→Ac
27、
28、Aad
29、bd
30、e改写为：A→bdA′
31、eA′A′→cA′
32、adA′
33、ε9/18/20218编译原理第四章语法分析方法二：采用扩充的BNF表示法改写文法规则式用花括号{α}表示符号串α出现0次或多次。即α*标识符：I→l{l
34、d}或I→l{l
35、d}7即将A→Aα
36、β改写成A→β{α}中括号[α]表示α是可供选择的符号串。<条件语句>→ifBthen<语句>[else<语句>]使用圆括号，可以在规则中提因子。U→XY
37、XW
38、…
39、XZU→X(Y
40、W
41、…
42、Z)例如：算术表达式文法左递归E→E+T
43、TE→T{+T}T→T*F
44、FT→F{*F}F→(E)
45、iF→(E)
46、i9/18/20219编译原理第
47、四章语法分析②消除所有左递归的算法(1)把文法G的所有非终结符按任一顺序排列成P1,P2,…Pn;(2)执行循环语句：fori:=1tondo将规则Pi→Pjγ改写；{改写方法：Pj→δ1
48、δ2
49、…δn则Pi→δ1γ
50、δ2γ
51、…δnγ}消除关于Pi的直接左递归end(3)化简由(2)得到的文法。9/18/202110编译原理第四章语法分析例如：消除下面文法的左递归。文法：S→Qc
52、cQ→Rb
53、bR→Sa
54、a(1)排列：R,Q,S(2)对R：没有直接左递归，不执行内循环对Q：将R代入Q变为Q→Sab
55、ab
56、b，也没有直接左递归，不执行内循环。对S：将Q代入S变为S→Sabc
57、abc
58、bc
59、c
60、消除S的直接左递归，得下面文法：S→abcS′
61、bcS′
62、cS′S′→abcS′
63、ε(3)S→abcS′
64、bcS′
65、cS′Q→Sab
66、ab
67、bS′→abcS′
68、εR→Sa
69、a若排列方法不同，得到的文法也可能不同，但等价9/18/202111编译原理第四章语法分析2.回溯问题问题：如果对同一个非终结符号，有若干个产生式右部A→α1
70、α2
71、…
72、αn,选择哪一个产生式匹配呢？匹配不好就产生回溯。回溯使语法分析器的动作不确定。分析：要消除回溯，必须使文法具有一定的特性。例如：S→cAdA→ad
73、a输入符号w=cad分析：要求各规则式右部α1
74、α2
75、…
76、αn所推出的终结首符号的集合两两不相交。定义：
77、符号串αi终结首符号的集合：FIRST(αi)={α
78、αi=>a…,α∈VT}*9/18/202112编译原理第四章语法分析条件一：对文法中每一个非终结符A，如有规则：A→α1
79、α2
80、…
81、αn则下面条件成立FIRST(αi)∩FIRST(αj)=Ф(i≠j)上例中：FIRST(ab)∩FIRST(a)={a}∩{a}={a}≠Ф改写方法：提取公共左因子A→δβ1
82、δβ2
83、…
84、δβn
85、γ1
86、γ2
87、…γm则：A→δA′
88、γ1
