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

program Parser(input,output); var ch:char; procedure error; begin writeln(error!);halt; end; procedure A; begin if ch=( then begin 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; end; begin read(ch);A;if ord(ch)13 then error else writeln(good!); end. “递归下降分析法”的缺点：对文法要求高，必须满足LL(1)文法，当然在某些语言中个别产生式的推导不满足LL(1)而满足LL(2)时，也可以采用多向前扫描一个符号的办法；它的另一个缺点是由于递归调用多，所以速度慢占用空间多，尽管这样，它还是许多高级语言，如Pascal,C等编译系统常常采用的语法分析方法。 说明2 上述语法分析程序中读入的最小单元是ch（字符），在实际的语法分析程序中，读入的最小单元是sym（token）。 要注意子程序之间的接口，在程序编制时进入某个非终结符的分析程序时其所要分析的语法成分的第一个符号已经读入ch/sym中。在分析子程序的出口前，一定要读取下一个符号到ch/sym中。 编译原理实践--给定语法的语法分析程序构造 从语法图判断两条限制规则： 找出图中每一个分支点，考察每一个分支点的分支的头符号是否相异 找出图中每一个透明结构（无需读入一个符号就可以贯通），考察每一个透明结构的头符号集合和其跟随符号集合是否相异。 给定语法的语法分析程序构造 语法分析程序的主程序 语法图到语法分析程序的转换法则 构造实例 1.语法分析程序的主程序 假如一个文法满足两条语法限制规则，则其语法分析程序可以非常系统化地从这个图系统推演、构造出来 每一个语法图对应的一个个程序过程要置于一个主程序环境里 主程序结构： program Parser(input,output); var ch:char; begin read(ch); S end. 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) 从语法图到语法分析程序的转换法则B1a 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; x1 S1 x2 S2 xn Sn … 从语法图到语法分析程序的转换法则B2 begin P(S1);P(S2);…;P(Sn);end S1 S2 Sn 从语法图到语法分析程序的转换法则B3 while ch in L do P(S) 从语法图到语法分析程序的转换法则B3a while ch=“x” do begin read(ch); P(S); end; 从语法图到语法分析程序的转换法则B4 if ch in L then P(S) S 从语法图到语法分析程序的转换法则B5: 矩形图表示的非终结符号可以翻译成调用相应的过程 用圆表示的终结符号x可以翻译成一条读入语句： If ch=“x” then read(ch) else error 3. 构造实例 画出语法图 证明符合两条限制规则，是确定的图系统 采用自顶向下、逐步求精方法系统地写出语法分析程序 例1：简单的例子 文法： A=“x”|”(”B”)” B=AC C={“+”A} 第一步：画出语法图： ( A ) A + x A 第二步：判别符合两条限制规则 第三步：根据转换法则，采用自顶向下、逐步求精的方法系统地写出语法分析程序 写出主程序 写出过程A 逐步求精 归纳、优化 例2：稍复杂一点的例子 编程识别由下列文法所定义的表达式的递归下降语法分析器。 E-E+T | E-T | T T-T*F | T/F |F F-(E) | i 输入：含一个表达式的文本文件。 输出：分析成功或不成功信息。 存在左递归，用直接改写法消除左递归，得到如下： E-TE’ E’ -+TE’|?TE’|ε T-FT’ T’