本文共 24525 字,大约阅读时间需要 81 分钟。
设计一个 C 语言的预处理程序,将C语言中所有的宏常量进行计算,并生成另外一个文件,将宏常量展开和计算的结果全部显示出来,最后将定义的宏在源程序中全部进行替换。
例如,源程序为:
#include#define ADDR_START 0x20480000#define ADDR_A ADDR_START + 0x04#define ADDR_B ADDR_START + 15#define BUFFER_SIZE 1024#define BUFFER_END ADDR_START + BUFFER_SIZE – 1#define PI 3.14void main(){ float r, l; scanf(“%f”, &r); l = 2 * PI *r; memset(ADDR_START, BUFFER_SIZE, 0x00);}
替换后为:
#include#define ADDR_START 0x20480000#define ADDR_A 0x20480004#define ADDR_B 0x2048000F#define BUFFER_SIZE 1024#define BUFFER_END 0x204803FF#define PI 3.14void main(){ float r, l; scanf(“%f”, &r); l = 2 * 3.14 *r; memset(0x20480000, 1024, 0x00);}
我们知道,C 语言中运算符的优先级为:[] > (! ~) > (* / %) > (+ -) > (<< >>) > (> >= < <=) > (== !=) > & > ^ > | > && > || > ?: > (= += -= /= *= %=) > ,(逗号)。
为保证依据设计的文法求得的算符优先矩阵符合上述要求,根据求算符优先矩阵的方法,从优先级别最低的逗号开始逐次往高级别推导,这样算出来的算符优先矩阵就是符合预期的。 比如& < = = == ==,则文法设计为 G->G&H,G->H,H->H==I。可以看到 FirstVt(G) = {&, = = == ==},FirstVt(H) = { = = == ==},而 G->G&H,所以& < FirstVt(H),即& < ==。同理根据 LastVt 可得= = = = > &。 表达式文法设计过程中有以下几点值得考虑:本次课设表达式的计算思路为:将原表达式转为逆波兰式,再进行计算,不使用属性文法计算。
事先写好三个待分析的源程序文件,点击 Open 按钮,可选择打开哪一个源程序,打开后,会马上进行词法分析,得到各种有意义字符串的种别号,然后根据种别号对源程序设置不同的颜色,例如大小括号为红色,define 以及 include 为粉红色等等(参考了 VS CODE 的CPP 程序界面)。
接下来点击 Lexical 按钮,开始进行词法分析。词法分析实际上在源程序打开后就已经结束了,点击 Lexical 按钮只是做一个展示功能。 词法分析程序的主要任务是对构成源程序的字符串从左到右扫描,逐个字符地读入源程序字符并按照构词规则切分成一个一个具有独立意义的单词。并确定其属性(如关键字、宏常量、标识符等)。 词法分析中将单词分为以下几类:词法分析得到的结果是一个初始符号表,每一个表项都是一个向量,每一个向量表示一个有意义的字符串,比如(SIZE, MACRO, X + Y),表明 SIZE 是一个宏常量,其表达式为 X +Y。又如(+, 4)表明加法运算符的种别号为 4。
接下来点击 Grammar 按钮,即可进行语法分析。语法分析首先分析的是宏常量的表达式, 根据词法分析得到的符号表,找到每一个宏常量的表达式(可以是一个常数,也可以是一个很复杂的表达式),然后将每个表达式中的变量以及常数都用小写字母 i 替代,因为设计的文法当中默认用 i 表示操作数。例如 SIZE + X / Y 变为 i+i/i,然后用算符优先文法来规约这个表达式,并判断是否合法。 宏常量的表达式语法分析完毕后,紧接着分析主函数当中的表达式,对于主函数中的表达式,与宏常量表达式一样,也将除开运算符以外的所有变量用 i 表示,然后用上述定义的表达式文法进行规约分析。分析完毕后,所有的分析过程在点击 Grammar 按钮的一瞬间都会显示在模拟器界面上。 语法分析结束后,最后进行的是表达式计算。点击 Calculate 按钮,即可对所有经过语法分析并且合法的表达式进行计算。计算时首先将表达式转成逆波兰式,然后利用栈对其进行计算。每计算完一个表达式,就将符号表进行更新,方便下一步的计算,所有表达式的计算过程会显示在模拟器界面上。 表达式计算完毕之后,开始对源程序进行替换,替换过程与计算过程同步进行。扫描源程序,对宏常量以及相关表达式出现的地方,用计算得到的值进行替换,该值通过扫描符号表得到。替换完毕后,再根据结果变换程序字符串的颜色,显示在模拟器界面上。系统中包含一个主界面 MainActivity 以及五个子类,分别介绍如下:
点击词法分析后,编辑器上缩,下方的显示栏显示词法分析结果,如下所示:
点击语法分析按钮,可对源程序中所有表达式进行语法分析,如下所示:
点击表达式计算按钮,可将计算过程显示出来。另外可以看到,计算结果已经在源程序中替换。
package com.example.compiler;import androidx.appcompat.app.AppCompatActivity;import android.graphics.Color;import android.os.Bundle;import android.text.Spannable;import android.text.SpannableStringBuilder;import android.text.style.ForegroundColorSpan;import android.view.View;import android.view.ViewGroup;import android.widget.EditText;import android.widget.PopupWindow;import android.widget.RadioButton;import android.widget.RadioGroup;import android.widget.RelativeLayout;import android.widget.TextView;import com.example.compiler.Utils.CheckAllExpression;import com.example.compiler.Utils.Compute;import com.example.compiler.Utils.Lexical_Analysis;import java.io.FileNotFoundException;import java.util.ArrayList;import java.util.Map;import java.util.Vector;public class MainActivity extends AppCompatActivity { private RadioGroup rg_tab_bar; private RadioButton rb_open; private RadioButton rb_lexer; private RadioButton rb_grammar; private RadioButton rb_calculate; private View div; private EditText editText; private EditText editTextComp; private Lexical_Analysis lexical_analysis; private PopupWindow popupWindow; public String resourceString = ""; //源程序 public String tab = ""; public VectorresVectors = new Vector<>(); @Override protected void onCreate(Bundle savedInstanceState) { super.onCreate(savedInstanceState); setContentView(R.layout.activity_main); bindViews(); rg_tab_bar.setOnCheckedChangeListener(new RadioGroup.OnCheckedChangeListener() { @Override public void onCheckedChanged(RadioGroup group, int checkedId) { switch (checkedId) { case R.id.rb_open: rb_open.setOnClickListener(new View.OnClickListener() { @Override public void onClick(View v) { View view=getLayoutInflater().inflate(R.layout.layout_pop,null); TextView textView1 = view.findViewById(R.id.s1); textView1.setOnClickListener(new View.OnClickListener() { @Override public void onClick(View v) { popupWindow.dismiss(); resourceString = getResources().getString(R.string.source_1); //lexical_analysis.show(); SpannableStringBuilder builder = convert(resourceString); editText.setText(builder); } }); TextView textView2 = view.findViewById(R.id.s2); textView2.setOnClickListener(new View.OnClickListener() { @Override public void onClick(View v) { popupWindow.dismiss(); resourceString = getResources().getString(R.string.source_2); //lexical_analysis.show(); SpannableStringBuilder builder = convert(resourceString); editText.setText(builder); } }); TextView textView3 = view.findViewById(R.id.s3); textView3.setOnClickListener(new View.OnClickListener() { @Override public void onClick(View v) { popupWindow.dismiss(); resourceString = getResources().getString(R.string.source_3); SpannableStringBuilder builder = convert(resourceString); editText.setText(builder); } }); popupWindow=new PopupWindow(view, rb_open.getWidth(), ViewGroup.LayoutParams.WRAP_CONTENT); popupWindow.setOutsideTouchable(true); popupWindow.setFocusable(true); popupWindow.showAsDropDown(rb_open); } }); break; case R.id.rb_lexer: //词法分析 Lexical(); break; case R.id.rb_grammar: //语法分析每一个跟宏有关的式子是否是合法的 Grammar(); break; case R.id.rb_calculate: //计算并替换所有表达式 try { Calculate(); } catch (FileNotFoundException e) { e.printStackTrace(); } break; } } }); } private void bindViews() { tab = getResources().getString(R.string.tab); rg_tab_bar = findViewById(R.id.rg_tab_bar); rb_open = findViewById(R.id.rb_open); rb_lexer = findViewById(R.id.rb_lexer); rb_grammar = findViewById(R.id.rb_grammar); rb_calculate = findViewById(R.id.rb_calculate); div = findViewById(R.id.div_tab_bar); editText = findViewById(R.id.edit); editTextComp = findViewById(R.id.comp); } private SpannableStringBuilder convert(String x) { String yy = getResources().getString(R.string.source_1); String []yyStrings = x.split("\n"); for(int i = 0; i < yyStrings.length; i++) { if(yyStrings[i].contains("main")) { break; } else { yyStrings[i] = yyStrings[i].trim(); } } x = ""; for(int i = 0; i temp = new ArrayList<>(); for(Vector vector : lexical_analysis.resVector) { if(vector.get(1).equals("MACRO")) { temp.add(vector.get(0)); } } System.out.println("temp = " + temp.size()); for(String xString : temp) { int index = 0 - xString.length(); while(index != -1) { index = x.indexOf(xString, index + xString.length()); if(index != -1) { builder.setSpan(new ForegroundColorSpan(Color.rgb(26, 107, 230)), index, index + xString.length(), Spannable.SPAN_EXCLUSIVE_EXCLUSIVE); } } } return builder; } //词法分析 private void Lexical() { lexical_analysis = new Lexical_Analysis(resourceString); lexical_analysis.initNum(); lexical_analysis.mainFunc(); String finalString = ""; for(Vector vector : lexical_analysis.resVector) { //System.out.print("("); String temp = "("; for(int j = 0; j < vector.size() - 1; j++) { //System.out.print(vector.get(j) + "," + " "); temp += (vector.get(j) + "," + " "); } //System.out.println(vector.get(vector.size() - 1) + ")"); temp += (vector.get(vector.size() - 1) + ")" + "\n"); finalString += temp; } RelativeLayout.LayoutParams lp = (RelativeLayout.LayoutParams) editText.getLayoutParams(); lp.height = 500; editText.setLayoutParams(lp); RelativeLayout.LayoutParams lp1 = (RelativeLayout.LayoutParams) editTextComp.getLayoutParams(); lp1.height = 2000; editTextComp.setLayoutParams(lp1); finalString = "词法分析结果为:" + "\n" + finalString; SpannableStringBuilder builder1 = new SpannableStringBuilder(finalString); builder1.setSpan(new ForegroundColorSpan(Color.RED), 0, 8, Spannable.SPAN_EXCLUSIVE_EXCLUSIVE);//指定索引a到b-1的字符 editTextComp.setText(builder1); } //语法分析 private void Grammar() { CheckAllExpression checkAllExpression = new CheckAllExpression(resourceString, tab); checkAllExpression.checkMacro(); checkAllExpression.checkMain(); RelativeLayout.LayoutParams lp = (RelativeLayout.LayoutParams) editText.getLayoutParams(); lp.height = 500; editText.setLayoutParams(lp); RelativeLayout.LayoutParams lp1 = (RelativeLayout.LayoutParams) editTextComp.getLayoutParams(); lp1.height = 1800; editTextComp.setLayoutParams(lp1); String finalString = checkAllExpression.resString; finalString = "语法分析结果为:" + "\n" + finalString; SpannableStringBuilder builder1 = new SpannableStringBuilder(finalString); builder1.setSpan(new ForegroundColorSpan(Color.RED), 0, 8, Spannable.SPAN_EXCLUSIVE_EXCLUSIVE);//指定索引a到b-1的字符 editTextComp.setText(builder1); } private void Calculate() throws FileNotFoundException { lexical_analysis = new Lexical_Analysis(resourceString); lexical_analysis.initNum(); lexical_analysis.mainFunc(); resVectors = lexical_analysis.resVector; String showProcess = ""; CheckAllExpression checkAllExpression = new CheckAllExpression(resourceString, ""); checkAllExpression.checkMacro(); checkAllExpression.checkMain(); Map expMap = checkAllExpression.expMap; //存储表达式 for(Map.Entry entry : expMap.entrySet()) { String keyString = entry.getKey(); String valueString = entry.getValue(); //System.out.println(keyString + ":" + valueString); if(!keyString.equals("mainExp")) { String waitString = valueString.replace(" ", ""); showProcess += ("正在计算的宏常量:" + keyString + "\n"); showProcess += ("宏常量表达式:" + valueString + "\n"); System.out.println("正在计算的宏常量:" + keyString); System.out.println("宏常量表达式:" + valueString); //System.out.println(waitString); waitString = Compute.hex2dec(waitString); //System.out.println(waitString); Compute compute = new Compute(waitString, resourceString); compute.lexical_Analysis.resVector = resVectors; String suffixString = compute.mid2suffix(); showProcess += ("逆波兰式:" + suffixString + "\n"); System.out.println("逆波兰式:" + suffixString); //System.out.println("suffix:" + suffixString); String resString = compute.calculateSuffix(suffixString); showProcess += compute.processString; showProcess += ("计算结果:" + resString + "\n" + "\n"); System.out.println("计算结果:" + resString); System.out.println(); for(int i = 0; i < resVectors.size(); i++) { Vector vector = resVectors.get(i); if(vector.get(0).equals(keyString)) { //System.out.println("当前被替换的宏常量为:" + keyString + " " + resString); resVectors.get(i).set(2, resString); }else { continue; } } } } //计算主函数中表达式 System.out.println("计算主函数中表达式:"); ArrayList mainExpArrayList = checkAllExpression.mainExpArrayList; for(String valueString : mainExpArrayList) { if(valueString.contains("PI")) { continue; } String waitString = valueString.replace(" ", ""); showProcess += ("正在计算的表达式:" + valueString + "\n"); System.out.println("正在计算的表达式:" + valueString); //System.out.println(waitString); waitString = Compute.hex2dec(waitString); //System.out.println(waitString); Compute compute = new Compute(waitString, resourceString); compute.lexical_Analysis.resVector = resVectors; String suffixString = compute.mid2suffix(); showProcess += ("逆波兰式:" + suffixString); System.out.println("逆波兰式:" + suffixString); //System.out.println("suffix:" + suffixString); String resString = compute.calculateSuffix(suffixString); showProcess += ("计算结果:" + resString + "\n" + "\n"); System.out.println("计算结果:" + resString); System.out.println(); for(int i = 0; i < resVectors.size(); i++) { Vector vector = resVectors.get(i); if(waitString.contains(vector.get(0)) && vector.get(1).equals("var") || waitString.contains(vector.get(0)) && vector.get(1).equals("const")) { //先找到resString中的答案 int index = resString.indexOf('='); String real = resString.substring(index + 2, resString.length()); resVectors.get(i).add(real); resVectors.get(i).set(1, "const"); } } } //replace Macro for(int i = 0; i < resourceString.length(); i++) { if(resourceString.charAt(i) == '#' && i + 1 < resourceString.length() && resourceString.charAt(i + 1) == 'd') { //当前位置为#define i += 7; //当前位置为e后面的空格 while(resourceString.charAt(i) == ' ') { i++; }//结束后位置为一个宏变量的开始符号 int j = i; int k = i; while(resourceString.charAt(i) != ' ') { i++; }//当前位置为变量后第一个空格 String macroString = resourceString.substring(j, i); //System.out.println("待替换的变量为:" + macroString); String replaceString = ""; for(Vector vector : resVectors) { if(vector.get(0).equals(macroString)) { replaceString = (String) vector.get(2); //System.out.println(macroString + "替换为:" + replaceString); break; } } while(resourceString.charAt(i) == ' ') { i++; }//当前结束为表达式第一个字符的位置 j = i; while(resourceString.charAt(i) != '\n') { i++; } StringBuilder builder = new StringBuilder(resourceString); builder.replace(j, i, replaceString); resourceString = builder.toString(); i = k; continue; } } int mainIndex = 0; for(int i = 0; i < resourceString.length(); i++) { if(resourceString.substring(i, i + 4).equals("main")) { mainIndex = i; break; } } String finalX = resourceString.substring(0, mainIndex); String finalY = resourceString.substring(mainIndex, resourceString.length()); //替换主函数中的宏 boolean flag = false; while(true) { flag = false; for(Vector vector : resVectors) { if(vector.get(1).equals("MACRO")) { String macroString = (String) vector.get(0); int index = finalY.indexOf(macroString); if(index != -1) { flag = true; StringBuilder builder = new StringBuilder(finalY); builder.replace(index, index + macroString.length(), (String) vector.get(2)); finalY = builder.toString(); } } } if(!flag) { break; } } //替换主函数中的表达式 int index = 0; resourceString = finalX + finalY; String []subStrings = resourceString.split("\n"); for(int i = 0; i < subStrings.length; i++) { if(subStrings[i].contains("define")) { continue; } if(subStrings[i].contains("=") && !subStrings[i].contains("3.14")) { int j = 0; //System.out.println("主函数中待替换: " + subStrings[i]); while (subStrings[i].charAt(j) == '\t' || subStrings[i].charAt(j) == ' ') { j++; }//当前位置变量起始位置 int k = j; while (subStrings[i].charAt(j) != ' ') { j++; }//当前位置变量结束 String varString = subStrings[i].substring(k, j); String replaceString = ""; //search value for(Vector vector : resVectors) { if(vector.get(0).equals(varString)) { replaceString = vector.get(2 + index++); break; } } subStrings[i] = subStrings[i].substring(0, k) + varString + " = " + replaceString; } } resourceString = ""; for(String xString : subStrings) { resourceString += (xString + "\n"); } System.out.println("替换结束了"); System.out.println(resourceString); RelativeLayout.LayoutParams lp = (RelativeLayout.LayoutParams) editText.getLayoutParams(); lp.height = 1000; editText.setLayoutParams(lp); RelativeLayout.LayoutParams lp1 = (RelativeLayout.LayoutParams) editTextComp.getLayoutParams(); lp1.height = 1300; editTextComp.setLayoutParams(lp1); SpannableStringBuilder builder = convert(resourceString); editText.setText(builder); editTextComp.setText(showProcess); }}
CheckAllExpression.java
/** * Date : 2021/1/5 12:30 * Author : KI * File : CheckAllExpression * Desc : check expression * Motto : Hungry And Humble */package com.example.compiler.Utils;import java.util.ArrayList;import java.util.Arrays;import java.util.LinkedHashMap;import java.util.Map;import java.util.Vector;public class CheckAllExpression { public MapexpMap = new LinkedHashMap (); String tab = ""; public String resString = ""; public ArrayList mainExpArrayList = new ArrayList<>(); Lexical_Analysis lexical_Analysis; Grammatical_Analysis grammatical_Analysis; Operator_Precedence operator_Precedence; ArrayList Vt = new ArrayList (Arrays.asList( ",", "=", "+=", "-=", "*=", "/=", "%=", "||", "&&", "|", "^", "&", "=", "!=", ">", ">=", "<", "<=", "<<", ">>", "+", "-", "*", "/", "%", "!", "[]", "(", ")", "i", "#")); //规定一个顺序 ArrayList Vn = new ArrayList (Arrays.asList( "S", "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N")); String []proRule = { "S->#A#", "A->A,B", "A->B", "B->C=B", "B->C+=B", "B->C-=B", "B->C*=B", "B->C/=B", "B->C%=B", "B->C", "C->C||D", "C->D", "D->D&&E", "D->E", "E->E|F", "E->F", "F->F^G", "F->G", "G->G&H", "G->H", "H->H=I", "H->H!=I", "H->I", "I->I>J", "I->I>=J", "I->I I<=J", "I->J", "J->J< J>>K", "J->K", "K->K+L", "K->K-L", "K->L", "L->L*M", "L->L/M", "L->L%M", "L->M", "M->!M", "M->N", "N->N[]N", "N->(A)", "N->i"}; String procedure = ""; public CheckAllExpression(String procedure, String tab) { this.tab = tab; lexical_Analysis = new Lexical_Analysis(procedure); lexical_Analysis.initNum(); lexical_Analysis.mainFunc(); this.procedure = procedure; grammatical_Analysis = new Grammatical_Analysis(); operator_Precedence = new Operator_Precedence(Vn, Vt, proRule, tab); } public String convert(String xString) { xString = xString.trim(); String resString = ""; for(int i = 0; i < xString.length(); i++) { char char1 = xString.charAt(i); if(char1 == '(') { xString = xString.substring(0, i + 1) + " " + xString.substring(i + 1, xString.length()); i++; } if(char1 == ')') { xString = xString.substring(0, i) + " " + xString.substring(i, xString.length()); i++; } } String list[] = xString.split(" "); for(String yString : list) { if(yString.equals("(") || yString.equals(")") || Vt.contains(yString)) { resString += yString; }else { resString += "i"; } } return resString; } public boolean checkMacro() { //convert("(ADD_t + (FR * tt + 100))"); //先检查所有宏表达式定义的 boolean resFlag = true; String []lineStrings = procedure.split("\n"); ArrayList tempArrayList = new ArrayList (); for(int k = 0; k < lineStrings.length; k++) { String xString = lineStrings[k]; if(!xString.contains("define")) { continue; } if(xString.contains("define") && k + 1 < lineStrings.length && !lineStrings[k + 1].contains("main")) { //说明为宏定义语句 for(int i = 0; i < lexical_Analysis.resVector.size(); i++) { Vector vector = lexical_Analysis.resVector.get(i); if(vector.get(1).equals("MACRO") && !tempArrayList.contains(vector.get(0))) { tempArrayList.add(vector.get(0)); String waitString = vector.get(2); //待分析的表达式 resString += ("待分析的宏常量:" + vector.get(0) + "\n"); resString += ("待分析的表达式:" + waitString + "\n"); System.out.println("待分析的宏常量:" + vector.get(0)); System.out.println("待分析的表达式:" + waitString); expMap.put(vector.get(0), waitString); waitString = convert(waitString); resString += ("转换后:" + waitString + "\n"); System.out.println("转换后:" + waitString); operator_Precedence.processString = ""; boolean flag = operator_Precedence.check(waitString); resString += operator_Precedence.processString; operator_Precedence.processString = ""; if(flag) { resString += ("Successful!" + "\n" + "\n"); System.out.println("Successful!"); System.out.println(); }else { resFlag = false; resString += ("failed!" + "\n" + "\n"); System.out.println("failed!"); System.out.println(); } } } } } return resFlag; } public boolean checkMain() { boolean resFlag = true; String []lineStrings = procedure.split("\n"); flag:for(String xString : lineStrings) { if(xString.contains("define") || xString.contains("include") || xString.contains("main") || xString.contains("{") || xString.contains("}")) { continue; } for(String yString : lexical_Analysis.keyWord) { if(xString.contains(yString)) { continue flag; } } for(String yString : lexical_Analysis.function) { if(xString.contains(yString)) { continue flag; } } resString += ("待分析的句子:" + xString + "\n"); System.out.println("待分析的句子:" + xString); mainExpArrayList.add(xString); xString = convert(xString); resString += ("转换后:" + xString + "\n"); System.out.println("转换后:" + xString); operator_Precedence.processString = ""; boolean flag = operator_Precedence.check(xString); resString += operator_Precedence.processString; operator_Precedence.processString = ""; if(flag) { resString += ("Successful!" + "\n" + "\n"); System.out.println("Successful!"); System.out.println(); }else { resString += ("failed!" + "\n" + "\n"); resFlag = false; System.out.println("failed!"); System.out.println(); } } return resFlag; }}
转载地址:http://vmiqf.baihongyu.com/