まず、悪いタイトルには申し訳ありません。私は本当にこの問題と呼ぶべきか分からない。Java - リーフノードの解析ツリー再帰を処理する方法は?
私はTurtleグラフィックスプログラムのパーサーをコーディングしようとしています(それが何であるかわからない場合は、基本的には「タートル」の動きを指示するコマンドからなる小さなプログラミング言語を作成します)例えば、「5 LEFT 45 FORW」入力は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;
}
}
(スウェーデンにあるコメントに申し訳ありませんが):(私はコードが、最も重要な部分のすべてを追加
/**
* 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トークンを処理しようとしているときに、Parserコードの一番下にあります。
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は2つの「結果」を持つことができます。それは、1回のコマンドXの回数だけ、または一連のコマンドX回を繰り返すことができます(私はQUOTEトークンの助けを借りてセットを識別します)。しかし、私は第2のif
とelse
ステートメントの中で何をすべきか、何を書くべきか分かりません。私は現在、Expr()
関数またはCmd()
関数への再帰呼び出しを追加しましたが、これは間違っていると思います。私は、代わりに、現在のCMDNodeに接続されているノードの代わりに、2番目のParseツリーを作成すると考えています。私はこれをどのように解決するか分かりません。
長くて厄介な説明を申し訳ありませんが、問題の内容を理解していただければ幸いです。
ちょうど追記として、私はツリー構造でかなり早い経験を持っていなかったので、この問題はあなたに愚かに見えるかもしれません:)
をありがとう!