1. casa
  2. Domanda e risposta
  3. Le grammatiche dei linguaggi di programmazione moderni sono prive di contesto o sensibili al contesto?

Le grammatiche dei linguaggi di programmazione moderni sono prive di contesto o sensibili al contesto?

2012-03-11 13 views

risposta

6

C++ non è né context-free né sensibile al contesto, dal momento che il template system is Turing-complete e determinare se un pezzo di codice C++ è legale C++ è indecidibilmente difficile. Ad esempio, potrei definire una classe template che simula una TM su una stringa e quindi crea una costante con valore 1 se la macchina accetta e 0 se non lo fa. Se ho fatto, quindi il seguente codice sarebbe legale sse TM fermato sull'ingresso proposta:

int myArray[TMTemplate</* ... args ... */>::value];

Poiché se TM respinge, questo crea un array di dimensione 0, che non è consentito.

Né C# né Java sono privi di contesto, poiché è noto che il controllo di una variabile utilizzata correttamente e in modo coerente in un particolare ambito non è privo di contesto (la dimostrazione è complessa e si basa su Ogden's lemma). Tuttavia, non sono sicuro se siano sensibili al contesto.

Spero che questo dia una risposta parziale alle tue domande!

fonte

2012-03-11 05:33:10 templatetypedef

+4

Non sono sicuro che la completezza dei modelli influenzi la * grammatica * del C++. Certo, i risultati della metaprogrammazione del modello possono decidere se un programma supera determinati controlli semantici, ma ciò va ben oltre lo scopo delle grammatiche. E i modelli non cambiano nulla sulla sintassi: se il programma ha un errore di sintassi, i modelli non vengono instanciati e, se sono instanciati, non danno mai errori di sintassi. Prendi in considerazione anche tutte le lingue tipizzate in modo statico sensibili al contesto perché devi conoscere tutti i tipi coinvolti per decidere se, ad es. una dichiarazione di assegnazione è valida? – delnan

+0

@ delnan- Stavo interpretando la domanda in modo tale che qualsiasi linguaggio tipizzato staticamente non sia privo di contesto, poiché la correttezza del programma dipende da come i tipi si riferiscono. Mi sto avvicinando a questo dal punto di vista di "se hai raccolto tutte le stringhe che rappresentano programmi X legali, che tipo di linguaggio torni?" Quel set non è privo di contesto, anche se come precondizione per essere valido la stringa deve essere nella grammatica. Ha senso? E questa è un'interpretazione irragionevole della domanda? – templatetypedef

+2

Secondo questa interpretazione, la tua risposta ha un senso. Non è come avrei interpretato la domanda, ma perché presumo che "linguaggio senza contesto" (usato da OP) sia solo una scorciatoia per "linguaggio con una grammatica senza contesto". Ma penso che abbia senso (e se quella era davvero la domanda, la tua risposta è corretta). Dovresti aggiungere questa spiegazione alla risposta, per evitare ulteriori equivoci. – delnan

Problemi correlati

 Problemi correlati