1

I am desperately looking for the Java grammar which can guarantees to be LR(1). I don't care which version of Java; I should be able to modify it to the version I want.

I'm reading the last chapter of Java™ Language Specification, Second Edition. And hell, the grammar in that chapter seems not be LR(1) at all. I have a feeling that the grammar is cyclic or somewhat weird, as I keep getting reduce-shift conflicts when I'm trying to generate the parse table from the grammar.

Can anyone gives some suggestions on this?

Note: Edited the title to L(AL)R since I'm okay to accept LALR grammar for Java as well.

Erencie
  • 391
  • 2
  • 3
  • 12
  • 1
    [This might help.](http://www.eclipse.org/jdt/core/howto/generate%20parser/generateParser.html) – Mike Strobel Jan 31 '14 at 02:43
  • Look at the answer to this question: http://stackoverflow.com/questions/8378521/are-c-sharp-and-java-grammars-lalrx – Jerry Jeremiah Jan 31 '14 at 02:46
  • 2
    LR(1)? Are you sure? Mostly this gets giant parser tables without buying you anything? Or do you just want LALR(1)? – Ira Baxter Jan 31 '14 at 02:58
  • @JerryJeremiah I read that one. Firstly the links given there are outdated and don't point to any useful places. Secondly the person asks for Java 7; but I am okay even if you give me Java version 1.0. – Erencie Jan 31 '14 at 03:52
  • @TedHopp Same answer as above...(not sure why I can't @ two persons at the same comment) – Erencie Jan 31 '14 at 03:53
  • @IraBaxter I'm okay with both LR(1), LALR(1), or SLR(1). And I'm okay with a Java version 1.0 or anything else. The reason I ask for LR(1) is that I thought it's easier to debug. – Erencie Jan 31 '14 at 03:54
  • If the grammar is LR/LALR/SLR or whatever PQR when given to you, what is there to debug? Perhaps you'd be better off telling us what you want to do. If you want to simply start parsing Java, you're probably in find shape using ANTLR and its existing Java grammar(s). Unless you want the experience of debugging a grammar with a parser generator (easy to get: start with an empty grammar), what you want is a working grammar. There's far more work on the other side of parsing if you are going to do *anything* with your parsed results. – Ira Baxter Jan 31 '14 at 03:58
  • ... and if you don't care what class of grammar you get, you should change your question title to something more like "Any working L(AL)R grammar for Java?". – Ira Baxter Jan 31 '14 at 04:01
  • @IraBaxter Yes I've changed the title. I want to write parser for the Java programming language without using external tools; so a working grammar would help me a lot. – Erencie Feb 01 '14 at 17:18

1 Answers1

4

Chapter 19 of the Java Language Specification, version 1.0 has an LALR(1) grammar for Java. This document can be found in many places by searching the web for "java language specification 1.0". This chapter disappeared in the second edition of the JLS, replaced by a grammar that (as you already point out) is not LR(1). Here are a couple of working links1 to the version 1.0 spec:

However, regarding this grammar, it's worth reading this analysis by Trevor Jim, who points out that the presented grammar is ambiguous. It's unclear whether it is possible to introduce disambiguation rules without destroying the context-free nature of the grammar. His conclusion is that whether Java is a context-free language is an open question (although he believes it is).

Note that the above applies to Java 1.0. I don't believe that more recent Java language versions are context-free. As pointed out in this thread, "Neither C# nor Java is context-free, because checking of whether a variable is used correctly and consistently throughout a particular scope is known not to be context-free". For instance, forward references (e.g., to methods) cannot be resolved in a single pass with a PDA.

1At least they were live when I posted this answer.

Community
  • 1
  • 1
Ted Hopp
  • 232,168
  • 48
  • 399
  • 521