语法分析的主要内容是，对于我们自己规定的语法，判断哪些token可以在一起，哪些token不行。我们在这里，主要使用建立first，follow，predict_table的方法。（针对LL文法）
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.*;
import Scanner.Kind;
import Scanner.LexicalException;
import Scanner.Token;
import Parser.SyntaxException;
import static Scanner.Kind.*;
public class Parser {
@SuppressWarnings("serial")
public class SyntaxException extends Exception {
Token t;
public SyntaxException(Token t, String message) {
super(message);
this.t = t;
}
}
public class ThreeTuple {
public String first;
public String second;
public ThreeTuple(String a, String b) {
this.first = a;
this.secOnd= b;
}
public void put(String a, String b) {
this.first = a;
this.secOnd= b;
}
public String toString() {
return this.first+" "+this.second;
}
public String GetFirst() {
return this.first;
}
public String GetSecond() {
return this.second;
}
@Override
public boolean equals(Object obj) {
return obj instanceof ThreeTuple &&
this.first.equals(((ThreeTuple)obj).first) &&
this.second.equals(((ThreeTuple)obj).second);
}
@Override
public int hashCode() {
return (first!=null?first.hashCode():1)*31+(second!=null?second.hashCode():1)*31;
}
}
Scanner scanner;
Token t;
ArrayList grammar;
HashSet terminator;//终结符
HashMap> F;//建立first集合
HashMap> FO;//建立follow集合
String tsts;
ArrayList toks;
Parser(Scanner scanner) {
this.scanner = scanner;
t = scanner.nextToken();
tsts="";
toks=new ArrayList ();//添加已经转换为LL文法的新语法
grammar=new ArrayList();
grammar.add("Program ::= IDENTIFIER Pro");
grammar.add("Pro ::= Declaration Zec | Statement Zec | ε");
grammar.add("Zec ::= SEMI Pro");
grammar.add("Declaration ::= VariableDeclaration | ImageDeclaration | SourceSinkDeclaration");
grammar.add("VariableDeclaration ::= VarType IDENTIFIER Va");
grammar.add("Va ::= OP_ASSIGN Expression | ε");
grammar.add("VarType ::= KW_int | KW_boolean");
grammar.add("SourceSinkDeclaration ::= SourceSinkType IDENTIFIER OP_ASSIGN Source");
grammar.add("Source ::= STRING_LITERAL | OP_AT Expression | IDENTIFIER");
grammar.add("SourceSinkType ::= KW_url | KW_file");
grammar.add("ImageDeclaration ::= KW_image Im IDENTIFIER Ma");
grammar.add("Im ::= LSQUARE Expression COMMA Expression RSQUARE | ε");
grammar.add("Ma ::= OP_LARROW Source | ε");
grammar.add("Statement ::= IDENTIFIER St");
grammar.add("St ::= AssignmentStatement | ImageOutStatement | ImageInStatement");
grammar.add("ImageOutStatement ::= OP_RARROW Sink");
grammar.add("Sink ::= IDENTIFIER | KW_SCREEN");
grammar.add("ImageInStatement ::= OP_LARROW Source");
grammar.add("AssignmentStatement ::= Lhs OP_ASSIGN Expression");
grammar.add("Expression ::= OrExpression E");
grammar.add("E ::= OP_Q Expression OP_COLON Expression | ε");
grammar.add("OrExpression ::= AndExpression An");
grammar.add("An ::= OP_OR AndExpression An | ε");
grammar.add("AndExpression ::= EqExpression Eq");
grammar.add("Eq ::= OP_AND EqExpression Eq | ε");
grammar.add("EqExpression ::= RelExpression Rel");
grammar.add("Rel ::= OP_EQ RelExpression Rel | OP_NEQ RelExpression Rel | ε");
grammar.add("RelExpression ::= AddExpression Add");
grammar.add("Add ::= OP_LT AddExpression Add | OP_GT AddExpression Add | OP_LE AddExpression Add | OP_GE AddExpression Add | ε");
grammar.add("AddExpression ::= MultExpression Mul");
grammar.add("Mul ::= OP_PLUS MultExpression Mul | OP_MINUS MultExpression Mul | ε");
grammar.add("MultExpression ::= UnaryExpression Unary");
grammar.add("Unary ::= OP_TIMES UnaryExpression Unary | OP_DIV UnaryExpression Unary | OP_MOD UnaryExpression Unary | ε");
grammar.add("UnaryExpression ::= OP_PLUS UnaryExpression | OP_MINUS UnaryExpression | UnaryExpressionNotPlusMinus");
grammar.add("UnaryExpressionNotPlusMinus ::= OP_EXCL UnaryExpression | Primary | IdentOrPixelSelectorExpression | KW_x | KW_y | KW_r | KW_a | KW_X | KW_Y | KW_Z | KW_A | KW_R | KW_DEF_X | KW_DEF_Y");
grammar.add("Primary ::= INTEGER_LITERAL | LPAREN Expression RPAREN | FunctionApplication | BOOLEAN_LITERAL");
grammar.add("IdentOrPixelSelectorExpression ::= IDENTIFIER Id");
grammar.add("Id ::= LSQUARE Selector RSQUARE | ε");
grammar.add("Lhs ::= LSQUARE LhsSelector RSQUARE | ε");
grammar.add("FunctionApplication ::= FunctionName Fc");
grammar.add("Fc ::= LPAREN Expression RPAREN | LSQUARE Selector RSQUARE ");
grammar.add("FunctionName ::= KW_sin | KW_cos | KW_atan | KW_abs | KW_cart_x | KW_cart_y | KW_polar_a | KW_polar_r");
grammar.add("LhsSelector ::= LSQUARE Se RSQUARE");
grammar.add("Se ::= XySelector | RaSelector");
grammar.add("XySelector ::= KW_x COMMA KW_y");
grammar.add("RaSelector ::= KW_r COMMA KW_a");
grammar.add("Selector ::= Expression COMMA Expression");
terminator=new HashSet ();//添加终结符
terminator.add("IDENTIFIER"); terminator.add("INTEGER_LITERAL"); terminator.add("BOOLEAN_LITERAL");
terminator.add("STRING_LITERAL"); terminator.add("KW_x"); terminator.add("KW_X");
terminator.add("KW_y"); terminator.add("KW_Y"); terminator.add("KW_r");
terminator.add("KW_R"); terminator.add("KW_a"); terminator.add("KW_A");
terminator.add("KW_Z"); terminator.add("KW_DEF_X"); terminator.add("KW_DEF_Y");
terminator.add("KW_SCREEN"); terminator.add("KW_cart_x"); terminator.add("KW_cart_y");
terminator.add("KW_polar_a"); terminator.add("KW_polar_r"); terminator.add("KW_abs");
terminator.add("KW_sin"); terminator.add("KW_cos"); terminator.add("KW_atan");
terminator.add("KW_log"); terminator.add("KW_image"); terminator.add("KW_int");
terminator.add("KW_boolean"); terminator.add("KW_url"); terminator.add("KW_file");
terminator.add("OP_ASSIGN"); terminator.add("OP_GT"); terminator.add("OP_LT");
terminator.add("OP_EXCL"); terminator.add("OP_Q"); terminator.add("OP_COLON");
terminator.add("OP_EQ"); terminator.add("OP_NEQ"); terminator.add("OP_GE");
terminator.add("OP_LE"); terminator.add("OP_AND"); terminator.add("OP_OR");
terminator.add("OP_PLUS"); terminator.add("OP_MINUS"); terminator.add("OP_TIMES");
terminator.add("OP_DIV"); terminator.add("OP_MOD"); terminator.add("OP_POWER");
terminator.add("OP_AT"); terminator.add("OP_RARROW"); terminator.add("OP_LARROW");
terminator.add("LPAREN"); terminator.add("RPAREN"); terminator.add("LSQUARE");
terminator.add("RSQUARE"); terminator.add("SEMI"); terminator.add("COMMA");
terminator.add("ε");terminator.add("EOF");
F=new HashMap> ();
FO=new HashMap> ();
for(Token sc: scanner.tokens){
if(!sc.kind.toString().equals("EOF")) tsts=tsts+sc.kind.toString()+" ";
toks.add(sc);
}
tsts=tsts.trim();
//System.out.println("This is Parser");
}
//字符串处理，去空格等
public HashMap Analysis(ArrayList k){
HashMap m=new HashMap();
for(int i=0;i String s=k.get(i);
String a[]=s.split("::=");
m.put(a[0].trim(), a[1].trim());
}
return m;
}//建立First集合
public HashSet getFirst(String s,HashMap c,HashSet t){
HashSet l=new HashSet();
if(s.contains("|")){
String k[]=s.split("\\|");
for(int i=0;i l.addAll(getFirst(k[i].trim(),c,t));
}
}
else{
String k[]=s.split(" ");
if(t.contains(k[0])){
l.add(k[0]);
}
else if(c.containsKey(k[0])){
//System.out.println(s+" "+k[0]);
l.addAll(getFirst(c.get(k[0]).trim(),c,t));
}
for(int i=0;i //System.out.println(s);
if(c.containsKey(k[i])&&getFirst(c.get(k[i]).trim(),c,t).contains("ε")) {
if(c.containsKey(k[i+1])) l.addAll(getFirst(c.get(k[i+1]).trim(),c,t));
else if(t.contains(k[i+1])) l.add(k[i+1]);
}
else break;
}
}
return l;
}
public HashMap> First(HashMap c,HashSet t){
HashMap> First= new HashMap>();
for (Map.Entry entry : c.entrySet()) {
String s=entry.getValue().trim();
//System.out.println(s);
HashSet temp=getFirst(s,c,t);
First.put(entry.getKey(), temp);
//System.out.println("hello");
}
return First;
}//建立follow集合
public HashMap> FollowLoop(HashMap c,HashSet t,HashMap> F,HashMap> Follow){
for (Map.Entry entry : c.entrySet()) {
String key=entry.getKey();
String value=entry.getValue();
if(key.equals("Program")){
Follow.get(key).add("EOF");
}
if(value.contains("|")){
Follow=FollowLoopForOr(c,t,F,Follow,value,key);
continue;
}
String k[]=value.split(" ");
int i=0;
for(i=0;i if(c.containsKey(k[i])&&t.contains(k[i+1])){
Follow.get(k[i]).add(k[i+1]);
}
else if(c.containsKey(k[i])&&c.containsKey(k[i+1])){
Follow.get(k[i]).addAll(F.get(k[i+1]));
if(F.get(k[i+1]).contains("ε")) {
Follow.get(k[i]).remove("ε");
}
}
}
if(c.containsKey(k[i])) Follow.get(k[i]).addAll(Follow.get(key));
if(c.containsKey(k[i])&&F.get(k[i]).contains("ε")&&c.containsKey(k[i-1])) Follow.get(k[i-1]).addAll(Follow.get(key));
}
return Follow;
}
public HashMap> FollowLoopForOr(HashMap c,HashSet t,HashMap> F,HashMap> Follow,String value,String key){
if(value.contains("|")){
String x[]=value.split("\\|");
for(int j=0;j x[j]=x[j].trim();
if(c.containsKey(x[j])){
Follow.get(x[j]).addAll(Follow.get(key));
}
else{
String kk[]=x[j].split(" ");int i=0;
for(i=0;i if(c.containsKey(kk[i])&&t.contains(kk[i+1]))
Follow.get(kk[i]).add(kk[i+1]);
else if(c.containsKey(kk[i])&&c.containsKey(kk[i+1])){
Follow.get(kk[i]).addAll(F.get(kk[i+1]));
if(F.get(kk[i+1]).contains("ε")) {
Follow.get(kk[i]).remove("ε");
}
}
}
if(c.containsKey(kk[i])) Follow.get(kk[i]).addAll(Follow.get(key));
if(c.containsKey(kk[i])&&F.get(kk[i]).contains("ε")&&c.containsKey(kk[i-1])) Follow.get(kk[i-1]).addAll(Follow.get(key));
}
}
}
return Follow;
}
public HashMap> Follow(HashMap c,HashSet t,HashMap> F){
HashMap> Follow=new HashMap>();
for (Map.Entry entry : c.entrySet()) {
HashSet temp=new HashSet();
Follow.put(entry.getKey(),temp);
}
Follow=FollowLoop(c,t,F,Follow);
Follow=FollowLoop(c,t,F,Follow);
Follow=FollowLoop(c,t,F,Follow);
Follow=FollowLoop(c,t,F,Follow);
Follow=FollowLoop(c,t,F,Follow);
return Follow;}//建立predict集合
public HashMap Prediction(HashSet t,HashMap c,HashMap> F,HashMap> Follow){
HashMap k=new HashMap();
for (Map.Entry entry : c.entrySet()) {
String key=entry.getKey().trim();
for(String str:t){
str=str.trim();
if(str.equals("ε")) continue;
//System.out.println(key+" "+str);
if(F.get(key).contains(str)){
//System.out.println("");
ThreeTuple temp = new ThreeTuple(key,str);
String con= c.get(key).trim();
if(!con.contains("|")) {
k.put(temp, con);
}
else{
String kk[]=con.split("\\|");
for(int i=0;i kk[i]=kk[i].trim();
if(c.containsKey(kk[i])&&F.get(kk[i]).contains(str))
k.put(temp,kk[i]);
else if(kk[i].contains(" ")){
String z[]=kk[i].split(" ");
if(z[0].equals(str)) k.put(temp, kk[i]);
else if(c.containsKey(z[0])&&F.get(z[0]).contains(str)) k.put(temp, kk[i]);
}
else if(kk[i].equals(str)) k.put(temp, kk[i]);
}
}
}
else if(Follow.get(key).contains(str)){
ThreeTuple temp = new ThreeTuple(key,str);
String con= c.get(key).trim();
if(!con.contains("|")) {
String s[]=con.split(" ");
boolean flag=true;
for(int i=0;i if((c.containsKey(s[i])&&!F.get(key).contains("ε"))||(t.contains(s[i])))
flag=false;
}
if(flag) k.put(temp, con);
}
else{
String kk[]=con.split("\\|");
for(int i=0;i kk[i]=kk[i].trim();
if(kk[i].contains(" ")){
String z[]=kk[i].split(" ");
boolean flag=true;
for(int j=0;j //System.out.println("Following");
if((c.containsKey(z[j])&&!F.get(key).contains("ε"))||(t.contains(z[j])))
flag=false;
}
if(flag) k.put(temp, kk[i]);
}
else if((c.containsKey(kk[i])&&F.get(kk[i]).contains("ε"))||kk[i].equals("ε"))
k.put(temp, kk[i]);
}
}
}
else continue;
}
}
return k;
}
public int Judgement(HashMap predict,String tokens,HashMap> F){
Stack st=new Stack();
ThreeTuple a=new ThreeTuple("Program","IDENTIFIER");
String s=predict.get(a);
int w=0;
//System.out.println(s);
s=Reverse(s);
String t[]=s.split(" ");
for(int i=0;i tokens+=" EOF";
String token[]=tokens.split(" ");
int i=0;
for(i=0;i if(token[i].equals(st.peek())){
st.pop();w++;this.t=scanner.nextToken();continue;
}
else{
String key=st.peek();
ThreeTuple temp=new ThreeTuple(key,token[i]);
if(predict.containsKey(temp)){
String z=st.pop();
if(!predict.get(temp).equals("ε")){
String k=Reverse(predict.get(temp));
String v[]=k.split(" ");
for(int j=0;j i--;}
else{
if(token[i].equals("EOF")&&z.equals("Pro")&&st.isEmpty()) break;
else i--;
}
}
else return w+st.size();;
}
}
return w;
}
public String Reverse(String s){
String z[]=s.split(" ");
String k="";
for(int i=z.length-1;i>=0;i--){
k+=z[i];
k+=" ";
}
return k;
}
public int JudgementforExpression(HashMap predict,String tokens,HashMap> F){
Stack st=new Stack();
String x[]=tokens.split(" ");
int w=0;
ThreeTuple a=new ThreeTuple("Expression",x[0]);
if(!predict.containsKey(a)){w++;return w;}
String s=predict.get(a);
//System.out.println(s);
s=Reverse(s);
String t[]=s.split(" ");
for(int i=0;i tokens+=" EOF";
String token[]=tokens.split(" ");
int i=0;
for(i=0;i if(token[i].equals(st.peek())){
st.pop();w++;this.t=scanner.nextToken();continue;
}
else{
String key=st.peek();
ThreeTuple temp=new ThreeTuple(key,token[i]);
if(predict.containsKey(temp)){
String z=st.pop();
if(!predict.get(temp).equals("ε")){
String k=Reverse(predict.get(temp));
String v[]=k.split(" ");
for(int j=0;j i--;}
else{
if(token[i].equals("EOF")&&st.isEmpty()) break;
else if(st.isEmpty()&&!token[i].equals("EOF")) return w+token.length-i-1;
else i--;
}
}
else return w;
}
}
return w;
}
/**
* Main method called by compiler to parser input.
* Checks for EOF
*
* @throws SyntaxException
*/
public static Program Pro(ArrayList list){
Token firstToken=list.get(0);
list.remove(0);
ArrayList decsAndStatements=new ArrayList();
ArrayList Onepart=new ArrayList();
for(Token a:list){
if(!a.kind.equals(SEMI)) onepart.add(a);
else{
if(a.kind.equals(SEMI)){
ASTNode dos;
if(onepart.get(0).kind.equals(IDENTIFIER))
dos=Stm(onepart);
else
dos=Dec(onepart);
decsAndStatements.add(dos);
Onepart=new ArrayList();
}
}
}
Program a=new Program(firstToken, firstToken,decsAndStatements);
return a;
}
public static Declaration Dec(ArrayList list){
Token firstToken=list.get(0);
if(list.get(0).kind.equals(KW_int)||list.get(0).kind.equals(KW_boolean))
return DV(list);
else if(list.get(0).kind.equals(KW_url)||list.get(0).kind.equals(KW_file))
return DS(list);
else
return DI(list);
}
public static Declaration_Variable DV(ArrayList list){
Token firstToken=list.get(0);
list.remove(0);
Token name=list.get(0);
list.remove(0);
if(!list.isEmpty()&&list.get(0).kind.equals(OP_ASSIGN)) {
list.remove(0);
Declaration_Variable a=new Declaration_Variable(firstToken, firstToken, name, Exp(list));
return a;
}
else {
Declaration_Variable a=new Declaration_Variable(firstToken, firstToken, name, null);
return a;
}
}
public static Declaration_SourceSink DS(ArrayList list){
Token firstToken=list.get(0);
list.remove(0);
Token name=list.get(0);
list.remove(0);
list.remove(0);
Declaration_SourceSink a=new Declaration_SourceSink(firstToken, firstToken, name, sou(list));
return a;
}
public static Declaration_Image DI(ArrayList list){
Token firstToken=list.get(0);
list.remove(0);
if(list.get(0).kind.equals(LSQUARE)){
list.remove(0);
Expression x=Exp(list);
list.remove(0);
Expression y=Exp(list);
list.remove(0);
Token name=list.get(0);
list.remove(0);
if(!list.isEmpty()&&list.get(0).kind.equals(OP_LARROW)){
list.remove(0);
Declaration_Image a=new Declaration_Image(firstToken, x, y, name,sou(list));
return a;
}
else {
Declaration_Image a=new Declaration_Image(firstToken, x, y, name,null);
return a;
}
}
else{
Token name=list.get(0);
list.remove(0);
if(!list.isEmpty()&&list.get(0).kind.equals(OP_LARROW)){
list.remove(0);
Declaration_Image a=new Declaration_Image(firstToken, null, null, name,sou(list));
return a;
}
else {
Declaration_Image a=new Declaration_Image(firstToken, null, null, name, null);
return a;
}
}
}
public static Source sou(ArrayList list){
Token firstToken=list.get(0);
if(list.get(0).kind.equals(STRING_LITERAL))
return SouS(list);
else if(list.get(0).kind.equals(OP_AT))
return SouCo(list);
else
return SouId(list);
}
public static Source_StringLiteral SouS(ArrayList list){
Token firstToken=list.get(0);
list.remove(0);
Source_StringLiteral a=new Source_StringLiteral(firstToken, firstToken.getText());
return a;
}
public static Source_CommandLineParam SouCo(ArrayList list){
Token firstToken=list.get(0);
list.remove(0);
Source_CommandLineParam a=new Source_CommandLineParam(firstToken, Exp(list));
return a;
}
public static Source_Ident SouId(ArrayList list){
Token firstToken=list.get(0);
list.remove(0);
Source_Ident a=new Source_Ident(firstToken, firstToken);
return a;
}
public static Statement Stm(ArrayList list){
Token firstToken=list.get(0);
if(list.get(1).kind.equals(OP_LARROW))
return StaIn(list);
else if(list.get(1).kind.equals(OP_RARROW))
return StaOut(list);
else
return StaAs(list);
}
public static Statement_In StaIn(ArrayList list){
Token firstToken=list.get(0);list.remove(0);list.remove(0);
Statement_In a=new Statement_In(firstToken, firstToken, sou(list));
return a;
}
public static Statement_Out StaOut(ArrayList list){
Token firstToken=list.get(0);list.remove(0);list.remove(0);
Statement_Out a=new Statement_Out(firstToken, firstToken, sin(list));
return a;
}
public static Statement_Assign StaAs(ArrayList list){
Token firstToken=list.get(0);
LHS lhs=LHS(list);
list.remove(0);
Expression e=Exp(list);
Statement_Assign a=new Statement_Assign(firstToken, lhs, e);
return a;
}
public static Sink sin(ArrayList list){
Token firstToken=list.get(0);
if(list.get(0).kind.equals(IDENTIFIER))
return SinId(list);
else
return SinSc(list);
}
public static Sink_Ident SinId(ArrayList list){
Token firstToken=list.get(0);
list.remove(0);
Sink_Ident a=new Sink_Ident(firstToken, firstToken);
return a;
}
public static Sink_SCREEN SinSc(ArrayList list){
Token firstToken=list.get(0);
list.remove(0);
Sink_SCREEN a=new Sink_SCREEN(firstToken);
return a;
}
public static LHS LHS(ArrayList list){
Token firstToken=list.get(0);
list.remove(0);
if(!list.isEmpty()&&list.get(0).kind.equals(LSQUARE)){
list.remove(0);list.remove(0);
Index Ind=Ind(list);
list.remove(0);list.remove(0);
LHS a=new LHS(firstToken, firstToken, Ind);
return a;
}
else{
LHS a=new LHS(firstToken, firstToken, null);
return a;
}
}
public static Index Ind(ArrayList list){
Token firstToken=list.get(0);
/*if((list.get(0).kind.equals(KW_x)||list.get(0).kind.equals(KW_r))&&list.get(1).kind.equals(COMMA)){
Expression e0=EPre(list);
list.remove(0);
Expression e1=EPre(list);
Index a=new Index(firstToken, e0, e1);
return a;
}
else{*/
Expression e0=Exp(list);
list.remove(0);
Expression e1=Exp(list);
Index a=new Index(firstToken, e0, e1);
return a;
//}
}
public static Expression Exp(ArrayList list){
ArrayList newList=new ArrayList();
for(Token a:list) newList.add(a);
Expression EB=EB(newList);
if(!newList.isEmpty()&&newList.get(0).kind.equals(OP_Q)){
return EC(list);
}
else return EB(list);
}
public static Expression_Conditional EC(ArrayList list){
Token firstToken=list.get(0);
Expression cOndition=EB(list);
list.remove(0);
Expression trueExpression=Exp(list);
list.remove(0);
Expression falseExpression=Exp(list);
Expression_Conditional a=new Expression_Conditional(firstToken, condition, trueExpression,falseExpression);
return a;
}
public static Expression EB(ArrayList list){
Token firstToken=list.get(0);
ArrayList OrList=new ArrayList ();
ArrayList OpList=new ArrayList ();
while(true){
Expression e0=EB_AND(list);
if(!list.isEmpty()&&list.get(0).kind.equals(OP_OR)){
Token op=list.get(0);
OpList.add(op);
list.remove(0);
OrList.add(e0);
}
else{
OrList.add(e0);
break;
}
}
while(OrList.size()>1){
Expression ek=OrList.get(0);
OrList.remove(0);
Expression es=OrList.get(0);
OrList.remove(0);
Token op=OpList.get(0);
OpList.remove(0);
Expression_Binary a=new Expression_Binary(firstToken, ek, op, es);
OrList.add(0, a);
}
return OrList.get(0);
}
public static Expression EB_AND(ArrayList list){
Token firstToken=list.get(0);
ArrayList AndList=new ArrayList ();
ArrayList OpList=new ArrayList ();
while(true){
Expression e0=EB_EQ(list);
if(!list.isEmpty()&&list.get(0).kind.equals(OP_AND)){
Token op=list.get(0);
OpList.add(op);
list.remove(0);
AndList.add(e0);
}
else{
AndList.add(e0);
break;
}
}
while(AndList.size()>1){
Expression ek=AndList.get(0);
AndList.remove(0);
Expression es=AndList.get(0);
AndList.remove(0);
Token op=OpList.get(0);
OpList.remove(0);
Expression_Binary a=new Expression_Binary(firstToken, ek, op, es);
AndList.add(0, a);
}
return AndList.get(0);
}
public static Expression EB_EQ(ArrayList list){
Token firstToken=list.get(0);
ArrayList EqList=new ArrayList ();
ArrayList OpList=new ArrayList ();
while(true){
Expression e0=EB_REL(list);
if(!list.isEmpty()&&(list.get(0).kind.equals(OP_EQ)||list.get(0).kind.equals(OP_NEQ))){
Token op=list.get(0);
OpList.add(op);
list.remove(0);
EqList.add(e0);
}
else{
EqList.add(e0);
break;
}
}
while(EqList.size()>1){
Expression ek=EqList.get(0);
EqList.remove(0);
Expression es=EqList.get(0);
EqList.remove(0);
Token op=OpList.get(0);
OpList.remove(0);
Expression_Binary a=new Expression_Binary(firstToken, ek, op, es);
EqList.add(0, a);
}
return EqList.get(0);
}
public static Expression EB_REL(ArrayList list){
Token firstToken=list.get(0);
ArrayList RelList=new ArrayList ();
ArrayList OpList=new ArrayList ();
while(true){
Expression e0=EB_ADD(list);
if(!list.isEmpty()&&(list.get(0).kind.equals(OP_LT)||list.get(0).kind.equals(OP_GT)||list.get(0).kind.equals(OP_LE)||list.get(0).kind.equals(OP_GE))){
Token op=list.get(0);
OpList.add(op);
list.remove(0);
RelList.add(e0);
}
else{
RelList.add(e0);
break;
}
}
while(RelList.size()>1){
Expression ek=RelList.get(0);
RelList.remove(0);
Expression es=RelList.get(0);
RelList.remove(0);
Token op=OpList.get(0);
OpList.remove(0);
Expression_Binary a=new Expression_Binary(firstToken, ek, op, es);
RelList.add(0, a);
}
return RelList.get(0);
}
public static Expression EB_ADD(ArrayList list){
Token firstToken=list.get(0);
ArrayList AddList=new ArrayList ();
ArrayList OpList=new ArrayList ();
while(true){
Expression e0=EB_MUL(list);
if(!list.isEmpty()&&(list.get(0).kind.equals(OP_PLUS)||list.get(0).kind.equals(OP_MINUS))){
Token op=list.get(0);
OpList.add(op);
list.remove(0);
AddList.add(e0);
}
else{
AddList.add(e0);
break;
}
}
while(AddList.size()>1){
Expression ek=AddList.get(0);
AddList.remove(0);
Expression es=AddList.get(0);
AddList.remove(0);
Token op=OpList.get(0);
OpList.remove(0);
Expression_Binary a=new Expression_Binary(firstToken, ek, op, es);
AddList.add(0, a);
}
return AddList.get(0);
}
public static Expression EB_MUL(ArrayList list){
Token firstToken=list.get(0);
ArrayList MulList=new ArrayList ();
ArrayList OpList=new ArrayList ();
while(true){
Expression e0=EU(list);
if(!list.isEmpty()&&(list.get(0).kind.equals(OP_TIMES)||list.get(0).kind.equals(OP_DIV)||list.get(0).kind.equals(OP_MOD))){
Token op=list.get(0);
OpList.add(op);
list.remove(0);
MulList.add(e0);
}
else{
MulList.add(e0);
break;
}
}
while(MulList.size()>1){
Expression ek=MulList.get(0);
MulList.remove(0);
Expression es=MulList.get(0);
MulList.remove(0);
Token op=OpList.get(0);
OpList.remove(0);
Expression_Binary a=new Expression_Binary(firstToken, ek, op, es);
MulList.add(0, a);
}
return MulList.get(0);
}
public static Expression EU(ArrayList list){
Token firstToken=list.get(0);
if(firstToken.kind.equals(OP_PLUS)||firstToken.kind.equals(OP_MINUS)||firstToken.kind.equals(OP_EXCL)){
list.remove(0);
Expression e=EU(list);
Expression_Unary a=new Expression_Unary(firstToken, firstToken, e);
return a;
}
else {
HashSet kinds=new HashSet ();
kinds.add(KW_x);kinds.add(KW_y);kinds.add(KW_r);kinds.add(KW_a);kinds.add(KW_X);
kinds.add(KW_Y);kinds.add(KW_Z);kinds.add(KW_A);kinds.add(KW_R);kinds.add(KW_DEF_X);
kinds.add(KW_DEF_Y);
if(kinds.contains(list.get(0).kind)){
return EPre(list);
}
else if(list.get(0).kind.equals(IDENTIFIER)){
if(list.size()>1&&list.get(1).kind.equals(LSQUARE)){
return EPix(list);
}
else return EId(list);
}
else if(list.get(0).kind.equals(INTEGER_LITERAL)){
return EIn(list);
}
else if(list.get(0).kind.equals(BOOLEAN_LITERAL)){
return EBo(list);
}
else if(list.get(0).kind.equals(LPAREN)){
list.remove(0);
Expression a=Exp(list);
list.remove(0);
return a;
}
else{
HashSet kindfuncs=new HashSet ();
kindfuncs.add(KW_sin); kindfuncs.add(KW_cos); kindfuncs.add(KW_atan);
kindfuncs.add(KW_abs); kindfuncs.add(KW_cart_x); kindfuncs.add(KW_cart_y);
kindfuncs.add(KW_polar_a); kindfuncs.add(KW_polar_r);
if(kindfuncs.contains(list.get(0).kind)&&list.get(1).kind.equals(LPAREN)){
return EFe(list);
}
else return EFi(list);
}
}
}
public static Expression_PredefinedName EPre(ArrayList list){
Token firstToken=list.get(0);list.remove(0);
Expression_PredefinedName a=new Expression_PredefinedName(firstToken, firstToken.kind);
return a;
}
public static Expression_PixelSelector EPix(ArrayList list){
Token firstToken=list.get(0);list.remove(0);list.remove(0);
Index index=Ind(list);
list.remove(0);
Expression_PixelSelector a=new Expression_PixelSelector(firstToken, firstToken, index);
return a;
}
public static Expression_Ident EId(ArrayList list){
Token firstToken=list.get(0);list.remove(0);
Expression_Ident a=new Expression_Ident(firstToken, firstToken);
return a;
}
public static Expression_IntLit EIn(ArrayList list){
Token firstToken=list.get(0);list.remove(0);
Expression_IntLit a=new Expression_IntLit(firstToken, Integer.parseInt(firstToken.getText()));
return a;
}
public static Expression_BooleanLit EBo(ArrayList list){
Token firstToken=list.get(0);list.remove(0);
Expression_BooleanLit a=new Expression_BooleanLit(firstToken, Boolean.parseBoolean(firstToken.getText()));
return a;
}
public static Expression_FunctionAppWithExprArg EFe(ArrayList list){
Token firstToken=list.get(0);
list.remove(0);
list.remove(0);
Expression arg=Exp(list);
list.remove(0);
Expression_FunctionAppWithExprArg a=new Expression_FunctionAppWithExprArg(firstToken, firstToken.kind, arg);
return a;
}
public static Expression_FunctionAppWithIndexArg EFi(ArrayList list){
Token firstToken=list.get(0);
list.remove(0);
list.remove(0);
//System.out.println("HELLO");
Index arg=Ind(list);
list.remove(0);
Expression_FunctionAppWithIndexArg a=new Expression_FunctionAppWithIndexArg(firstToken, firstToken.kind, arg);
return a;
}
public Program parse() throws SyntaxException {
//System.out.println("This is Parser");
//System.out.println(tsts);
Program a= program();
matchEOF();
return a;
}
/**
* Program ::= IDENTIFIER ( Declaration SEMI | Statement SEMI )*
*
* Program is start symbol of our grammar.
*
* @throws SyntaxException
*/
public Program program() throws SyntaxException {
HashMap d=Analysis(grammar);
F= First(d,terminator);
FO= Follow(d,terminator,F);
HashMap P=Prediction(terminator,d,F,FO);
//String test="IDENTIFIER KW_int IDENTIFIER OP_ASSIGN KW_y OP_PLUS KW_x OP_PLUS OP_MINUS KW_y OP_MOD KW_r OP_EQ KW_A OP_LE KW_DEF_Y OP_AND KW_Z OP_NEQ KW_r OP_OR INTEGER_LITERAL OP_Q IDENTIFIER LSQUARE LPAREN IDENTIFIER RPAREN COMMA KW_cos LPAREN KW_Z RPAREN RSQUARE OP_COLON BOOLEAN_LITERAL SEMI IDENTIFIER LSQUARE LSQUARE KW_r COMMA KW_A RSQUARE RSQUARE OP_ASSIGN KW_X SEMI KW_image LSQUARE KW_Y COMMA KW_Z RSQUARE IDENTIFIER SEMI IDENTIFIER OP_RARROW KW_SCREEN SEMI IDENTIFIER OP_LARROW STRING_LITERAL SEMI KW_file IDENTIFIER OP_ASSIGN OP_AT IDENTIFIER SEMI";
String sp[]=tsts.split(" ");
if(Judgement(P,tsts,F)!=sp.length) throw new SyntaxException(this.t, "Token not allowed in grammar");
else return Pro(toks);
//System.out.println(this.t.toString());
// throw new UnsupportedOperationException();
}
/**
* Expression ::= OrExpression OP_Q Expression OP_COLON Expression | OrExpression
*
* Our test cases may invoke this routine directly to support incremental development.
*
* @throws SyntaxException
*/
Expression expression() throws SyntaxException {
HashMap d=Analysis(grammar);
F= First(d,terminator);
FO= Follow(d,terminator,F);
HashMap P=Prediction(terminator,d,F,FO);
//String test="IDENTIFIER KW_int IDENTIFIER OP_ASSIGN KW_y OP_PLUS KW_x OP_PLUS OP_MINUS KW_y OP_MOD KW_r OP_EQ KW_A OP_LE KW_DEF_Y OP_AND KW_Z OP_NEQ KW_r OP_OR INTEGER_LITERAL OP_Q IDENTIFIER LSQUARE LPAREN IDENTIFIER RPAREN COMMA KW_cos LPAREN KW_Z RPAREN RSQUARE OP_COLON BOOLEAN_LITERAL SEMI IDENTIFIER LSQUARE LSQUARE KW_r COMMA KW_A RSQUARE RSQUARE OP_ASSIGN KW_X SEMI KW_image LSQUARE KW_Y COMMA KW_Z RSQUARE IDENTIFIER SEMI IDENTIFIER OP_RARROW KW_SCREEN SEMI IDENTIFIER OP_LARROW STRING_LITERAL SEMI KW_file IDENTIFIER OP_ASSIGN OP_AT IDENTIFIER SEMI";
String sp[]=tsts.split(" ");
if(JudgementforExpression(P,tsts,F)!=sp.length) throw new SyntaxException(this.t, "Token not allowed in Expression grammar");
else return Exp(toks);
//System.out.println(this.t.toString());
//throw new UnsupportedOperationException();
}
/**
* Only for check at end of program. Does not "consume" EOF so no attempt to get
* nonexistent next Token.
*
* @return
* @throws SyntaxException
*/
private Token matchEOF() throws SyntaxException {
if (t.kind == EOF) {
return t;
}
String message = "Expected EOL at " + t.line + ":" + t.pos_in_line;
throw new SyntaxException(t, message);
}
}
![[大整数乘法] java代码实现](https://img1.php1.cn/3cd4a/24c6f/9f3/0133bb25da242824.jpeg)
京公网安备 11010802041100号