![[编译原理] 构造预测分析表预测分析器的编码实现,第1张](/aiimages/%5B%E7%BC%96%E8%AF%91%E5%8E%9F%E7%90%86%5D+%E6%9E%84%E9%80%A0%E9%A2%84%E6%B5%8B%E5%88%86%E6%9E%90%E8%A1%A8%E9%A2%84%E6%B5%8B%E5%88%86%E6%9E%90%E5%99%A8%E7%9A%84%E7%BC%96%E7%A0%81%E5%AE%9E%E7%8E%B0.png "[编译原理] 构造预测分析表预测分析器的编码实现,第1张")
目录
前言
1、 通过文法构造first集合和follow集合
1.1 文法
1.2 构建 First集
1.3 构建follow集合
2.、通过文法构建预测分析表
2.1 预测分析表
2.2 构造过程
3. 通过预测分析器分析序列
3.1 分析输入序列id + id * id;的过程
3.2 过程分析
4. 编码实现
4.1 对数据约定
4.2 编码效果展示
4.3 编写代码JavaScript实现
4.4 编写代码java实现
前言
本博客主要记录 给定文法 通过算法得到预测分析表，然后通过预测分析表 分析输入序列的过程。
1、 通过文法构造first集合和follow集合 1.1 文法（1）L -> E ; L | @（2）E -> TE' （3）E' -> + T E' | - T E' | @ （4）T -> F T'（5）T' -> * F T' | / F T' | mod F T' | @（6）F -> (E) | id | num
所使用的文法必须为消除左递归后的最左子式，上述文法即为消除左递归后的文法。
1.2 构建 First集要构建follow集合首先需要得到first集合，下面分析first集合的官方解释和步骤。
（约定 @ 代替 ε，因为编码实现敲不出来 ε ）
1. 定义：
对于任意文法符号串α ，FIRST(α)是可从α推导得到的串的首符号的集合
如果α-->@，则@也在FIRST(α)中（ 即α可空）；
FIRST(α)={t|α-->tβ, t∈T}U{@|α-->@}；
2. 做法：
首先明确FIRST集合是对推导符号后面的首符号（仅仅只是一个符号）进行判断的。
3. 步骤：
假设 α-->tβ，求FIRST(α)
① 如果首符号t是终结符则直接放入first集合中。
②如果t不是非终结符：
i．如果t—>@，则将@加入FIRST(α)，并且将β进行①② *** 作判断。
ii．如果t不是@，那么求first（t），并将first（t）的结果放入FIRST(@)中。
简而言之，用个人的理解来说：
（1）first集合是从文法中得到的，分析文法时是自下而上分析，如下 应该从F开始分析，最后分析L。
（2）分析某个产生式的first(A)集合时，看其右部，每次取其第一个字符，如果是终结符则加入到该first(A)集合中，如果为非终结符B，则 first(A) = fitst(B) U {A对应的右部其他终结符};
（3）该文法的所有first 集合为：
1.3 构建follow集合first(F) = { ( , id , num }
first(T') = { * , / , mod, @}
first(T) = first(F) = { ( , id , num }
first(E') = { + , - , @ };
first(E) = first(T) = first(F) = { ( , id , num }
first(L) = first(E) U { @ } = { ( , id , num , @ }
Follow集是从上至下分析文法得到的，下面是分析过程：
（约定 @ 代替 ε，因为编码实现敲不出来 ε ）
假设：
A -->αBβ，A -->αB，求follow（B）
做法：
寻找B在à右边出现的规则式，然后按照以下步骤进行 *** 作
步骤：
①如果A是开始符, 将$加入FOLLOW(A), 这里 # 是输入结束标记.
②对于A -->αBβ，首先判断β是不是可以推出@ （α可能为空）
i．如果不能推出@，那么将first（β）加入follow（B）
ii．如果推出@，那么将{first（β）- @} U follow(A)
iii . 如果 β 为 终结符，直接将 β 加入到 follow（B）中
(ps:为了便于理解，iii 为个人理解!)
③对于A -->αB，将follow(A)结果加入follow（B）。
注意：
Follow一般从上往下找，而且第一轮的时候有时候不能够将所有的follow都填满，所以要采用迭代的方式不断循环。有时候遇到闭环的时候，先假设按照第一遍 把所有的都算出来后，第二轮的时候将所有集合制空，如果有变化，则在进行一轮，直到没有变化为止。
分析过程：
第一次分析：follow(L) = {#}
（1）根据规则1 ：L为开始符，将 # 加入其中；
第二次分析：follow（E）= { ; , ) }
（1）根据规则2.iii 和 产生式（1），将终结符 ； 加入到follow(E)
（2）根据规则2.iii 和 产生式 （6），将终结符 ) 加入到follow（E）
第三次分析：follow（E'）= { ; , ) }
（1）根据规则3 和 产生式（2），将终结符 follow（E） 加入到follow(E')
第四次分析：follow（T）= { + ， - , ; , ) }
（1）根据规则2.ii 和 产生式（2），first(E') 包含 @ ，所以将first(E') - {@} U follow(E)加入到follow（T）中，即 { + ， - , ; , ) }。
（2）根据规则2.ii 和 产生式 （3），first(E') 包含 @ ，所以将first(E') - {@} U follow(E')加入到follow（T）中，即 { + ， - , ; , ) }。
ps:此时发现会有重复的存在，编译程序时可以执行去重 *** 作，也可以在此判断之前是否加入过了。
第五次分析：follow（T '）= { + ， - , ; , ) }
（1）根据规则3 和 产生式（4），将 follow（T） 加入到follow（T '）中
第六次分析：follow（ F ）= { * ，/ , mod , + , - , ; , ) }
（1）根据规则2.ii 和 产生式（4），first(T') 包含 @ ，所以将first(T') - {@} U follow(T)加入到follow（F）中，即 { * ，/ , mod , + , - , ; ,) }。
（2）根据规则2.ii 和 产生式（5），first(T') 包含 @ ，所以将first(T') - {@} U follow(T ')加入到follow（F）中，即 { * ，/ , mod , + , - , ; , ) }。
ps:此时发现会有重复的存在，编译程序时可以执行去重 *** 作，也可以在此判断之前是否加入过了。
整理得：
follow(L) = {#}follow（E）= follow（E'）= { ; , ) }follow（T）= follow（T '）= { + ， - , ; , ) }follow（ F ）= { * ，/ , mod , + , - , ; , ) }2.、通过文法构建预测分析表 2.1 预测分析表
| id | num | + | - | * | / | mod | ( | ) | ; | # | |
| L | E;L | E;L | E;L | @ | |||||||
| E | TE' | TE' | TE' | ||||||||
| E‘ | +TE' | -TE' | @ | @ | |||||||
| T | FT' | FT' | FT' | ||||||||
| T’ | @ | @ | *FT' | /FT' | modFT' | @ | @ | ||||
| F | id | num | (E) |
1. 将文法中的产生式右部填写在表中，首先需要确定填写的位置。
（1）如果该产生式右部不为 @
i ：获取该产生式左部A对应的first(A) - { @ }集合。
ii : 遍历 first(A) -{@} 集合,与该产生式 左部A ，在表中确认位置。
（2）如果该产生式右部为 @
i ：获取该产生式左部A对应的 follow（A）集合。
ii : 遍历 follow(A) 集合,与该产生式 左部A ，在表中确认位置。
2. 举例：
（1）填写 L -> E;L | @; 先填写 L -> E;L ;
左部 ：L ，右部 ：E;L ，不为 @ ，所以遍历first（L）- { @ } 集合。
first(L) - {@} = { ( , id ,num }
所以将表中：table[L][(]=E;L table[L][id]=E;L table[L][num]=E;L
接着填写 L-> @
左部 ：L ，右部 ：@ ，为 @ ，所以遍历 follow（L） 集合。
follow（L） = { # }
所以将表中：table[L][#]=@
（2）填写 E -> TE' ;
左部 ：E ，右部 TE' ，不为 @ ，所以遍历 first(L) - {@}集合。
first(E) - {@} = { ( , id ,num }
所以将表中：table[E][(]=TE' table[E][id]=TE' table[E][num]=TE'
其他产生式以此类推，即可完成预测分析表的构造。
3. 通过预测分析器分析序列 3.1 分析输入序列id + id * id;的过程3.2 过程分析
1. 首先初始化栈（栈内容）
stack = [ # , L]; （结束标志 # ，开始符号 L ）
序列后也要加上结束标志 #
2. 四种改变格局的动作（也就是下一步怎么走）：
（1）匹配终结符
如果栈顶和当前输入终结符相当且不是结束标志#，则分析器d出栈顶符号（pop），输入指针指向下一个终结符（next（ip））。
举例：
此时栈顶d出 终结符id ，输入序列指向下一个字符 + 。
（2）展开非终结符
栈顶符号是非终结符X，当前输入是终结符a,驱动器访问预测分析表M[X][a];若M[X][a]是X产生式的某候选项，则用此候选项取代栈顶的X。
举例：1 到 2的过程
栈内容 #L ，此时栈顶 L（非终结符）, 当前序列输入 id , 在预测分析表中查 table[L][id]
发现 table[L][id] = E;L，所以 先将栈内容 pop(L) , 再 将 E ; L push进栈 ,注意push的是单个字符，栈是先进后出，所以push完成后，栈中内容为 # L;E。
注意：如果查表查出来的是 @ ，@ 代表空，所以只d出栈顶字符，不加入。
（3）报告分析成功
栈顶和当前输入符号均为#，分析成功并结束。
（4）报告出错
有不在前面几种情况中的事故发生。
4. 编码实现为了有更好的视觉呈现效果，采用JavaScript进行编译实现。
4.1 对数据约定1.字符处理
id , num ,mod 等 多字符组成的，均采用首字母。如 id 用 i 代替。
2.约定 @ 代替 ε，因为编码实现敲不出来 ε
3. 用数组模拟栈
4.2 编码效果展示
错误输入
4.3 编写代码JavaScript实现
预测分析表
package com.wang;
import java.util.*;
public class Demo2 {
public static List res1= new ArrayList<>();
public static List res2= new ArrayList<>();
public static List res3= new ArrayList<>();
public static List res4= new ArrayList<>();
public static Stack prefix= new Stack<>();
public static String w;
public static String grammer[][]=new String[6][11];
public static Map init(){
Map map= new HashMap<>();
String a[]={"E;L","ε"};
map.put("L",a);
String b[]={"Te"};
map.put("E",b);
String c[]={"+Te","-Te","ε"};
map.put("e",c);
String d[]={"Ft"};
map.put("T",d);
String e[]={"*Ft","/Ft","mFt","ε"};
map.put("t",e);
String f[]={"(E)","i","n"};
map.put("F",f);
return map;
}
public static int getPosionX(char x){
int num=-1;
switch (x){
case 'L': num=0;break;
case 'E': num=1;break;
case 'e': num=2;break;
case 'T': num=3;break;
case 't': num=4;break;
case 'F': num=5;break;
default:num=-1;break;
}
return num;
}
public static int getPosionY(char x){
int num=-1;
switch (x){
case 'i':num=0;break;
case 'n':num=1;break;
case '+':num=2;break;
case '-':num=3;break;
case '*':num=4;break;
case '/':num=5;break;
case 'm':num=6;break;
case '(':num=7;break;
case ')':num=8;break;
case ';':num=9;break;
case '#':num=10;break;
default:num=-1;break;
}
return num;
}
public static List DisRepet(List arr){
List arrayList=new ArrayList();
for (int i = 0; i splice(List list){
for (int i = 0; i < list.size(); i++) {
if ('ε'==list.get(i)){
list.remove(i);
i--;
}
}
return list;
}
public static String[] initTemp(String s[]){
int index=0;
s[index++]="L";
s[index++]="E";
s[index++]="e";
s[index++]="T";
s[index++]="t";
s[index++]="F";
return s;
}
public static List concat(List a,List b){
List c=new LinkedList<>();
c.addAll(a);
c.addAll(b);
return DisRepet(c);
}
public static String listTransfrom(String str){
str.replaceAll("i","id").replaceAll("n","num").replaceAll("m","mod");
return str;
}
public static String getQuery(char x,char y){
int x1 = getPosionX(x);
int y1 = getPosionY(y);
if (x1!=-1&&y1!=-1){
return grammer[x1][y1];
}else {
return "-1";
}
}
public static boolean isZJF(){
Character ch = prefix.get(prefix.size() - 1);
boolean flag=true;
if (getPosionY(ch)==-1){
flag=false;
}
return flag;
}
public static String queryRefer(char ch){
String str="";
switch (ch){
case 'e':str="E'";break;
case 't':str="T'";break;
default:str=ch+"";break;
}
return str;
}
public static void dealData(int resNum,String refer,String x){
if (resNum==1){
String str="";
for (int i = 0; i "+refer+"展开");
}else {
x=queryRefer(x.toCharArray()[0]);
x=listTransfrom(x);
res4.add("按"+x+"->"+str+"展开");
}
}
}
}
public static void output(int len){
for (int j = 0; j <25-len ; j++) {
System.out.print(" ");
}
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
w=sc.nextLine();
w = w.replaceAll("id", "i").replaceAll("num", "n").replaceAll("mod", "m");
w+=";#";
Map iniGrammer=init();
Map> first=new HashMap<>();
String first_temp[]=initTemp(new String[iniGrammer.size()]);
for (int i = first_temp.length-1; i >=0 ; i--) {
String[] temp = iniGrammer.get(first_temp[i]);
List first_map_arr=new ArrayList<>();
for (int j = 0; j > follow=new HashMap<>();
for(String key:first_temp){
String[] temp = iniGrammer.get(key);
List follow_map_arr=new ArrayList<>();
if (key.equals("L")){
follow_map_arr.add('#');
}
for(String key2:first_temp){
if (!key2.equals(key)){
String[] brr = iniGrammer.get(key2);
for (int k = 0; k concat = concat(follow.get(key2 + ""), first.get(nextChar + ""));
follow_map_arr=concat(follow_map_arr,concat);
follow_map_arr=DisRepet(follow_map_arr);
follow_map_arr=splice(follow_map_arr);
}else {
//如果不包含 '@' ,则将 first（β）加入follow（B）
follow_map_arr=concat(follow_map_arr,first.get(nextChar+""));
follow_map_arr=DisRepet(follow_map_arr);
}
}catch (Exception e){
}
}
}else {
//4. 如果在末尾则应用规则3
follow_map_arr=concat(follow_map_arr,follow.get(key2+""));
follow_map_arr=DisRepet(follow_map_arr);
}
}
}
}
}
follow.put(key,follow_map_arr);
}
// System.out.println(follow);
for (int i = 0; i <6 ; i++) {
for (int j = 0; j <11 ; j++) {
grammer[i][j]="0";
}
}
for(String key:first_temp){
String[] iniGrammer_arr = iniGrammer.get(key);
List first_arr = first.get(key);
List follow_map_arr = follow.get(key);
for (int i = 0; i =0 ; i--) {
prefix.push(refer.charAt(i));
}
dealData(3,refer,x3+"");
dealData(4,refer,x3+"");
}else {
res3.add("出错了");
res4.add("出错了");
break;
}
}
for (int i = 0; i 总结：此方法可能不是最优，如果错误请评论区多多指教。😄
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）