ときどきの雑記帖 RE* (新南口)

無理だ!(YOU CAN NOT DO THAT)

メモメモ

Calculator Homepage

Calculator Homepage - Hayden’s Calculator Site - calculators.haywalk.ca

awkcc

どういう経緯かわからんけど、awkccのソースコードがgithubで公開されている。 ライセンスは

awkcc is licensed under the BSD 2-Clause “Simplified” License.

とのこと。

dash

tklauser/dash: DASH Shell (clone of git://git.kernel.org/pub/scm/utils/dash/dash.git)

dash のparser.cにあるreadtoken1の実装が面白かった。 応用が利くかというと微妙なところではあるのだけど。

dash/parser.c at master · tklauser/dash

/*
 * If eofmark is NULL, read a word or a redirection symbol.  If eofmark
 * is not NULL, read a here document.  In the latter case, eofmark is the
 * word which marks the end of the document and striptabs is true if
 * leading tabs should be stripped from the document.  The argument firstc
 * is the first character of the input token or document.
 *
 * Because C does not have internal subroutines, I have simulated them
 * using goto's to implement the subroutine linkage.  The following macros
 * will run code that appears at the end of readtoken1.
 */

#define CHECKEND()	{goto checkend; checkend_return:;}
#define PARSEREDIR()	{goto parseredir; parseredir_return:;}
#define PARSESUB()	{goto parsesub; parsesub_return:;}
#define PARSEBACKQOLD()	{oldstyle = 1; goto parsebackq; parsebackq_oldreturn:;}
#define PARSEBACKQNEW()	{oldstyle = 0; goto parsebackq; parsebackq_newreturn:;}
#define	PARSEARITH()	{goto parsearith; parsearith_return:;}

STATIC int
readtoken1(int firstc, char const *syntax, char *eofmark, int striptabs)
{

goawk

しばらくリリースがないと思ったら いきなり数日間で何回もリリースがあった(今はまた落ち着いた?) ので、なんか大きなバグでもあったのかとということでリリースノートを見た。

Release Version 1.10.0 · benhoyt/goawk

This release includes a performance improvement and several bug fixes:

  • Only convert numeric string values to number lazily when needed: this gives an 11% average improvement on the real-world benchmarks, and around 40% improvement on my countwords script
  • Support ENVIRON special array
  • Show parse errors in a simpler, more standard format
  • Fix ARGV numeric string handling
  • Fix FILENAME numeric string handling
  • Fix field numeric string handling: this brings a slight performance decrease, but thankfully the lazy numeric string improvement above more than makes up for it
  • Fix parsing of string concatenation with prefix ++ and –
  • Fix output synchronization by flushing appropriately

This release also adds the AWKGo AWK-to-Go compiler as described here, but it’s a separate executable that doesn’t change GoAWK itself at all. Read more about AWKGo.

Release Version 1.11.0 (minor breaking change) · benhoyt/goawk

This release changes the handling of the builtin functions length, substr, index, and match to use character indexes instead of byte indexes, as per the POSIX spec.

So this is a small backwards-incompatible change, but I think it’s 1) warranted given GoAWK tries to conform to POSIX, and 2) won’t break most scripts, even ones that use non-ASCII, unless they use constant indexes for substr on non-ASCII strings. To revert to the previous bytes-index behavior, set interp.Config.Bytes to true when using from Go, or use the new goawk -b option for the command-line version.

This does affect the performance of those builtins, as some operations that were O(1) are now O(N) in the length of the string. Still, v1.10.0 introduced other performance improvements, and it’s pretty much a wash on the “real world” benchmarks overall.

See PR #83 and issue #35 for further discussion.

Release Version 1.12.0 · benhoyt/goawk

This release adds support for “getline lvalue” forms. See #85.

Release Version 1.13.0 · benhoyt/goawk

Support RS being multiple characters and regular expressions RS (#86), allowing significantly more powerful text processing. This is a Gawk extension to POSIX, which says, “If RS contains more than one character, the results are unspecified.”

バグがあってそれに対する対処で短期間に複数回のリリース、というわけではないらしい。

A Brief History of the Greater Ungulates

Bison のInfoを眺めていて興味深いものを見つけたので ちょいと訳をつけてみる。

11 A Brief History of the Greater Ungulates

Ungulatesとは、ここでは 有蹄類(有蹄類 - Wikipedia) のこと。Bisonもyacc(yak)も蹄を持った動物に関連した名前なので こうまとめたのでしょう。

11.1 The ancestral Yacc

Bison originated as a workalike of a program called Yacc - Yet Another Compiler Compiler.(1) Yacc was written at Bell Labs as part of the very early development of Unix; one of its first uses was to develop the original Portable C Compiler, pcc. The same person, Steven C. Johnson, wrote Yacc and the original pcc.

BisonはYacc(Yet Another Compiler Compiler. 脚注1) という名前を持った プログラムに互換のもの(a workalike)として始められました。 Yaccは最初期のUnixの一部としてBell Labsで作られ、 そのfirst usesのひとつは original Portable C Compiler, pcc を開発するためというものでした。 Yaccとoriginal pccは同じ人物、 Steven C. Johnsonが作成しました。

According to the author (2), Yacc was first invented in 1971 and reached a form recognizably similar to the C version in 1973. Johnson published ‘A Portable Compiler: Theory and Practice’ (*note Johnson 1978::).

作者の証言(脚注2)によれば、 Yaccは1971年に first invent され、 reached a form recognizably similar to the C version in 1973.
Johnson は‘A Portable Compiler: Theory and Practice’ を publishしました。(*note Johnson 1978::).

Yacc was not itself originally written in C but in its predecessor language, B. This goes far to explain its odd interface, which exposes a large number of global variables rather than bundling them into a C struct. All other Yacc-like programs are descended from the C port of Yacc.

Yaccは元々、Cではなくそのpredecessor languageであるBで書かれました。 このことはYaccの持つodd interface、 つまり、Cの構造体にbundlingしておらずに グローバル変数が大量にあるということ を説明するのに十分なものです。 すべてのYacc-likeなプログラムはCに移植されたYaccからdescendされたものです。

Yacc, through both its deployment in pcc and as a standalone tool for generating other parsers, helped drive the early spread of Unix. Yacc itself, however, passed out of use after around 1990 when workalikes with less restrictive licenses and more features became available.

Yacc自身はしかし、より制約の緩いライセンスとより多くの機能を持った workalikes が使えるようになった1990年前後以降には あまり使われなくなっていきました。

Original Yacc became generally available when Caldera released the sources of old versions of Unix up to V7 and 32V in 2002. By that time it had been long superseded in practical use by Bison even on Yacc’s native Unix variants.

オリジナルYaccは、2002年にCalderaがUnixのV7から32Vまでのバージョンの ソースを公開した時点でgenerally available になりました。 その頃までにはオリジナルYaccや Yaccのnative Unix variants さえも practical use においてBisonに取って代わられていました。

———- Footnotes ———-

(1) Because of the acronym, the name is sometimes given as “YACC”, but Johnson used “Yacc” in the descriptive paper included in the Version 7 Unix Manual (https://s3.amazonaws.com/plan9-bell-labs/7thEdMan/v7vol2b.pdf)

(2) https://lists.gnu.org/r/bison-patches/2019-02/msg00061.html

脚注

1)

略語(acronym)ということから"YACC"と書かれることがあるが、 JohnsonはVersion 7 Unixマニュアルに含まれていた descriptive paper で"Yacc"という表記を使っていた ( https://s3.amazonaws.com/plan9-bell-labs/7thEdMan/v7vol2b.pdf )。

2)

https://lists.gnu.org/r/bison-patches/2019-02/msg00061.html

11.2 yacchack

One of the deficiencies of original Yacc was its inability to produce reentrant parsers. This was first remedied by a set of drop-in modifications called “yacchack”, published by Eric S. Raymond on USENET around 1983. This code was quickly forgotten when zoo and Berkeley Yacc became available a few years later.

オリジナルYaccにあった欠点の一つは再入可能(reentrant)なパーザーを生成することができないという点です。 これはまず1983年にEric S. Raymond がUSENETで公開した “yacchack”と呼ばれる drop-in modifications のsetによりremedied されました。 しかしこのコードは数年後zooやBerkeley Yaccが利用可能になったときに 即座に忘れ去られてしまいました。

11.3 Berkeley Yacc

Berkeley Yacc was originated in 1985 by Robert Corbett (*note Corbett 1984::). It was originally named “zoo”, but by October 1989 it became known as Berkeley Yacc or byacc.

Berkeley Yacc はRobert Corbettによって1985年にoriginateされました (*note Corbett 1984::)。
初めは“zoo”という名前でしたが、 1989年10月にBerkeley Yacc もしくは byacc として知られるようになりました。

Berkeley Yacc had three advantages over the ancestral Yacc: it generated faster parsers, it could generate reentrant parsers, and the source code was released to the public domain rather than being under an AT&T proprietary license. The better performance came from implementing techniques from DeRemer and Penello’s seminal paper on LALR parsing (*note DeRemer 1982::).

Berkeley Yacc はオリジナルYaccに対して 三つのアドバンテージを有していました。 その三つとは、 より高速なパーザーを生成し、 再入可能なパーザーを生成可能で そしてBerkeley Yaccのソースコードは AT&Tのproprietary licenseの下ではなく パブリックドメインのものとしてリリースされた というものです。 Berkeley Yaccのbetter performanceは DeRemer と Penelloによる LALR parsingについての seminal paper (*note DeRemer 1982::) にあった手法の実装から得られらたものでした。

Use of byacc spread rapidly due to its public domain license. However, once Bison became available, byacc itself passed out of general use.

パブリックドメインライセンスだったことにより byaccの利用は急速に広まりましたが、 Bisonが利用できるようになると byacc は general use では用いられないようになっていきました。

11.4 Bison

Robert Corbett actually wrote two (closely related) LALR parsers in 1985, both using the DeRemer/Penello techniques. One was “zoo”, the other was “Byson”. In 1987 Richard Stallman began working on Byson; the name changed to Bison and the interface became Yacc-compatible.

1985年にRobert Corbettは実質的に二つの(密接に関係している)LALRパーザーを作り上げましたが、 そのどちらもDeRemer/Penelloの手法を用いていました。 そのひとつが“zoo”であり、もうひとつが“Byson”です。 1987年にRichard StallmanはBysonに対する作業を始めました。 BysonはBisonと改名され、インターフェースはYacc互換のものになりました。

The main visible difference between Yacc and Byson/Bison at the time of Byson’s first release is that Byson supported the ‘@N’ construct (giving access to the starting and ending line number and character number associated with any of the symbols in the current rule).

Bythonが最初にリリースされた時点での YaccとByson/Bisonとの間のmain visible difference は、 Bysonが‘@N’ construct をサポートしていたという点です (これは、current rule 中にあるシンボルのいずれかに結びついている 開始の行番号や終端の行番号、character numberに対するアクセスを提供します)。

There was also the command ‘%expect N’ which said not to mention the conflicts if there are N shift/reduce conflicts and no reduce/reduce conflicts. In more recent versions of Bison, ‘%expect’ and its ‘%expect-rr’ variant for reduce/reduce conflicts can be applied to individual rules.

違いには‘%expect N’もありました。 これは、N 個のshift/reduce conflicts があっても reduce/reduce conflictsがなければ そのconflictsについての報告をしないというものです。 より新しいバージョンのBisonでは、reduce/reduce conflicts に対する ‘%expect’ や、その ‘%expect-rr’ variant は individual rules に適用可能です。

Later versions of Bison added many more new features.

のちのバージョンのBisonでは多くの新機能が追加されました。

Bison error reporting has been improved in various ways. Notably. ancestral Yacc and Byson did not have carets in error messages.

Bisonのエラーレポートは様々な方法で改良されてきました。 特にエラーメッセージ中のキャレットは ancestral Yacc や Byson にはなかったものです。

Compared to Yacc Bison uses a faster but less space-efficient encoding for the parse tables (*note Corbett 1984::), and more modern techniques for generating the lookahead sets (*note DeRemer 1982::). This approach is the standard one since then.

Yaccと比較してBisonは高速かつ省スペースなencoding をパーザーテーブル に使っており(*note Corbett 1984::)、また、 先読み集合(lookahead sets)の生成にはよりmodernな手法(*note DeRemer 1982::)を用いていました。 このアプローチは以後の標準のものとなりました。

(It has also been plausibly alleged the differences in the algorithms stem mainly from the horrible kludges that Johnson had to perpetrate to make the original Yacc fit in a PDP-11.)

(オリジナルYaccをPDP-11で動作させるためにJohnsonがperpetrateしなければならなかった horrible kludges に主に由来するアルゴリズムの違いもあるだろうと言われています)

Named references, semantic predicates, ‘%locations’, ‘%glr-parser’, ‘%printer’, %destructor, dumps to DOT, ‘%parse-param’, ‘%lex-param’, and dumps to XSLT, LAC, and IELR(1) generation are new in Bison.

名前による参照, semantic predicates, ‘%locations’, ‘%glr-parser’, ‘%printer’, %destructor, DOTへのダンプ, ‘%parse-param’, ‘%lex-param’, XSLTへのダンプ, LAC (Lookahead Correction), IELR(1) generation はBisonで追加されました。

Bison also has many features to support C++ that were not present in the ancestral Yacc or Byson.

Bisonには (ancestral Yacc や Bysonが作られたころには存在していなかった) C++をサポートするための数多くの機能があります。

Bison obsolesced all previous Yacc variants and workalikes generating C by 1995.

Bisonは1995年までにすべてのprevious Yacc variants やCのコードを生成するworkalikes を時代遅れにしてしまいました。

11.5 Other Ungulates

The Yacc concept has frequently been ported to other languages. Some of the early ports are extinct along with the languages that hosted them; others have been superseded by parser skeletons shipped with Bison.

Yaccのコンセプトはしばしば他の言語へ移植されました。 そういった移植の初期のもののいくつかはそのホスト言語とともに絶滅し、 その他のものも Bisonに付随してshipされたスケルトンに取って代わられました。

However, independent implementations persist. One of the best-known still in use is David Beazley’s “PLY” (Python Lex-Yacc) for Python. Another is goyacc, supporting the Go language. An “ocamlyacc” is shipped as part of the Ocaml compiler suite.

しかし independent implementationsは残っています。 今も使われ続けているものでよく知られているもののひとつが David BeazleyによるPython向けの “PLY” (Python Lex-Yacc)です。 その他にもGo向けのgoyaccがありますし、 Ocaml compiler suiteの一部としてshipされている “ocamlyacc”があります。

ということなのでちょっと WG 14 Document log を眺めてみたのだけど

N2859 2021/10/15 Steenberg, break break

なんだこれ (いや、欲しい機能なのはわかるが)。

≪ prev 5年後の世界
next ≫ 虹とスニーカーの頃