LL(1)
package phrase;
/*
*
* 目前还存在的问题以及改进方法
* 1：栈中连续终结符只能默认第二为非终结符
* 解决办法：用循环进行排除
* 2：对非法输入扫描串不能识别
*/
import java.util.Scanner;
/*@代表空
//终结符
i+*()#
//非终结符
EeTtF
//LL(1)表
Te n n Te n n
n +Te n n @ @
Ft n n Ft n n
n @ *Ft n @ @
i n n (E) n n
/*
正确匹配例子
i*i+i#
i+i*i#
//错误匹配例子
i**i#
//栈中匹配中结束 ,但是扫描串未扫描完
i*i+i+i#
//扫描串匹配完成，但是栈中还有存留
i*i#
*/
public class phrase {
//终结符串
static String final_sign=null;
//非终结符串
static String Nfinal=null;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
///////////////////////////////////////////////
/*----------------初始化表---------------------
// ///////////////////////////////////////////*/
//接受终结符
System.out.println("请输入终结符号集合：");
final_sign=sc.nextLine();
//接受非终结符
System.out.println("请输入非终结符号集合：");
Nfinal=sc.nextLine();
//根据终结符与非终结符的长度创建一个表
int h=Nfinal.length();
int l=final_sign.length();
String[][] Table=new String[h][l];
System.out.println(Table.length);
System.out.println(Table[0].length);
System.out.println("请输入矩阵句型：");
for (int i = 0; i < Table.length; i++) { //行
for (int j = 0; j < Table[0].length; j++) { //列
Table[i][j]=sc.next();
}
}
for (String[] strings : Table) {
for (String string : strings) {
System.out.printf("%s\t",string);
}
System.out.println();
}
//接受输入要扫描的字符串
System.out.println("请输入你所要扫描的字符串：");
String input_str=sc.next();
sc.close();
/*/////////////////////////////////////////////////////////
//--------------------如下进行匹配------------------------/
/////////////////////////////////////////////////////////*/
//构建栈
char[] sign_stack=new char[10];
//构建指针
int top=1; //指向栈顶
int lr=0; //指向扫描字符
//初始化栈
sign_stack[0]='#';
sign_stack[1]=Nfinal.charAt(0);
//表的行坐标
int hang=0;
int lie=0;
//取得栈顶元素
char stack_top;
while(sign_stack[top]!='#'||input_str.charAt(lr)!='#') {
stack_top=sign_stack[top]; //取出栈顶元素
/*/////////////////////////////////////////////////
*
* 问题存在区域
*
*/////////////////////////////////////////////////
//---------------判断栈顶元素是否为终结符--------------
if(!isNfinal(stack_top)) { //是终结符
//与扫描串当前字符匹配
if(stack_top==input_str.charAt(lr)){ //可以匹配
lr++; //进行下一个字符匹配
sign_stack[top]='0';
top--; //弹出栈顶元素终结符
stack_top=sign_stack[top];
}else { //句型不匹配推出
System.out.println("GGGG!!!");
break;
}
}
//---------------进行非终结符推导----------------------
hang=Nfinal.indexOf(stack_top); //查找在表中的行位置
lie=final_sign.indexOf(input_str.charAt(lr)); //查找在表中的列位置
//将当前表中符号串与字符进行比较
if(Table[hang][lie].equals("n")) { //1.如果没有匹配的
System.out.println("GG!!");
break;
}else {
if(Table[hang][lie].length()==1&&Table[hang][lie].charAt(0)==input_str.charAt(lr)) { //如果终结符匹配成功将栈顶元素弹出，并且进行下一个字符匹配
sign_stack[top]='0'; //出栈
top--; //栈顶指针变化
lr++; //扫描指针发生变化
}else if(Table[hang][lie].equals("@")){ //如果存在是空@则弹出栈顶元素
sign_stack[top]='0';
top--;
}else { //否则将栈顶元素出栈并将推导式入栈
for(int i=Table[hang][lie].length()-1;i>=0;i--) {
//判断将要插入的字符是否为非终结符
sign_stack[top]=Table[hang][lie].charAt(i);
top++;
}
top--;
}
}
}
/*//////////////////////////////////////////////////////////////
* 判断匹配成功
*//////////////////////////////////////////////////////////////
if(sign_stack[top]=='#'&&input_str.charAt(lr)=='#')
System.out.println("匹配成功！！！");
else {
System.out.println("出错位置："+lr+1);
}
}
/*//////////////////////////////////////////////////////////////
* 判断字符是否为非终结符
*//////////////////////////////////////////////////////////////
private static boolean isNfinal(char temp) {
for (int i = 0; i < Nfinal.length(); i++) {
if(temp==Nfinal.charAt(i)) return true;
}
return false;
}
/*
*
* 目前还存在的问题以及改进方法
* 1：栈中连续终结符只能默认第二为非终结符
* 解决办法：用循环进行排除
* 2：对非法输入扫描串不能识别
*/
import java.util.Scanner;
/*@代表空
//终结符
i+*()#
//非终结符
EeTtF
//LL(1)表
Te n n Te n n
n +Te n n @ @
Ft n n Ft n n
n @ *Ft n @ @
i n n (E) n n
/*
正确匹配例子
i*i+i#
i+i*i#
//错误匹配例子
i**i#
//栈中匹配中结束 ,但是扫描串未扫描完
i*i+i+i#
//扫描串匹配完成，但是栈中还有存留
i*i#
*/
public class phrase {
//终结符串
static String final_sign=null;
//非终结符串
static String Nfinal=null;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
///////////////////////////////////////////////
/*----------------初始化表---------------------
// ///////////////////////////////////////////*/
//接受终结符
System.out.println("请输入终结符号集合：");
final_sign=sc.nextLine();
//接受非终结符
System.out.println("请输入非终结符号集合：");
Nfinal=sc.nextLine();
//根据终结符与非终结符的长度创建一个表
int h=Nfinal.length();
int l=final_sign.length();
String[][] Table=new String[h][l];
System.out.println(Table.length);
System.out.println(Table[0].length);
System.out.println("请输入矩阵句型：");
for (int i = 0; i < Table.length; i++) { //行
for (int j = 0; j < Table[0].length; j++) { //列
Table[i][j]=sc.next();
}
}
for (String[] strings : Table) {
for (String string : strings) {
System.out.printf("%s\t",string);
}
System.out.println();
}
//接受输入要扫描的字符串
System.out.println("请输入你所要扫描的字符串：");
String input_str=sc.next();
sc.close();
/*/////////////////////////////////////////////////////////
//--------------------如下进行匹配------------------------/
/////////////////////////////////////////////////////////*/
//构建栈
char[] sign_stack=new char[10];
//构建指针
int top=1; //指向栈顶
int lr=0; //指向扫描字符
//初始化栈
sign_stack[0]='#';
sign_stack[1]=Nfinal.charAt(0);
//表的行坐标
int hang=0;
int lie=0;
//取得栈顶元素
char stack_top;
while(sign_stack[top]!='#'||input_str.charAt(lr)!='#') {
stack_top=sign_stack[top]; //取出栈顶元素
/*/////////////////////////////////////////////////
*
* 问题存在区域
*
*/////////////////////////////////////////////////
//---------------判断栈顶元素是否为终结符--------------
if(!isNfinal(stack_top)) { //是终结符
//与扫描串当前字符匹配
if(stack_top==input_str.charAt(lr)){ //可以匹配
lr++; //进行下一个字符匹配
sign_stack[top]='0';
top--; //弹出栈顶元素终结符
stack_top=sign_stack[top];
}else { //句型不匹配推出
System.out.println("GGGG!!!");
break;
}
}
//---------------进行非终结符推导----------------------
hang=Nfinal.indexOf(stack_top); //查找在表中的行位置
lie=final_sign.indexOf(input_str.charAt(lr)); //查找在表中的列位置
//将当前表中符号串与字符进行比较
if(Table[hang][lie].equals("n")) { //1.如果没有匹配的
System.out.println("GG!!");
break;
}else {
if(Table[hang][lie].length()==1&&Table[hang][lie].charAt(0)==input_str.charAt(lr)) { //如果终结符匹配成功将栈顶元素弹出，并且进行下一个字符匹配
sign_stack[top]='0'; //出栈
top--; //栈顶指针变化
lr++; //扫描指针发生变化
}else if(Table[hang][lie].equals("@")){ //如果存在是空@则弹出栈顶元素
sign_stack[top]='0';
top--;
}else { //否则将栈顶元素出栈并将推导式入栈
for(int i=Table[hang][lie].length()-1;i>=0;i--) {
//判断将要插入的字符是否为非终结符
sign_stack[top]=Table[hang][lie].charAt(i);
top++;
}
top--;
}
}
}
/*//////////////////////////////////////////////////////////////
* 判断匹配成功
*//////////////////////////////////////////////////////////////
if(sign_stack[top]=='#'&&input_str.charAt(lr)=='#')
System.out.println("匹配成功！！！");
else {
System.out.println("出错位置："+lr+1);
}
}
/*//////////////////////////////////////////////////////////////
* 判断字符是否为非终结符
*//////////////////////////////////////////////////////////////
private static boolean isNfinal(char temp) {
for (int i = 0; i < Nfinal.length(); i++) {
if(temp==Nfinal.charAt(i)) return true;
}
return false;
}
}