实验4-算符优先分析法.doc

实验名称 实验任务 对下述描述算符表达式的算符优先文法 G E 给出算符优先分析的 实验结果 实验内容 有上下无关文法如下 E E T E T T T T F T F F F E i 说明 优先关系矩阵的构造过程 1 关系 由产生式 F E 知 FIRSTVT 集 及 LASTVT 集 FIRSTVT E i FIRSTVT F i FIRSTVT T i LASTVT E i LASTVT F i LASTVT T i 2 关系 T 则有 FIRSTVT T T 则有 FIRSTVT T F 则有 FIRSTVT F F 则有 FIRSTVT F E 则有 关系 E 则有 LASTVT E E 则有 LASTVT E T 则有 LASTVT T T 则有 LASTVT T E 则有 LASTVT E 4 请大家画出优先关系矩阵 终结符之间的优先关系是唯一的 所以该文法是算符优先文法 程序的功能描述 程序由文件读入字符串 以 结束 然后进行 算符优先分析 分析过程中如有错误 则终止程序并报告错误位置 最终向屏幕输出移近 规约过程 5 依据文法和求出的相应 FirstVT 和 LastVT 集生成算符优先分析 表 算法描述如下 for 每个形如 P X1X2 Xn 的产生式 do for i 1 to n 1 do begin if Xi 和 Xi 1 都是终结符 then Xi Xi 1 if i n 2 Xi 和 Xi 2 是终结符 但 Xi 1 为非终结符 then Xi Xi 2 if Xi 为终结符 Xi 1 为非终结符 then for FirstVT 中的每个元素 a do Xi Xi 1 end 6 构造总控程序 算法描述如下 stack S k 1 符号栈 S 的使用深度 S k REPEAT 把下一个输入符号读进 a 中 If S k VT then j k else j k 1 While S j a do Begin Repeat Q S j if S j 1 VT then j j 1 else j j 2 until S j Q 把 S j 1 S k 归约为某个 N 并输出归约为哪个符号 K j 1 S k N end of while if S j a or S j a then begin k k 1 S k a end else error 调用出错诊察程序 until a 7 代码如下 include stdio h include stdlib h include iostream h char data 20 20 算符优先关系 char s 100 模拟符号栈 s char lable 20 文法终极符集 char input 100 文法输入符号串 char string 20 10 用于输入串的分析 int k char a int j char q int r 文法规则个数 int r1 转化后文法规则个数 char st 10 30 用来存储文法规则 char first 10 10 文法非终结符 FIRSTVT 集 char last 10 10 文法非终结符 LASTVT 集 int fflag 10 0 标志第 i 个非终结符的 FIRSTVT 集是否已求 出 int lflag 10 0 标志第 i 个非终结符的 LASTVT 集是否已求出 int deal 对输入串的分析 int zhongjie char c 判断字符 c 是否是终极符 int xiabiao char c 求字符 c 在算符优先关系表中的下标 void out int j int k char s 打印 s 栈 void firstvt char c 求非终结符 c 的 FIRSTVT 集 void lastvt char c 求非终结符 c 的 LASTVT 集 void table 创建文法优先关系表 void main int i j k 0 printf 请输入文法规则数 scanf d printf 请输入文法规则 n for i 0 i r i scanf s st i 存储文法规则 初始化 FIRSTVT 集和 LASTVT 集 first i 0 0 first i 0 和 last i 0 分别表示 st i 0 非终极 符的 FIRSTVT 集和 LASTVT 集中元素的个数 last i 0 0 for i 0 i r i 判断文法是否合法 for j 0 st i j 0 j if st i 0 Z printf 不是算符文法 n exit 1 if st i j A exit 1 for i 0 i r i for j 0 st i j 0 j if st i j Z lable k lable k 1 0 table printf 每个非终结符的 FIRSTVT 集为 n 输出每个非终结符的 FIRSTVT 集 for i 0 i r i printf c st i 0 for j 0 j first i 0 j printf c first i j 1 printf n printf 每个非终结符的 LASTVT 集为 n 输出每个非终结符的 LASTVT 集 for i 0 i r i printf c st i 0 for j 0 j last i 0 j printf c last i j 1 printf n printf 算符优先分析表如下 n for i 0 lable i 0 i printf t c lable i printf n for i 0 i k 1 i printf c t lable i for j 0 j k 1 j printf c t data i j printf n printf 请输入文法输入符号串以 结束 scanf s input deal void table char text 20 10 int i j k t l x 0 y 0 int m n x 0 for i 0 i r i firstvt st i 0 lastvt st i 0 for i 0 i else text x y st i j y text x y 0 x y 0 r1 x printf 转化后的文法为 n for i 0 i x i 输出转化后的文法规则串 printf s n text i for i 0 i 后的转化文法 用于最后的规约 string i 0 text i 0 for j 3 l 1 text i j 0 j l string i l text i j string i l 0 for i 0 i x i for j 1 text i j 1 0 j if zhongjie text i j n xiabiao text i j 1 data m n if text i j 2 0 n xiabiao text i j 2 data m n if zhongjie text i j k r k if st k 0 text i j 1 break m xiabiao text i j for t 0 t first k 0 t n xiabiao first k t 1 data m n if zhongjie text i j k r k if st k 0 text i j break n xiabiao text i j 1 for t 0 t m xiabiao for t 0 t first 0 0 t n xiabiao first 0 t 1 data m n n xiabiao for t 0 t data n n void firstvt char c 求 FIRSTVT 集 int i j k m n for i 0 i r i if st i 0 c break if fflag i 0 n first i 0 1 m 0 do if m 2 st i m if zhongjie st i m 1 first i n st i m 1 n else if zhongjie st i m 2 first i n st i m 2 n if st i m 1 c firstvt st i m 1 for j 0 j r j if st j 0 st i m 1 break for k 0 k first j 0 k int t for t 0 t n t if first i t first j k 1 break if t n first i n first j k 1 n m while st i m 0 first i n 0 first i 0 n fflag i 1 void lastvt char c 求 LASTVT 集 int i j k m n for i 0 i r i if st i 0 c break if lflag i 0 n last i 0 1 m 0 do if st i m 1 0 st i m 1 if zhongjie st i m last i n st i m n else if zhongjie st i m 1 last i n st i m 1 n if st i m c lastvt st i m for j 0 j r j if st j 0 st i m break for k 0 k last j 0 k int t for t 0 t out 1 k s printf c a out i 1 z input printf 规约 n do q s j if zhongjie s j 1 j j 1 else j j 2 x xiabiao s j y xiabiao q while data x y int m n N for m j 1 m k m for N 0 N r1 N for n 1 string N n 0 n if zhongjie s m break else if zhongjie s m if s m string N n s j 1 string N 0 break k j 1 if k 2 printf c a out i 1 z input printf 结束 n printf 输入串符合文法的定义 n return 1 输入串符合文法的定义 else if data x y data x y 移进 out 1 k s printf c a out i 1 z input printf 移进 n k s k a i else printf nflase return 0 printf nflase return 0 void out int j int k char s int n 0 int i