Yacc
Yacc
その他の名称ベル研究所Yacc、AT&T Yacc
原著者スティーブン・C・ジョンソン
リポジトリ
言語C
オペレーティングシステムUnix、Unixライク、Plan 9、Inferno
プラットフォームクロスプラットフォーム
タイプコマンド
ライセンスプラン9: MITライセンス

Yacc（Yet Another Compiler-Compiler）は、スティーブン・C・ジョンソンが開発したUnixオペレーティングシステム用のコンピュータプログラムです。これは、先読み左から右への右端導出（LALR）パーサージェネレーターであり、バッカス・ナウア記法（BNF）に似た記法で書かれた形式文法に基づいてLALRパーサー（ソースコードの構文解析を試みるコンパイラーの一部）を生成します。 [ 1 ] Yaccは、BSDおよびAT&T Unixの標準ユーティリティとして提供されています。[ 2 ] GNUベースのLinuxディストリビューションには、Yaccの上位互換性のある代替品であるBisonが含まれています。[ 3 ]

歴史

1970年代初頭、ベル研究所/ AT&Tのコンピュータ科学者であるStephen C. Johnsonは、 B言語コンパイラ[ 4 ]（McIlroyのTMGコンパイラ-コンパイラ[ 5 ]を使用して開発）に排他的論理和演算子を挿入したいという理由でYaccを開発しましたが、これは困難な作業であることが判明しました。その結果、彼はベル研究所の同僚Al Ahoから、Yaccの基礎となったDonald KnuthのLR構文解析に関する研究を紹介されました。 [ 4 ] Yaccは[ 6 ]の影響を受け、TMGコンパイラ-コンパイラにちなんでその名前が付けられました。[ 7 ]

YaccはもともとBプログラミング言語で書かれていましたが、すぐにアラン・スナイダーによってC言語で書き直されました。 [ 5 ]これはバージョン3 Unixの一部として登場し、[ 8 ] Yaccの完全な説明は1975年に出版されました。[ 6 ]

ジョンソンはYaccを使ってポータブルCコンパイラを作成した。[ 8 ]ビャーネ・ストロウストルップもYaccを使ってC++の正式な仕様を作成しようとしたが、「Cの構文に打ち負かされた」。[ 9 ]ストロウストルップはYaccが言語の正式な仕様には不向きだと感じながらも、 C++の最初の実装であるCfrontの実装にYaccを使った。 [ 10 ]

2008年のインタビューでジョンソンは「YaccがUnixとCの普及に貢献したことが、私が最も誇りに思っていることだ」と語っている。[ 11 ]

説明

Yaccへの入力は、C言語のコードスニペット（「アクション」と呼ばれる）がルールに付加された文法です。出力はC言語のシフト還元パーサで、ルールが認識されるとすぐに、各ルールに関連付けられたC言語のスニペットを実行します。典型的なアクションには、構文木の構築が含まれます。ジョンソンの例を用いると、呼び出しnode(label, left, right)が指定されたラベルと子を持つ二分構文木ノードを構築する場合、ルールは 

式:式'+'式{ $$ = node ( '+' , $1 , $3 ); }

は合計式を認識し、それに対応するノードを構築します。特別な識別子$$、$1、$3 は、パーサのスタック上の項目を参照します。[ 6 ]

Yaccは、スキャナレス構文解析の場合には単独で使用できるパーサー（フレーズアナライザー）のみを生成します。しかし、完全な構文解析には通常、外部の字句解析器が必要です。この字句解析器は、まずトークン化段階（単語解析）を実行し、その後に構文解析段階が続きます。[ 6 ] LexやFlexなどの字句解析器生成器は、この目的のために広く利用可能です。IEEE POSIX P1003.2標準は、LexとYaccの両方の機能と要件を定義しています。[ 12 ]

AT&T Yaccのいくつかのバージョンはオープンソース化されています。例えば、Plan 9の標準ディストリビューションではソースコードが利用可能です。[ 13 ]

インパクト

Yaccや類似のプログラム（主に再実装）は非常に人気があります。Yacc自体はかつてはほとんどのUnixシステムのデフォルトのパーサージェネレータとして利用できましたが、その後、Berkeley Yacc、GNU Bison、MKS Yacc、Abraxas PCYACCといった、より新しく、ほぼ互換性のあるプログラムに取って代わられました。オリジナルのAT&T Yaccの更新版は、 SunのOpenSolarisプロジェクトに含まれています。いずれもオリジナルのYaccに対して若干の改良と追加機能を提供していますが、コンセプトと基本的な構文は同じままです。[ 14 ]

Yaccは、ベル研究所のライセンスの下でチャールズリバーデータシステムズのUNOSオペレーティングシステムで利用できるいくつかのUNIXツールの1つでもありました。[ 15 ]

Yaccで最初に実装された言語には、AWK、C++、[ 10 ] eqn、Picなどがあります。[ 16 ] [ 11 ] YaccはUnix上でポータブルCコンパイラの実装にも使用され、 FORTRAN 77、Ratfor、APL、bc、m4などのプログラミング言語のパーサーも実装されました。[ 8 ] [ 17 ]

YaccはOCaml、[ 18 ] Ratfor、ML、Ada、Pascal、Java、PHP、 Python、Ruby、Go、[ 19 ] Common Lisp [ 20 ] Erlangなど他の言語向けにも書き直されています。[ 21 ]

  • Berkeley Yacc : BerkeleyのYacc実装は、そのパフォーマンスと再利用制限のなさから、AT&T Yacc自体よりも急速に人気が高まりました。[ 22 ]
  • LALR パーサー: Yacc で生成されたパーサーの基礎となる解析アルゴリズム。
  • Bison : Yacc の GNU バージョン。
  • Lex (およびFlex 字句解析器) は、Yacc (および Bison) と組み合わせてよく使用されるトークン パーサーです。
  • BNFは文脈自由文法を表現するために使用されるメタ構文です。つまり、文脈自由言語を記述する正式な方法です。
  • PLY (Python Lex-Yacc)は、Python における Lex と Yacc の代替実装です。

参照

参考文献

  1. ^ 「プログラミング言語AZ：YACC」 Computerworld. 2013年1月31日時点のオリジナルよりアーカイブ。 2012年11月30日閲覧。
  2. ^ Levine, John (1992). Lex & yacc . セバストポル, カリフォルニア州: O'Reilly & Associates. p. xx. ISBN 1-56592-000-7。
  3. ^ジョン・レヴァイン (2009). Flex & bison . セバストポル、カリフォルニア州: オライリーメディア. p. xv. ISBN 978-0-596-15597-1。
  4. ^ a bモリス、リチャード（2009年10月1日）「スティーブン・カーティス・ジョンソン：今週のギーク」レッドゲート・ソフトウェア。2018年1月19日閲覧
  5. ^ a bリッチー、デニス・M. (1993年4月). 「C言語の発展」.プログラミング言語の歴史---II . Association for Computing Machinery, Inc. (1996年1月1日発行). doi : 10.1145/234286.1057834 . ISBN 0-201-89502-1675ページ、684ページ：TMG版のBが動作するようになった後、トンプソンはB自体を書き直しました（ブートストラップのステップ）。…ジョンソンが1973年にベル研究所に戻ったとき、彼がカナダに持ち込んだ言語の種が母国で進化していることに気づき、当惑しました。彼自身のyaccプログラムでさえ、アラン・スナイダーによってCで書き直されていました
  6. ^ a b c d Johnson, Stephen C. (1975). Yacc: Yet Another Compiler-Compiler (技術レポート). Murray Hill, New Jersey: AT&T Bell Laboratories. 32 . 2020年1月31日閲覧。
  7. ^ 「初期の翻訳用書記体系」アトラスコンピュータ研究所。
  8. ^ a b c McIlroy, MD (1987). A Research Unix reader: annotated excerpts from the Programmer's Manual, 1971–1986 (PDF) (技術レポート). CSTR. ベル研究所. 139.
  9. ^ストルストラップ、ビャルネ。「C++ の歴史: 1979 − 1991」(PDF)。
  10. ^ a bストルストラップ、ビャルネ。「Cfront ソースコード」。
  11. ^ a b Hamilton, Naomi (2008年7月9日). 「Yacc、Unix、そしてベル研究所卒業生Stephen Johnsonからのアドバイス」 www.computerworld.com . 2020年8月22日時点のオリジナルよりアーカイブ。 2020年11月10日閲覧。
  12. ^lex  – Shell and Utilities Reference, The Single UNIX Specification、バージョン 5、 The Open Group発行、yacc – Shell and Utilities Reference, The Single UNIX Specification、バージョン 5、 The Open Group発行。
  13. ^ 「plan9: UC BerkeleyによるGPLv2に基づくPlan 9のリリース」 GitHub 、 2017年12月26日。 2018年1月2日閲覧。
  14. ^バイソンマニュアル：歴史
  15. ^ 『宇宙のインサイダーガイド』（PDF） Charles River Data Systems, Inc. 1983年、13ページ。
  16. ^ 「UNIXスペシャル：カーニハン教授とブレイルスフォード教授」 Computerphile 、 2015年9月30日。2021年12月11日時点のオリジナルよりアーカイブ。
  17. ^カーニハン, ブライアン・W.; パイク, ロブ (1984). Unixプログラミング環境. プレンティス・ホール. ISBN 0-13-937681-X。
  18. ^ 「OCamlユーザーズマニュアル：第12章 字句解析器とパーサジェネレータ（ocamllex、ocamlyacc）」。2013年11月25日時点のオリジナルよりアーカイブ。2013年11月25日閲覧
  19. ^ 「Yacc.go: Goプログラミング言語用のYaccのバージョン」 。 2017年7月15日閲覧。
  20. ^ 「CL-Yacc: Yacc の Common Lisp バージョン」。
  21. ^ 「yecc: Yacc の Erlang 実装」。
  22. ^ジョン・レヴァイン（2009年8月）、flex & bison、オライリーメディア
WikibookのUnixガイドには、コマンドに関するページがあります。
「 https://en.wikipedia.org/w/index.php?title=Yacc&oldid=1307075298」から取得