8

J. Barkley Rosser の " Logic for Mathematicians " で、彼は記法を使用して括弧が多すぎるのを避けています。論理学者がいつこの表記法を使い始めたのかはわかりませんが、1957 年に最初に出版されたその本と、1916 年に出版されたJGP Nicod の論文もこの表記法を使用していることを知っています。明らかに、これにはかなり長い歴史がありますが、今日では現代の論理学者には好まれていません。

プログラミングの世界では、LISP と同様のプログラミング言語で、プログラマーが適切な (膨大な!) 括弧の数を追跡するという大きな課題があります。Haskell は$、機能の一部を提供する演算子を提供しますが2 * $ 3 + 4、ドットほど強力ではないとは言えません (以下の例を参照)。C 言語のシリアルは、従来の操作の優先順位を使用しますが、場合によっては、ネストされた括弧が依然として必要です。では、なぜ実際の言語がこの戦略を使用していないのだろうか? 試してみましたが、文法を書くことさえできないことがわかりました!

+演算子とが 2 つしかなく*、すべての項が整数であるおもちゃの電卓言語の例をいくつか示しましょう。

この表記法を使用すると、翻訳者は次のテスト ケースに合格する必要があります。

1 + 3 .* 2
= (1 + 3) * 2
1 *. 3 + 2
= 1 * (3 + 2)
1 *. 2 +. 2
= (1 * 2) + 2
2 *: 2 + 3 .* 4
= 2 * ((2 + 3) * 4)

この表記法の詳細をすべて説明することはできません。Rosser の本では 5 ページ近くかかります。しかし、一般的に (そして短く)、.演算子の前後のドットは「セパレーター」を表し、両側を押しのけます。コロン:はより強力な区切り記号であり、3 つのドット.:または:.さらに強力ですが、よりも小さい::などです。

上記の言語の文法をどのように書き、それを解析できるのだろうか? また、この表記法は廃止されましたが、プログラマの目には非常に明確に見えることがわかりました。それで、その長所と短所は何ですか？

4

3 に答える 3

11

ドット表記法は、Russell と Whitehead がPrincipia Mathematica (1910-1913)で使用したことで最も有名ですが、この表記法はGuiseppe Peanoから借用したものです。また、アロンゾ・チャーチ、ウィラード・ヴァン・オーマン・クワイン、およびその他の影響力のある論理学者によっても使用されました (スタンフォード哲学百科事典のこのエントリを参照してください)。

少し練習すれば、ドット表記の数式を読むのは難しくありませんが、見た目ほどエレガントではありません。まず、Russell と Whitehead は、否定演算子で括弧を使用することが依然として有用であることを発見しました~。

*3·01. p.q .=. ~(~p v ~q)

上記の例が示すように、ドットは結合演算子としても優先順位を表すためにも使用されます。したがって、より強い接続詞は:または と書かれることもあり:.ます。

最後に、視覚的な煩雑さを軽減するために (私が思うに)、Russell と Whitehead は優先関係も使用します。この関係では、演算子のセットが 3 つの優先グループに分割され、優先順位の高い演算子のドットが同じ数のドットを支配するようになります。優先順位の低い演算子の場合。優先順位が等しい演算子間で、ドットの数が同じであることは正当ではありませんが、ラッセルとホワイトヘッドは、p v q v r重要でない優先順位を指定する必要を回避できるようにするために、いくつかの三項演算子も定義しました。(私の知る限り、そのような式の正確な構文解析規則は正式に綴られていませんが、定義は PM に記載されています。)

そうは言っても、分流場アルゴリズムの変形を使用してドット表記を解析することはそれほど難しくありません。残念ながら、文脈自由文法では解析できないため、自動ツールで生成された文法にはあまり役に立ちません。GLR パーサーでさえ CFG に制限されています。(ドット表記が文脈自由ではないという事実は、ポンピング補題で証明できます。これは、通常のポンピング補題の適用よりもかなり興味深い演習になります。少なくとも私見です。)

CFG に無数の (ドット) 記号とそれに対応する無数の規則を持たせると、文法 (または、より正確には、ほとんどの規則がドットによってパラメーター化されるため、文法テンプレート) を作成するのは非常に簡単になります。 -カウント）。したがって、理論的には、最初にスキャンして使用されるドットの最大数を見つけ、次にテンプレートから対応する有限 CFG を生成することにより、ドット式を解析できます。（結果は、ドットのシーケンスごとに個別のターミナルを定義する限り、LALR（1）になります。）実際には、これはCFGで述語を使用して行われるため、パーサージェネレーターを使用してパーサーを作成できます。述語（たとえば、ANTLRはそうしますが、個人的にはボトムアップジェネレーターを使用して、左再帰の除去をいじるのを避けます。）

少なくとも理論的には、必要以上のドットを使用する可能性があるため、ドット表記には独自の「冗長な括弧」のバリエーションがあることに注意することが重要です。上記の (理論的ではあるが実際には有用ではない) アルゴリズム (CFG の自動生成) をいじっていたとき、ドットの最小性を要求する方が簡単であることがわかりました。テストする PM の機械可読コピーを見つけることができませんでしたが、私が行ったすべての検索で、ドット最小ではない式は見つかりませんでした。それが衝動的な整理整頓の結果なのか、それともドット最小表現のみが正当であるという考えの結果なのかはわかりません。

于 2013-08-29T15:22:48.423 に答える
3

ここに興味深いアプリケーションがあります。Perl6では、言語を拡張して、新しい演算子を追加し、既存の演算子に対する優先順位を定義できます。次のコード サンプルでは、​​演算子*. .*などを定義しています。以下のテストに合格します。

use v6;
use Test;

sub infix:<*.>  ($a, $b) is looser(&infix:<+>)  { $a * $b }
sub infix:<.*>  ($a, $b) is looser(&infix:<+>)  { $a * $b }
sub infix:<*:>  ($a, $b) is looser(&infix:<*.>) { $a * $b }
sub infix:<:*>  ($a, $b) is looser(&infix:<.*>) { $a * $b }

sub infix:<+.>  ($a, $b) is looser(&infix:<*.>) { $a + $b }
sub infix:<.+>  ($a, $b) is looser(&infix:<.*>) { $a + $b }
sub infix:<+:>  ($a, $b) is looser(&infix:<*:>) { $a + $b }
sub infix:<:+>  ($a, $b) is looser(&infix:<:*>) { $a + $b }

# Tests

is 1 + 3 .* 2,
    (1 + 3) * 2;

is 1 *. 3 + 2,
    1 * (3 + 2);

is 1 *. 2 +. 2,
    (1 * 2) + 2;

is 2 *: 2 + 3 .* 4,
    2 * ((2 + 3) * 4);
于 2013-09-06T07:42:36.840 に答える
-1

ISO コア標準の Prolog では、古い論理士のドット表記を直接解析することはできません。ドットを含む記号を形成できますが、顕著なものは univ 演算子です

(=..)/2. 演算子として使用されるさまざまな記号は、解析された用語のさまざまなファンクターにつながります。問題を軽減するために、sys_alias/1オペレーターを導入しました

私のPrologシステムのプロパティ。定義の例を次に示します。

:- op(750, xfx, .=.).
:- set_oper_property(infix(.=.), sys_alias(=)).

上記では、 の 2 番目のバリアントを使用します(=)/2。通常(=)/2は operator level700があり、2 番目のバリアントにはより高い operator level750があり、目的の括弧につながります。

そして、ここに実行例があります：

Jekejeke Prolog 4, Runtime Library 1.4.5

?- write(p = q .=. q = p), nl.
(p = q) = (q = p)
Yes

この獣を解析するのに役立つかもしれません:

補綴の単一公理について。Ⅱ．
ソボチンスキ、ボレスワフ - 1961 年
https://projecteuclid.org/euclid.ndjfl/1093956834

于 2020-08-09T00:11:46.980 に答える