实验二 递归下降法语法分析.doc

实验二 递归下降语法分析 目的： 理解自定向下语法分析的基本模式，熟悉递归下降分析程序的构造。 内容： 采用递归下降法对赋值语句、算术表达式运算、while循环语句、if分支语句及其分类体系进行分析。 步骤： 1、重构单词内码表 在实验一的基础上，要求考虑while语句、if语句。以下为一参考实现： ? 保留字 内部编码 运算符号 内部编码 其他 内部编码 if 1 + 51 ( 81 else 2 - 52 ) 82 while 3 * 53 ; 83 int 4 / 54 { 84 float 5 ** 55 } 85 char 6 == 56 = 86 byte 7 57 , 87 ? ? 58 ? ? = 59 ? ? = 60 数字 100? ? ? 61 标识符 110 2、定义语言文法 （1）定义所需的非终结符 选取高级语言的部分语句，先定义其中所涉及的非终结符： 符号 定义 符号 定义 符号 定义 PR 程序 DSS 定义语句集 ESS 可执行语句集 DS 定义语句 IDS 变量列表 ROP 关系运算符 ES 可执行语句 WS while语句 IFS If语句 AS 赋值语句 SUB 过程调用语句 TYPE 类型声明 RE 关系表达式 OP1 算术运算符1 OP2 算术运算符2 ETT1 T2F 表达式文法引入的几个符号依然使用。 （2）用文法表达其语法规范。 PR →DSSESS DSS →DSDSS|ε DS → TYPEIDIDS; IDS →,IDIDS|ε TYPE→int | float | char | byte ESS →ES;ESS|ε ES →WS|IFS|AS WS →while ( RE ) { ESS } IFS →if ( RE ) { ESS } else { ESS } AS →ID=E; RE →EROPE ROP →||==|=|=|!= E →TE1 E1 →OP1TE1|ε T →FT1 T1 →OP2FT1|ε F →(E)|id|digits OP1 →+|- OP2 →*|/ 说明： ① 大写字母构成的单词（也用尖括号括起）表非终结符，小写单词表终结符。由于在词法分析阶段已经识别了数字和标识符，故逻辑上在此作为终结符对待；但另一方面又由于其概括性，又用尖括号括起。 ② 本文法设计对高级语言子集也作了较大的简化，如不考虑过程定义及调用；不考虑输入输出；不考虑主程序；不考虑for循环；不考虑switch case语句；不考虑字符串常量；变量定义只能在文件开头等等。 3、编码 （1）递归下降子程序的基本模式（请注意规则和下面的颜色对应关系）： ① 文法中的每个非终结符对应一个过程（函数）。 ② 若某个非终结符有多个产生式候选，或者某个分支路径有多个候选。则根据该候选的Select集是否包含输入符进行选择。每个候选对应一个if分支。 ③ 选择好候选之后，对产生式候选的右部的符号由左到右依次处理。 （a）若为终结符。则判别是否与输入符号相等。 若相等，继续。否则转③ （b）若为非终结符，则调用该非终结符所对应的过程。 （c）若当前扫描的符号为当前候选的第一个符号，且当前候选同层次有ε候选项.则不作出错处理。否则均出错处理。 例1：S((S)|a char str[];… //待检查的串 int ip; //扫描指针 void S() { //只有一个非终结符S if(str[ip]==’(‘) { //处理S((S)候选 ip++; S(); if(str[ip]==’)’) ip++; else error(); } else if(str[ip]==’a’) { //处理S(a候选 ip++; } else //对应第1符号 error(); //但无ε候选项，必须出错。 } 例2：S((S)|ε char str[];… //待检查的串 int ip; //扫描指针 void S() { //只有一个非终结符S if(str[ip]==’(‘) { ip++; S(); if(str[ip]==’)’) ip++; else error(); //不与第1个符号，出错。 } //最外层if不构造出错处理分支。 } （2）本实验中需要考虑的具体问题 ① 上例比较的是字符。而本实验中用的是符号（单词）编码，是经过词法分析后的编码。依据字符串的排列和内码排列构成的