顶针 东莞网站建设,有网站做淘宝客,教做家常菜的视频网站,狮岭箱包外发加工网1、词法分析器实现
词法分析器是编译器中的一个关键组件#xff0c;用于将源代码解析成词法单元。 词法分析器的结构与组件#xff1a; 通常#xff0c;词法分析器由两个主要组件构成#xff1a;扫描器#xff08;Scanner#xff09;和记号流#xff08;Token Stream用于将源代码解析成词法单元。 词法分析器的结构与组件 通常词法分析器由两个主要组件构成扫描器Scanner和记号流Token Stream。扫描器负责从源代码中读取字符流并按照预定义的词法规则将字符流解析为词法单元。扫描器通常由一个有限自动机实现用于根据词法规则进行状态转换识别出不同的词法单元。 有限自动机的代码实现 有限自动机是实现词法分析器的关键技术之一。它根据输入的字符进行状态转换并输出识别的词法单元。以下是一个用Python实现的简单有限自动机示例# 定义有限自动机的状态
def isAlpha(ch):return ch.isalpha()def isDigit(ch):return ch.isdigit()def scan(attr, i, s, n):# 核心子程序语法分析程序# 实现词法分析逻辑根据字符流识别词法单元# ...pass错误处理与诊断 在词法分析过程中可能会遇到无法识别的字符或不符合词法规则的输入。词法分析器通常需要进行错误处理与诊断例如跳过无法识别的字符、发出错误提示或错误修复。
import java.io.*;
import java.util.*;/*** 词法分析器实现*/
public class LexicalAnalyzer {private static final MapString, String word new HashMap();private static final ListNode 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、语法分析器实现
语法分析器是编译器中的关键组件用于检查源代码是否遵循编程语言的语法规则。 语法分析器的结构与组件 自顶向下语法分析器从文法的开始符号出发试图推导出与输入单词串相匹配的句子。通常自顶向下语法分析器由递归下降分析器构成它根据预定义的文法规则逐步构建语法树。语法树表示源代码的层次结构其中每个节点对应一个语法规则或终结符。 递归下降分析器的代码实现 递归下降分析器是自顶向下语法分析的一种常见方法。以下是一个简单的递归下降分析器示例使用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()错误处理与诊断 语法分析过程中可能会遇到不符合文法规则的输入。递归下降分析器通常需要进行错误处理与诊断例如报告无法识别的符号或缺失的符号。
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 HashSetString VN, VT;private static HashMapString, ArrayListArrayListString MAP;private static HashMapString, String oneLeftFirst;private static HashMapString, HashSetString FIRST, FOLLOW;private static HashMapString, 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) {ArrayListArrayListString 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(ε)) {HashSetString 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 {HashSetString 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() {HashSetString set new HashSet(VT);set.remove(ε);String[][] FORM new String[VN.size() 1][set.size() 2];IteratorString itVn VN.iterator();IteratorString 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)) {HashSetString 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 的分析过程:);QueueString 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(#);StackString 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 {ttmp.charAt(i);}if (!t.equals(ε))stack.push(t);}continue;}break;}if (!isSuccess)System.out.println((step) \t#\t#\t 分析失败);}// 符号分类private static void identifyVnVt(ArrayListString list) {START list.get(0).charAt(0) ;for (String oneline : list) {String[] vnvt oneline.split(→);String left vnvt[0].trim();VN.add(left);ArrayListArrayListString mapValue new ArrayList();ArrayListString 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) {HashSetString firstCell new HashSet();ArrayListArrayListString list MAP.get(s);for (ArrayListString listCell : list) {HashSetString 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);StackString stack new Stack();stack.push(vnGo);while (!stack.isEmpty()) {ArrayListArrayListString listGo MAP.get(stack.pop());for (ArrayListString 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集合:);IteratorString it VN.iterator();HashMapString, HashSetString keyFollow new HashMap();ArrayListHashMapString, String vn_VnList new ArrayList();HashSetString vn_VnListLeft new HashSet();HashSetString vn_VnListRight new HashSet();keyFollow.put(START, new HashSet() {private static final long serialVersionUID 1L;{add(#);}});while (it.hasNext()) {String key it.next();ArrayListArrayListString list MAP.get(key);ArrayListString listCell;if (!keyFollow.containsKey(key)) {keyFollow.put(key, new HashSet());}keyFollow.toString();for (ArrayListString strings : list) {listCell strings;for (int j 1; j listCell.size(); j) {HashSetString 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))) {HashSetString 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) {HashMapString, 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) {HashMapString, 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);QueueString keyQueue new LinkedList(vn_VnListLeft);while (!keyQueue.isEmpty()) {String keyLeft keyQueue.poll();for (int t 0; t vn_VnList.size(); t) {HashMapString, String vn_VnListCell vn_VnList.get(t);if (vn_VnListCell.containsKey(keyLeft)) {HashSetString 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()) {HashSetString f keyFollow.get(key);System.out.println(\tFOLLOW( key ){ String.join(、, f.toArray(new String[0])) });}}private static void reformMap() {boolean isReForm false;SetString keys new HashSet(MAP.keySet());IteratorString it keys.iterator();ArrayListString nullSign new ArrayList();nullSign.add(ε);while (it.hasNext()) {String left it.next();boolean flag false;ArrayListArrayListString rightList MAP.get(left);ArrayListString oldRightCell new ArrayList();ArrayListArrayListString newLeftNew new ArrayList();for (ArrayListString strings : rightList) {ArrayListString 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(ε);ArrayListArrayListString newLeftOld new ArrayList();newLeftOld.add(oldRightCell);MAP.put(left, newLeftOld);}}if (isReForm) {System.out.println(消除文法的左递归:);SetString kSet new HashSet(MAP.keySet());for (String k : kSet) {ArrayListArrayListString 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 ArrayListString readFile(File file) {System.out.println(从文件读入的文法为:);ArrayListString 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
