E文法表達式類
G 定義文法類
LL 文法分析類 ， 包含對First,Follow,Select集合的求解以及對表達式的分析函數
Main測試分析程式，并輸出結果
E.java
import java.util.ArrayList;
import java.util.List;
/**
* 文法表達式類
* @author jiangliuhong
* @createTime 2016年5月30日 上午11:28:43
* @function
*/
public class E {
//文法左部
private String left;
//文法右部
private String right;
private List<String> rights = new ArrayList<>();
public String getLeft() {
return left;
}
public void setLeft(String left) {
this.left = left;
}
public String getRight() {
return right;
}
public void setRight(String right) {
this.right = right;
}
public List<String> getRights() {
return rights;
}
public void setRights(List<String> rights) {
this.rights = rights;
}
public E() {
}
public E(String left, String right) {
this.left = left;
this.right = right;
createTaken();
}
public void createTaken() {
// this.getLefts().add(this.getLeft());
String right = this.getRight();
/*if (right.equals("$")) {
this.getRights().add(right);
} else {*/
/* while (right.contains("$")) {
right = right.replaceFirst("$", "#");
}*/
if (right.length() == 1) {
this.getRights().add(right);
} else {
for (int i = 0; i < right.length(); i++) {
if ((i + 1 < right.length())
&& String.valueOf(right.charAt(i + 1)).equals("'")) {
this.getRights().add(right.charAt(i) + "'");
} else {
if (!(String.valueOf(right.charAt(i)).equals("'"))) {
if (String.valueOf(right.charAt(i)).equals("#")) {
this.getRights().add("$");
} else {
this.getRights().add(
String.valueOf(right.charAt(i)));
}
}
}
}
}
}
/**
* 格式化實處文法表達式
* 重寫toString方法
* @return
*/
public String toString(){
return this.left+"->"+this.right;
}
}
G.java 文法定義類
import java.util.Arrays;
import java.util.List;
/**
* 文法定義類
*
* @author jiangliuhong
* @createTime 2016年5月30日 上午11:33:06
* @function
*/
public class G {
// 開始非終結符
private String start;
// 文法表達式
private List<E> es;
// 終結符
private List<String> terminator;
// 非終結符
private List<String> nonterminator;
public G() {
}
public G(String start, List<E> es) {
this.start = start;
this.es = es;
}
public G(String start) {
this.start = start;
}
public String getStart() {
return start;
}
public void setStart(String start) {
this.start = start;
}
public List<E> getEs() {
return es;
}
public void setEs(List<E> es) {
this.es = es;
}
public List<String> getTerminator() {
return terminator;
}
public void setTerminator(List<String> terminator) {
this.terminator = terminator;
}
public void setTerminator(String terminator) {
//this.terminator = new ArrayList<>();
/*for (int i = 0; i < terminator.length(); i++) {
this.terminator.add(terminator.charAt(i) + "");
}*/
String[] split = terminator.split(",");
this.terminator = Arrays.asList(split);
}
public List<String> getNonterminator() {
return nonterminator;
}
public void setNonterminator(List<String> nonterminator) {
this.nonterminator = nonterminator;
}
public void setNonterminator(String nonterminator) {
//this.nonterminator = new ArrayList<>();
/*for (int i = 0; i < nonterminator.length(); i++) {
this.nonterminator.add(nonterminator.charAt(i) + "");
}*/
String[] split = nonterminator.split(",");
this.nonterminator = Arrays.asList(split);
}
/**
* 向文法中添加表達式
*
* @param e
*/
public void andE(E e) {
this.es.add(e);
}
}
LL.java ll文法分析類
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;
/**
* ll文法分析類
*
* @author jiangliuhong
* @createTime 2016年5月30日 上午11:38:52
* @function
*/
public class LL {
private G g;
// 三個集合
private Map<String, List<String>> first = new HashMap<>();
private Map<String, List<String>> follow = new HashMap<>();
private Map<String, List<String>> select = new HashMap<>();
//分析棧
private Stack<String> stack = new Stack<String>();
private Stack<String> str = new Stack<String>();
public LL(G g) {
this.g = g;
}
public G getG() {
return g;
}
public void setG(G g) {
this.g = g;
}
/**
* 分析輸入串
*/
public void chkString(String string){
//判斷是否為标準文法
//判斷終結符
for(int i = string.length()-1 ;i>=0;i--){
String s = string.charAt(i) + "";
str.push(s);
if(!g.getTerminator().contains(s)){
System.out.println("輸入串不符合規則");
return ;
}
}
//分析串
boolean flag = true;
int ii = 1;
stack.push("#");
stack.push(g.getStart());
System.out.println("步驟\t分析棧\t剩餘輸入串\t推導所用比對");
ff:while(flag){
if(str.isEmpty()){
return ;
}
if(ii == 100){
return ;
}
System.out.print(ii+"\t");
String peek = stack.peek();
String speek = str.peek();
for (Map.Entry<String, List<String>> entry : select.entrySet()) {
String key = entry.getKey();
List<String> list = entry.getValue();
if(list.contains(speek)){
String first = getSelectFirtsOrFollow(true,key);
if(!first.equals(peek)){
continue;
}
String kright = getSelectFirtsOrFollow(false, key);
if(peek.equals(speek)){
if(speek.equals("#")&&peek.equals("#")){
System.out.print(stack.toString()+"\t"+str.toString()+"\t"+"接受\n");
return;
}
System.out.print(stack.toString()+"\t"+str.toString()+"\t"+speek+"比對\n");
str.pop();
stack.pop();
}else{
System.out.print(stack.toString()+"\t"+str.toString()+"\t"+key+"\n");
stack.pop();
}
for(int j = kright.length()-1;j>=0;j--){
String ss = kright.charAt(j)+"";
if(ss.equals("'")){
ss = kright.charAt(j-1)+ss;
j--;
}
stack.push(ss);
}
ii++;
continue ff;
}
}
ii++;
//select中無比對項 ， 輸入串錯誤
//System.out.println("\n輸入串錯誤");
//return;
}
}
/**
* 列印分析表
*/
public void printfAnalyzeTable(){
//列印表頭
System.out.print("\t\t");
for(String term : g.getTerminator()){
System.out.print("\t"+term+"\t");
}
System.out.println();
/*for (Map.Entry<String, List<String>> entry : select.entrySet()) {
String key = entry.getKey();
int indexOf = key.indexOf("->");
String nonter = key.substring(0, indexOf);
}*/
for(E e : g.getEs()){
System.out.print("\t"+e.getLeft()+"\t");
for(String term : g.getTerminator()){
Map<String, List<String>> selectLikeKey = findSelectLikeKey(e.getLeft());
for(String term_ : g.getTerminator()){
for (Map.Entry<String, List<String>> entry : selectLikeKey.entrySet()) {
List<String> value = entry.getValue();
if(value.contains(term_)){
String key = entry.getKey();
int indexOf = key.indexOf(">");
String string = key.substring(indexOf+1 );
System.out.print("\t->"+string+"\t");
}else{
System.out.print("\t");
}
}
}
}
System.out.println();
}
}
/**
* 得到 select key中含指定非終結符的映射
*/
private Map<String, List<String>> findSelectLikeKey(String likeKey){
Map<String, List<String>> result = new HashMap<>();
for (Map.Entry<String, List<String>> entry : select.entrySet()) {
String key = entry.getKey();
String skey = getSelectFirtsOrFollow(true,key);
if(skey.equals(likeKey)){
result.put(key, entry.getValue());
}
}
return result;
}
/**
* 取select ->前部分
*/
private String getSelectFirtsOrFollow(boolean isFirst,String key){
if(isFirst){
int indexOf = key.indexOf("-");
String skey = key.substring(0, indexOf);
return skey;
}else{
int indexOf = key.indexOf(">");
String skey = key.substring(indexOf+1);
return skey;
}
}
/**
* 列印Select集合
*/
public void printfSelect(){
System.out.println("Select集合為：");
for (Map.Entry<String, List<String>> entry : select.entrySet()) {
List<String> list = entry.getValue();
System.out.print("Select(" + entry.getKey() + ")={");
System.out.print(list.toString());
System.out.println("}");
}
}
/**
* 分析Select 集合
*/
public void chkSelect(){
//周遊文法
for(E e : g.getEs()){
String right = e.getRight();
String left = e.getLeft();
// | 判斷
String[] split = right.split("\\|");
for(String sp : split){
// $ 判斷
if(!right.contains("$")){
String begin = right.charAt(0) + "";
if(g.getNonterminator().contains(begin)){
//非終結符，存入first
select.put(left+"->"+sp,first.get(begin) );
}else{
//終結符
List<String> sel = new ArrayList<>();
sel.add(begin);
select.put(left+"->"+sp,sel);
}
}else{
select.put(left+"->"+sp,follow.get(left));
}
}
}
}
/**
* 列印follow集合
*/
public void printfFollow() {
System.out.println("Follow集合為：");
for (Map.Entry<String, List<String>> entry : follow.entrySet()) {
List<String> list = entry.getValue();
System.out.print("Follow(" + entry.getKey() + ")={");
System.out.print(list.toString());
System.out.println("}");
}
}
/**
* 分析follow集合
*/
public void chkFollow() {
//給每個非終結符建立一個map集合
for (String symbol : g.getNonterminator()) {
List<String> list = new ArrayList<String>();
list.add("#");
follow.put(symbol, list);
}
//定義一個循環上線
int count = 100;
//周遊非終結符
for (int i = 0, j = 0; i < g.getNonterminator().size()
&& j < count; i = (i + 1) % (g.getNonterminator().size()), j++) {
String symbol = g.getNonterminator().get(i);
//周遊文法表達式
for (E e : g.getEs()) {
if (e.getRight().contains(symbol)) {
for (int k = 0; k < e.getRights().size(); k++) {
//該文法表達式右部包含該非終結符
if (e.getRights().get(k).equals(symbol)) {
// 開始文法分析
//定義循環變量
boolean canDo = false, meDo = false;
for (int n = k; n < e.getRights().size() && !(e.getRights().get(n).equals("|"))
&& !canDo; n++) {
//判斷後補是否為非終結符
if (n + 1 < e.getRights().size()) {
String rightString = e.getRights().get(n + 1);
if (g.getNonterminator().contains(rightString)) {
if (!canDo && !meDo) {
meDo = true;
List<String> leftFirst = first.get(rightString);
List<String> symbolFollow = follow.get(symbol);
for (int m = 0; m < leftFirst.size(); m++) {
if (!(symbolFollow.contains(leftFirst.get(m)))
) {
if (!(leftFirst.get(m).equals("$")))
if (!(leftFirst.get(m).equals("|")))
symbolFollow.add(leftFirst.get(m));
}
}
follow.put(symbol, symbolFollow);
}
} else {
List<String> symbolFollow = follow.get(symbol);
if (!(symbolFollow.contains(rightString)) && !(rightString.equals("|"))) {
symbolFollow.add(rightString);
follow.put(symbol, symbolFollow);
canDo = true;
}
}
}
}
// | 的文法判斷
if (k == e.getRights().size() - 1
|| e.getRights().get(k + 1).equals("|") && !canDo) {
String leftSymbol = e.getLeft();
List<String> leftFollow = follow.get(leftSymbol);
List<String> symbolFollow = follow.get(symbol);
for (int m = 0; m < leftFollow.size(); m++) {
if (!(symbolFollow.contains(leftFollow.get(m)))) {
if (!(leftFollow.get(m).equals("$")))
if (!(leftFollow.get(m).equals("|")))
symbolFollow.add(leftFollow.get(m));
}
}
follow.put(symbol, symbolFollow);
canDo = true;
} else {
int nonTerminatingSymbol = 0;
int isepsilon = 0;
boolean isMe = false;
for (int n = k; n < e.getRights().size()
&& !(e.getRights().get(n).equals("|")); n++) {
if (n + 1 < e.getRights().size()) {
String rightString = e.getRights().get(n + 1);
if (g.getTerminator().contains(rightString)) {
isMe = true;
}
if (g.getNonterminator().contains(rightString)) {
nonTerminatingSymbol++;
if (hasepsilon(rightString)) {
isepsilon++;
}
}
}
}
if (nonTerminatingSymbol == isepsilon && !canDo && !isMe) {
String leftSymbol = e.getLeft();
List<String> leftFollow = follow.get(leftSymbol);
List<String> symbolFollow = follow.get(symbol);
for (int m = 0; m < leftFollow.size(); m++) {
if (!(symbolFollow.contains(leftFollow.get(m)))) {
if (!(leftFollow.get(m).equals("$")))
if (!(leftFollow.get(m).equals("|")))
symbolFollow.add(leftFollow.get(m));
}
}
follow.put(symbol, symbolFollow);
}
}
}
}
}
}
}
}
/**
* 判斷是否含有 $ $ 即 epsilon
* @param symbol
* @return
*/
private boolean hasepsilon(String symbol) {
for (E e : g.getEs()) {
if (e.getLeft().equals(symbol)) {
int index = e.getRights().indexOf("$");
if (index < 0) {
return false;
} else {
if (e.getRights().size() == 1 && e.getRights().contains("$")) {
return true;
} else {
if (index == e.getRights().size() - 1 && e.getRights().get(index - 1).equals("|")) {
return true;
} else {
if (index + 1 < e.getRights().size() && e.getRights().get(index + 1).equals("|")
&& index == 0) {
return true;
} else {
if (index + 1 < e.getRights().size()
&& e.getRights().get(index + 1).equals("|") && index - 1 > 0
&& e.getRights().get(index - 1).equals("|")) {
return true;
}
}
}
}
}
}
}
return false;
}
/**
* 輸出first集合
*/
public void printfFirst() {
System.out.println("First集合為：");
for (Map.Entry<String, List<String>> entry : first.entrySet()) {
List<String> list = entry.getValue();
System.out.print("First(" + entry.getKey() + ")={");
System.out.print(list.toString());
System.out.println("}");
}
}
/**
* 分析first集合
*/
public void chkFirst() {
// 周遊非終結符
for (String nonter : g.getNonterminator()) {
List<String> listFirst = new ArrayList<String>();
iterativeToFirst(nonter, listFirst);
}
}
/**
* 文法分析
*
* @param symbol
* @param listFirst
*/
private void iterativeToFirst(String symbol, List<String> listFirst) {
for (E e : g.getEs()) {
if (e.getLeft().equals(symbol)) {
// 根據| 劃分文法表達式
String[] rights = e.getRight().split("\\|");
for (String right : rights) {
if (!isStartWithSymbol(right)) {
// 不是非終結符，加入list
listFirst.add(getStartWithSymbol(right));
} else {
iterativeToFirst(getStartWithSymbol(right), listFirst);
}
}
}
}
first.put(symbol, listFirst);
}
/**
* 判斷開始是否為非終結符
*
* @param symbol
* @return
*/
private boolean isStartWithSymbol(String symbol) {
for (String nonTerminatingSymbol : g.getNonterminator()) {
if (symbol.startsWith(nonTerminatingSymbol)) {
return true;
}
}
return false;
}
/**
* 得到文法的第一個字元
*
* @param symbol
* @return
*/
private String getStartWithSymbol(String symbol) {
for (String nonTerminatingSymbol : g.getNonterminator()) {
if (symbol.startsWith(nonTerminatingSymbol)) {
return nonTerminatingSymbol;
}
}
// $ 代替epsilon
if (symbol.equals("$")) {
return "$";
} else {
return String.valueOf(symbol.charAt(0));
}
}
}
Main.java測試類
import java.util.ArrayList;
import java.util.List;
/**
* @author jiangliuhong
* @createTime 2016年5月30日 上午11:31:15
* @function
*/
public class Main {
public static void main(String[] args) {
List<E> es = new ArrayList<>();
es.add(new E("E", "TE'"));
es.add(new E("E'", "+TE'|$"));
es.add(new E("T", "FT'"));
es.add(new E("T'", "*FT'|$"));
es.add(new E("F", "i|(E)"));
G g = new G("E", es );
List<String> non = new ArrayList<>();
g.setNonterminator("E,E',T,T',F");
g.setTerminator("i,+,*,(,),#");
LL ll = new LL(g);
ll.chkFirst();
ll.printfFirst();
ll.chkFollow();
ll.printfFollow();
ll.chkSelect();
ll.printfSelect();
ll.printfAnalyzeTable();
ll.chkString("i+i*i#");
}
}
控制台輸出結果
First集合為：
First(E)={[i, (]}
First(T)={[i, (]}
First(T')={[*, $]}
First(F)={[i, (]}
First(E')={[+, $]}
Follow集合為：
Follow(T)={[#, +, )]}
Follow(E)={[#, )]}
Follow(F)={[#, *, +, )]}
Follow(T')={[#, +, )]}
Follow(E')={[#, )]}
Select集合為：
Select(F->(E))={[i]}
Select(F->i)={[i]}
Select(E'->+TE')={[#, )]}
Select(T->FT')={[i, (]}
Select(E'->$)={[#, )]}
Select(E->TE')={[i, (]}
Select(T'->$)={[#, +, )]}
Select(T'->*FT')={[#, +, )]}
i + * ( ) #
E ->TE' ->TE'
E' ->TE' ->$ ->$
T ->FT' ->FT'
T' ->$ ->*FT' ->$ ->$
F ->i ->(E)
步驟 分析棧 剩餘輸入串 推導所用比對
1 [#, E] [#, i, *, i, +, i] E->TE'
2 [#, E', T] [#, i, *, i, +, i] T->FT'
3 [#, E', T', F] [#, i, *, i, +, i] F->i
4 [#, E', T', i] [#, i, *, i, +, i] i比對
5 [#, E', T'] [#, i, *, i, +] T'->$
6 [#, E'] [#, i, *, i, +] E'->+TE'
7 [#, E',T,+] [#, i, *, i, +] +比對
8 [#, E',T] [#, i, *, i] T->FT'
9 [#, E',T',F] [#, i, *, i] F->i
10 [#, E',T',i] [#, i, *, i] i比對
11 [#, E',T'] [#, i, *] T'->*FT'
12 [#, E',T',F,*] [#, i, *] *比對
13 [#, E',T',F] [#, i] F->i
14 [#, E',T',i] [#, i] i比對
15 [#, E',T'] [#] T'->$
16 [#, E'] [#] E'->$
17 [#] [#] 接受
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)