精华内容
下载资源
问答
  • 第六章 自底向上优先分析 郑先容 回顾简单优先分析法 回顾简单优先分析法 简单优先分析算法的基本思想 算符优先分析法 直观的算符优先分析法 算符优先分析法 区别是什么 算符优先关系的产生 优先关系的有序性 i i i ...
  • 实现算符优先过程 具体的算法 和结构体 一般报告都适用
  • 算符优先

    2020-05-27 18:21:27
    算符优先-------Java实现 实验题目 实验结果 1、读取文本 package by02; import java.io.BufferedReader; import java.io.File; import java.io.FileNotFoundException; import java.io.FileReader; import java...

    算符优先-------Java实现

    实验题目
    在这里插入图片描述
    实验结果
    在这里插入图片描述
    在这里插入图片描述
    1、读取文本

    package by02;
    
    import java.io.BufferedReader;
    import java.io.File;
    import java.io.FileNotFoundException;
    import java.io.FileReader;
    import java.io.IOException;
    import java.util.ArrayList;
    
    public class by02file {
    
    	private ArrayList<ArrayList<String>> G = new ArrayList<ArrayList<String>>();
    
    	private String str = "";
    
    	public by02file() throws IOException {
    		File file = new File("D://byfile02.txt");
    		try {
    			BufferedReader bu = new BufferedReader(new FileReader(file));
    			String s = null;
    			while ((s = bu.readLine()) != null) {
    				str += s;
    				str += '\n';
    			}
    			bu.close();
    		} catch (FileNotFoundException e) {
    			e.printStackTrace();
    		}
    	}
    
    	public void getStr() {
    		System.out.println(str);
    	}
    
    	public ArrayList<ArrayList<String>> PG() {
    		ArrayList<String> A = new ArrayList<String>();
    		//A中以字符串形式保存产生式的左部和右部候选式
    		int i = 0;
    		String s0 = "";
    		//集合不是将对象克隆存储,而是对对象的引用,为不改之前信息,需重新定义
    
    		while ((i < str.length())) {
    			if (str.charAt(i) == '-' && str.charAt(i + 1) == '>') {
    				A.add(s0);
    				s0 = "";
    				i += 2;
    			}else if(str.charAt(i)=='|') {
    				A.add(s0);
    				s0="";
    				i++;		
    			}else if(str.charAt(i)=='\n') {
    				A.add(s0);
    				G.add(A);
    				s0="";
    				A=new ArrayList<String>();
    				i++;
    			}
    			else {
    				s0+=str.charAt(i);
    				i++;
    			}
    
    
    		}
    		return G;	
    	}
    
    }
    
    

    2、FirstVt集、LastVt集及归约分析过程

    package by02;
    
    import java.io.IOException;
    import java.util.ArrayList;
    import java.util.HashSet;
    import java.util.Scanner;
    
    public class by02main {
    
    	static ArrayList<ArrayList<String>> G = new ArrayList<ArrayList<String>>();
    	static ArrayList<String> Vn = new ArrayList<String>();
    	static ArrayList Vt = new ArrayList();
    	static ArrayList<ArrayList> VnFirstVT = new ArrayList<ArrayList>();
    	static ArrayList<ArrayList> VnLastVT = new ArrayList<ArrayList>();
    	static int N = 3;
    
    	public static void removeDuplicate(ArrayList<ArrayList> list) {// 清楚集中的重复元素
    		int i = 0;
    		while (i < G.size()) {
    			HashSet h = new HashSet(list.get(i));
    			list.get(i).clear();
    			list.get(i).addAll(h);
    			i++;
    		}
    
    	}
    
    	public static void FirstVT() {
    		int i = 0;
    		while (i < G.size()) {// 第一遍扫描
    			ArrayList A = new ArrayList();
    			int j = 1;
    			while (j < G.get(i).size()) {
    				int t = 0;
    				for (; t < 2 && t < G.get(i).get(j).length(); t++) {
    					char c = G.get(i).get(j).charAt(t);
    					if (Vt.contains(c)) {
    						A.add(c);
    						break;
    					}
    				}
    
    				j++;
    			}
    			VnFirstVT.add(A);
    			i++;
    		}
    //		System.out.println(VnFirstVT);
    		i = 0;
    		while (i < G.size()) {// 第二遍扫描
    			int j = 1;
    			ArrayList<String> L = new ArrayList<String>();
    			int count = 0;
    			while (j < G.get(i).size()) {
    				String s = "";
    				s += G.get(i).get(j).charAt(0);
    				if (Vn.contains(s) && !s.equals(Vn.get(i))) {// 后者條件是避免自身first加入自身,無終止進行
    					L.add(s);
    //					System.out.println(s);
    				}
    				j++;
    			}
    			while (count < L.size()) {
    				int t = Vn.indexOf(L.get(count));
    				int m = 1;
    				while (m < G.get(t).size()) {
    					String s = "";
    					s += G.get(t).get(m).charAt(0);
    					if (Vn.contains(s) && !L.contains(s)) {
    						L.add(s);
    					}
    					m++;
    				}
    				count++;
    			}
    //			System.out.println(L);
    			int m = 0;
    			while (m < L.size()) {
    				int t = Vn.indexOf(L.get(m));
    				VnFirstVT.get(i).addAll(VnFirstVT.get(t));
    				m++;
    			}
    			i++;
    		}
    		removeDuplicate(VnFirstVT);// 清重复元素
    		System.out.println("各非终结符的FIRSTVT集为:" + VnFirstVT);
    
    	}
    
    	public static void LastVT() {
    		int i = 0;
    		while (i < G.size()) {// 第一遍扫描
    			ArrayList A = new ArrayList();
    			int j = 1;
    			while (j < G.get(i).size()) {
    				int t = G.get(i).get(j).length() - 1;
    				for (; t >= 0 && t >= G.get(i).get(j).length() - 2; t--) {
    					char c = G.get(i).get(j).charAt(t);
    					if (Vt.contains(c)) {
    						A.add(c);
    						break;
    					}
    				}
    
    				j++;
    			}
    			VnLastVT.add(A);
    			i++;
    		}
    
    		i = 0;
    		while (i < G.size()) {// 第二遍扫描
    			int j = 1;
    			ArrayList<String> L = new ArrayList<String>();
    			int count = 0;
    			while (j < G.get(i).size()) {
    				String s = "";
    				s += G.get(i).get(j).charAt(G.get(i).get(j).length() - 1);
    				if (Vn.contains(s) && !s.equals(Vn.get(i))) {// 后者條件是避免自身first加入自身,無終止進行
    					L.add(s);
    					// System.out.println(s);
    				}
    				j++;
    			}
    			while (count < L.size()) {
    				int t = Vn.indexOf(L.get(count));
    				int m = 1;
    				while (m < G.get(t).size()) {
    					String s = "";
    					s += G.get(t).get(m).charAt(G.get(t).get(m).length() - 1);
    					if (Vn.contains(s) && !L.contains(s)) {
    						L.add(s);
    					}
    					m++;
    				}
    				count++;
    			}
    			// System.out.println(L);
    			int m = 0;
    			while (m < L.size()) {
    				int t = Vn.indexOf(L.get(m));
    				VnLastVT.get(i).addAll(VnLastVT.get(t));
    				m++;
    			}
    			i++;
    		}
    		removeDuplicate(VnLastVT);// 清重复元素
    		System.out.println("各非终结符的LASTVT集为:" + VnLastVT);
    
    	}
    
    	public static void VnAndVt(by02file bf) {// 整理文法中非终结符和终结符,由于扩展开始符E',所以非终结符采用字符串存储
    		String s0 = "";
    		G = bf.PG();
    		int i = 0;
    		while (i < G.size()) {
    			Vn.add(G.get(i).get(0));
    			i++;
    		}
    		i = 0;
    		while (i < G.size()) {
    			int j = 1;
    			while (j < G.get(i).size()) {
    				int t = 0;
    				while (t < G.get(i).get(j).length()) {
    					s0 = "";
    					s0 += G.get(i).get(j).charAt(t);
    					if (!Vn.contains(s0) && !Vt.contains(G.get(i).get(j).charAt(t))) {
    						Vt.add(G.get(i).get(j).charAt(t));
    					}
    					t++;
    				}
    				j++;
    			}
    			i++;
    		}
    
    	}
    
    	public static char[][] Table() {
    		N = Vt.size() + 1;
    		char[][] c = new char[N][N];
    		for (int i = 1; i < N; i++) {
    			c[i][0] = (char) Vt.get(i - 1);
    			c[0][i] = (char) Vt.get(i - 1);
    		}
    		int i = 0;
    		int j;
    		while (i < G.size()) {
    			j = 1;
    			while (j < G.get(i).size()) {
    				for (int t = 0; t < G.get(i).get(j).length(); t++) {
    					if (Vt.contains(G.get(i).get(j).charAt(t))) {// 遍历到终结符
    						if (t - 1 >= 0 && !Vt.contains(G.get(i).get(j).charAt(t - 1))) {
    							// 判其前是否有非终结符,若有将其LastVT集中元素>此终结符,L中元素>此元素
    							String s = "";
    							s += G.get(i).get(j).charAt(t - 1);
    							int x = Vn.indexOf(s);
    							for (int y = 0; y < VnLastVT.get(x).size(); y++) {
    								c[Vt.indexOf(VnLastVT.get(x).get(y)) + 1][Vt.indexOf(G.get(i).get(j).charAt(t))
    										+ 1] = '>';
    							}
    						}
    						if (t + 1 < G.get(i).get(j).length() && !Vt.contains(G.get(i).get(j).charAt(t + 1))) {
    							// 判其后是否有非终结符,若有将其FirstVT集中元素<此终结符,此元素<F中元素
    							String s = "";
    							s += G.get(i).get(j).charAt(t + 1);
    							int x = Vn.indexOf(s);
    							for (int y = 0; y < VnFirstVT.get(x).size(); y++) {
    								c[Vt.indexOf(G.get(i).get(j).charAt(t)) + 1][Vt.indexOf(VnFirstVT.get(x).get(y))
    										+ 1] = '<';
    							}
    							if (t + 2 < G.get(i).get(j).length() && Vt.contains(G.get(i).get(j).charAt(t + 2))) {
    								c[Vt.indexOf(G.get(i).get(j).charAt(t)) + 1][Vt.indexOf(G.get(i).get(j).charAt(t + 2))
    										+ 1] = '=';
    							}
    						} else if (t + 1 < G.get(i).get(j).length() && Vt.contains(G.get(i).get(j).charAt(t + 1))) {
    							c[Vt.indexOf(G.get(i).get(j).charAt(t)) + 1][Vt.indexOf(G.get(i).get(j).charAt(t + 1))
    									+ 1] = '=';
    						}
    
    					}
    				}
    				j++;
    			}
    			i++;
    		}
    		for (i = 0; i < N; i++) {
    			for (j = 0; j < N; j++) {
    				System.out.print(c[i][j]);
    				System.out.print('\t');
    			}
    			System.out.println();
    			System.out.println();
    		}
    
    		return c;
    	}
    
    	public static String DataReduction(String s, String s0) {
    		int i = 0;
    		while (i < s.length()) {
    			if (Vt.contains(s.charAt(i))) {
    				String ss = "";
    				ss += s.charAt(i);
    				int x = 0;
    				while (x < G.size()) {
    					int j = 1;
    					while (j < G.get(x).size()) {
    						if (G.get(x).get(j).contains(ss)) {
    							s0 = s0.replace(s, G.get(x).get(0));
    							return s0;
    						}
    						j++;
    					}
    					x++;
    				}
    			}
    			i++;
    		}
    		return s0;
    
    	}
    
    	public static void analysis(char[][] c, String s) {
    		String s0 = "#";// 入栈字符
    		String s1 = "";// 临时字符串
    		int j = 0;// j最后一个终结符在栈中位置,i为输入串当前扫描位置
    		int i = 1;
    		do {
    			if (Vt.contains(s.charAt(i))) {
    				if (c[Vt.indexOf(s0.charAt(j)) + 1][Vt.indexOf(s.charAt(i)) + 1] == '>') {
    					s1 = "";
    					// 从当前位置往前找<
    					if (j != s0.length() - 1) {
    						s1 = s0.charAt(s0.length() - 1) + s1;
    					}
    					s1 = s0.charAt(j) + s1;
    
    					while (j > 0) {
    
    						if (Vt.contains(s0.charAt(j - 1))) {
    
    							if (c[Vt.indexOf(s0.charAt(j - 1)) + 1][Vt.indexOf(s0.charAt(j)) + 1] == '<') {
    								// s1为将要归约的字符串
    
    								s0 = DataReduction(s1, s0);
    								if (s0 == "") {
    									return;
    								}
    								j = s0.length() - 1;
    								while (!Vt.contains(s0.charAt(j))) {
    									j--;
    
    								}
    								System.out.println("规约\t栈中\t" + s0);
    
    								i--;
    								break;
    							} else {
    								s1 = s0.charAt(j - 1) + s1;
    								j--;
    								continue;
    							}
    						} else {
    							s1 = s0.charAt(j - 1) + s1;
    							if (j - 2 >= 0 && Vt.contains(s0.charAt(j - 2))) {
    								if (c[Vt.indexOf(s0.charAt(j - 2)) + 1][Vt.indexOf(s0.charAt(j)) + 1] == '<') {
    									// s1为将要归约的字符串
    									s0 = DataReduction(s1, s0);
    									if (s0 == "") {
    										return;
    									}
    									j = s0.length() - 1;
    									while (!Vt.contains(s0.charAt(j))) {
    										j--;
    									}
    									System.out.println("规约\t栈中\t" + s0);
    									i--;
    									break;
    								} else {
    									s1 = s0.charAt(j - 2) + s1;
    									j -= 2;
    									continue;
    								}
    							} else
    								System.out.println("error!");
    						}
    
    					}
    				} else if (c[Vt.indexOf(s0.charAt(j)) + 1][Vt.indexOf(s.charAt(i)) + 1] == '<'
    						|| c[Vt.indexOf(s0.charAt(j)) + 1][Vt.indexOf(s.charAt(i)) + 1] == '=') {
    					s0 += s.charAt(i);
    					System.out.println("移进\t栈中:\t" + s0);
    					j = s0.length() - 1;
    				} else {
    					System.out.println("error!");
    					return;
    				}
    
    			} else {
    				s0 += s.charAt(i);
    				System.out.println("移进\t栈中:\t" + s0);
    
    			}
    			i++;
    		} while (s.charAt(i - 1) != '#');
    		if (s0.length() == 3) {
    			System.out.println("接受");
    		}
    
    	}
    
    	public static void main(String[] args) throws IOException {
    		// TODO Auto-generated method stub
    		by02file bf = new by02file();
    		bf.getStr();
    		VnAndVt(bf);
    		System.out.println("文法非终结符:" + Vn);
    
    		System.out.println("文法终结符:" + Vt);
    		FirstVT();
    		LastVT();
    		N = Vt.size() + 1;
    		char[][] c = new char[N][N];
    		c = Table();
    		
    		Scanner sc = new Scanner(System.in);
    		String s = sc.nextLine();
    		s = "#" + s + "#";
    		analysis(c, s);
    
    //		System.out.println(Vn);
    	}
    
    }
    
    
    展开全文
  • 算符优先文法

    2020-11-28 16:40:58
    算符优先文法概述自底向上分析优先关系算符文法算符优先文法构造算符优先表的算法确定算符优先关系构造集合FIRSTVT(P)FIRSTVT(P)FIRSTVT(P)的算法构造集合LASTVT(P)LASTVT(P)LASTVT(P)的算法构造算符优先表实例算符...

    概述

    自底向上分析

    在自底向上分析中,分析过程的每一步都是从当前句型中选择一个可规约的子串,将它规约到某个非终结符。
    自底向上分析的关键问题是在分析过程中如何确定句柄或其他可规约串,也就是说如何知道何时在栈符号串中已形成某句型的句柄或其他可规约串。

    优先关系

    任何两个可能相继出现的终结符aabb可能有三种优先关系:

    • a<ba < baa的优先级低于bb
    • a=ba = baa的优先级等于bb
    • a>ba > baa的优先级大于bb

    算符文法

    一个文法,如果它的任一产生式的右部都不含两个相继(并列)的非终结符,即不含QR\dots QR \dots形式的产生式右部,则我们称该文法为算符文法。
    约定:

    • a,ba,b代表任意终结符
    • P,Q,RP,Q,R代表任意非终结符
    • '\dots'代表由终结符和非终结符组成的任意序列,包括空字

    算符优先文法

    假定GG是一个不含ϵ\epsilon-产生式的算符文法,对于任何一对终结符a,ba,b,我们说:

    • a=ba = b,当且仅当文法GG中含有形如PabP \rightarrow \dots ab \dotsPaQbP \rightarrow \dots aQb \dots的产生式;
    • a<ba < b,当且仅当GG中含有形如PaRP \rightarrow \dots aR \dots的产生式,而RbR \Rightarrow b\dotsRQbR \Rightarrow Qb\dots
    • a>ba > b,当且仅当GG中含有形如PRbP \rightarrow \dots Rb \dots的产生式,而RaR \Rightarrow \dots aRaQR \Rightarrow \dots aQ
      如果一个算符文法GG中的任何终结符对(a,b)(a,b)至多只满足a=ba<ba>ba = b、a < b、a > b这三个关系之一,则称GG是一个算符优先文法。

    构造算符优先表的算法

    确定算符优先关系

    • 确定满足关系==的所有终结符对
      • a=ba = b,当且仅当文法GG中含有形如PabP \rightarrow \dots ab \dotsPaQbP \rightarrow \dots aQb \dots的产生式
      • 通过检查GG的每个产生式的每个候选式,可找出所有满足a=ba = b的终结符对
    • 确定满足关系$ < $的所有终结符对
      • a<ba < b,当且仅当GG中含有形如PaRP \rightarrow \dots aR \dots的产生式,而RbR \Rightarrow b\dotsRQbR \Rightarrow Qb\dots
      • 构造FIRSTVT(P)={aPaFIRSTVT(P) = \{a|P \Rightarrow a\dotsRQa,aVTQVN}R \Rightarrow Qa\dots,a \in V_T且Q \in V_N\}
    • 确定满足关系$ > $的所有终结符对
      • a>ba > b,当且仅当GG中含有形如PRbP \rightarrow \dots Rb \dots的产生式,而RaR \Rightarrow \dots aRaQR \Rightarrow \dots aQ
      • 构造LASTVT(P)={aPaLASTVT(P) = \{a|P \Rightarrow \dots aRaQ,aVTQVN}R \Rightarrow \dots aQ,a \in V_T且Q \in V_N\}
    • 根据FIRSTVTFIRSTVTLASTVTLASTVT集合,检查每个产生式的候选式,确定满足关系<<>>的所有终结符对
      • 假定有个产生式的一个候选形为aP\dots aP \dots,那么,对任何bFIRSTVT(P)b \in FIRSTVT(P),有a<ba < b
      • 假定有个产生式的一个候选形为Pb\dots Pb \dots,那么,对任何aLASTVT(P)a \in LASTVT(P),有a>ba > b

    构造集合FIRSTVT(P)FIRSTVT(P)的算法

    反复使用下面两条规则构造集合FIRSTVT§

    • 若有产生式PaP \rightarrow a \dotsPQaP \rightarrow Qa \dots,则aFIRSTVT(P)a \in FIRSTVT(P)
    • aFIRSTVT(Q)a \in FIRSTVT(Q),且有产生式PQP \rightarrow Q \dots,则aFIRSTVT(P)a \in FIRSTVT(P)

    构造集合LASTVT(P)LASTVT(P)的算法

    反复使用下面两条规则构造集合LASTVT§

    • 若有产生式PaP \rightarrow \dots aPaQP \rightarrow \dots aQ,则aLASTVT(P)a \in LASTVT(P)
    • aLASTVT(Q)a \in LASTVT(Q),且有产生式PQP \rightarrow \dots Q,则aLASTVT(P)a \in LASTVT(P)

    构造算符优先表实例

    考虑下面的文法G(E)G(E):
    (1)EE+TTE \rightarrow E + T | T
    (2)TTFFT \rightarrow T * F | F
    (3)FPFPF \rightarrow P \uparrow F | P
    (4)P(E)iP \rightarrow (E) | i
    先计算FIRSTVTFIRSTVTLASTVTLASTVT

    • FIRSTVTFIRSTVT集:
      FIRSTVT(E)={+,,,(,i}FIRSTVT(E) = \{+,*,\uparrow,(,i\}
      FIRSTVT(T)={,,(,i}FIRSTVT(T) = \{*,\uparrow,(,i\}
      FIRSTVT(F)={,(,i}FIRSTVT(F) = \{\uparrow,(,i\}
      FIRSTVT(P)={(,i}FIRSTVT(P) = \{(,i\}
    • LASTVTLASTVT集:
      LASTVT(E)={+,,,),i}LASTVT(E) = \{+,*,\uparrow,),i\}
      LASTVT(T)={,,),i}LASTVT(T) = \{*,\uparrow,),i\}
      LASTVT(F)={,),i}LASTVT(F) = \{\uparrow,),i\}
      LASTVT(P)={),i}LASTVT(P) = \{),i\}
      然后构造算符优先表:
    ++ * \uparrow ii (( ))
    ++ > < < < < >
    * > > < < < >
    \uparrow > > < < < >
    ii > > > >
    (( < < < < < =
    )) > > > >

    算符优先分析算法

    最左素短语

    • 一个文法GG的句型的素短语是指这样一个短语,它至少含有一个终结符,并且,除它自身之外不再含任何更小的素短语
    • 最左素短语是指处于句型最左边的那个素短语

    最左素短语定理

    • 算符优先文法句型(括在两个#之间)的一般形式:
      #N1a1N2a2NnanNn+1\#N_1a_1N_2a_2\dots N_na_nN_{n+1}
      其中,aia_i都是终结符,NiN_i是可有可无的非终结符
    • 定理:一个算符优先文法GG的任何举行的最左素短语是满足如下条件的最左子串NjajNiaiNi+1N_ja_j\dots N_ia_iN_{i+1}
      • aj1<aja_{j-1} < a_j
      • aj=aj+1,,ai+1=aia_j = a_{j+1},\dots ,a_{i + 1} = a_i
      • a>ai+1a > a_{i + 1}

    流程

    • 使用一个符号栈SS,用它寄存终结符和非终结符,kk代表符号栈SS的使用深度
    • 在正确的情况下,算法工作完毕时,符号栈SS应呈现:#N#\# N \#

    评价

    • 算符优先分析结果产生的分析树,不一定是语法树
    • 优点:简单、快速
    • 缺点:可能错误接受非法句子
    展开全文
  • 编译原理 算符优先

    2010-04-23 22:58:37
    编译原理算符优先 编译原理算符优先 编译原理算符优先 编译原理算符优先 编译原理算符优先 编译原理算符优先
  • 算符优先算法

    2012-03-22 14:48:46
    算符优先算法, 算符优先算法(Java) 比较好的语法分析程序!
  • 算符优先分析

    2019-11-20 19:54:41
    算符优先分析 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 算法优先分析法是一种不太规范的自下而上分析方法,分析速度快,特别适用于表达式的分析。为了便于大家理解和实践算符优先分析法,...

    算符优先分析
    Time Limit: 1000 ms Memory Limit: 65536 KiB

    Problem Description
    算法优先分析法是一种不太规范的自下而上分析方法,分析速度快,特别适用于表达式的分析。为了便于大家理解和实践算符优先分析法,本题目先给出一个算符优先文法,请大家构造该文法的算符优先关系表。然后请对给定的输入串进行算符优先分析,判断其是否为该文法的一个句子。
    例如表达式文法:

    E→E+T |T
    
    T→T*F |F
    
        F→(E) | i
    

    该表达式文法是算符优先文法,其算符优先分析表为:
    在这里插入图片描述
    注意:构造算符优先分析表前,请先拓广文法,例如引入非终结符Q,令Q→#E#。

    Input
    输入数据有多行。
    第一行为一个整数n(n<=50),代表文法中产生式的个数,其中不包括拓广文法增加的产生式。
    接下来的n行,每行给出一个产生式。
    最后一行给出待分析的输入串,长度不超过50个符号。
    Output
    要求输出该文法的算符优先分析表,输出格式请参考上面的表格。
    算符优先分析表中算符的排列顺序为输入文法时终结符出现的顺序,#出现在最后。
    算符之间的优先关系,分别用=、<和>表示,代表相同、低于和高于的优先关系。
    第一行先输出一个空格,然后按顺序输出所有算符。
    第二行开始第一列为对应的算符,接着输出对应算法之间的优先关系。
    输出的最后一行表示对输入串的分析是否成功结束,如果成功分析结束输出Success,表示该输入串是文法的一个句子,否者输出Fail,表示该输入串不是文法的一个句子。
    Sample Input

    6
    E->E+T
    E->T
    T->T*F
    T->F
    F->(E)
    F->i
    i+i*i
    

    Sample Output

    +*()i#
    +><<><>
    *>><><>
    (<<<=< 
    )>> > >
    i>> > >
    #<<< <=
    Success
    
    #include <iostream>
    #include <string.h>
    using namespace std;
    string str[30][100];
    char st[30][100],st1[30][100],order[60],st2[100][2],st3[100],st4[100][2];
    int num[30],num1[30],bj1[30],bj2[150],sum[100][100],st3l,st4l;
    char Stack[100],sta[100];
    int top,top1,end1,number,bj0[150];
    void print(char a)
    {
        int b=a-'A';
        for(int i=0;i<num[b];i++)
        {
            if(st[b][i]>='A'&&st[b][i]<='Z')
                print(st[b][i]);
            else st3[st3l++]=st[b][i];
        }
    }
    void print1(char a)
    {
        int b=a-'A';
        for(int i=0;i<num1[b];i++)
        {
            if(st1[b][i]>='A'&&st1[b][i]<='Z')
                print1(st1[b][i]);
            else st3[st3l++]=st1[b][i];
        }
    }
    void print_stack()
    {
        for(int i=0;i<=top;i++)
            cout<<Stack[i];
    }
    void print_sta()
    {
        if(top1+1==end1) cout<<"#";
        for(int i=top1+1;i<end1;i++)
            cout<<sta[i];
    }
    int main()
    {
        int i,j,k,kk,m,n,nn,mm,bj,l,ll,bj3;
        char s;
        while(cin>>m)
        {
            memset(bj0,0,sizeof(bj0));    //test9
            l=ll=bj3=st4l=0;
            for(i=0;i<150;i++)
                bj2[i]=0;
            for(i=0;i<30;i++)
            {
                num[i]=0; num1[i]=0; bj1[i]=0;
            }
            string str1,str2;
            for(i=0;i<m;i++)
            {
                cin>>str1;
                if(i==0) s=str1[0];
                mm=str1[0]-'A';
                n=str1.size();
                str2=str1.substr(3,n);
                char *p=&str2[0];
    
                //const char *d="|";
                //p=strtok(str3,d);
                //while(p!=NULL)
                //{
                    bj=0;
                    nn=strlen(p);
                    if(nn==1)
                    {
                        st[mm][num[mm]]=p[0];num[mm]++;
                        st1[mm][num1[mm]]=p[0];num1[mm]++;
                        if(p[0]<'A'||p[0]>'Z')
                        {
    
                            bj0[p[0]]=1;     //test9
                            if(p[0]!='#')
                            {
                                order[l++]=p[0]; bj2[p[0]]=1;
                            }
                            else bj3=1;
                        }
                    }
                    else
                    {
                        int aa=0;char bb;
                        for(j=0;j<nn;j++)
                        {
                             if(p[j]<'A'||p[j]>'Z')
                             {
                                 bj0[p[j]]=nn;       //test9
                                 if(aa==0)
                                 {
                                     bb=p[j];aa=1;
                                 }
                                 else
                                 {
                                     st4[st4l][0]=bb;st4[st4l++][1]=p[j];
                                 }
                                 if(bj2[p[j]]==0)
                                 {
                                     if(p[j]!='#')
                                     {
                                         order[l++]=p[j];bj2[p[j]]=1;
                                     }
                                     else bj3=1;
                                 }
                                 if(bj!=1)
                                 {
                                     bj=1;st[mm][num[mm]]=p[j];num[mm]++;
                                 }
                             }
                             if(j>0)
                             {
                                 if((p[j]<'A'||p[j]>'Z')&&p[j-1]>='A'&&p[j-1]<='Z')
                                 {
                                     st2[ll][0]=p[j-1];st2[ll++][1]=p[j];continue;
                                 }
                                 if((p[j-1]<'A'||p[j-1]>'Z')&&p[j]>='A'&&p[j]<='Z')
                                 {
                                     st2[ll][0]=p[j-1];st2[ll++][1]=p[j];
                                 }
                             }
                        }
                        if(bj==0)
                        {
                            st[mm][num[mm]]=p[0];num[mm]++;
                        }
                        bj=0;
                        for(j=nn-1;j>=0;j--)
                        {
                             if(p[j]<'A'||p[j]>'Z')
                             {
                                 bj=1;st1[mm][num1[mm]]=p[j];num1[mm]++;break;
                             }
                        }
                        if(bj==0)
                        {
                            st1[mm][num[mm]]=p[0];num1[mm]++;
                        }
                    }
                    //p=strtok(NULL,d);
                //}
            }
            order[l++]='#';bj2['#']=1;
            st2[ll][0]='#';st2[ll++][1]=s;
            st2[ll][0]=s;st2[ll++][1]='#';
            memset(sum,0,sizeof(sum));
            for(i=0;i<ll;i++)
            {
                st3l=0;
                if(st2[i][0]>='A'&&st2[i][0]<='Z')
                {
                    print1(st2[i][0]);
                    for(j=0;j<l;j++)
                    {
                        if(st2[i][1]==order[j])
                        {
                            for(k=0;k<st3l;k++)
                            {
                                for(kk=0;kk<l;kk++)
                                {
                                    if(st3[k]==order[kk])
                                    {
                                        sum[kk][j]=3;break;
                                    }
                                }
                            }
                            break;
                        }
                    }
                }
                else
                {
                    print(st2[i][1]);
                    for(j=0;j<l;j++)
                    {
                        if(st2[i][0]==order[j])
                        {
                            for(k=0;k<st3l;k++)
                            {
                                for(kk=0;kk<l;kk++)
                                {
                                    if(st3[k]==order[kk])
                                    {
                                        sum[j][kk]=1;break;
                                    }
                                }
                            }
                            break;
                        }
                    }
                }
            }
            for(i=0;i<st4l;i++)
            {
                for(j=0;j<l;j++)
                {
                    if(st4[i][0]==order[j])
                    {
                        for(k=0;k<l;k++)
                        {
                            if(st4[i][1]==order[k])
                            {
                                sum[j][k]=2;break;
                            }
                        }
                        break;
                    }
                }
            }
            sum[l-1][l-1]=2;
            //test9
            cin>>sta;
            cout<<" ";
            for(i=0;i<l;i++)
                cout<<order[i];
            cout<<endl;
            for(i=0;i<l;i++)
            {
                cout<<order[i];
                for(j=0;j<l;j++)
                {
                    if(sum[i][j]==1)
                        cout<<"<";
                    else if(sum[i][j]==2)
                        cout<<"=";
                    else if(sum[i][j]==3)
                        cout<<">";
                    else cout<<" ";
                }
                cout<<endl;
            }
            int flag=0;
            end1=strlen(sta);
            sta[end1]='#';end1++;
            top=number=top1=0;
            Stack[0]='#';
            bj0['#']=1;
            /*for(i=0;i<150;i++)
                cout<<bj0[i]<<" ";
            cout<<endl;*/
            for(i=0;i<end1;i++)
            {
                if(bj0[sta[i]]==0)
                {
                    flag=1;break;
                }
            }
            while(top>=0)
            {
                if(flag==1) break;
                //number++;
                //cout<<number<<"\t";
                //print_stack();
                mm=-1;
                for(i=top;i>=0;i--)
                {
                    if(Stack[i]<'A'||Stack[i]>'Z')
                    {
                        mm=i;break;
                    }
                }
                if(mm==-1) {flag=1;break;}
                k=kk=-1;
                for(i=0;i<l;i++)
                {
                    if(order[i]==Stack[mm])
                    {
                        k=i;
                    }
                    if(order[i]==sta[top1])
                    {
                        kk=i;
                    }
                }
                if(k==-1||kk==-1)
                {
                    flag=1;break;
                }
                //cout<<"\t";
                if(sum[k][kk]==1)
                {
                    //cout<<"<\t";
                }
                else if(sum[k][kk]==2)
                {
                    //cout<<"=\t";
                }
                else if(sum[k][kk]==3)
                {
                    //cout<<">\t";
                }
                else
                {
                    flag=1;break;
                }
                //if(sta[top1]!='#') cout<<sta[top1]<<"\t";
                //else cout<<" \t";
                //print_sta();
                //cout<<"\t";
                if(sum[k][kk]==1)
                {
                    //cout<<"移进"<<endl;
                    top1++;
                    Stack[++top]=sta[top1-1];
                }
                else if(sum[k][kk]==2)
                {
                    if(sta[top1]!='#')
                    {
                        //cout<<"移进"<<endl;
                        top1++;
                        Stack[++top]=sta[top1-1];
                    }
                    else if(Stack[mm]=='#')
                    {
                        //cout<<"接受"<<endl;
                        break;
                    }
                }
                else if(sum[k][kk]==3)
                {
                    //cout<<"归约"<<endl;
                    top-=(bj0[Stack[mm]]-1);
                    Stack[top]='N';
                }
            }
            if(flag==0) cout<<"Success"<<endl;
            else cout<<"Fail"<<endl;
        }
        return 0;
    }
    
    展开全文
  • 1. 已知算符优先关系矩阵如下表:+*i()#+><<<>>*>><<>>i>>>>(<<<<=)>>>>#<<<<=写出符号串(i+i)*i#的算符优先分析过程。2.接...

    1. 已知算符优先关系矩阵如下表:

    +

    *

    i

    (

    )

    #

    +

    >

    <

    <

    <

    >

    >

    *

    >

    >

    <

    <

    >

    >

    i

    >

    >

    >

    >

    (

    <

    <

    <

    <

    =

    )

    >

    >

    >

    >

    #

    <

    <

    <

    <

    =

    写出符号串(i+i)*i#的算符优先分析过程。

    2.接上个作业(P121练习1),完成4),5)两个步骤。

    1)计算FIRSTVT和 LASTVT。

    2)找三种关系对。

    3)构造算符优先关系表。

    4)是否算符优先文法?

    5)给出输入串(a,(a,a))#的算符优先分析过程。

    3.尝试编写自下而上的语法分析程序。

    可以只写表达式部分。

    4.写出a+b*(c-d)+e/(c-d)↑n 的逆波兰表达式,三元式,四元式。

    ----------------------------------------------------------------------------------------------------------------------------------------------

    (i+i)*i#

    关系

    输入串

    动作

    1

    #

    <

    ( i + i ) * i #

    移进

    # (

    <

    i + i ) * i #

    移进

    # ( i

    >

    + i ) * i #

    归约

    # ( N

    <

    + i ) * i #

    移进

    # ( N +

    <

    i ) * i #

    移进

    # ( N + i

    >

    ) * i #

    归约

    # ( N + N

    >

    ) * i #

    归约

    # ( N

    =

    ) * i #

    移进

    # ( N )

    >

    * i #

    归约

    # N

    <

    * i #

    移进

    # N *

    <

    i #

    移进

    # N * i

    #

    接受

    2.已知文法:

    S -> a | ^ | (T)

    T -> T , S | S

    1)计算FIRSTVT和LASTVT。

    2)找三种关系对。

    3)构造算符优先关系表。

    4)是否算符优先文法?

    5)给出输入串(a,(a,a))#的算符优先分析过程。

    因为:

    E -> #S#

    S -> a | ^ | (T)

    T -> T , S | S

    (1) 计算FIRSTVT和LASTVT。

    FisrtVT(S) = { a , ^ , ( }

    FirstVT(T) = { a , ^ , ( , , }

    LastVT(S) = { a , ^ , ) }

    LastVT(T) = { a , ^ , ) , , }

    (2) 找三种关系对。

    = :

    #S#

    (T)

    < :

    #S

    (T

    ,S

    > :

    S#

    T)

    T,

    (3) 构造算符优先关系表。

    a

    ^

    (

    )

    ,

    #

    a

    >

    >

    >

    ^

    >

    >

    >

    (

    <

    <

    <

    =

    <

    <

    )

    >

    >

    >

    ,

    <

    <

    <

    <

    <

    <

    #

    <

    <

    <

    <

    <

    =

    (4)算!

    (5)(a,(a,a))#

    关系

    输入串

    动作

    #

    <

    ( a , ( a , a ) ) #

    移进

    # (

    <

    a , ( a , a ) ) #

    移进

    # ( a

    >

    , ( a , a ) ) #

    归约

    # ( N

    <

    , ( a , a ) ) #

    移进

    # ( N ,

    <

    ( a , a ) ) #

    移进

    # ( N , (

    <

    a , a ) ) #

    移进

    # ( N , ( a

    >

    , a ) ) #

    归约

    # ( N , ( N

    <

    , a ) ) #

    移进

    # ( N , ( N ,

    <

    a ) ) #

    移进

    # ( N , ( N , a

    >

    ) ) #

    归约

    # ( N , ( N , N

    <

    ) ) #

    移进

    # ( N , ( N , N )

    >

    ) #

    归约

    # ( N , ( N )

    <

    ) #

    移进

    # ( N , ( N ) )

    #

    接受

    3.尝试编写自下而上的语法分析程序。

    可以只写表达式部分。

    4.写出a+b*(c-d)+e/(c-d)↑n 的逆波兰表达式,三元式,四元式。

    逆波兰表达式

    abcd-*+ ecd-n↑/ +

    三元式

    (1) ( - , c , d )

    (2) ( * , b , (1) )

    (3) ( + , a , (2) )

    (4) ( - , c , d )

    (5) (↑, (4) , n)

    (6) ( / , e / (5) )

    (7) ( + , (3) , (6) )

    四元式

    (1) ( - , c , d , t1 )

    (2) ( * , b , t1 , t2 )

    (3) ( + , a , t2 , t3 )

    (4) ( - , c , d , t4 )

    (5) (↑, t4 , n ,t5)

    (6) ( / , e , t5 , t6 )

    (7) ( + , t3 , t6 )

    展开全文
  • 算符优先代码

    2011-12-29 19:36:35
    编译原理中的算符优先算法~
  • 算符优先

    2012-07-12 16:15:42
    编译原理,firstvt ,lastvt集和算符优先表!MFC实现的!
  • 算符优先系列之(二)算符优先关系表 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 学过编译原理的菊苣们都知道算符优先文法,作为一个有点深度的分析方法,我们怎么能只止步于理论呢,实践才是...
  • 算符优先分析 编译原理算符优先分析 编译原理算符优先分析 编译原理算符优先分析 编译原理算符优先分析 编译原理算符优先分析 编译原理算符优先分析 编译原理
  • 算符优先PPT

    2012-06-20 09:32:51
    算符优先课程PPT 有需要的看看 我们老师自己做的 不一定符合其他学校的教材
  • 算符优先设计报告 算符优先设计报告 算符优先设计报告 算符优先设计报告
  • 算符优先分析程序

    2016-05-22 23:00:21
    编写一个算符优先分析程序,能实现以下功能: 1. 输入文法,判断是否为算符文法。 2. 构造并输出文法的每个非终结符的FIRSTVT和LASTVT。 3. 构造并输出算符优先分析表,判断是否为算符优先文法,如果不是提示无法进行...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,097
精华内容 438
关键字:

优先算符