编译4语法分析—自上而下分析解读.ppt

* * 主程序: PROGRAM PARSER; BEGIN ADVANCE; E; IF SYM ’#’ THEN ERROR END; * * 在元符号“→”和“|”的基础上，扩充几个元语言符号： 1. 用花括号{?}表示闭包运算?*。 2. 用 {?}n0表示可任意重复0次至n次，。 3. 用方括号[?]表示{?}10 ，即表示?的出现可有可无(等价于?|?)。 引入上述元符号的文法亦称扩充的巴科斯范式。 文法的另一种表示法和转换图(略) * * 例如，通常的“实数”可定义为： decimal→[sign]integer.{digit}[exponent] exponent→E[sign]integer integer→digit{digit} sign→ + | - 用扩充的巴科斯范式来描述语法，直观易懂，便于表示左递归消去和因子提取。 * * 例4.5 文法 E→T | E+T T→F | T*F F→i | (E) 可表示成 E→T{+T} T→F{*F} F→i | (E) (4.6) * * 可以用语法图来表示语言的文法。 T + E T F * T F i ) F E ( * * 可构造一组递归下降分析程序： PROCEDURE E； BEGIN T； WHILE SYM=‘+’ DO BEGIN ADVANCE； T END END； PROCEDURE T； BEGIN F； WHILE SYM=‘*’ DO BEGIN ADVANCE； F END END； * * 4.5 预测分析程序 一、预测分析程序工作原理 预测分析程序或LL(1)分析法： 总控程序 分析表 M[A，a]矩阵，A ? VN ，a ? VT 是终结符或‘＃’， 分析栈 STACK 用于存放文法符号 * * 总控程序 分析表 X ? # 输入串 分析栈 STACK a1a2...ai…# 预测分析程序的工作图 # S a1a2...ai…# 分析开始时： * * 总控程序根据现行栈顶符号X和当前输入符号a，执行下列三种动作之一: 1. 若X＝a＝‘＃’，则宣布分析成功，停止分析。 2. 若X＝a ?‘＃’，则把X从STACK栈顶弹出，让a指向下一个输入符号。 匹配成功 * * 3. 若X是一个非终结符，则查看分析表M 若M[X，a]中存放着关于X的一个产生式，把X弹出栈顶，把产生式的右部符号串按反序入栈(若右部符号为?，则什么也不做)。在把产生式的右部符号推进栈的同时应做这个产生式相应的语义动作。 若M[X，a]中存放着“出错标志”，则调用出错诊察程序ERROR。 推导 * * 例4.6 对于文法G(E) E→TE? E?→+TE? | ? T→FT? T?→*FT? | ? F→(E) | i 输入串为i1*i2+i3，利用分析表进行预测分析： * 编译原理(第三版) 陈火旺等编著 （2016年9月-10月） 主讲：朱世松 计算机学院 * * 第四章 语法分析—自上而下分析 本章主要介绍语法分析的处理 要进行语法分析，必须对语言的语法结构进行描述。 采用正规式和有限自动机可以描述和识别语言的单词符号； 用上下文无关文法来描述语法规则。 * * 上下文无关文法的定义： 一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中 VT：终结符集合(非空) VN：非终结符集合(非空)，且VT ? VN=? S：文法的开始符号，S?VN P：产生式集合(有限)，每个产生式形式为 P??， P?VN， ? ? (VT ? VN)* 开始符S至少必须在某个产生式的左部出现一次。 * * 4.1 语法分析器的功能 语法分析的任务是分析一个文法的句子结构。 语法分析器的功能：按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子。 * * 源程序 单词符号 取下一单词 ... 语法分 析树 词法分 析器 语法分 析器 符号表 编译程序 后续部分 * * 语法分析的方法： 自下而上分析法(Bottom-up) 自上而下分析法(Top-down) 基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找匹配的推导。 * * 4.2 自上而下分析面临的问题 自上而下就是从文法的开始符号出发，向下推导，推出句子。 带“回溯”的 不带回溯的递归