HN 日本語サマリー

← 一覧へ戻る
プログラミング

Show HN: Yantra – C++向けLALR(1)パーサー生成ツール

Show HN: Yantra – an LALR(1) parser generator for C++ (github.com)

33 pointsby renjipanicker17 コメント

要約

Yantraは、C++で利用できるLALR(1)パーサー生成ツールです。従来のパーサー生成ツールとは異なり、構文解析中にセマンティックアクションを実行するのではなく、まず完全な抽象構文木(AST)を構築してから、それをトップダウンでウォークします。これにより、親ルールのアクションが子ノードの処理前に実行されるなど、より柔軟な構文解析が可能になります。

全文翻訳

YantraはC++用のパーサージェネレータです。lexer、parser、ASTウォーカーをすべて1つのツールから生成します。全体としてASTを構築してから、それをウォークします。

ほとんどのLALRパーサージェネレータ(Yacc、Bison、Lemon)は、解析中に、各ルールがボトムアップで還元されるときにセマンティックアクションを実行します。

これは、ルールのアクションが実行される時点で、その親がどのようになっているかまだ分からないことを意味します。このため、多くの文法で手作りのASTクラスが必要になり、兄弟ノードを先読みしたり、より多くのコンテキストが利用可能になるまで決定を遅延させたりする必要がある場合は、別途ウォークパスが必要になります。

一方、Yantraは常にまず完全なASTを構築し、その後、別のパスでトップダウンにウォークし、実行中にセマンティックアクションを呼び出します。親ルールのactionは、子ノードが訪問される前に実行できます。

単一の文法で複数のウォーカーを定義できます。例えば、同じパースからC++を出力するものと、Javaを出力するものの両方です。ASTとウォーカークラスは両方とも生成されます。

簡単な例(完全版、コンパイルコマンド付きはREADMEにあります):

  start := expr;

  expr := expr(a) PLUS expr(b)
  %{
      std::cout << "Adding" << std::endl;
  %}

  expr := NUMBER(N)
  %{
      std::cout << "Number: " << N.text << std::endl;
  %}

  NUMBER := "\d+";
  PLUS := "\+";
  WS := "\s+"!;

これを "1 + 2 + 3" で実行すると、以下のように出力されます:

  Adding
  Number: 1
  Adding
  Number: 2
  Number: 3

外側の "Adding"、つまりツリーのルートが、子ノードのどちらよりも先に表示されます。これは、アクションが実行される前にツリー全体が存在しているからこそ可能です。

その他の機能:モードサポート付きの統合lexer(ネストされたコメントなどのため)、生成されたmain()を含むオプションの単一ファイル出力モード、C++23、MITライセンス。

まだ若い(0.5.1、1.0未満)シングルメンテナープロジェクトなので、初期段階として扱ってください。完成度が高く見えるよりも、何が壊れるかを知りたいです。

既知の制限事項は https://github.com/TantrixAuto/yantra/blob/main/docs/known_limitations.md にリストされています。

リポジトリ: https://github.com/TantrixAuto/yantra

フィードバックや質問は歓迎します。私もここにいます。