语法分析器实验报告

语法分析器的设计实验报告语法分析器的设计实验报告 一 实验内容 语法分析程序用 LL 1 语法分析方法 首先输入定义好的文法书写文件 所用的 文法可以用 LL 1 分析 先求出所输入的文法的每个非终结符是否能推出空 再分别计算非终结符号的 FIRST 集合 每个非终结符号的 FOLLOW 集合 以 及每个规则的 SELECT 集合 并判断任意一个非终结符号的任意两个规则的 SELECT 集的交集是不是都为空 如果是 则输入文法符合 LL 1 文法 可以进 行分析 对于文法 G E E E T T T T F F F i E 分析句子 i i i 是否符合文法 二 基本思想 1 语法分析器实现 语法分析是编译过程的核心部分 它的主要任务是按照程序的语法规则 从由 词法分析输出的源程序符号串中识别出各类语法成分 同时进行词法检查 为 语义分析和代码生成作准备 这里采用自顶向下的 LL 1 分析方法 语法分析程序的流程图如图 5 4 所示 开始 读入文法 有效 判断句型 报错 结束 语法分析程序流程图 是 LL 1 文法 该程序可分为如下几步 1 读入文法 2 判断正误 3 若无误 判断是否为 LL 1 文法 4 若是 构造分析表 5 由句型判别算法判断输入符号串是为该文法的句型 三 核心思想 该分析程序有 15 部分组成 1 首先定义各种需要用到的常量和变量 2 判断一个字符是否在指定字符串中 3 读入一个文法 4 将单个符号或符号串并入另一符号串 5 求所有能直接推出定义临时数组 int i for i 0 iB B 可推出空 if 右部长度为 1 但第一个字符为终结符 then 返回 0 A a a 为终结符 else for k 0 kAB if 找到的字符与当前字符相同 A AB 结束本次循环 else mark 等于 0 查找右部符号是否可推出空字 把返回值赋给 result 把当前符号加入到临时数组 empt 里 if 当前字符不能推出空字且还没搜索完全部的产生式 then 跳出本次循环继续搜索下一条产生式 else if 当前字符可推出空字 返回 1 2 计算每个符号的 first 集 实例中求单个符号的 FIRST 集的算法描述如下 void first2 int i 参数 i 为符号在所有输入符号中的序号 c 等于指示器 i 所指向的符号 在保存终结符元素的 termin 数组查找 c if c 为终结符 c VT then FIRST c c 在保存终结符元素的 non ter 数组查找 c if c 是非终结符 c VN 在所有产生式中查找 c 所在的产生式 if 产生式右部第一个字符为终结符或空 即 c a a VT 或 c i 产生式总数 1 i 先把当前产生式右部的 FIRST 集 一切非空元素 不包括 放入到当前产生式的 SELECT i if 产生式右部符号串可推出空字 then 把 i 指向的当前产生式左部的非终结符号的 FOLLOW 集并入到 SELECT i 中 5 判断是否 LL 1 文法 要判断是否为 LL 1 文法 需要输入的文法 G 有如下要求 具有相同左部的规则的 SELECT 集两两不相交 即 SELECT A SELECT A 如果输入的文法都符合以上的要求 则该文法可以用 LL 1 方法分析 算法描述如下 把第一条产生式的 SELECT 0 集放到一个临时数组 temp 中 for i 1 i 产生式总数 1 i 求 temp 的长度 length if i 指向的当前产生式的左部等于上一条产生式的左部 then 把 SELECT i 并入到 temp 数组中 If temp 的长度小于 length 加上 SELECT i 的长度 返回 0 else 把 temp 清空 把 SELECT i 存放到 temp 中 结果返回 1 四 算法 include include include int count 0 产生式的个数 int number 所有终结符和非终结符的总数 char start 开始符号 char termin 50 终结符号 char non ter 50 非终结符号 char v 50 所有符号 char left 50 左部 char right 50 50 右部 char first 50 50 follow 50 50 各产生式右部的 FIRST 和左部的 FOLLOW 集合 char first1 50 50 所有单个符号的 FIRST 集合 char select 50 50 各个产生式的 SELECT 集合 char firstflag 50 followflag 50 记录各符号的 FIRST 和 FOLLOW 是否已求过 char empty 20 记录可推出 记录不可推出 求 emp 时使用 char TEMP 50 求 FOLLOW 时存放某一符号串的 FIRST 集合 int validity 1 表示输入文法是否有效 int ll 1 表示输入文法是否为 LL 1 文法 int M 20 20 分析表 char choose 用户输入时使用 char foll 20 求 FOLLOW 集合时使用 判断一个字符 c 是否在指定字符串 p 中 int in char c char p int i if strlen p 0 return 0 for i 0 i if p i c return 1 若在 返回 1 if i int strlen p return 0 若不在 返回 0 将单个符号或符号串并入另一符号串 void merge char d char s int type 是目标符号串 s 是源串 type 1 源串中的 for i 0 i int strlen s 1 i if type 2 else for j 0 j if j int strlen d 若已存在 则退出 继续看下一个源串字符 if j int strlen d 若不存在 则并入 d j s i d j 1 0 break 读入一个文法 char grammer char t char n char left char right 50 50 char vn 50 vt 50 char s char p 50 50 int i j printf 请输入文法的非终结符号串 scanf s vn getchar i strlen vn memcpy n vn i n i 0 printf 请输入文法的终结符号串 scanf s vt getchar i strlen vt memcpy t vt i t i 0 printf 请输入文法的开始符号 scanf c getchar printf 请输入文法产生式的条数 scanf d getchar count i for j 1 j i j printf 请输入文法的第 d 条 共 d 条 产生式 j i scanf s p j 1 getchar for j 0 j 检测输入错误 printf n 输入错误 validity 0 return 0 return s 判断读入的文法是否正确 int judge int i j for i 0 i count 1 i if in left i non ter 0 若左部不在非终结符中 报错 printf n 文法左部出错 validity 0 return 0 for j 0 j int strlen right i 1 j if in right i j non ter 0 validity 0 return 0 return 1 求所有能直接推出 int i for i 0 iB B 可推出空 return 1 else if j 1 else for k 0 kAB mark 1 if mark 1 找到的字符与当前字符相同 A AB continue 结束本次循环 else mark 等于 0 for k 0 k j 1 k result emp right i k 递归调用 查找右部符号是否可推出 空字 把返回值赋给 result temp 0 right i k temp 1 0 merge empt temp 1 把当前符号加入到临时数组 empt 里 标 记已查找 if result 0 else if result 1 求单个符号的 FIRST void first2 int i i 为符号在所有输入符号中的序号 char c temp 20 int j k m char ch c v i emp ch 求所有能直接推出空字的符号 结果保存到 empty 中 if in c termin 1 若为终结符 c VT 则 FIRST c c first1 i 0 c first1 i 1 0 else if in c non ter 1 若为非终结符 for j 0 j count 1 j j 为所有产生式中的序列 if left j c 找一个左部为 c 的产生式 if in right j 0 termin 1 right j 0 temp 1 0 merge first1 i temp 1 X Y1Y2 Yk 的产生式 若 Y1 VN 则把 FIRST Y1 中的一切非空符号加进 FIRST X else if in right j 0 non ter 1 产生式右部第一个字符为非终结符 if right j 0 c 产生式右部的第一个符号等于当前字符 则跳到下 一条产生式进行查找 continue for k 0 k if v k right j 0 求右部第一个字符在所有字符集中的位置 k break if firstflag k 0 first2 k 求其 FIRST 集 firstflag k 1 标识其为查找状态 merge first1 i first1 k 2 求得结果并入到 X 的 FIRST 集 for k 0 k int strlen right j k empt 0 0 存放到一个临时数组里 标识此字符已查找其是否 可推出空字 if emp right j k 1 m if v m right j k 1 获取右部符号下一个字符在所 有字符集中的位置 break if firstflag m 0 如果此字符的 FIRST 集还未查找 则找 其 FIRST 集 并标其查找状态为 1 first2 m firstflag m 1 merge first1 i first1 m 2 把求得结果并入到 X 的 FIRST 集 产生式为 X Y1Y2 Yk 若对一切 1 i 0 i 不为 1 时是产生式的序号 first i 0 把 else i 为 1 时 表示求 FOLLOW 时用到的产生式右部的 FIRST 集 保存在 TEMP 中 TEMP 0 TEMP 1 0 else 右部符号串字符不为 j if v j p 0 求右部符号的第一个字符 p 0 在所有字符集中的位置 j break if i 0 memcpy first i first1 j strlen first1 j 把 j 所指向的单个符号的 FIRST 集拷贝到该右部符号串的 FIRST 集 first i strlen first1 j 0 else memcpy TEMP first1 j strlen first1 j TEMP strlen first1 j 0 else 如果右部为符号串 for j 0 j if v j p 0 求右部符号的第一个字符 p 0 在所有字符集中的位置 j break if i 0 merge first i first1 j 2 else merge TEMP first1 j 2 for k 0 k length 1 k empt 0 0 if emp p k 1 else merge TEMP first1 m 2 else if emp p k 1 temp 1 0 if i 0 merge first i temp 1 else merge TEMP temp 1 else if emp p k 0 break 求各产生式左部的 FOLLOW void FOLLOW int i 参数 i 为该符号在非终结符中的位置 int j k m n result 1 char c temp 20 c non ter i c 为待求的非终结符 temp 0 c temp 1 0 merge foll temp 1 把当前字符放到一临时数组 foll 中 标识求已求其 FOLLOW 集 避 免循环递归 if c start 若为开始符号 开始符号 S 则 FOLLOW S temp 0 temp 1 0 merge follow i temp 1 for j 0 j k if right j k c break k 为 c 在该产生式右部的序号 如 B 在产生式 A B 中的位置 for m 0 m if v m left j break m 为产生式左部非终结符在所有符号中的序号 如果 c 在产生式右部的最后 形如产生式 A B 则 FOLLOW A FOLLOW B if k int strlen right j 1 if in v m foll 1 查找该非终结符是否已经求过其 FOLLOW 集 避免循 环递归 是则 FOLLOW A FOLLOW B merge follow i follow m 1 把 c 所在产生式的左部非终结符的 FOLLOW 集加入到 FOLLOW c 中 continue 结束本次循环 进入 j 循环 if followflag m 0 如果该非终结符的 FOLLOW 未求过 FOLLOW m 求之 FOLLOW 集 followflag m 1 标识为 1 merge follow i follow m 1 FOLLOW A FOLLOW B else 如果 c 不在产生式右部的最后 形如 A B for n k 1 n FOLLOW A FOLLOW B continue if followflag m 0 FOLLOW m followflag m 1 merge follow i follow m 1 若 A B 其中 B VN VT U VN VT U VN 则 FIRST FOLLOW B for n k 1 n int strlen right j 1 n temp n k 1 right j n temp strlen right j k 1 0 FIRST 1 temp 求 FIRST merge follow i TEMP 2 把 FIRST 中所有非空元素加入到 FOLLOW B 中 followflag i 1 标识当前要求的非终结符的 FOLLOW 集已求过 判断读入文法是否为一个 LL 1 文法 int LL1 int i j length result 1 char temp 50 for j 0 j 49 j 初始化 first j 0 0 follow j 0 0 first1 j 0 0 select j 0 0 TEMP j 0 temp j 0 firstflag j 0 用来记录该字符的 FIRST 集是否已求过 1 表示已求 0 表示未求 followflag j 0 用来记录该字符的 FOLLOW 集是否已求过 1 表示已求 0 表示未 求 for j 0 j int strlen v 1 j first2 j 求单个符号的 FIRST 集合 结果保存在 first1 里 printf n 各非终结符推出的 first 集 n for j 0 j int strlen v 1 j printf c s v j first1 j printf n 能导空的非终结符集合 s empty printf n emp for j 0 j int strlen v 1 j printf d emp v j for i 0 i count 1 i FIRST i right i 求 FIRST for j 0 j int strlen non ter 1 j 求 FOLLOW if foll j 0 foll 0 0 FOLLOW j printf nfirst 集 for i 0 i count 1 i printf s first i printf nfollow 集合 for i 0 i int strlen non ter 1 i printf s follow i for i 0 i count 1 i 求每一产生式的 SELECT 集合 memcpy select i first i strlen first i first 存放的是各产生式右部的 FIRST 集 select i strlen first i 0 for j 0 j if result 1 for j 0 j if v j left i j 为左部符号在所有字符集中的位置 break merge select i follow j 1 printf nselect 集合顺序是 for i 0 i count 1 i printf s select i memcpy temp select 0 strlen select 0 temp strlen select 0 0 for i 1 i count 1 i 判断输入文法是否为 LL 1 文法 length strlen temp if left i left i 1 merge temp select i 1 if strlen temp length strlen select i 比较两个产生式的 SELECT 长度 return 0 else temp 0 0 memcpy temp select i strlen select i temp strlen select i 0 return 1 构造分析表 M void MM int i j k m for i 0 i 19 i for j 0 j 19 j 初始化分析表 全部置为空 1 M i j 1 i strlen termin termin i 将 加入终结符数组 termin i 1 0 for i 0 i count 1 i 查看每个产生式的 SELECT 集 for m 0 m if non ter m left i break m 为产生式左部非终结符的序号 for j 0 j 0 n S p right m n S q strlen right m 0 printf S s str S for p j p int strlen str 1 p printf c str p printf n 一个用户调用函数 void menu syntax printf n 是否继续 y or n scanf c getchar while choose y menu 主函数 void main int i j start grammer termin non ter left right 读入一个文法 printf count d coun