Loading article…
| 原作者 | スティーブン・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のコンピュータ科学者であったスティーブン・C・ジョンソンは、 B言語コンパイラ[4]（マキロイのTMGコンパイラ・コンパイラ[5]を使用して開発された）に排他的論理和演算子を挿入したいという理由でYaccを開発しましたが、それは困難な作業であることがわかりました。その結果、ベル研究所の同僚アル・アホから、ドナルド・クヌースのLR構文解析に関する研究を紹介され、それがYaccの基礎となりました。[4] Yaccは[6]の影響を受け、TMGコンパイラ・コンパイラにちなんでその名前が付けられました。[7]
YaccはもともとBプログラミング言語で書かれていましたが、すぐにAlan SnyderによってC言語で書き直されました。 [5]これはバージョン3 Unixの一部として登場し、[8] Yaccの完全な説明は1975年に出版されました。[6]
ジョンソンはYaccを使用してポータブルCコンパイラを作成しました。[8] ビャーネ・ストロストラップもYaccを使用してC++の正式な仕様を作成しようとしましたが、「Cの構文に負けました」。[9]ストロストラップは、言語の正式な仕様には不適切であると判断しましたが、Yaccを使用してC++の最初の実装であるCfrontを実装しました。 [10]
2008年のインタビューでジョンソンは「YaccがUnixとCの普及に貢献したことは、私が最も誇りに思っていることだ」と語った。[11]
説明
Yacc への入力は、ルールにCコードの断片 (「アクション」と呼ばれる) が添付された文法です。出力は C のシフト リデュース パーサーで、ルールが認識されるとすぐに、各ルールに関連付けられた C の断片を実行します。一般的なアクションには、構文解析ツリーの構築が含まれます。Johnson の例を使用すると、呼び出し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] 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 の代替実装です。
参照
参考文献
- ^ 「プログラミング言語のAZ: YACC」。Computerworld。2013年1月31日時点のオリジナルよりアーカイブ。2012年11月30日閲覧。
- ^ Levine, John (1992). Lex & yacc . セバストポル、カリフォルニア州: O'Reilly & Associates. p. xx. ISBN 1-56592-000-7。
- ^ Levine, John (2009). Flex & bison . セバストポル、カリフォルニア州: O'Reilly Media. p. xv. ISBN 978-0-596-15597-1。
- ^ ab Morris, Richard (2009年10月1日). 「Stephen Curtis Johnson: Geek of the Week」. Red Gate Software . 2018年1月19日閲覧。
- ^ ab Ritchie, Dennis M. (1993 年 4 月)。「C 言語の開発」。プログラミング言語の歴史---II。Association for Computing Machinery, Inc. (1996 年 1 月 1 日発行) 。doi : 10.1145 / 234286.1057834。ISBN 0-201-89502-1. pp. 675, 684:
TMG バージョンの B が動作するようになった後、トンプソンは B 自体を書き直しました (ブートストラップ手順)。…ジョンソンが 1973 年にベル研究所に戻ったとき、彼がカナダに持ち込んだ言語の種が母国で進化していることに当惑しました。彼自身の yacc プログラムでさえ、アラン スナイダーによって C で書き直されていました。
- ^ abcd Johnson, Stephen C. (1975). Yacc: Yet Another Compiler-Compiler (技術レポート). Murray Hill, New Jersey: AT&T Bell Laboratories. 32 . 2020年1月31日閲覧。
- ^ 「初期の翻訳書記体系」アトラスコンピュータ研究所。
- ^ abc McIlroy, MD (1987). A Research Unix reader: annotated excerpts from the Programmer's Manual, 1971–1986 (PDF) (技術レポート). CSTR. Bell Labs. 139.
- ^ Stroustrup, Bjarne . 「C++の歴史: 1979−1991」(PDF)。
- ^ ab ス トロイストラップ、ビャルネ。 「Cfront ソースコード」。
- ^ Hamilton, Naomi (2008-07-09). 「Yacc、Unix、そしてベル研究所卒業生のStephen Johnsonからのアドバイス」www.computerworld.com。 2020年8月22日時点のオリジナルよりアーカイブ。2020年11月10日閲覧。
- ^ – シェルおよびユーティリティ リファレンス、The Single UNIX 仕様、バージョン 4、The Open Group発行、 – シェルおよびユーティリティ リファレンス、The Single UNIX 仕様、バージョン 4、The Open Group発行。
- ^ 「plan9: UC Berkeley による Plan 9 の GPLv2 でのリリース」。GitHub。2017年 12 月 26 日。2018 年1 月 2 日閲覧。
- ^ バイソンマニュアル: 歴史
- ^ The Insider's Guide To The Universe (PDF) . Charles River Data Systems, Inc. 1983. p. 13.
- ^ 「UNIXスペシャル：カーニハン教授とブレイルスフォード教授」。Computerphile 2015年9月30日。2021年12月11日時点のオリジナルよりアーカイブ。
- ^ カーニハン、ブライアン W.、パイク、ロブ (1984)。Unixプログラミング環境。プレンティス ホール。ISBN 0-13-937681-X。
- ^ 「OCaml ユーザーズマニュアル: 第 12 章 字句解析器とパーサージェネレーター (ocamllex、ocamlyacc)」 。 2013 年11 月 25 日閲覧。
- ^ 「Yacc.go: Goプログラミング言語用のYaccのバージョン」 。 2017年7月15日閲覧。
- ^ 「CL-Yacc: Yacc の Common Lisp バージョン」。
- ^ 「yecc: Yacc の Erlang 実装」。
- ^ ジョン・レヴァイン（2009年8月）、flex & bison、オライリーメディア
外部リンク
- 構文を学習およびテストするためのプレイグラウンド環境
WikibookのUnixガイドには、コマンドに関するページがあります。
- – シェルおよびユーティリティ リファレンス、The Single UNIX 仕様、バージョン 4、The Open Group
- – Plan 9プログラマーズマニュアル、第 1 巻
- – インフェルノ一般コマンドマニュアル
- – Linux一般コマンドマニュアル