Sono LALR C# e grammatica Java (x)?

Question

Mi chiedo se le grammatiche C# e Java siano LALR (x)? Se sì, qual è il valore di x?

Edit:

Dopo aver accettato la vera risposta, penso che sia meglio cambiare il Q in questo modo:

C'è un LALR (x) parser che potrebbe analizzare versioni correnti di Java (versione 7) o C# (versione 4)? Se sì, qual è il valore di x?

Answer 1

Non si può fare questa domanda senza prima definire una grammatica specifica per una lingua, come alcune grammatiche possono essere, e altre no.

Forse si intende la grammatica Java come pubblicata nelle recenti specifiche Java. Intendi per Java 7?

Non sono sicuro che sia possibile designare una grammatica specifica per C#, almeno non una di Microsoft, in particolare per C# 4.0; Non credo che abbiano pubblicato una grammatica.

Posso dirti che non penso che C# possa essere LALR (x), perché ha alcuni elementi che sembrano identificatori, ma possono essere parole chiave in determinati contesti. Ciò richiede al lexer di sapere che cosa si aspetta che il parser decida se un token identifier-like è una parola chiave, o just e identificatore. Quindi ci deve essere un feedback dal parser al lexer, o il lexer deve produrre entrambi i token e passarli al parser per decidere quale vuole. I parser LALR sono definiti sui flussi di token senza feedback e in cui ogni token di input ha una sola interpretazione.

Non credo che Java sia, da Java 1.5 in su, quando enum è stato introdotto come tipo speciale con una propria parola chiave. Questo perché, per Java 1.5 compilatori per elaborare programmi esistenti Java 1.4 che utilizzavano enum come un nome di variabile, enum devono essere trattati come parola chiave in alcuni contesti, e come un nome di variabile in altri. Quindi un parser di Java 1.5 ha gli stessi problemi di C#.

In pratica, nessun vero linguaggio è LALR (1) [la prima edizione di Java può essere un'eccezione] e chiunque costruisca un parser reale (esp LALR) deve fare una specie di trucco per aggirare questo problema.(GCC notoriamente ha analizzato C++ con un parser LALR con una tabella di simboli terribile che hack per molto tempo, quindi potrebbe indicare la differenza tra un identificatore come variabile e un identificatore come un'istanza typedef. parser di discendenza ricorsiva, ma penso che l'orribile hack resti). Quindi non sono sicuro del valore della risposta alla tua domanda.

Il nostro C# 4.0 and Java 7 members of our family of language front ends analizza entrambe le lingue utilizzando un parser GLR, esteso sia con la capacità di feedback che la capacità di elaborare due interpretazioni dello stesso token. GLR fa la domanda di LALR (x) moot, e il feedback e le molteplici interpretazioni ci permettono di gestire molti linguaggi che sarebbero al di fuori delle pure capacità di GLR.

EDIT: Dopo un po 'di riflessione, potrebbe esserci un modo davvero brutto per far sì che entrambe le grammatiche gestiscano la loro parola chiave nel contesto. Usiamo enum di Java come esempio. Ci deve realisticamente essere la regola grammaticale:

type = 'enum' '{' enum_members '}' ; 

Ma dobbiamo anche consentire 'enum' come identificativo. Possiamo farlo, sostituendo il terminale gettone identificatore con un non terminale:

identifier = IDENTIFIER | 'enum' ; 

e insistere che identificatori sono i terminali prodotte dal lexer. Ora almeno il lexer non deve decidere come trattare enum; fa il parser. Ma la tua grammatica designata dovrebbe essere strutturata in questo modo per avere anche la possibilità di essere LALR (x).

I nostri parser facevano questo per consentire l'uso di alcune parole chiave a volte come identificatori. Abbiamo modificato il nostro motore di analisi come descritto in precedenza e non lo facciamo più.

Answer 2

Almeno per Java (versione 1.0) che è: http://java.sun.com/docs/books/jls/first_edition/html/19.doc.html

Answer 3

La grammatica Java (versione 1.0) è noto per essere LALR (1); this site fornisce una grammatica e inizia con la nota che

La grammatica è stata controllata meccanicamente per assicurarsi che sia LALR (1).

io non sono sicuro se C# è LALR (1), ma c'è un C# parser written in bison disponibile qui, il che suggerisce che probabilmente è LALR (1) (assumendo che si consenta per le dichiarazioni di precedenza).

Per quello che vale, in genere LALR (1) è l'unico parser LALR utilizzato. Se è necessario utilizzare qualcosa come LALR (2) per una grammatica, è in genere un'idea migliore utilizzare un parser LALR (1) con la disambiguazione della precedenza esplicita o un parser più potente come un parser GLR.

Spero che questo aiuti!