プログラミング言語を構文木でパースする際goto文はどう処理すればよいか

Question

自作言語のコンパイルを考えています。(コンパイル以前に構文解析で躓いています)

何も考えずに、先頭からソースを読み、再帰的にパースしていたのですが、goto文の扱いに困ってしまいました。(あとから構文木という言葉を知りました。たぶん構文木だと思います)。C#で構文解析をする想定です。

例えば、if(A){B}else{C}なら、Aを必ず実行してその結果BまたはCを実行する、といった具合にパースできたのですが、goto文をパースしようと思ったときに脈絡のない場所にジャンプできてしまうためどうすればよいかわからなくなりました

if, while(for), break, continue, 四則演算, この辺りはどれもクラスで表すことができ、パースしながらオブジェクト化しています。実際の実装は、オブジェクト指向の練習を兼ねて、足し算クラス、条件分岐クラスなどなど…で実装してみました。
↓にイメージを載せます。

//基底クラス
abstract class baseClass{
    public virtual returnObj Exec();  //構文を実行する
}

//複数の処理を連続して行うだけのクラス
class Sequence: baseClass{
  public List<baseClass> seq;
  public override Exec(){
    foreach(s in seq) s.Exec();  //順に実行する
  }
}

//足し算をするクラス
class Add: baseClass{
  public int left, right;
  public override returnObj Exec(){
    return left + right;
  }
}

//条件分岐をするクラス
class If: baseClass{
  public baseClass ConditionalObj;  //条件を指定
  public baseClass trueObj;　　　//↑がtrueのとき実行
  public baseClass falseObj;　　//↑がfalseのとき実行

  public override returnObj Exec(){
    if(ConditionalObj.Exec()){
      trueObj.Exec();
    }else{
      falseObj.Exec();
    }
  }
}

//画面に表示するクラス
class Print: baseClass{
  public returnObj printObj;
  public override returnObj Exec(){
    Console.write(printObj);
  }
}

「goto文は処理の流れを無視する構文だ」という言葉の意味がよくわかりました。
既存のコンパイラがgoto文をどのように解析？処理？しているのかヒントを教えていただけないでしょうか。

Comments

[episteme]

tagが C になってるけど C# のまちがい?

[ElecDove]

ありがとうございます。修正しました

[Zuishin]

C# には構文木を表現するための Expression クラスがあります。
Goto は Label を目標にします。

https://docs.microsoft.com/ja-jp/dotnet/api/system.linq.expressions.expression.goto?view=net-5.0
https://docs.microsoft.com/ja-jp/dotnet/api/system.linq.expressions.expression.label?view=net-5.0

Answer 1

既存のコンパイラがgoto文をどのように解析？処理？しているのか

例えば MetaJC++: A flexible and automatic program transformation technique using meta framework の §4.4. Goto Statement に一例があります。

AST（抽象構文木）上の表現としては、ジャンプ先のラベルノード（と後続命令AST）と、goto命令ノードとジャンプ先ラベル情報をそれぞれ持てばよいはずです。

---

if, while(for), break, continue, 四則演算, この辺りはどれもクラスで表すことができ、パースしながらオブジェクト化しています。

質問文からはソースコードからASTを構築するフェーズ(Lexer/Parser)と、そのASTを解釈実行(Interpreter)するフェーズを混同している印象を受けました。

自作言語とのことですから、そもそもC言語のような非構造化ジャンプを許すgoto構文をサポートする必要性があるかを再検討してもよいかもしれませんね。

Comments

[ElecDove]

回答ありがとうございます。
いただいたリンク先をよく読んでみます

>>質問文からはソースコードからASTを構築するフェーズ(Lexer/Parser)と、そのASTを解釈実行(Interpreter)するフェーズを混同している印象を受けました。
ありがとうございます。ここから見直してみます

[yohhoy]

リンク先はあくまでASTとgoto構文の関係例示のために取り上げただけですので、まずは一般的なコンパイラやインタプリタ（＝プログラミング言語処理系）がどのように作られ・動作するのかを調べた方が良いと思います。

例えば下記サイトなどが参考になるかも？
C#で作るインタプリタ https://webbibouroku.com/gorilla-interpreter

（質問文には"コンパイラ"とありますが、実現したい内容を見るに"インタプリタ"が近いと思います）

[ElecDove]

ありがとうございます
まだ読み始めたばかりですがまさに自分にぴったりの内容のように思えます
感謝です

Answer 2

C言語にはクラスというものがないので、そこまで難しく考えなくていいかと思いますが