linguaggio con due operatori binari della stessa precedenza, associativo sinistro e associativo destro

11

Ci sono linguaggi di programmazione (o scripting) (o qualche linguaggio specifico del dominio) con due operatori binari opl e opr di stessa precedenza con opl che è associato a sinistra e opr è a destra-associativa?

(Non riesco a trovare un simile esempio, ma sto provando a codificare un parser generale abbastanza per gestire quel caso strano)

In che modo le espressioni della forma x opl y opr z o x opr y opl z essere analizzato? E più in generale con ancora più operandi?

    
posta Basile Starynkevitch 22.02.2016 - 09:49
fonte

2 risposte

10

Ecco tre lingue che ti permettono di definire i tuoi operatori, che fanno due e mezzo differenti cose! Haskell e Coq rifiutano entrambi questi tipi di imbrogli - ma in modo diverso - mentre Agda consente questo tipo di mescolanza di associatività.

Innanzitutto, in Haskell , semplicemente non ti è permesso farlo. Puoi definire i tuoi operatori e dare loro la precedenza (da 0-9) e l'associatività di tua scelta. Tuttavia, il rapporto Haskell ti impedisce di mescolare le associazioni :

Consecutive unparenthesized operators with the same precedence must both be either left or right associative to avoid a syntax error. [Haskell 2010 Report, Ch. 3]

Quindi, in GHC , se definiamo un operatore associato a sinistra ( infixl ) <@ e right- operatore associativo @> allo stesso livello di precedenza - diciamo 0 - quindi la valutazione di x <@ y @> z restituisce l'errore

Precedence parsing error
    cannot mix ‘<@’ [infixl 0] and ‘@>’ [infixr 0] in the same infix expression

(Infatti, puoi anche dichiarare un operatore come infisso ma non associativo, come == , in modo che x == y == z sia un errore di sintassi!)

D'altra parte, c'è il proverio della lingua / teorema tipicamente dipendente Agda (che, certamente , è considerevolmente meno mainstream). Agda ha la sintassi più malleabile di qualsiasi lingua che conosca, supportando gli operatori mixfix : la libreria standard contiene la funzione

if_then_else_ : ∀ {a} {A : Set a} → Bool → A → A → A

che, quando chiamato, è scritto

if b then t else f

con gli argomenti che riempiono i caratteri di sottolineatura! Lo dico perché questo significa che deve supportare un parsing incredibilmente flessibile. Naturalmente, Agda ha anche dichiarazioni di fissità (anche se i suoi livelli di precedenza spaziano su numeri naturali arbitrari e sono tipicamente in 0-100) e Agda consente di combinare operatori con la stessa precedenza ma differenti fissità. Tuttavia, non posso trovare informazioni a riguardo nella documentazione, quindi ho dovuto sperimentare.

Riutilizziamo <@ e @> da sopra. Nei due casi semplici, abbiamo

  • x <@ y @> z analizzando come x <@ (y @> z) ; e
  • x @> y <@ z analizzando come (x @> y) <@ z .

I penso che cosa fa Agda è raggruppare la linea in blocchi "associativo sinistro" e "associativo destro" e - a meno che non stia pensando a cose sbagliate - il pezzo associativo di destra diventa "priorità" "nel prendere gli argomenti adiacenti. Quindi questo ci dà

a <@ b <@ c @> d @> e @> f <@ g

analisi come

(((a <@ b) <@ (c @> (d @> (e @> f)))) <@ g

o

Tuttavia,nonostanteimieiesperimenti,hoindovinatolaprimavoltachel'hoscritto,chepotrebbeessereistruttivo:-)

(EAgda,comeHaskell,haoperatorinonassociativi,chefornisconocorrettamenteerroridianalisi,quindisarebbepossibilecheancheleassociazionimistegenerinounerroredianalisi.)

Infine,c'èillinguaggioproverbio/dattilografotipicamente Coq , che ha una sintassi ancora più flessibile di Agda perché le sue estensioni di sintassi vengono effettivamente implementati dando specifiche per i nuovi costrutti sintattici e quindi riscrivendoli nel linguaggio core (vagamente macro-like, suppongo). In Coq, la sintassi dell'elenco [1; 2; 3] è un'importazione facoltativa dalla libreria standard. Le nuove sintassi possono anche legare le variabili!

Ancora una volta, in Coq, possiamo definire i nostri operatori di infisso e dargli dei livelli di precedenza (da 0 a 99, soprattutto) e associatività. Tuttavia, in Coq, ciascun livello di precedenza può avere solo un'associatività . Quindi se definiamo <@ come left-associative e poi proviamo a definire @> come right-associative allo stesso livello - diciamo, 50 - otteniamo

Error: Level 50 is already declared left associative while it is now expected to be right associative

La maggior parte degli operatori in Coq si trova su livelli divisibili per 10; se ho avuto problemi di associatività (queste associazioni di livello sono globali), ho generalmente superato il livello di uno in entrambe le direzioni (di solito in aumento).

    
risposta data 22.02.2016 - 11:44
fonte
2

Dal momento che sono stati resi popolari da Douglas Crockford, i parser di Pratt (o parser di Precedenza dell'operatore top-down) hanno iniziato a diventare più comuni. Questi parser funzionano da una tabella di precedenza e associatività degli operatori, anziché avere le regole incorporate in una grammatica fissa, quindi sono utili per le lingue che consentono agli utenti di definire i propri operatori.

Hanno una funzione di analisi che funziona analizzando dapprima il termine più a sinistra di un'espressione, quindi associa in modo ricorsivo i nuovi operatori e i termini della mano destra finché si collegano in modo appropriato. Gli operatori associativi di sinistra vincoleranno i termini della mano destra che hanno la precedenza fino a includere la stessa precedenza, mentre gli operatori associativi di destra si collegheranno solo al loro livello di precedenza, ma non lo includeranno. Credo che questo si traduca nello stesso albero di analisi di Agda, citato sopra.

    
risposta data 22.02.2016 - 22:13
fonte

Leggi altre domande sui tag