编译原理实践 5.给定语法的语法分析程序构造.

Presentation on theme: "编译原理实践 5.给定语法的语法分析程序构造."— Presentation transcript:

1 编译原理实践 5.给定语法的语法分析程序构造

2 上一次课的结论 从语法图判断两条限制规则： 找出图中每一个分支点，考察每一个分支点的分 支的头符号是否相异
找出图中每一个透明结构（无需读入一个符号就 可以贯通），考察每一个透明结构的头符号集合 和其跟随符号集合是否相异。

3 给定语法的语法分析程序构造 语法分析程序的主程序 语法图到语法分析程序的转换法则 构造实例

4 1.语法分析程序的主程序 假如一个文法满足两条语法限制规则，则其语法分析程 序可以非常系统化地从这个图系统推演、构造出来
每一个语法图对应的一个个程序过程要置于一个主程序 环境里 主程序结构(pascal语言，下同)： program Parser(input,output); var ch:char; begin read(ch); S end.

5 2.从语法图到语法分析程序的转换法则B1 if ch in L1 then P(S1) else if ch in L2 then P(S2) else … if ch in Ln then P(Sn) else error 其中Li表示集合first(Si)

6 从语法图到语法分析程序的转换法则B1a x1 S1 x2 S2 … xn Sn
if ch=“x1” then begin read(ch);P(S1) end else if ch=“x2” then begin read(ch);P(S2) end else … if ch=“xn” then begin read(ch);P(Sn) end else error;

7 从语法图到语法分析程序的转换法则B2 S1 S2 Sn begin P(S1);P(S2);…;P(Sn);end

8 从语法图到语法分析程序的转换法则B3 while ch in L do P(S)

9 从语法图到语法分析程序的转换法则B3a while ch=“x” do begin read(ch); P(S); end;

10 从语法图到语法分析程序的转换法则B4 S if ch in L then P(S)

11 从语法图到语法分析程序的转换法则B5: 矩形图表示的非终结符号可以翻译成调用相应的过程 用圆表示的终结符号x可以翻译成一条读入语句： If ch=“x” then read(ch) else error

12 3. 构造实例 画出语法图 证明符合两条限制规则，是确定的图系统 采用自顶向下、逐步求精方法系统地写出语法分 析程序

13 例 文法： A=“x”|”(”B”)” B=AC C={“+”A} 第一步：画出语法图： A ( A ) A + x

14 第二步：判别符合两条限制规则 第三步：根据转换法则，采用自顶向下、逐步求精 的方法系统地写出语法分析程序 写出主程序 写出过程A 逐步求精 归纳、优化

15 program Parser(input,output); var ch:char; procedure error; begin writeln('error!');halt; end; procedure A; if ch='(' then read(ch);A; while ch='+' do begin read(ch);A;end; if ch=')' then read(ch) else error; end else if ch='x' then read(ch) else error; read(ch);A;if ord(ch)<>13 then error else writeln('good!'); end.

16 说明1 该方法也称作“递归下降分析法（递归子程序 法）”，适合分析比较简单的文法，易于手工 实现，这是它的优点。
但每个分析子程序都与文法中的每条规则密切 相关。当规则不同时，就需要编制不同的程序 来实现分析，所以递归下降分析方法不适合编 制通用的语法分析程序。

17 “递归下降分析法”的缺点： 尽管这样，它还是许多高级语言，如Pascal,C等编 译系统常常采用的语法分析方法。
对文法要求高，必须满足LL(1)文法，当然在某些语 言中个别产生式的推导不满足LL(1)而满足LL(2)时， 也可以采用多向前扫描一个符号的办法； 它的另一个缺点是由于递归调用多，所以速度慢占用 空间多 尽管这样，它还是许多高级语言，如Pascal,C等编 译系统常常采用的语法分析方法。

18 说明2 上述语法分析程序中读入的最小单元是ch（字符）， 在实际的语法分析程序中，读入的最小单元是sym （token）。
要注意子程序之间的接口，在程序编制时进入某个 非终结符的分析程序时其所要分析的语法成分的第 一个符号已经读入ch/sym中。在分析子程序的出 口前，一定要读取下一个符号到ch/sym中。