我需要制作一個遵循語法的遞回下降決議器
<program> → <statements>
<statements>→ <statement> | <statement><semi_colon><statements>
<statement> → <ident><assignment_op><expression>
<expression> → <term><term_tail>
<term_tail> → <add_op><term><term_tail> | ε
<term> → <factor> <factor_tail>
<factor_tail> → <mult_op><factor><factor_tail> | ε
<factor> → <left_paren><expression><right_paren> | <ident> | <const>
<const> → any decimal numbers
<ident> → any names conforming to C identifier rules
<assignment_op> → :=
<semi_colon> → ;
<add_operator> → | -
<mult_operator> → * | /
<left_paren> → (
<right_paren> →)
我制作了一個詞法分析器，將輸入標記為標記型別、標記字串和標記值。
public Token(int type, String token_string, Object value) {
this.type = type;
this.token_string = token_string;
this.value = value;
}
public class TokenType {
public static final int NUMBER=1;
public static final int LEFT_PAR=2;
public static final int RIGHT_PAR=3;
public static final int PLUS=4;
public static final int MINUS=5;
public static final int STAR=6;
public static final int SLASH=7;
public static final int IDENT=8;
public static final int ASSIGN=9;
public static final int SEMI_COLON=10;
}
我應該決議像這樣的輸入
運算子 1 := 200 100 *(100 - 200);
operator2 := operator1 300 并回傳運算子的值
但是，我不確定如何制作決議器。
uj5u.com熱心網友回復：
你添加END_OF_TOKEN到TokenType.
public class TokenType {
public static final int NUMBER = 1;
.....
public static final int END_OF_TOKEN = 11;
}
你定義一個Tokenizer類。Token它通過呼叫回傳一個物件get()。為簡單起見，它回傳Token傳遞給建構式。
public class Tokenizer {
Token[] tokens;
int index = 0;
Tokenizer(Token... tokens) {
this.tokens = tokens;
}
public Token get() {
if (index < tokens.length)
return tokens[index ];
else
return new Token(TokenType.END_OF_TOKEN, "End of token", null);
}
}
你定義一個Parser.
public class Parser {
Tokenizer tokenizer;
Token token;
Map<String, Double> variables = new HashMap<>();
Parser(Tokenizer tokenizer) {
this.tokenizer = tokenizer;
}
double factor() {
if (token.type == TokenType.LEFT_PAR) {
token = tokenizer.get();
double e = expression();
if (token.type != TokenType.RIGHT_PAR)
throw new RuntimeException("')' expected");
token = tokenizer.get();
return e;
} else if (token.type == TokenType.IDENT) {
String name = token.token_string;
token = tokenizer.get();
if (!variables.containsKey(name))
throw new RuntimeException("variable '" name "' undefined");
return variables.get(name);
} else if (token.type == TokenType.NUMBER) {
double value = Double.parseDouble(token.token_string);
token = tokenizer.get();
return value;
} else
throw new RuntimeException("unknown token '" token.token_string "'");
}
double term() {
double value = factor();
while (true) {
if (token.type == TokenType.STAR) {
token = tokenizer.get();
value *= factor();
} else if (token.type == TokenType.SLASH) {
token = tokenizer.get();
value /= factor();
} else
break;
}
return value;
}
double expression() {
double value = term();
while (true) {
if (token.type == TokenType.PLUS) {
token = tokenizer.get();
value = term();
} else if (token.type == TokenType.MINUS) {
token = tokenizer.get();
value -= term();
} else
break;
}
return value;
}
void statement() {
if (token.type != TokenType.IDENT)
throw new RuntimeException("identifier expected");
String name = token.token_string;
token = tokenizer.get();
if (token.type != TokenType.ASSIGN)
throw new RuntimeException("':=' expected");
token = tokenizer.get();
double value = expression();
variables.put(name, value);
}
void statements() {
while (true) {
statement();
if (token.type != TokenType.SEMI_COLON)
break;
token = tokenizer.get();
}
}
public Map<String, Double> parse() {
token = tokenizer.get();
statements();
if (token.type != TokenType.END_OF_TOKEN)
throw new RuntimeException("extra token '" token.token_string "'");
return variables;
}
}
測驗：
@Test
public void testParser() {
Tokenizer tokenizer = new Tokenizer(
new Token(TokenType.IDENT, "operator1", null),
new Token(TokenType.ASSIGN, null, null),
new Token(TokenType.NUMBER, "200", null),
new Token(TokenType.PLUS, null, null),
new Token(TokenType.NUMBER, "100", null),
new Token(TokenType.STAR, null, null),
new Token(TokenType.LEFT_PAR, null, null),
new Token(TokenType.NUMBER, "100", null),
new Token(TokenType.MINUS, null, null),
new Token(TokenType.NUMBER, "200", null),
new Token(TokenType.RIGHT_PAR, null, null),
new Token(TokenType.SEMI_COLON, null, null),
new Token(TokenType.IDENT, "operator2", null),
new Token(TokenType.ASSIGN, null, null),
new Token(TokenType.IDENT, "operator1", null),
new Token(TokenType.PLUS, null, null),
new Token(TokenType.NUMBER, "300", null));
Parser parser = new Parser(tokenizer);
Map<String, Double> variables = parser.parse();
System.out.println(variables);
}
輸出：
{operator2=-9500.0, operator1=-9800.0}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/532399.html
標籤：爪哇解析计算器递归下降