编译原理课程设计之第四章-自上而下的语法分析PPT课件.ppt

1 课程内容第一章概论第二章词法分析第三章上下文无关文法及分析第四章自上而下的语法分析第五章自下而上的语法分析第六章语义分析第七章运行时环境第八章代码生成 2 3 语法分析以词法分析程序输出的单词序列为输入 分析源程序的语法结构 判断它是否为相应程序设计语言的合法程序 通常我们将语法分析的结果表示为分析树 parsetree 或语法树 syntaxtree 4 4 1分析树与抽象语法树4 2自上而下的语法分析算法概述4 3递归下降分析4 3LL 1 分析 第四章自上而下的语法分析 5 4 1分析树与抽象语法树 句子的每一个推导过程都对应一个分析树 分析树的定义 文法G VT VN P S 对应的分析树是一个作了标记的树 1 每个节点都用终结符 非终结符或 标出 2 根结点用开始符号S标出 3 每个叶结点都用终结符或 标出 6 4 每个非叶结点都用非终结点标出 5 每一步直接推导对应一个子树 如果分析树中标记为A VN的节点有n个标记为X1 X2 Xn的孩子 可以是终结符也可以是非终结符 则文法G中有对应的产生式A X1X2 Xn P 7 exp expopexp numberopexp number exp number number 简单整型算术表达式文法 exp expopexp exp numberop 符号串3 4的最左推导 8 exp exp op exp number number 1 2 3 4 3 4的分析树 9 exp expopexpexpopnumberexp numbernumber number 简单整型算术表达式文法 exp expopexp exp numberop 3 4的最右推导 10 exp exp op exp number number 1 2 3 4 3 4的分析树 11 分析树对于显示程序的各语法单位或程序的单词序列很有帮助 但是相比纯粹为编译生成可执行代码所需的信息而言 分析树却包括了更多的信息 所以语法分析程序更趋向于生成抽象语法树 抽象语法树是分析树中所含信息的浓缩 这种树是源代码单词序列的抽象表示 它却包含了进一步分析所需的所有信息 而且比分析树效率更高 注 各语法单位对应的抽象语法树的结构可以规定 没有标准 但可以参考现有编译器的做法 12 简单整型算术表达式文法 exp expopexp exp numberop 简单算术表达式的对应的抽象语法树结构 op l operand r operand 13 14 Typedefenum Plus Minus Times OpKind Typedefenum OpKind ConstKind ExpKind Typedefstructstreenode ExpKindkind OpKindop structstreenode lchild rchild intval StreeNodeTypedefStreeNode SyntaxTree 15 4 1分析树与抽象语法树4 2自上而下的语法分析算法概述4 3递归下降分析4 3LL 1 分析 第四章自上而下的语法分析 16 自上而下的语法分析算法 从文法的开始符号出发 反复使用文法的产生式规则 试图寻找与输入符号串匹配的推导 从语法树的构造过程来看 是从文法的开始符号出发 将它做为语法树的根 试图向下逐步建立语法树 语法树的叶子节点是输入符号串 4 2自上而下的语法分析算法概述 17 自上而下的语法分析算法 已知文法G S 对任意输入串w 若从文法的开始符号S出发 能为w构造一个最左推导 则w是一个合法的句子 即w L G 否则w有语法错误 从S出发 尝试了所有可能的最左推导序列都不能推出w 则说明w有语法错误 该算法试图自上而下为w的分析结果建立一棵语法树 18 例4 1 文法G S aAS cAdA aA ab识别输入串w cabd是否为该文法所定义的句子 运用自上而下的语法分析方法 19 cAd cabd cAd cad 从文法开始符号S出发试图为w cabd构造一个最左推导 S cAd cabd 成功 20 自上而下的语法分析方法 从文法开始符号S出发试图为输入符号串构造一个最左推导 构造最左推导的过程就是选择产生式和匹配符号串的过程 有时需要重复扫描词法分析输出的单词序列 21 4 1递归下降语法分析 4 1 1递归下降分析的基本方法4 1 2文法规则使用EBNF表示法4 1 3其它应注意的问题 22 递归下降分析法是一种自上而下的语法分析方法 在这种方法中 执行一组递归函数来处理输入串 对文法的每一个非终结符A 都根据其相应的产生式 即文法规则 为其编写一个函数 子程序 用来识别该非终结符所表示的语法范畴 4 1 1递归下降分析的基本方法 23 例4 2 文法G S cAdA ab 识别输入串w cabd是否为该文法定义的句子 识别S的递归下降函数的伪代码 24 voidmatch expectedToken iftoken expectedTokentoken getToken elseerror cabd 变量token存储当前扫描的下一个单词 25 voidS void match c A match d voidA void match a match b 26 例4 3 文法G S cAdA aA ab 识别输入串w cabd是否为该文法定义的句子 写出识别S的递归下降函数的伪代码 27 识别S的递归下降函数的伪代码 voidS void match c A1 记住当前的token位置match d if error then A2 match d voidA1 void match a voidA2 void match a match b 28 如果语法分析使用递归下降分析程序 为了避免重复扫描词法分析输出的单词序列 提高效率 需要先将文法G采用EBNF表示法 然后写出递归下降分析程序 29 4 1递归下降语法分析 4 1 1递归下降分析的基本方法4 1 2文法规则使用EBNF表示法4 1 3其它应注意的问题 30 选择的情况重复的情况 4 1 2文法规则使用EBNF表示法 31 选择的情况EBNF使用 表示选择 文法G S cAdA aA ab 的EBNF表示法如下 S cAdA a b 32 识别S的递归下降函数的伪代码 S cAdA a b voidS void match c A match d voidA void match a iftoken bthenmatch b 避免了重复扫描词法分析输出的单词序列 33 例4 4 一个简化了的if文法规则 if stmt if exp statement if exp statementelsestatement 写出识别if stmt的递归下降函数的伪代码 34 首先给出if文法规则的EBNF表示法 if stmt if exp statement elsestatement 识别if stmt的递归下降函数的伪代码如下 35 viodifStmt void match if match exp match statement iftoken elsethen match else statement 36 重复情况 简单整型算术表达式文法 exp expaddopterm termaddop term termmulopfactor factormulop factor exp number 写出识别表达式exp的递归下降函数的伪代码 37 现在考虑BNF中简单算术表达式文法中的exp情况 exp expaddopterm term 如要我们试着将写一个exp函数 则首先应做的是调用exp本身 而这将导致一个无限递归循环 由于exp和term可以以相同的单词开头 一个数或左括号 所以要想测试使用哪个选择 exp expaddopterm或exp term 就会出现问题了 38 解决问题的办法是使用EBNF规则 EBNF使用 表示重复 A 和A 重复的一般规则 A A 左递归 和A A 右递归 表示其中的内容重复n次 n 1 写递归下降程序时可将花括号表示的重复部分翻译成循环代码 39 将花括号表示的重复部分addopterm翻译成循环代码 语法范畴exp对应的函数的定义如下 上述产生式规则exp expaddopterm term用EBNF表示成exp term addopterm 40 viodexp void term whiletoken ortoken match token term 41 简单整型算术表达式文法 exp expaddopterm termaddop term termmulopfactor factormulop factor exp number 写出识别表达式exp的完整的递归下降函数的伪代码 42 4 1递归下降语法分析 4 1 1递归下降分析的基本方法4 1 2文法规则应使用EBNF表示法4 1 3其它应注意的问题 43 4 1 3其它应注意的问题 前面描述的递归下降分析虽然非常强大 但它仍有特殊性 若使用的是一个设计精巧的小型语言 例如TINY 甚至是C 那么对于构造一个完整的分析程序 这些办法是适合的 但还会出现一些问题 44 两个或多个文法规则的选项 例如 A 如果 和 均以非终结符开始 那么就很难决定何时使用A 选项 何时又使用A 选项 这个问题就要求计算 和 的First集合 间接递归的文法 例如 S Ab cA Sa可将其变换为S Sab c 进而变换为 S c ab 45 在分析程序中安排动作 例如 1 保持运算的结合性 2 构造相应的语法树节点 46 EBNF文法表示的tiny语言的语法 doc 用递归下降分析算法写出TINY语言的语法分析程序 47 语法分析的基本步骤 根据语言的语法描述形式 定义各种基本语法结构的抽象语法树形式 选择一种合适的语法分析算法 生成句子语法分析的结果 抽象语法树或错误报告 48 语句序列stmt sequence statement statement TINY语言的各基本语法范畴的抽象语法树结构形式如下 49 if stmt ifexpthenstmt sequence elsestmt sequence end if语句的抽象语法树结构 50 repeat语句repeat stmt repeatstmt sequenceuntilexp 51 assign语句assign stmt identifier exp 52 write语句write stmt writeexp read语句read stmt readidentifier 53 算符表达式 54 typedefenum StmtK ExpK NodeKind typedefenum IfK RepeatK AssignK ReadK WriteK StmtKind typedefenum OpK ConstK IdK ExpKind typedefenum Void Integer Boolean ExpType defineMAXCHILDREN3 55 typedefstructtreeNode structtreeNode child MAXCHILDREN structtreeNode sibling intlineno NodeKindnodekind union StmtKindstmt ExpKindexp kind union TokenTypeop intval char name attr ExpTypetype TreeNode 56 Tiny语言的递归下降分析函数如下 PARSE C 一个输出其输入阶乘的TINY语言程序readx ifx 0thenfact 1 repeatfact fact x x x 1untilx 0 writefactend 57 58 一个输出其输入阶乘的TINY语言程序readx ifx 0thenfact 1 repeatfact fact x x x 1untilx 0 writefactend 59 60 递归下降语法分析课程设计 共20分 详细信息 语法分析课程设计 doc 61 第四章自上而下的语法分析 4 1递归下降分析4 2LL 1 分析 作业 62 4 2LL 1 分析 4 2 1LL 1 分析的基本方法4 2 2LL 1 分析与算法4 2 3消除左递归和提取 63 4 2 1LL 1 分析的基本方法 LL 1 分析方法是一种自上而下的语法分析方法 第1个 L 指的是由左向右地处理输入 第2个 L 指的是它为输入串找出一个最左推导 括号中的数字1意味着它仅使用输入串中的一个符号来预测分析的方向 64 例如 假设有生成成对括号的串的简单文法 S S S 判断输入串 是否是符合该文法规则的句子 LL 1 分析方法如下 输入串 的自上而下分析程序的分析动作 65 S S S S 的最左推导 构造最左推导要解决的问题 每一步推导是针对当前句型中的哪一个非终结符进行推导 用该非终结符的哪一个产生式进行推导 选择产生式 66 LL 1 分析方法如下 通过栈来 记忆 针对当前句型中的哪一个非终结符进行推导 首先将文法的开始符号S入栈 如果栈的顶部是终结符a 则将其与当前输入记号匹配 出栈 如果栈的顶部是非终结符A 则利用A对应的某个文法规则A 将栈顶部的非终结符A 出栈 替换成串 将串 自右至左入栈 67 构造一个终结符和非终结符索引的二维表格M N T 可以表达出用哪一个产生式进行进行下一步推导 其中N是非终结符的集合 T是终结符的集合 即构造一个LL 1 分析表 通过该表格引导用哪一个产生式进行推导 68 M S 表示当前分析栈的栈顶符号为S 而当前词法分析的输入记号为 时 按产生式S S S进行推导 M S 表示当前分析栈的栈顶符号为S 而当前词法分析的输入记号为 时 按产生式S 进行推导 69 分析栈 输入 动作 步骤 注 将句型自右至左入栈 LL 1 分析方法 70 LL 1 分析程序通过将分析栈顶部的非终结符替换成文法规则中该非终结符的一个选择来做出分析 在分析过程中有两个基本动作 如果栈的顶部是终结符a 则将其与当前输入记号匹配 如果栈的顶部是非终结符A 则利用文法规则A 将栈顶部的非终结符A替换成串 保证 自右至左入栈 71 问题 如何构造LL 1 分析表 构造分析表的步骤 求First集合求Follow集合构造LL 1 分析表 72 文法符号X的First 集合 令X为一个文法符号 一个终结符或非终结符 或 则First X 是终结符的集合 此外可能还有 它的定义如下 若X是终结符或 则First X X 73 若X是非终结符 则对于X对应的每个产生式X X1X2 Xn First X 包括First X1 若对于某个i n 所有的集合First X1 First Xi 都包括了 则First X 也包括First Xi 1 若所有集合First X1 First Xn 包括了 则First X 也包括 74 文法符号串的First 集合 设任意串a X1X2 Xn 终结符和非终结符的串 则First a 的定义如下 First a 包括First X1 对于每个i 2 n 如果对于所有的k 1 i 1 First Xk 包括了 则First a 也包括First Xi 如果对于所有的i 1 n First Xi 包括了 则First a 也包括 75 exp expaddopterm 2 exp term 3 addop 4 addop 5 term termmulopfactor 6 term factor 7 mulop 8 factor exp 9 factor number 例4 3 考虑下述简单整型表达式文法 求各非终结符的First 集合 76 First addop First mulop First factor First term First exp number number number 77 1 E TE 2 E TE 3 E 4 T FT 5 T FT 6 T 7 F E 8 F a 先求其First 集包含 的非终结符 例4 4 考虑下述文法 求各非终结符的First 集合 文法G E E T 78 First E First E First T 从文法的开始符号E 将求First 集的算法过程表示成下列图示 79 求得各非终结符的First集合如下 First E a First E First T a First T First F a 80 定义 给出一个非终结符A 那么集合Follow A 则是由终结符组成 此外可能还有 集合Follow A 的定义如下 Follow集合 1 若A是开始符号 则Follow A 包含 2 若存在产生式B A 则Follow A 包含First 3 若存在产生式B A 且 在First 中 则Follow A 包含Follow B 81 例4 5 考虑下述简单整型表达式文法 求各非终结符的Follow 集合 exp expaddopterm 2 exp term 3 addop 4 addop 5 term termmulopfactor 6 term factor 7 mulop 8 factor exp 9 factor number 82 Follow exp Follow addop Follow term Follow mulop Follow factor number number 83 例2 考虑下述文法 求各非终结符的Follow 集合 先求其First集包含 的非终结符为 E T 1 E TE 2 E TE 3 E 4 T FT 5 T FT 6 T 7 F E 8 F a 文法G E 84 从文法的开始符号E 将求Follow 集的算法过程表示成下列图示 85 86 各非终结符的Follow集合如下 Follow E Follow E Follow T Follow T Follow F 87 构造LL 1 分析表 对于First 中的每个终结符a 都将A 添加到项目M A a 中 置M A a A 即当当前分析栈的栈顶符号为A时 而当前词法分析的输入记号为a时 按产生式A 进行推导 LL 1 分析表的构造方法 为每个非终结符A和它对应的产生式A 重复以下两步骤 88 定义 如果文法G相关的LL 1 分析表的每个项目中至多只有一个产生式 则该文法就是LL 1 文法 3 所有没有定义的元素位置 A a 标上 出错 标志 若 在First 中 则对于Follow A 的每个元素a 或是 都将A 添加到M A a 中 即在此情况下按产生式A 进行推导 89 例4 6 考虑简化了的C声明的文法 declaration typevar listtype int floatvar list identifierlistlist var list 求该文法各非终结符的First 集合和Follow 集合 构造该文法的LL 1 分析表 说明该文法是LL 1 文法 假设有输入串intx y z写出相对应的LL 1 分析程序的动作 90 First declaration int float First type int float First var list identifier First list 所求得的各非终结符的First集合和Follow集合如下 91 Follow declaration Follow type identifier Follow var list Follow list 92 r1 declaration typevar listr2 type intr3 type floatr4 var list identifierlistr5 list var listr6 list 对各产生式进行编号 构造该文法的LL 1 分析表 93 M N T declaration int identifier type var list list float r1 r1 r2 r3 r4 r5 r6 由于文法G相关的LL 1 分析表的每个项目中至多只有一个产生式 故该文法是LL 1 文法 94 输入串intx y z相对应的LL 1 分析程序的分析过程如下表所示 95 96 4 2LL 1 分析 4 2 1LL 1 分析的基本方法4 2 2LL 1 分析与算法4 2 3消除左递归和提取 97 98 4 2 2LL 1 分析与算法 基于表的LL 1 分析算法流程 99 4 2LL 1 分析 4 2 1LL 1 分析的基本方法4 2 2LL 1 分析与算法4 2 3消除左