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

第1章引言第2章词汇分析第3章上下文无关语法和分析第4章自上而下语法分析第5章自下而上语法分析第6章语义分析第7章运行时环境第8章代码生成第2、3章语法分析使用词汇分析程序输出的单词序列作为输入来分析源程序的语法结构，并确定它是否是相应编程语言中的合法程序。通常，我们将语法分析的结果表示为语法树或语法树。4，4.1分析树和抽象语法树4.2自顶向下语法分析算法概述4.3递归下降分析4.3LL(1)分析，第4章自顶向下语法分析，5，4.1分析树和抽象语法树，一个句子的每个派生过程对应一个分析树，分析树的定义：对应语法的分析树G=(VT，VN，P，S)是一个标记树：(1)每个节点都标记有终止符，非终止符或；(2)根节点用起始符号S标记；(3)每个叶节点用终止符或标记；(4)每个非叶节点标记一个非终点；(5)每一步被直接推导为对应于一个子树：如果分析树中标记为AVN的节点具有标记为X1，X2的N个子节点，Xn(可以是终端或非终端)，语法G具有相应的生成公式A X1X2，xnP；嘿。嘿。7，expopexpnumberexppnumberexpnublexpnublexpnumbernumbernumbernumbernumbernumbernumbernumbernumbernumbernumber，简单整数算术表达式语法：expexp exp |(exp)| numberop|-| *，符号字符串3的最左侧派生4 :8，exp，exp，op，exp，number，Number，1，2，3，4，34分析树。9，expexpexpopnumberexppnumbernnumber，简单整数算术表达式语法：expexp exp |(exp)| numberop|-| *，最右边的派生34，10、exp、exp、OP、EXP、NUMBER、NUMBER、1、2、3、4、34和11的分析树对于显示程序的每个语法单元或程序的字序列非常有帮助，但是分析树包含的信息比编译和生成可执行代码所需的信息多。因此，语法分析程序倾向于生成抽象语法树，这是包含在分析树中的信息的浓缩，并且是源代码单词序列的抽象表示。它包含了进一步分析所需的所有信息。而且比分析树更有效。注意：可以指定对应于每个语法单元的抽象语法树的结构，并且没有标准，但是可以参考现有编译器的实践。嘿。12，简单整数算术表达式语法：expexp exp |(exp)| number op|-| *，简单算术表达式的相应抽象语法树结构，op，l _ operator，r _ operator，13，14，typedefenum 加号，减号，times opkind键入defense um Opkind，ConstKind ExpKindtypedefstructstreenode ExPKindkind；OpKindopstructstreenode*lchild，*rchild。intval StreeNodeTypedefStreeNode *语法树；15，4.1分析树和抽象语法树4.2自顶向下的语法分析算法概述4.3递归下降分析4.3LL(1)分析，第4章自顶向下的语法分析，16，自顶向下的语法分析算法：从语法的开始符号开始，反复使用语法的生成规则，试图找到与输入符号串匹配的派生。根据语法树的构造过程，从语法的开始符号开始，将其作为语法树的根，试图逐步向下构建语法树，语法树的叶节点是输入符号串；4.2自顶向下语法分析算法概述，17，自顶向下语法分析算法：已知语法。对于任何输入字符串W，如果可以从语法的起始符号S开始为W构造最左边的派生，则W是一个合法的句子，即WL (G)，否则W有语法错误。从S开始，如果所有可能的最左边的推导序列都不能推导出W，那么W就有语法错误。该算法试图从上到下为W的分析结果建立一个语法树。如果输入字符串w=cabd是由语法定义的句子：格：S AAS CADA AA AB？使用自上而下的语法分析方法：19，cadcabd，cadcadcadcad，尝试从语法开始符号s开始为w=cabd构造最左边的派生，scarcabd，success，20，自顶向下的语法分析方法：试图从语法开始符号s开始为输入符号串构造最左边的派生；构造最左边的派生的过程是选择生产公式和匹配符号串的过程。有时需要反复扫描词汇分析输出的单词序列。21，4.1递归下降语法分析，4.1.1递归下降分析的基本方法4.1.2语法规则使用EBNF符号4.1.3其他应注意的问题，递归下降分析是一种自顶向下的语法分析方法，其中执行一组递归函数来处理输入字符串。对于语法的每个非终结点A，根据其相应的生成公式(即语法规则)为其编写一个函数(子程序)，以识别由非终结点表示的语法类别。4.1.1递归下降分析的基本方法。23，例4-2:语法g: s cada ab，识别输入字符串w=cabd是否是语法定义的句子？识别S的递归下降函数的错误代码：24，voidmatch(预期通话时间)； if token=ExpectedTokenToken=GetToken()；elseerror。，cabd，变量令牌存储当前扫描的下一个单词，25，void match(c)；(a)；匹配(d)；，作废(void)匹配(a)；匹配(b)；此外，很难确定输入字符串w=cabd是否是由语法G: S CADA AA AB定义的句子。编写识别S的递归下降函数的伪代码。27，识别S的递归下降函数的伪代码：a1()；/记住当前令牌位置匹配(d)；如果(错误)，则 A2()；匹配(d)；，作废1(作废)匹配(a)；作废2(作废)匹配(a)；匹配(b)；如果语法分析使用递归下降分析程序，为了避免反复扫描词法分析输出的单词序列(以提高效率)，语法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表达式如下：ScAdAab，32，识别s的递归下降函数的伪代码：s cada a b，void(void) match(c)；(a)；匹配(d)；，作废(void)匹配(a)；if token=bthenmatch(b)；我们没有重复扫描从词法分析输出的单词序列，我们写了伪代码来识别if-STMT的递归下降函数，例如4-4:一个简化的if语法规则：if-stmt IF (EXP)语句| IF (EXP)语句。首先，给出了if语法规则的EBNF表达式：if-stmt if (exp)语句else语句识别if-stmt递归下降函数的伪代码如下：35，violif stmt(void) match(if)；匹配()；exp()；match()；语句()；if token=else then match(else)；语句()；、36，repetition:simple integer算术表达式语法：expexp padopterm | term addop|-termterm mulop factor | factor mulop * factor (exp)| number，编写伪代码来标识表达式exp的递归下降函数。37，现在考虑BNF的简单算术表达式语法中的exp:expexppadopterm |术语。如果我们试图编写一个exp函数，首先要做的是调用exp本身，这将导致一个无限递归循环。由于exp和term可以以同一个单词(一个数字或一个左括号)开头，如果您想测试使用哪个选项(expexp padopterm或expterm)，就会出现问题。这个问题的解决方法是用EBNF规则：EBNF用表示重复：和，一般的重复规则： | (左递归)和 a | (右递归)，表示重复n次(n=1)的内容。当编写递归下降程序时，用花括号表示的重复部分可以被翻译成循环码。39，将花括号指示的重复部分附加码翻译成循环码。对应于语法类别exp的函数的定义如下：上述产生规则exp exppadopterm |术语被表示为exp术语 addopterm 。40，violeexp(void) term()；whiletoken=ortoken=-match(令牌)；术语()；一个简单的整数算术表达式语法：expexpadopterm | term addop|-term mulop factor | factor mulop * 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 选项。这个问题需要计算第一组和。例如，SAb|cASa可以将其转换为SSAB | C，然后转换为SC AB，45岁。在分析程序中安排动作：例如，(1)保持操作的组合，(2)构造相应的语法树节点。46，以EBNF语法为代表的微小语言的语法。用递归下降分析算法编写TINY语言的语法分析程序？47、语法分析的基本步骤，根据语言的语法描述形式定义各种基本语法结构的抽象语法树形式；选择适当的语法分析算法；生成句子语法分析的结果(抽象语法树或错误报告)。48，语句序列stmt-sequencestatement ；语句，TINY语言的每个基本语法类别的抽象语法树结构如下：49，if-stmtifexptheinstmt-sequenceelse stmt-sequenceend，if语句的抽象语法树结构：50，Repeat语句Repeat-sttrepetestmt-sequenceuntilexp，51，assign语句assign _ stmtidentifier :=exp，52，写声明write_stmtwriteexp，读声明read_stmtreadidentifier,53岁。53，运算符表达式，54，typedefenum stmtk，expk nodkink，typedefenum IfK，RepeatK，AssignK，ReadK，WriteK StmtKind，typedefenum OpK，ConstK，IdK ExpKind，typedefenumVoid，整数，布尔值 ExpType，#defineMAXCHILDREN3，55，TypeDefStructTreeNode StructTreeNode * childMAXCHILDS；structtreeNode *同级；intlinenoNodeKindnodekindunion StmtKindstmtExpKindexp亲切；union TokenTypeopintvalchar *名称； attrExpTypetype。 TreeNode语言TINY的递归下降分析函数如下：PARSE。一个TINY语言程序readx，它输出输入的阶乘；ifx 0 then fact :=1；repeat fact :=fact * x；x :=x-1直到x=0；WriteFactEnd， 57， 58，一个输出其输入阶乘的TINY语言程序readx。ifx 0 then fact :=1；repeat fact :=fact * x；x :=x-1直到x=0；Writefactend。59岁。60，递归下降语法分析课程设计(共20分):细节：语法分析课程设计。医生。61，第4章自上而下的语法分析，4.1递归下降分析，4.2学习分析，家庭作业。62，4.2LL(1)分析，4.2.1LL(1)基本分析方法4.2.2LL(1)分析和算法4.2.3消除左递归和提取，63，4.2.1LL(1)基本分析方法，LL(1)分析方法是一种自上而下的语法分析方法：第一个“l”是指从左到右处理输入。第二个“L”表示它为输入字符串找到了最左边的派生。括号中的数字1表示它在输入字符串中只使用一个符号来预测分析的方向。例如，假设有一个简单的语法生成一串括号：s (s) s | 确定输入字符串()