Experimental purpose
1) Understand the principle of LR (0) analysis;
2) Master the method of LR (0) analyzing and identifying symbol string;
3) Master the application of LR (0) analysis table;
4) Be able to write programs to realize LR (0) syntax analysis;
Test requirements:
1) Understand and master the judgment and analysis process of LR(0) grammar.
2) This experiment requires the design of an LR(0) parser.
3) This experiment is required to be completed independently, and it is not allowed to copy other people's experimental results.
4) Implemented in C# or JAVA language;
Submission of test report and test procedure:
1) Before the deadline of the experimental task, the word documents of the experimental program and experimental report are packaged and uploaded to the superstar network teaching platform.
2) The compressed file package of each student is named: student number_ Name_ 5.rar
3) The compressed package shall contain two folders, one for storing programs and the other for storing word files of experimental reports.
Experiment content:
1. Design LR(0) syntax parser.
Select the grammar of textbook P136 and LR(0) analysis table of P136
2. Apply the designed analysis program to perform LR(0) analysis on the input string bccd# and output the analysis process and results (as shown in table 6.4 of P137)
Verify the correctness of the analysis program.
Design requirements:
(1) In order to facilitate grammar input, the ">" in the production formula can be replaced by ":"
(2) Non terminators and terminators can be stored in one-dimensional arrays VN[100] and VT[100], grammar G[S] can be stored in two-dimensional array G[100][100], and the ACTION table and conversion table of LR(1) are represented by ACTION and GOTO arrays respectively.
(3) LR(0) analysis table is table 6.3 of textbook P136.
The main analysis process is as follows:
Set ip to point to the first symbol of the input string w
Set S to the top of the stack
a is the symbol pointed to by ip
Repeat begin
if ACTION[S,a]=Sj
then
Begin push J, a
ip forward(Point to next input symbol)
end
else
if ACTION[S,a]=rj (reduce a - > e with the production of article j)
then
begin
According to the length of production formula | e |,
Stack the corresponding symbols and states
Make the current stack top state S'
push GOTO[S', A] and A (stack)
end
else
if ACTION[s,a]=acc
then
return (successful)
else
error
end.
repeat
public class Main {
//Non Terminator
private static final String[] vn = new String[]{"S\\'", "A", "B", "E"};
//Terminator
private static final String[] vt = new String[]{"a", "b", "c", "d", "#"};
//State stack
private static final Stack<String> state = new Stack();
//Symbol stack
private static final Stack<String> symbol = new Stack();
//Input stack
private static final Stack<Character> input = new Stack();
//Grammar
private static final List<String> grammar = new ArrayList<>();
private static final HashMap<String, String> grammarMap = new HashMap<>();
//Analysis table
private static final HashMap<String, HashMap<String, String>> analysisTable = new HashMap<>();
//Initialization data
public static void initData() {
grammar.add("S\\':E");
grammar.add("E:aA");
grammar.add("E:bB");
grammar.add("A:cA");
grammar.add("A:d");
grammar.add("B:cB");
grammar.add("B:d");
HashMap<String, String> zero = new HashMap<>() {
{
put("a", "S2");
put("b", "S3");
put("c", "null");
put("d", "null");
put("#", "null");
put("E", "1");
put("A", "null");
put("B", "null");
}
};
HashMap<String, String> one = new HashMap<>() {
{
put("a", "null");
put("b", "null");
put("c", "null");
put("d", "null");
put("#", "acc");
put("E", "null");
put("A", "null");
put("B", "null");
}
};
HashMap<String, String> two = new HashMap<>() {
{
put("a", "null");
put("b", "null");
put("c", "S4");
put("d", "S10");
put("#", "null");
put("E", "null");
put("A", "6");
put("B", "null");
}
};
HashMap<String, String> three = new HashMap<>() {
{
put("a", "null");
put("b", "null");
put("c", "S5");
put("d", "S11");
put("#", "null");
put("E", "null");
put("A", "null");
put("B", "7");
}
};
HashMap<String, String> four = new HashMap<>() {
{
put("a", "null");
put("b", "null");
put("c", "S4");
put("d", "S10");
put("#", "null");
put("E", "null");
put("A", "8");
put("B", "null");
}
};
HashMap<String, String> five = new HashMap<>() {
{
put("a", "null");
put("b", "null");
put("c", "S5");
put("d", "S11");
put("#", "null");
put("E", "null");
put("A", "null");
put("B", "9");
}
};
HashMap<String, String> six = new HashMap<>() {
{
put("a", "r1");
put("b", "r1");
put("c", "r1");
put("d", "r1");
put("#", "r1");
put("E", "null");
put("A", "null");
put("B", "null");
}
};
HashMap<String, String> seven = new HashMap<>() {
{
put("a", "r2");
put("b", "r2");
put("c", "r2");
put("d", "r2");
put("#", "r2");
put("E", "null");
put("A", "null");
put("B", "null");
}
};
HashMap<String, String> eight = new HashMap<>() {
{
put("a", "r3");
put("b", "r3");
put("c", "r3");
put("d", "r3");
put("#", "r3");
put("E", "null");
put("A", "null");
put("B", "null");
}
};
HashMap<String, String> nine = new HashMap<>() {
{
put("a", "r5");
put("b", "r5");
put("c", "r5");
put("d", "r5");
put("#", "r5");
put("E", "null");
put("A", "null");
put("B", "null");
}
};
HashMap<String, String> ten = new HashMap<>() {
{
put("a", "r4");
put("b", "r4");
put("c", "r4");
put("d", "r4");
put("#", "r4");
put("E", "null");
put("A", "null");
put("B", "null");
}
};
HashMap<String, String> eleven = new HashMap<>() {
{
put("a", "r6");
put("b", "r6");
put("c", "r6");
put("d", "r6");
put("#", "r6");
put("E", "null");
put("A", "null");
put("B", "null");
}
};
analysisTable.put("0", zero);
analysisTable.put("1", one);
analysisTable.put("2", two);
analysisTable.put("3", three);
analysisTable.put("4", four);
analysisTable.put("5", five);
analysisTable.put("6", six);
analysisTable.put("7", seven);
analysisTable.put("8", eight);
analysisTable.put("9", nine);
analysisTable.put("10", ten);
analysisTable.put("11", eleven);
}
public static void main(String[] args) {
initData();
String content = "";
Scanner scanner = new Scanner(System.in);
ArrayList<Character> characters = new ArrayList<>();
while (true) {
symbol.clear();
state.clear();
symbol.push("#");
state.push("0");
System.out.println("Please enter the string to analyze(Please do not include spaces, please#(end): ");
content = scanner.nextLine();
characters.clear();
for (int i = 0; i < content.length(); i++) {
characters.add(content.charAt(i));
}
input.clear();
for (int i = characters.size() - 1; i >= 0; i--) {
input.push(content.charAt(i));
}
if (inputIsLegal()) {
System.out.println(String.format("%-10s", "step") + String.format("%-10s", "State stack") + String.format("%-10s", "Symbol stack") + String.format("%-10s", "Input string") + String.format("%-10s", "ACTION") + String.format("%-10s", "GOTO"));
analysisContent();
} else {
System.out.println("Illegal input!!!!");
}
}
}
static public void analysisContent() {
Character temp = 'Q';
String temp3 = "";
String result = "";
String stateString = "";
int steps = 0;
while (true) {
//Input stack top element
steps++;
temp = input.peek();
//Input string stack top element
temp3 = String.valueOf(temp);
//Stack top state
stateString = state.peek();
result = analysisTable.get(stateString).get(temp3);
if (result.equals("null")) {
showResult(steps, "report errors", "report errors");
break;
}
//Move in with action
else if (result.contains("S")) {
showResult(steps, result, "");
state.push(result.substring(1));
symbol.push(temp3);
input.pop();
continue;
}
//Using goto
else if (result.replaceAll("%d", "").length() == 0) {
continue;
} else if (result.equals("acc")) {
if (symbol.size() == 2 && input.size() == 1) {
showResult(steps, result, "");
break;
}
continue;
}
//Statute
else if (result.contains("r")) {
String tempGrammar = grammar.get(Integer.parseInt(result.substring(1)));
String[] tempArray = tempGrammar.split(":");
Stack<String> tempState = new Stack<>();
Stack<String> tempSymbol = new Stack<>();
for (int i = 0; i < state.size(); i++) {
tempState.push(state.get(i));
}
for (int i = 0; i < symbol.size(); i++) {
tempSymbol.push(symbol.get(i));
}
for (int i = 0; i < tempArray[1].length(); i++) {
tempState.pop();
tempSymbol.pop();
}
stateString = tempState.peek();
String gotoResult = analysisTable.get(stateString).get(tempArray[0]);
showResult(steps, result, gotoResult);
tempSymbol.push(tempArray[0]);
tempState.push(gotoResult);
state.clear();
symbol.clear();
for (int i = 0; i < tempState.size(); i++) {
state.push(tempState.get(i));
}
for (int i = 0; i < tempSymbol.size(); i++) {
symbol.add(tempSymbol.get(i));
}
continue;
} else {
continue;
}
}
}
static public void showResult(int steps, String action, String goTo) {
System.out.println();
String id = steps + "";
id = String.format("%-10s", id);
System.out.print(id);
browseState();
browseAnalysis();
browseInput();
System.out.print(String.format("%-10s", action));
System.out.print(String.format("%-10s", goTo));
System.out.println();
}
static public void browseAnalysis() {
String analysisStr = "";
for (int i = 0; i < symbol.size(); i++) {
analysisStr = analysisStr + symbol.get(i) + "";
}
analysisStr = String.format("%-10s", analysisStr);
System.out.print(analysisStr);
System.out.print(" ");
}
static public void browseState() {
String stateStr = "";
for (int i = 0; i < state.size(); i++) {
stateStr = stateStr + state.get(i) + "";
}
stateStr = String.format("%-10s", stateStr);
System.out.print(stateStr);
System.out.print(" ");
}
static public void browseInput() {
String inputStr = "";
for (int i = 0; i < input.size(); i++) {
inputStr = inputStr + input.get(input.size() - i - 1) + "";
}
inputStr = String.format("%-10s", inputStr);
System.out.print(inputStr);
System.out.print(" ");
}
static public boolean inputIsLegal() {
boolean flag = false;
int num = 0;
for (Character character : input) {
num++;
for (String s : vt) {
if (String.valueOf(character).equals(s)) {
flag = true;
}
}
if (!flag) {
return flag;
}
if (num == input.size()) {
return flag;
} else {
flag = false;
}
}
return false;
}
}