2017-12-25 28 views
0

まず、悪いタイトルには申し訳ありません。私は本当にこの問題と呼ぶべきか分からない。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のifelseステートメントの中で何をすべきか、何を書くべきか分かりません。私は現在、Expr()関数またはCmd()関数への再帰呼び出しを追加しましたが、これは間違っていると思います。私は、代わりに、現在のCMDNodeに接続されているノードの代わりに、2番目のParseツリーを作成すると考えています。私はこれをどのように解決するか分かりません。

長くて厄介な説明を申し訳ありませんが、問題の内容を理解していただければ幸いです。

ちょうど追記として、私はツリー構造でかなり早い経験を持っていなかったので、この問題はあなたに愚かに見えるかもしれません:)

をありがとう!

答えて

0

これはテストされていない疑似コードですが、開発を続けるのに十分であるはずです。

// Existing code 
else if(t.getType() == TokenType.REP) { 
    ... 
} 
// New code starts here 
else if(t.getType() == TokenType.QUOTE) { 
    // This "command" is only used when parsing the input string. 
    return new CMDNode(t.getType()); 
} 
// Existing code again 
else { 
    throw new SyntaxError(); 
} 

 if(lexer.peekToken().getType() == TokenType.QUOTE) { 
      // Here we know there will be one or more children and that the sequence starts and ends with a "quote command" 
      List<ParseTree> children = new ArrayList<>(); 
      ParseTree child = Cmd(); // The initial "quote command" - just ignore 
      while ((child = Cmd()) != TokenType.QUOTE) { 
       // Will stop looping when the second quote is found 
       children.add(child); 
      } 
      return new CMDNode(t.getType(), children); // Yes, you need to create a new constructor 
     } 
     else { 
      // Here we know there will only one child 
      ParseTree child = Cmd(); 
      return new CMDNode(t.getType(), child); 
     } 

はまた、新しい "引用コマンド" を追加する必要があります

関連する問題