语法分析的例子.ppt

* 编译原理 * YACC规格说明 用%{和%}括起来的部分是C语言程序的正规说明 说明翻译规则和辅助过程里使用的变量和函数的类型 * 编译原理 * YACC规格说明 形如 左部→候选1|候选2|…|候选n| 的产生式，在YACC规格说明里写成 左部:候选1{语义动作1} |候选2{语义动作2} …… |候选n{语义动作n} ; * 编译原理 * YACC规格说明 E→E+T|T T→T*F|F F→(E)|digit * 编译原理 * LR语法分析器的结构 一个LR分析器实质上是一个带先进后出存储器（栈）的确定有限状态自动机。 * 编译原理 * LR语法分析器分析过程举例 文法G：(1)E ? E+T (2)E ? T(3)T ? T*F (4)T ? F (5)F ? (E) (6)F ? i 状态 ACTION GOTO i + * （ ） # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 * 编译原理 * YACC中的冲突 YACC可以指出移进-归约冲突和归约-归约冲突默认情况下： 移移进-归约冲突中选择移进 归约-归约冲突中选择先出现的规则来归约 优先级升高 * 编译原理 * 语法分析过程 语法分析开始于词法分析阶段，其输入为词法分析输出的token序列，输出为语法树 语法树和源程序中各个语句的语法结构一一对应，并且作为后续语义分析的重要数据结构 词法分析输入的token序列中包括诸如变量、数字、操作符等，对应于产生式中的终结符 在token序列中，各个token按照上下文无关文法的规则连接在一起 语法分析的任务是将token序列中是否采用正确的语法规则分析出来，并且以树形的数据结构表示出来，最后整个源程序将转化为一棵以程序节点为根，非终结符为中间节点，终结符为叶子节点的语法树。 * 编译原理 * 抽象语法树的树形结构 程序 程序头 子程序 代码头 代码体 子程序 函数头 过程声明 函数声明 代码段 变量 常数 标签 Case语句 If语句 复合语句 过程语句 赋值语句 复合语句 子程序 过程头 … * 编译原理 * YACC的例子 YACC中文件的说明： 生成语法分析器文件为spl.y。其中进行SPL语法的描述，在语法检查和分析过程中，加入语法树节点生成的代码。 Spl.y包含了语法规则的描述和语法树节点生成的程序，YACC程序根据这些自动生成LALR(1)分析表，并用一系列矩阵存储分析表中的内容 Yacc的输出文件rule.h/rule.c中的yytable及相关部分代码 YACC程序初始化接收token序列的数组数据结构（包含方法），用于语法分析过程的栈数据结构（包含压入和弹出操作），以及查找LALR分析表和进行语法分析动作。 按照语法分析过程组织上述数据结构，完成语法分析 * 编译原理 * YACC的例子 存储输入的token序列需要的字符串数组数据结构——rule.c中的函数yylex就实现了token序列生成和返回token的操作（01850） 分析过程的中间状态需要栈数据结构。Rule.c中存储分析过程的中间状态的栈为(01710) 文法规则需要存储在表数据结构中，这个数据结构是yytable，其使用见01870行。 当状态值为正时，移进token 状态值为负时，采用正数对应的规则进行规约 如果是0，则依照YYDEFACT中定义的情况动作 如果是YYTABLE_NINF即-169为语法错误 Yytable的定义在0999行，yyreduce在01913行 * 编译原理 * 语法分析过程中的数据结构 语法树需要树数据结构来存储。Tree.h中定义的_tree结构体（046） Op记录节点或者树的操作参见ops.h中的节点和树操作的枚举结构定义 Result_tye记录节点的类型 Kids[2]记录该节点或树的两个孩子节点或树 U为当前树节点的值部分 tree op Resule_type u * 编译原理 * 具体实现 A程序 Spl.y中的00226开始。创建树为00235，对应rule.c为01940 树节点的操作类型为TAIL，表示该树节点实现的是程序结束的操作。见ops.h中TAIL类型的定义0068 New_tree函数的实现在tree.c中0008 子程序sub_program的创建：00285树节点创建：00306和00309，对应于rule.c中也有相应表示。