Sfida di analisi: notazione punto vecchio logico

Question

In "Logic for Mathematicians" di J. Barkley Rosser utilizza una notazione per evitare troppe parentesi. Anche se non so quando i logici iniziano a usare questa notazione, ma so che quel libro pubblicato per la prima volta nel 1957 e lo J. G. P. Nicod's paper pubblicato nel 1916 usa anche questa notazione. Quindi, ovviamente, ha una storia piuttosto lunga, sebbene al giorno d'oggi questo non sia favorito dai logici moderni.

Nel mondo della programmazione, nei linguaggi di programmazione simili a LISP c'è una grande sfida per i programmatori di tenere traccia della quantità giusta (enorme!) Di parentesi. Haskell fornisce un operatore $ che fornisce parte delle funzionalità, ma dal momento che non si può dire 2 * $ 3 + 4 non è potente come i punti (vedi esempi sotto). I periodici in linguaggio C utilizzano una precedenza di operazione convenzionale, ma in alcuni casi sono ancora necessarie parentesi annidate profonde. Quindi mi chiedo perché nessuna lingua reale usa questa strategia? Ci ho provato, ma non ho trovato nemmeno in grado di scrivere una grammatica per questo!

Lasciami mostrare alcuni esempi di un linguaggio di calcolatrice giocattolo con solo due operatori + e * e tutti i termini sono numeri interi.

Con questa notazione, un traduttore deve superare i seguenti casi di test:

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) 

ho cann't spiegare tutti i dettagli di questa notazione, che costa quasi 5 pagine nel libro di Rosser. Ma in generale (e breve), un punto . prima o dopo un operatore rappresenta un "separatore", per spingere via i due lati. A due punti : è un separatore più forte, tre punti .: o :. è ancora più forte, ma meno di :: e così via.

Mi chiedo come possiamo scrivere una grammatica per la lingua sopra e quindi analizzarla? Anche se questa notazione è stata obsoleta, ho trovato che appare molto chiara all'occhio del programmatore. Quindi quali sono i suoi pro e contro?

Answer 1

La notazione a punti era più comunemente utilizzata da Russell e Whitehead nel Principia Mathematica (1910-1913) ma la notazione era presa in prestito da Guiseppe Peano. Veniva usato anche da Alonzo Church, Willard Van Orman Quine e altri influenti logici (vedi this entry nella Stanford Encylopedia of Philosophy).

Con un po 'di pratica, non è difficile leggere le formule in dot-notation, ma non è così elegante come appare prima. Per cominciare, Russell e Whitehead ancora trovato utile usare le parentesi con l'operatore di negazione ~:

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

Come mostra l'esempio esposizione qui sopra, il punto è utilizzato sia come l'operatore congiunzione e per esprimere la precedenza. Di conseguenza, una congiunzione più forte potrebbe essere scritta come : o anche :..

Infine, per ridurre l'ingombro visivo (suppongo), Russell e Whitehead utilizzano anche relazioni di precedenza, in cui l'insieme di operatori è diviso in tre gruppi di precedenza, in modo tale che i punti per un operatore di precedenza superiore dominano un uguale numero di punti per un operatore di precedenza inferiore. Tra operatori di uguale precedenza, non è legale che il numero di punti sia uguale, ma Russell e Whitehead hanno anche definito alcuni operatori ternari come p v q v r per poter evitare di dover specificare la precedenza non importante. (Le precise regole di parsing per tali espressioni non sono mai state formulate formalmente, per quanto ne so, ma le definizioni appaiono in PM.

Detto questo, non è terribilmente difficile analizzare la notazione a punti utilizzando una variante dell'algoritmo di smistamento. Sfortunatamente, non può essere analizzato con una grammatica context free, che lo rende meno utile per le grammatiche generate con strumenti automatici. Anche i parser GLR sono limitati ai CFG. (Il fatto che la notazione a punti non sia libera dal contesto può essere dimostrata con il lemma del pompaggio, ma è un esercizio piuttosto interessante rispetto alle solite applicazioni di lemma di pompaggio, per lo meno imho.)

Se si consente al CFG di avere un numero infinito di simboli (punto) e un corrispondente numero infinito di regole, quindi è abbastanza semplice scrivere una grammatica (o, più precisamente, un modello di grammatica poiché la maggior parte delle regole sono parametrizzate per numero di punti). Quindi, in teoria, è possibile analizzare un'espressione di punti mediante la prima scansione per trovare il numero massimo di punti utilizzati e quindi generare il CFG finito corrispondente dal modello. (Il risultato è LALR (1) purché si definisca un terminale separato per ogni sequenza di punti.) In pratica, questo sarebbe fatto usando i predicati nel CFG, così si potrebbe creare un parser con un parser-generator che permetta predicati (ad esempio ANTLR, ma personalmente utilizzerei un generatore bottom-up per evitare di giocherellare con l'eliminazione della ricorsione sinistra.)

È importante notare che la notazione a punti ha una sua variante di "parentesi ridondanti" ", dal momento che potresti, almeno in teoria, usare più punti del necessario. Quando stavo giocando con l'algoritmo (teorico ma non molto utile) sopra - generando automaticamente CFG - ho trovato più facile richiedere la minimizzazione dei punti, perché altrimenti si finisce per creare molte più regole di unità. Non ero in grado di trovare una copia leggibile dalla macchina di PM con cui testarla, ma in tutte le ricerche che ho fatto, non ho mai trovato un'espressione che non fosse minimale. Non so se questo fosse il risultato di un ordine compulsivo o dell'idea che solo le espressioni dot-minimal erano legali.

Answer 2

Ecco una domanda interessante. Perl6 consente di estendere la lingua, aggiungere nuovi operatori e definire la loro precedenza rispetto agli operatori esistenti. Il seguente esempio di codice definisce gli operatori *..* ecc. Le prove di seguito passano.

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);