0
우선, 나쁜 제목에 대해 유감스럽게 생각합니다. 나는이 문제를 무엇이라고 부를지 정말로 모른다.Java - 리프 노드의 구문 분석 트리 재귀를 처리하는 방법?
내 거북이 그래픽 프로그램의 구문 분석기를 코딩하려고합니다. 그 코드가 무엇인지 모르는 경우 기본적으로 "거북이"의 움직임을 지시하는 데 사용되는 명령으로 구성된 작은 프로그래밍 언어를 만듭니다. . 예를 들어, 입력 "FORW 5. LEFT 45."5 단계로 앞으로 거북이의 움직임을 만들 것입니다 왼쪽으로 45도 회전 후)
내 BNF 문법은 다음과 같습니다.
<EXPR>::= <CMD><EXPR> | <EOF>
<CMD>::=
<FORW><INT><PERIOD>
| <BACK><INT><PERIOD>
| <LEFT><INT><PERIOD>
| <RIGHT><INT><PERIOD>
| <DOWN><PERIOD>
| <UP><PERIOD>
| <COLOR><HEX><PERIOD>
| <REP><INT><CMD>
| <REP><INT><QUOTE><EXPR><QUOTE>
(모두 <-.->은 <EXPR> 및 <CMD>을 제외한 터미널 [토큰]입니다.
REP 명령은 일련의 명령 (따옴표 안에있는 명령) X 번을 반복합니다. 예 : REP 3 "FORW 5. LEFT 45."은 FORW 5. LEFT 45. 명령을 3 번 반복합니다.
이것은 구문 분석기에 구현할 때 문제가되는 명령입니다 (REP는 문법에 비 터미널을 포함하고 있기 때문에).
구문 분석 트리 :
파서
// Ett syntaxträd
abstract class ParseTree {
abstract public int evaluate();
}
// Ett syntaxträd som representerar ett tal
class ExprNode extends ParseTree {
ParseTree left, right;
public ExprNode(ParseTree left, ParseTree right) {
this.left = left;
this.right = right;
}
public int evaluate() {
return 0;
}
}
// Ett syntaxträd som representerar någon av de fyra binära operationerna
class CMDNode extends ParseTree {
TokenType cmd;
int num;
String hex;
ParseTree child;
public CMDNode(TokenType cmd) {
this.cmd = cmd;
}
public CMDNode(TokenType cmd, int num) {
this.cmd = cmd;
this.num = num;
}
public CMDNode(TokenType cmd, String hex) {
this.cmd = cmd;
this.hex = hex;
}
public CMDNode(TokenType cmd, ParseTree child) {
this.cmd = cmd;
this.child = child;
}
public int evaluate() {
return 0;
}
}
(스웨덴어되는 덧글에 대한 죄송) : (I 코드 있지만 가장 중요한 부분을 모두 추가
/**
* En rekursiv medåknings-parser för aritmetiska uttryck.
* Se README för mer info.
*
*
*/
public class Parser {
private Lexer lexer;
/** Variabler för att kunna ge pratig förklaring av vad som händer
* i parsningen. Om man inte har behov av denna feature kan koden
* som relaterar till dessa variabler tas bort.
*/
private boolean verbose;
private int depth;
/** Om verbose är satt till sann kommer Parsern att prata en massa
* medans den gör sitt jobb.
*/
public Parser(Lexer lexer, boolean verbose) {
this.lexer = lexer;
this.verbose = verbose;
}
private void talk(String s) {
if (verbose)
System.out.printf("%"+(3*depth+1)+"s%s\n", "", s);
}
public ParseTree parse() throws SyntaxError {
// Startsymbol är Expr
depth = 0;
talk("Start parse()");
++depth;
ParseTree result = Expr();
// Borde inte finnas något kvar av indata när vi parsat ett uttryck
if (lexer.nextToken().getType() != TokenType.EOF) {
throw new SyntaxError();
}
return result;
}
private ParseTree Expr() throws SyntaxError {
//talk("Enter Expr()");
//++depth;
ParseTree result = Cmd();
//talk("[Expr()] Read cmd done");
while (lexer.peekToken().getType() == TokenType.FORW ||
lexer.peekToken().getType() == TokenType.BACK||
lexer.peekToken().getType() == TokenType.LEFT||
lexer.peekToken().getType() == TokenType.RIGHT||
lexer.peekToken().getType() == TokenType.UP||
lexer.peekToken().getType() == TokenType.DOWN||
lexer.peekToken().getType() == TokenType.COLOR||
lexer.peekToken().getType() == TokenType.REP) {
ParseTree expression = Expr();
//talk("[Expr()] Read operator " + operator);
//talk("[Expr()] Read term done");
result = new ExprNode(result, expression);
}
//--depth;
//talk("Leave Expr()");
return result;
}
private ParseTree Cmd() throws SyntaxError {
Token t = lexer.nextToken();
if(t.getType() == TokenType.FORW || t.getType() == TokenType.BACK || t.getType() == TokenType.LEFT || t.getType() == TokenType.RIGHT) {
Token num = lexer.nextToken();
if(num.getType() != TokenType.DECIMAL) {
throw new SyntaxError();
}
if(lexer.nextToken().getType() != TokenType.PERIOD) {
throw new SyntaxError();
}
return new CMDNode(t.getType(), (Integer)num.getData());
}
else if(t.getType() == TokenType.UP || t.getType() == TokenType.DOWN) {
if(lexer.nextToken().getType() != TokenType.PERIOD) {
throw new SyntaxError();
}
return new CMDNode(t.getType());
}
else if(t.getType() == TokenType.COLOR) {
Token hex = lexer.nextToken();
if(hex.getType() != TokenType.HEX) {
throw new SyntaxError();
}
if(lexer.nextToken().getType() != TokenType.PERIOD) {
throw new SyntaxError();
}
return new CMDNode(t.getType(), (String)hex.getData());
}
else if(t.getType() == TokenType.REP) {
Token num = lexer.nextToken();
if(num.getType() != TokenType.DECIMAL) {
throw new SyntaxError();
}
if(lexer.peekToken().getType() == TokenType.QUOTE) {
Expr();
}
else {
Cmd();
}
}
else {
throw new SyntaxError();
}
return null;
}
}
부분 REP 토큰을 처리하려고 할 때 파서 코드 맨 아래에 있습니다.
else if(t.getType() == TokenType.REP) {
Token num = lexer.nextToken();
if(num.getType() != TokenType.DECIMAL) {
throw new SyntaxError();
}
if(lexer.peekToken().getType() == TokenType.QUOTE) {
Expr();
}
else {
Cmd();
}
문법에 따라 REP는 두 가지 "결과"를 가질 수 있습니다. 하나의 명령 X 번 또는 명령 집합 X 번을 반복 할 수 있습니다 (QUOTE 토큰을 사용하여 집합을 식별 함). 그러나 나는 두 번째 if과 else 진술서 내에서 무엇을 해야할지 또는 무엇을 써야할지 모른다. 나는 현재 방금 Expr() 함수 또는 Cmd() 함수에 대한 재귀 호출을 추가했지만 이것이 잘못되었다고 생각합니다. 나는 이것이 현재 CMDNode에 연결된 노드 대신에 두 번째 파스 트리를 대신 생성 할 것이라고 생각한다. 이 문제를 해결하는 방법을 모르겠습니다.
길고 잔인한 설명을 드려 죄송합니다. 문제가 무엇인지 이해 하셨기를 바랍니다. 이 문제가 당신에게 바보 보일 수 있도록 :
감사를
은 그냥 (!) 참고로, 저는 트리 구조로 훨씬 이전에 경험하지 않은!