Java实现简单词法、语法分析器

1、词法分析器实现

词法分析器是编译器中的一个关键组件，用于将源代码解析成词法单元。

1. 词法分析器的结构与组件：

   • 通常，词法分析器由两个主要组件构成：扫描器（Scanner）和记号流（Token Stream）。
   • 扫描器负责从源代码中读取字符流，并按照预定义的词法规则将字符流解析为词法单元。
   • 扫描器通常由一个有限自动机实现，用于根据词法规则进行状态转换，识别出不同的词法单元。

2. 有限自动机的代码实现：

   • 有限自动机是实现词法分析器的关键技术之一。它根据输入的字符进行状态转换，并输出识别的词法单元。
   • 以下是一个用Python实现的简单有限自动机示例：

     # 定义有限自动机的状态
     def isAlpha(ch):return ch.isalpha()def isDigit(ch):return ch.isdigit()def scan(attr, i, s, n):# 核心子程序（语法分析程序）# 实现词法分析逻辑，根据字符流识别词法单元# ...pass
     

3. 错误处理与诊断：

   • 在词法分析过程中，可能会遇到无法识别的字符或不符合词法规则的输入。
   • 词法分析器通常需要进行错误处理与诊断，例如跳过无法识别的字符、发出错误提示或错误修复。

import java.io.*;
import java.util.*;/*** 词法分析器实现*/
public class LexicalAnalyzer {private static final Map<String, String> word = new HashMap<>();private static final List<Node> aa = new ArrayList<>();static class Node {String id;String s;Node(String id, String s) {this.id = id;this.s = s;}}public static void mapInit() {word.put("main", "0");word.put("return", "3");word.put("if", "4");word.put("else", "5");word.put("int", "6");word.put("char", "7");word.put("(", "8");word.put(")", "9");word.put("{", "10");word.put("}", "11");word.put(",", "12");word.put(";", "13");word.put("=", "14");word.put("!=", "15");word.put(">", "16");word.put("<", "17");word.put(">=", "18");word.put("<=", "19");word.put("==", "20");word.put("+", "21");word.put("*", "22");word.put("/", "23");}public static void main(String[] args) {mapInit();char ch;int len = 0;StringBuilder word1;String str;System.out.println("-----------------词法分析器-----------------");Scanner scanner = new Scanner(System.in);System.out.println("请输入源文件地址：(路径中请不要包含中文)");String dir = scanner.nextLine();System.out.println("请输入目标文件地址：");String targetDir = scanner.nextLine();try (BufferedReader infile = new BufferedReader(new FileReader(dir));BufferedWriter outfile = new BufferedWriter(new FileWriter(targetDir))) {StringBuilder buf = new StringBuilder();while ((ch = (char) infile.read()) != (char) -1) {buf.append(ch);}str = buf.toString();int csize = str.length();for (int i = 0; i < csize; i++) {while (str.charAt(i) == ' ' || str.charAt(i) == '\n') i++;if (Character.isAlphabetic(str.charAt(i))) {word1 = new StringBuilder(String.valueOf(str.charAt(i++)));while (Character.isAlphabetic(str.charAt(i)) || Character.isDigit(str.charAt(i))) {word1.append(str.charAt(i++));}if (word.containsKey(word1.toString())) {System.out.println("(" + word.get(word1.toString()) + "," + word1 + ")");aa.add(new Node(word.get(word1.toString()), word1.toString()));} else {System.out.println("(1," + word1 + ")");aa.add(new Node("1", word1.toString()));}i--;} else if (Character.isDigit(str.charAt(i))) {word1 = new StringBuilder(String.valueOf(str.charAt(i++)));while (Character.isDigit(str.charAt(i))) {word1.append(str.charAt(i++));}if (Character.isAlphabetic(str.charAt(i))) {System.out.println("error1!");break;} else {System.out.println("(2," + word1 + ")");aa.add(new Node("2", word1.toString()));}i--;} else if (str.charAt(i) == '<') {word1 = new StringBuilder(String.valueOf(str.charAt(i++)));if (str.charAt(i) == '>') {word1.append(str.charAt(i));System.out.println("(" + word.get(word1.toString()) + "," + word1 + ")");aa.add(new Node(word.get(word1.toString()), word1.toString()));} else if (str.charAt(i) == '=') {word1.append(str.charAt(i));System.out.println("(" + word.get(word1.toString()) + "," + word1 + ")");aa.add(new Node(word.get(word1.toString()), word1.toString()));} else if (str.charAt(i) != ' ' || !Character.isDigit(str.charAt(i)) || !Character.isAlphabetic(str.charAt(i))) {System.out.println("(" + word.get(word1.toString()) + "," + word1 + ")");aa.add(new Node(word.get(word1.toString()), word1.toString()));} else {System.out.println("error2!");break;}i--;} else if (str.charAt(i) == '>') {word1 = new StringBuilder(String.valueOf(str.charAt(i++)));if (str.charAt(i) == '=') {word1.append(str.charAt(i));System.out.println("(" + word.get(word1.toString()) + "," + word1 + ")");aa.add(new Node(word.get(word1.toString()), word1.toString()));} else if (str.charAt(i) != ' ' || !Character.isDigit(str.charAt(i)) || !Character.isAlphabetic(str.charAt(i))) {System.out.println("(" + word.get(word1.toString()) + "," + word1 + ")");aa.add(new Node(word.get(word1.toString()), word1.toString()));} else {System.out.println("error3!");break;}i--;} else if (str.charAt(i) == ':') {word1 = new StringBuilder(String.valueOf(str.charAt(i++)));if (str.charAt(i) == '=') {word1.append(str.charAt(i));System.out.println("(" + word.get(word1.toString()) + "," + word1 + ")");aa.add(new Node(word.get(word1.toString()), word1.toString()));} else if (str.charAt(i) != ' ' || !Character.isDigit(str.charAt(i)) || !Character.isAlphabetic(str.charAt(i))) {System.out.println("(" + word.get(word1.toString()) + "," + word1 + ")");aa.add(new Node(word.get(word1.toString()), word1.toString()));} else {System.out.println("error4!");break;}i--;} else {word1 = new StringBuilder(String.valueOf(str.charAt(i)));if (word.containsKey(word1.toString())) {System.out.println("(" + word.get(word1.toString()) + "," + word1 + ")");aa.add(new Node(word.get(word1.toString()), word1.toString()));}}}for (Node node : aa) {outfile.write("(" + node.id + "," + node.s + ")\n");}} catch (IOException e) {e.printStackTrace();}System.out.println("输入任意键关闭");scanner.nextLine();}
}

2、语法分析器实现

语法分析器是编译器中的关键组件，用于检查源代码是否遵循编程语言的语法规则。

1. 语法分析器的结构与组件：

   • 自顶向下语法分析器从文法的开始符号出发，试图推导出与输入单词串相匹配的句子。
   • 通常，自顶向下语法分析器由递归下降分析器构成，它根据预定义的文法规则逐步构建语法树。
   • 语法树表示源代码的层次结构，其中每个节点对应一个语法规则或终结符。

2. 递归下降分析器的代码实现：

   • 递归下降分析器是自顶向下语法分析的一种常见方法。
   • 以下是一个简单的递归下降分析器示例（使用Python）：

     # 定义文法规则
     def expr():term()while lookahead == '+':match('+')term()def term():factor()while lookahead == '*':match('*')factor()def factor():if lookahead.isdigit():match(lookahead)elif lookahead == '(':match('(')expr()match(')')# 初始化
     lookahead = input()  # 输入的单词串# 匹配函数
     def match(expected):if lookahead == expected:lookahead = input()else:raise SyntaxError("Unexpected token: " + lookahead)# 开始分析
     expr()
     

3. 错误处理与诊断：

   • 语法分析过程中，可能会遇到不符合文法规则的输入。
   • 递归下降分析器通常需要进行错误处理与诊断，例如报告无法识别的符号或缺失的符号。

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;/*** 语法分析器实现*/
public class Parser {public static final String PATH = "C:\\code\\idea\\CompilePrinciple\\src\\grammar.txt";private static String START;private static HashSet<String> VN, VT;private static HashMap<String, ArrayList<ArrayList<String>>> MAP;private static HashMap<String, String> oneLeftFirst;private static HashMap<String, HashSet<String>> FIRST, FOLLOW;private static HashMap<String, String> preMap;public static void main(String[] args) {init();identifyVnVt(readFile(new File(PATH)));reformMap();findFirst();findFollow();if (isLL1()) {preForm();System.out.println("请输入要分析的单词串:");Scanner in = new Scanner(System.in);printAutoPre(in.nextLine());in.close();}}// 变量初始化private static void init() {VN = new HashSet<>();VT = new HashSet<>();MAP = new HashMap<>();FIRST = new HashMap<>();FOLLOW = new HashMap<>();oneLeftFirst = new HashMap<>();preMap = new HashMap<>();}// 判断是否是LL(1)文法private static boolean isLL1() {System.out.println("\n正在判断是否是LL(1)文法....");boolean flag = true;for (String key : VN) {ArrayList<ArrayList<String>> list = MAP.get(key);if (list.size() > 1)for (int i = 0; i < list.size(); i++) {String aLeft = String.join("", list.get(i).toArray(new String[0]));for (int j = i + 1; j < list.size(); j++) {String bLeft = String.join("", list.get(j).toArray(new String[0]));if (aLeft.equals("ε") || bLeft.equals("ε")) {HashSet<String> retainSet = new HashSet<>(FIRST.get(key));if (FOLLOW.get(key) != null)retainSet.retainAll(FOLLOW.get(key));if (!retainSet.isEmpty()) {flag = false;System.out.println("\tFIRST(" + key + ") ∩ FOLLOW(" + key + ") = {"+ String.join("、", retainSet.toArray(new String[0])) + "}");break;} else {System.out.println("\tFIRST(" + key + ") ∩ FOLLOW(" + key + ") = φ");}} else {HashSet<String> retainSet = new HashSet<>(FIRST.get(key + "→" + aLeft));retainSet.retainAll(FIRST.get(key + "→" + bLeft));if (!retainSet.isEmpty()) {flag = false;System.out.println("\tFIRST(" + aLeft + ") ∩ FIRST(" + bLeft + ") = {"+ String.join("、", retainSet.toArray(new String[0])) + "}");break;} else {System.out.println("\tFIRST(" + aLeft + ") ∩ FIRST(" + bLeft + ") = φ");}}}}}if (flag)System.out.println("\t是LL(1)文法,继续分析!");elseSystem.out.println("\t不是LL(1)文法,退出分析!");return flag;}// 构建预测分析表FORMprivate static void preForm() {HashSet<String> set = new HashSet<>(VT);set.remove("ε");String[][] FORM = new String[VN.size() + 1][set.size() + 2];Iterator<String> itVn = VN.iterator();Iterator<String> itVt = set.iterator();for (int i = 0; i < FORM.length; i++)for (int j = 0; j < FORM[0].length; j++) {if (i == 0 && j > 0) {if (itVt.hasNext()) {FORM[i][j] = itVt.next();}if (j == FORM[0].length - 1)FORM[i][j] = "#";}if (j == 0 && i > 0) {if (itVn.hasNext())FORM[i][j] = itVn.next();}if (i > 0 && j > 0) {String oneLeftKey = FORM[i][0] + "$" + FORM[0][j];FORM[i][j] = oneLeftFirst.get(oneLeftKey);}}for (int i = 1; i < FORM.length; i++) {String oneLeftKey = FORM[i][0] + "$ε";if (oneLeftFirst.containsKey(oneLeftKey)) {HashSet<String> followCell = FOLLOW.get(FORM[i][0]);for (String vt : followCell) {for (int j = 1; j < FORM.length; j++)for (int k = 1; k < FORM[0].length; k++) {if (FORM[j][0].equals(FORM[i][0]) && FORM[0][k].equals(vt))FORM[j][k] = oneLeftFirst.get(oneLeftKey);}}}}// 打印预测表,并存于Map的数据结构中用于快速查找System.out.println("\n该文法的预测分析表为：");for (int i = 0; i < FORM.length; i++) {for (int j = 0; j < FORM[0].length; j++) {if (FORM[i][j] == null)System.out.print(" " + "\t");else {System.out.print(FORM[i][j] + "\t");if (i > 0 && j > 0) {String[] tmp = FORM[i][j].split("→");preMap.put(FORM[i][0] + FORM[0][j], tmp[1]);}}}System.out.println();}System.out.println();}// 输入的单词串分析推导过程public static void printAutoPre(String str) {System.out.println(str + "的分析过程:");Queue<String> queue = new LinkedList<>();for (int i = 0; i < str.length(); i++) {String t = str.charAt(i) + "";if (i + 1 < str.length() && (str.charAt(i + 1) == '\'' || str.charAt(i + 1) == '’')) {t += str.charAt(i + 1);i++;}queue.offer(t);}queue.offer("#");Stack<String> stack = new Stack<>();stack.push("#");stack.push(START);boolean isSuccess = false;int step = 1;while (!stack.isEmpty()) {String left = stack.peek();String right = queue.peek();if (left.equals(right) && right.equals("#")) {isSuccess = true;System.out.println((step++) + "\t#\t#\t" + "分析成功");break;}if (left.equals(right)) {String stackStr = String.join("", stack.toArray(new String[0]));String queueStr = String.join("", queue.toArray(new String[0]));System.out.println((step++) + "\t" + stackStr + "\t" + queueStr + "\t匹配成功" + left);stack.pop();queue.poll();continue;}if (preMap.containsKey(left + right)) {String stackStr = String.join("", stack.toArray(new String[0]));String queueStr = String.join("", queue.toArray(new String[0]));System.out.println((step++) + "\t" + stackStr + "\t" + queueStr + "\t用" + left + "→"+ preMap.get(left + right) + "," + right + "逆序进栈");stack.pop();String tmp = preMap.get(left + right);for (int i = tmp.length() - 1; i >= 0; i--) {String t = "";if (tmp.charAt(i) == '\'' || tmp.charAt(i) == '’') {t = tmp.charAt(i-1)+""+tmp.charAt(i);i--;}else {t=tmp.charAt(i)+"";}if (!t.equals("ε"))stack.push(t);}continue;}break;}if (!isSuccess)System.out.println((step++) + "\t#\t#\t" + "分析失败");}// 符号分类private static void identifyVnVt(ArrayList<String> list) {START = list.get(0).charAt(0) + "";for (String oneline : list) {String[] vnvt = oneline.split("→");String left = vnvt[0].trim();VN.add(left);ArrayList<ArrayList<String>> mapValue = new ArrayList<>();ArrayList<String> right = new ArrayList<>();for (int j = 0; j < vnvt[1].length(); j++) {if (vnvt[1].charAt(j) == '|') {VT.addAll(right);mapValue.add(right);right = null;right = new ArrayList<>();continue;}if (j + 1 < vnvt[1].length() && (vnvt[1].charAt(j + 1) == '\'' || vnvt[1].charAt(j + 1) == '’')) {right.add(vnvt[1].charAt(j) + "" + vnvt[1].charAt(j + 1));j++;} else {right.add(vnvt[1].charAt(j) + "");}}VT.addAll(right);mapValue.add(right);MAP.put(left, mapValue);}VT.removeAll(VN);System.out.println("\nVn集合:\t{" + String.join("、", VN.toArray(new String[0])) + "}");System.out.println("Vt集合:\t{" + String.join("、", VT.toArray(new String[0])) + "}");}// 求每个非终结符号的FIRST集合 和 分解单个产生式的FIRST集合private static void findFirst() {System.out.println("\nFIRST集合:");for (String s : VN) {HashSet<String> firstCell = new HashSet<>();ArrayList<ArrayList<String>> list = MAP.get(s);for (ArrayList<String> listCell : list) {HashSet<String> firstCellOne = new HashSet<>();String oneLeft = String.join("", listCell.toArray(new String[0]));if (VT.contains(listCell.get(0))) {firstCell.add(listCell.get(0));firstCellOne.add(listCell.get(0));oneLeftFirst.put(s + "$" + listCell.get(0), s + "→" + oneLeft);} else {boolean[] isVn = new boolean[listCell.size()];isVn[0] = true;int p = 0;while (isVn[p]) {if (VT.contains(listCell.get(p))) {firstCell.add(listCell.get(p));firstCellOne.add(listCell.get(p));oneLeftFirst.put(s + "$" + listCell.get(p), s + "→" + oneLeft);break;}String vnGo = listCell.get(p);Stack<String> stack = new Stack<>();stack.push(vnGo);while (!stack.isEmpty()) {ArrayList<ArrayList<String>> listGo = MAP.get(stack.pop());for (ArrayList<String> listGoCell : listGo) {if (VT.contains(listGoCell.get(0))) {if (listGoCell.get(0).equals("ε")) {if (!s.equals(START)) {firstCell.add(listGoCell.get(0));firstCellOne.add(listGoCell.get(0));oneLeftFirst.put(s + "$" + listGoCell.get(0), s + "→" + oneLeft);}if (p + 1 < isVn.length) {isVn[p + 1] = true;}} else {firstCell.add(listGoCell.get(0));firstCellOne.add(listGoCell.get(0));oneLeftFirst.put(s + "$" + listGoCell.get(0), s + "→" + oneLeft);}} else {stack.push(listGoCell.get(0));}}}p++;if (p > isVn.length - 1)break;}}FIRST.put(s + "→" + oneLeft, firstCellOne);}FIRST.put(s, firstCell);System.out.println("\tFIRST(" + s + ")={" + String.join("、", firstCell.toArray(new String[0])) + "}");}}private static void findFollow() {System.out.println("\nFOLLOW集合:");Iterator<String> it = VN.iterator();HashMap<String, HashSet<String>> keyFollow = new HashMap<>();ArrayList<HashMap<String, String>> vn_VnList = new ArrayList<>();HashSet<String> vn_VnListLeft = new HashSet<>();HashSet<String> vn_VnListRight = new HashSet<>();keyFollow.put(START, new HashSet<>() {private static final long serialVersionUID = 1L;{add("#");}});while (it.hasNext()) {String key = it.next();ArrayList<ArrayList<String>> list = MAP.get(key);ArrayList<String> listCell;if (!keyFollow.containsKey(key)) {keyFollow.put(key, new HashSet<>());}keyFollow.toString();for (ArrayList<String> strings : list) {listCell = strings;for (int j = 1; j < listCell.size(); j++) {HashSet<String> set = new HashSet<>();if (VT.contains(listCell.get(j))) {set.add(listCell.get(j));if (keyFollow.containsKey(listCell.get(j - 1)))set.addAll(keyFollow.get(listCell.get(j - 1)));keyFollow.put(listCell.get(j - 1), set);}}for (int j = 0; j < listCell.size() - 1; j++) {if (VN.contains(listCell.get(j)) && VN.contains(listCell.get(j + 1))) {HashSet<String> set = new HashSet<>(FIRST.get(listCell.get(j + 1)));set.remove("ε");if (keyFollow.containsKey(listCell.get(j)))set.addAll(keyFollow.get(listCell.get(j)));keyFollow.put(listCell.get(j), set);}}for (int j = 0; j < listCell.size(); j++) {HashMap<String, String> vn_Vn;if (VN.contains(listCell.get(j)) && !listCell.get(j).equals(key)) {boolean isAllNull = false;if (j + 1 < listCell.size())for (int k = j + 1; k < listCell.size(); k++) {if ((FIRST.containsKey(listCell.get(k)) && FIRST.get(listCell.get(k)).contains("ε"))) {isAllNull = true;} else {isAllNull = false;break;}}if (j == listCell.size() - 1) {isAllNull = true;}if (isAllNull) {vn_VnListLeft.add(key);vn_VnListRight.add(listCell.get(j));boolean isHaveAdd = false;for (int x = 0; x < vn_VnList.size(); x++) {HashMap<String, String> vn_VnListCell = vn_VnList.get(x);if (!vn_VnListCell.containsKey(key)) {vn_VnListCell.put(key, listCell.get(j));vn_VnList.set(x, vn_VnListCell);isHaveAdd = true;break;} else {if (vn_VnListCell.get(key).equals(listCell.get(j))) {isHaveAdd = true;break;}}}if (!isHaveAdd) {vn_Vn = new HashMap<>();vn_Vn.put(key, listCell.get(j));vn_VnList.add(vn_Vn);}}}}}}keyFollow.toString();vn_VnListLeft.removeAll(vn_VnListRight);Queue<String> keyQueue = new LinkedList<>(vn_VnListLeft);while (!keyQueue.isEmpty()) {String keyLeft = keyQueue.poll();for (int t = 0; t < vn_VnList.size(); t++) {HashMap<String, String> vn_VnListCell = vn_VnList.get(t);if (vn_VnListCell.containsKey(keyLeft)) {HashSet<String> set = new HashSet<>();if (keyFollow.containsKey(keyLeft))set.addAll(keyFollow.get(keyLeft));if (keyFollow.containsKey(vn_VnListCell.get(keyLeft)))set.addAll(keyFollow.get(vn_VnListCell.get(keyLeft)));keyFollow.put(vn_VnListCell.get(keyLeft), set);keyQueue.add(vn_VnListCell.get(keyLeft));vn_VnListCell.remove(keyLeft);vn_VnList.set(t, vn_VnListCell);}}}FOLLOW = keyFollow;for (String key : keyFollow.keySet()) {HashSet<String> f = keyFollow.get(key);System.out.println("\tFOLLOW(" + key + ")={" + String.join("、", f.toArray(new String[0])) + "}");}}private static void reformMap() {boolean isReForm = false;Set<String> keys = new HashSet<>(MAP.keySet());Iterator<String> it = keys.iterator();ArrayList<String> nullSign = new ArrayList<>();nullSign.add("ε");while (it.hasNext()) {String left = it.next();boolean flag = false;ArrayList<ArrayList<String>> rightList = MAP.get(left);ArrayList<String> oldRightCell = new ArrayList<>();ArrayList<ArrayList<String>> newLeftNew = new ArrayList<>();for (ArrayList<String> strings : rightList) {ArrayList<String> newRightCell = new ArrayList<>();if (strings.get(0).equals(left)) {for (int j = 1; j < strings.size(); j++) {newRightCell.add(strings.get(j));}flag = true;newRightCell.add(left + "'");newLeftNew.add(newRightCell);} else {oldRightCell.addAll(strings);oldRightCell.add(left + "'");}}if (flag) {isReForm = true;newLeftNew.add(nullSign);MAP.put(left + "'", newLeftNew);VN.add(left + "'");VT.add("ε");ArrayList<ArrayList<String>> newLeftOld = new ArrayList<>();newLeftOld.add(oldRightCell);MAP.put(left, newLeftOld);}}if (isReForm) {System.out.println("消除文法的左递归:");Set<String> kSet = new HashSet<>(MAP.keySet());for (String k : kSet) {ArrayList<ArrayList<String>> leftList = MAP.get(k);System.out.print("\t" + k + "→");for (int i = 0; i < leftList.size(); i++) {System.out.print(String.join("", leftList.get(i).toArray(new String[0])));if (i + 1 < leftList.size())System.out.print("|");}System.out.println();}}MAP.toString();}public static ArrayList<String> readFile(File file) {System.out.println("从文件读入的文法为:");ArrayList<String> result = new ArrayList<>();try {BufferedReader br = new BufferedReader(new FileReader(file));String s = null;while ((s = br.readLine()) != null) {System.out.println("\t" + s);result.add(s.trim());}br.close();} catch (Exception e) {e.printStackTrace();}return result;}
}

E→TE'
E'→+E|ε
T→FT'
T'→T|ε
F→PF'
F'→*F'|ε
P→(E)|^|a|b